Designing Concurrent Programs

In shared memory concurrency, threads share a common memory space. We have to worry about cache misses (short), page faults (long) and using up scheduling quantum (very long).

Threads & Processes

A process is roughly one application (ignoring MPI). A thread is a single sequence of instructions within a process. A process can have multiple threads. Each process has its own memory space, while threads share the memory space of their parent process.

Concurrency vs Parallelism

Parallelism means multiple physical cores executing threads simultaneously. Concurrency means multiple threads making progress over time, but not necessarily simultaneously (e.g. by scheduling on one core).

1. Example Concurrent Program

For example, we could calculate all primes between and as:

1def primePrint(): Unit = {
2  val i = ThreadID.get // Thread IDs in 0..9
3  val block = math.pow(10, 5)
4  for (j <- (i * block) + 1 to ((i + 1) * block)) {
5    if (isPrime(j)) println(j)
6  }
7}

Although this is correct, the workload is unbalanced. Checking if is prime takes much longer than checking if is prime. Instead, we could have a queue of numbers to check:

1val counter = new Counter()
2
3def primePrint(): Unit = {
4  var i: Int = 1
5  val limit: Int = math.pow(10, 6)
6  while (i < limit) {
7    i = counter.getAndIncrement()
8    if (isPrime(i)) println(i)
9  }
10}

This counter is not necessarily thread-safe, as an increment i++ is not atomic. We could use locks to make it thread-safe, but this would be slow. Instead, we can use atomic operations (CAS), or a synchronized block in Scala.

1class Counter {
2  private var count = 0
3
4  def getAndIncrement(): Int = this.synchronized {
5    val temp = count
6    count += 1
7    temp
8  }
9}

2. Safety & Liveness

There are two formal properties in asynchronous computation:

  1. Safety: Nothing bad happens ever. If this is violated, it is done by a finite computation.
  2. Liveness: Something good happens eventually. Cannot be violated by a finite computation.

3. Concurrency & Mutual Exclusion

In mutual exclusion, a critical section is a piece of code that can only be executed by one thread at a time - essentially sequential. We want to minimise this to increase performance. Amdahl's Law states . Or, in mathematical terms where is the proportion of the program that can be parallelised and is the number of threads.

Back to Home