7. The Concurrent Programming Paradigm

In this chapter, we introduce the concurrent programming paradigm, which allows multiple computations to occur simultaneously or in overlapping time periods. This is particularly useful for applications that require responsiveness, such as user interfaces, or for leveraging multi-core processors to improve performance.

7.1. Core Elements

The concurrent paradigm is characterized by multiple sequences of execution (progressing independently, potentially interacting with each other). Concurrency allows programs to handle multiple tasks at once, overlap computation with I/O, and exploit multicore architectures.

7.1.1. Threads and Shared Memory

  • Threads represent independent flows of control within a program.

  • Multiple threads share memory; synchronization mechanisms (locks, mutexes, condition variables) ensure consistency.

7.1.2. Synchronization

  • Mechanisms such as mutexes, semaphores, barriers, and monitors coordinate access to shared resources.

  • Avoids race conditions, deadlocks, and data corruption.

7.1.3. Message Passing

  • Concurrency via communication rather than shared state.

  • Examples: channels (Rust), actors (Scala Akka), message queues.

7.1.4. Futures and Promises

  • Abstractions for values that may not yet be available.

  • Simplify asynchronous programming by representing results of concurrent tasks.

7.1.5. Data Parallelism

  • Operations automatically distributed over data structures.

  • Examples: Java parallel streams, Scala parallel collections.

7.1.6. Actors and Reactive Models

  • Concurrency modeled as independent actors that process messages sequentially.

  • Strong isolation; avoids shared state issues.

7.1.7. Examples Across Languages

Element

C/C++ (pthreads)

Java

Scala

Rust

Thread creation

pthread_create(&tid, NULL, f, arg);

new Thread(() -> f()).start();

new Thread(() => f()).start() or Future { f() }

thread::spawn(|| f());

Mutex / lock

pthread_mutex_lock(&m); ... pthread_mutex_unlock(&m);

synchronized(obj) { ... }

lock.synchronized { ... }

let m = Mutex::new(...); with m.lock()

Condition variable

pthread_cond_wait(&cv, &m);

wait() / notify() on objects

Await.result(future, timeout)

Condvar::wait(&mut guard)

Message passing

Not built-in (libraries required)

BlockingQueue.put(msg)

actor ! msg (Akka)

let (tx, rx) = mpsc::channel(); tx.send(msg);

Futures / promises

Not built-in

CompletableFuture.supplyAsync(f)

val f = Future { compute }

let f = async { compute().await };

Data parallelism

OpenMP or TBB (library-based)

list.parallelStream().map(...)

List(...).par.map(...)

vec.par_iter().map(...) (with Rayon crate)

Actors

Not standard

Akka-like libraries available

import akka.actor._ (full actor model)

External crates (e.g., Actix)

7.1.8. Discussion

Concurrency is not a single technique, but a family of approaches to overlapping computations.

  • Low-level threads and locks offer flexibility but require careful handling of synchronization.

  • Higher-level abstractions (futures, parallel collections, actors) increase safety and expressiveness.

  • Languages like Rust enforce memory safety and data-race freedom at compile time, while Scala and Java provide rich libraries for structured concurrency.

  • Choosing the right model depends on the problem: message-passing (actors, channels) suits distributed and reactive systems; data parallelism suits numerical workloads.

7.2. Concurrency vs. Parallelism

Although often used interchangeably, concurrency and parallelism are related but distinct concepts in programming.

7.2.1. Concurrency

  • Definition: Structuring a program as multiple tasks that can make progress independently.

  • Emphasis: Dealing with many things at once (logical composition).

  • A concurrent system may run on a single processor by interleaving tasks (time slicing), or on multiple processors.

  • Example:

    • A web server that handles thousands of client requests by overlapping network I/O with computation.

    • Java: CompletableFuture.supplyAsync(...) to launch asynchronous tasks.

    • Scala: Future { compute } with callback composition.

    • Rust: async fn handler() { ... } executed on an async runtime.

    • C/C++: cooperative scheduling or event loops layered on top of pthreads.

7.2.2. Parallelism

  • Definition: Using multiple processing units (cores, processors, machines) to perform computations simultaneously.

  • Emphasis: Doing many things at the same time (physical execution).

  • A parallel system requires hardware support for multiple execution units.

  • Example:

    • A numerical algorithm that splits an array into parts and processes each part simultaneously.

    • Java: list.parallelStream().map(...) distributes work across cores.

    • Scala: List(...).par.map(...) uses parallel collections.

    • Rust: vec.par_iter().map(...) with the Rayon library.

    • C/C++: OpenMP pragmas (#pragma omp parallel for) for loop parallelism.

7.2.3. Key Distinctions

Aspect

Concurrency

Parallelism

Primary goal

Handle multiple tasks logically at once

Speed up execution using multiple cores

Hardware requirement

Not required (can be simulated on a single CPU)

Requires multiple cores/CPUs or distributed systems

Typical mechanisms

Threads, async/await, actors, channels

Data parallel loops, SIMD, GPU kernels

Example use case

Web server handling requests

Matrix multiplication or image processing
Concurrency (Interleaving) Parallelism (Simultaneous) Task A Task B Task A Task B One core, time-sliced Multiple cores, true overlap

7.2.4. Discussion

  • Concurrency is about structure: decomposing programs into independent activities that can interleave.

  • Parallelism is about execution: exploiting hardware resources to perform computations faster.

  • Many modern systems combine both: a concurrent web server (handling many connections) uses parallelism internally to process requests across CPU cores.

7.3. Motivation

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

These are some key concurrency considerations:

  • physical (parallelism) versus logical concurrency

  • speedup and when to expect it

  • data parallelism versus task parallelism

7.4. Activity terminology and concerns

We distinguish several related concepts:

  • 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.5. Thread safety

Thread safety is a property of code that guarantees safe execution by multiple threads at the same time. This is particularly important when threads share mutable state.

  • nondeterminism

  • extent of nondeterminism: see subsection below

  • race conditions

  • root cause of thread safety problems

7.5.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.6. Dealing with shared state

One of the main challenges of concurrent programming is dealing with shared mutable state. Several strategies exist:

  • mutual exclusion/locking

  • confinement

  • immutability

  • case study: GUIs and the single-threaded rule

7.7. (Conflicting) design forces

This gives rise to several conflicting design forces:

7.8. Specific concurrency mechanisms

Several specific concurrency mechanisms can come as anguage constructs, patterns, and other building blocks:

7.9. References: concurrent and asynchronous computing