7. The Concurrent Programming Paradigm

7.1. Overview

Why and when do we need concurrency?

  • When it is a natural fit for the problem domain

    • multiple autonomous behaviors/simulations

    • user interfaces: timed events, background activities

  • When the technical solution domain requires it

    • more efficient use of available resources: asynchronous computing

    • graphical user interfaces: queuing of low-level input events

    • multi-core systems

    • network services/distributed systems

Key considerations:

  • physical (parallelism) versus logical concurrency

  • speedup and when to expect it

  • data parallelism versus task parallelism

7.2. Activity terminology and concerns

  • process: own memory

  • thread: shared memory and “thread-local” state

  • foreground versus background

  • CPU-bound versus IO-bound

  • run-to-completion versus coordination

  • progress reporting

  • cancelation

7.3. Thread safety

  • nondeterminism

  • extent of nondeterminism: see subsection below

  • race conditions

  • root cause of thread safety problems

7.3.1. Understanding the extent of nondeterminism

Consider this small example of two concurrent increment operations:

/*f1*/ final int local1 = shared;    /*f2*/ final int local2 = shared;
/*s1*/ shared = local1 + 1;          /*s2*/ shared = local2 + 1;

When analyzing race conditions, we might be tempted to enumerate the different possible interleavings. While it seems reasonable for this example, this quickly becomes impractical because of the combinatorial explosion for larger number of threads with more steps. (Please see the CDER chapter for more details.)

To appreciate this combinatorial explosion, let’s count the possible interleavings for the case of \(k\) threads with \(n\) steps each. We recall the binomial coefficient \(i\) choose \(j\) defined as

\[\binom{i}{j} = \frac{i!}{j!(i-j)!} \text{ for } 0 \leq j \leq i\]

In our case, there are \(kn\) steps, of which the first thread chooses \(n\); there are \(\binom{kn}{n}\) possibilities for this. This leaves \((k-1)n\) steps, of which the second thread chooses \(n\), and so on. At the end, there are \(n\) steps left, which are the only choice for the last thread. The total number of choices is the product of choices for each thread:

\[\binom{kn}{n} \binom{(k-1)n}{n} \dots \binom{2n}{n} \binom{n}{n} = \frac{(kn)!}{n!(kn-n)!} \frac{((k-1)n)!}{n!((k-1)n-n)!} \dots \frac{(2n)!}{n!(2n-n)!} \frac{(n)!}{n!(n-n)!}\]

Here the second factor in each denominator cancels out against the numerator of the next top-level factor and the second factor in the last denominator is \(1\), leaving

\[\frac{(kn)!}{{n!}^k}\]

As the number of threads and/or their number of steps grow beyond two, the number interleavings gets very large.

\[\begin{split}\begin{matrix} n / k & k = 2 & k = 3 & k = 4 \\ n = 2 & 6 & 90 & 2520 \\ n = 3 & 20 & 1680 & 369600 \\ n = 4 & 70 & 34650 & 63063000 \end{matrix}\end{split}\]

Therefore, we cannot attempt to comprehend, let alone enumerate, all possible interleavings. Instead, we need to think in terms of constraints, e.g., f1 always happens before s1, and f2 always happens before s2.

Once we make each thread atomic, however, the number of interleavings shrinks dramatically to \(k!\).

7.4. Dealing with shared state

  • mutual exclusion/locking

  • confinement

  • immutability

  • case study: GUIs and the single-threaded rule

7.5. (Conflicting) design forces

7.6. Specific concurrency mechanisms

Language constructs, patterns, building blocks:

7.7. References: concurrent and asynchronous computing