The Concurrent Programming Paradigm ----------------------------------- 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 Activity terminology and concerns ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ - process: own memory - thread: shared memory *and* "thread-local" state - foreground versus background - CPU-bound versus IO-bound - `CPU-bound example `_ - `IO-bound example `_ - run-to-completion versus coordination - progress reporting - cancelation Thread safety ~~~~~~~~~~~~~ - nondeterminism - `example `_ - extent of nondeterminism: see subsection below - race conditions - `example `_ - root cause of thread safety problems 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 :math:`k` threads with :math:`n` steps each. We recall the binomial coefficient :math:`i` choose :math:`j` defined as .. math:: \binom{i}{j} = \frac{i!}{j!(i-j)!} \text{ for } 0 \leq j \leq i In our case, there are :math:`kn` steps, of which the first thread chooses :math:`n`; there are :math:`\binom{kn}{n}` possibilities for this. This leaves :math:`(k-1)n` steps, of which the second thread chooses :math:`n`, and so on. At the end, there are :math:`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: .. math:: \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 :math:`1`, leaving .. math:: \frac{(kn)!}{{n!}^k} As the number of threads and/or their number of steps grow beyond two, the number interleavings gets very large. .. math:: \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} 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 :math:`k!`. Dealing with shared state ~~~~~~~~~~~~~~~~~~~~~~~~~ - mutual exclusion/locking - confinement - immutability - case study: GUIs and the single-threaded rule (Conflicting) design forces ~~~~~~~~~~~~~~~~~~~~~~~~~~~ - correctness/(thread-)safety - liveness/deadlock - `dining philosophers example `_ - fairness/starvation - performance - throughput - latency - jitter Specific concurrency mechanisms ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Language constructs, patterns, building blocks: - threads (familiar from 313/413) - monitors: synchronized/locks, wait/notify - fully synchronized object (pattern/building blocks) - Android (also familiar from 313/413) - `AsyncTask `_ - `ThreadPoolExecutor `_ - `java.util.concurrent `_ - atomic variables - thread-safe collections - FIFO locks - ... - `Scala parallel collections `_ - `futures and promises intro `_ - `composable futures in Scala/Akka `_ - `example: concurrent web requests `_ - `actors `_ - `reactive streams `_ including `Akka streams `_ - `software transactional memory `_ References: concurrent and asynchronous computing ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ - Läufer and Thiruvathukal, `CDER book chapter `_ - Goetz et al., `JCIP `_ - Doug Lea, `CPJ `_ - Thiruvathukal and Christopher, `HPJPC `_ - `SE Radio episode on concurrency: part 1 `_ - `SE Radio episode on concurrency: part 2 `_ - `SE Radio episode on concurrency: part 3 `_ - `SE Radio episode on concurrency: part 4 `_ - `futures and promises overview `_ - `RxJava/RxScala `_ - `asynchronous programming video `_ - `reactive/asynchronous programming with RxJava/RxScala video `_