Concurrency II: synchronization, deadlock and message passing

Lesson 9 showed that races arise from shared mutable state. There are two broad remedies. The first keeps the shared state but controls access to it, so that only one thread at a time can perform a critical sequence of operations: this is synchronization with locks, condition variables and related primitives. The second removes the shared state altogether: threads or processes own their data and communicate by sending messages through channels or mailboxes. This lesson covers both, along with the new hazard that locking introduces, deadlock. The implementation of these primitives inside an operating system, with atomic instructions and kernel scheduling, is covered in CMPUT-379.

Critical sections and mutual exclusion

A critical section is a piece of code that accesses shared state and must not run in more than one thread at a time. Mutual exclusion guarantees that it does not. A lock, also called a mutex, is the basic tool: a thread acquires the lock before entering the critical section and releases it afterwards, and any other thread that tries to acquire it waits until it is free. With the read, add and write of `count += 1` inside a critical section, no other thread can slip in between them, so no update is lost.

import sys, threading
sys.setswitchinterval(1e-6)          # switch threads very often to expose the race

def run(n_threads, n_incr, use_lock):
    count = 0
    lock = threading.Lock()
    def work():
        nonlocal count
        for _ in range(n_incr):
            if use_lock:
                with lock:              # acquire ... release, even if an exception occurs
                    count += 1
            else:
                tmp = count             # read
                for _ in range(5): pass # widen the window between read and write
                count = tmp + 1         # write
    ts = [threading.Thread(target=work) for _ in range(n_threads)]
    for t in ts: t.start()
    for t in ts: t.join()
    return count

expected = 4 * 50_000
with_lock = run(4, 50_000, True)
without = run(4, 50_000, False)
print("expected:", expected)
print("with lock:", with_lock, "| correct:", with_lock == expected)
print("without lock lost updates:", without < expected)

expected: 200000
with lock: 200000 | correct: True
without lock lost updates: True

The unlocked run reliably loses updates here because the artificial delay between read and write gives other threads time to interleave; in real code the window is smaller, so the bug appears less often, which makes it worse, not better. The `with lock:` form is important. It releases the lock however the block exits, including by an exception, so a failure inside the critical section cannot leave the lock held forever and freeze every other thread.

Locks have costs. Waiting threads do no useful work, so a heavily contended lock serializes the program and removes the benefit of concurrency. Holding a lock while doing slow work, such as I/O, makes this worse. The guideline is to keep critical sections short and to protect the smallest amount of state that keeps the invariant. A common design is to make each lock guard one clearly identified group of data, documented next to the data, so that everyone knows which lock to take.

Condition variables and coordination

Sometimes a thread must wait not for a lock but for a condition: a queue to become non-empty, a buffer to have space, a task to finish. A condition variable lets a thread release a lock and sleep until another thread signals that the condition may now hold. Higher-level tools are built from locks and condition variables: semaphores limit how many threads can use a resource at once, events let one thread signal others, and barriers make a group of threads wait until all have arrived. In Python, the thread-safe `queue.Queue` packages the most common pattern, producer and consumer, so that you rarely need raw condition variables.

Deadlock

Locks solve races but introduce a new failure: deadlock, in which two or more threads each wait for a lock held by another, so none can proceed. The classic example transfers money between accounts. If one thread transfers from account A to B by locking A then B, and another transfers from B to A by locking B then A, each can acquire its first lock and then wait forever for the second. The program does not crash; it simply stops making progress, which can be harder to diagnose than a crash.

Edward Coffman and colleagues identified four conditions that must all hold for deadlock to occur. Mutual exclusion: a resource is held by one thread at a time. Hold and wait: a thread holds one resource while waiting for another. No pre-emption: a resource cannot be forcibly taken away. Circular wait: there is a cycle of threads, each waiting for a resource held by the next. Preventing any one condition prevents deadlock. In practice, the easiest to break is circular wait: if every thread acquires locks in the same global order, a cycle is impossible.

import itertools

def philosophers(n, ordered):
    """Simulate n dining philosophers taking forks step by step in every round-robin start order.
    Each philosopher needs forks i and (i+1) % n. Returns True if some schedule deadlocks."""
    def needs(i):
        a, b = i, (i + 1) % n
        return (min(a, b), max(a, b)) if ordered else (a, b)   # ordered: lower-numbered fork first
    for start in itertools.permutations(range(n)):
        owner = {}                   # fork -> philosopher
        holding = {i: [] for i in range(n)}
        # each philosopher, in this order, tries to pick up its first fork
        for i in start:
            f = needs(i)[0]
            if f not in owner:
                owner[f] = i; holding[i].append(f)
        # then everyone tries the second fork; deadlock if nobody can get both
        can_eat = [i for i in range(n)
                   if len(holding[i]) == 1 and needs(i)[1] not in owner]
        if all(len(holding[i]) == 1 for i in range(n)) and not can_eat:
            return True, start
    return False, None

for ordered in (False, True):
    dead, example = philosophers(5, ordered)
    label = "global fork order" if ordered else "left fork first"
    print(f"{label:>17}: deadlock possible = {dead}" + (f", e.g. start order {example}" if dead else ""))

  left fork first: deadlock possible = True, e.g. start order (0, 1, 2, 3, 4)
global fork order: deadlock possible = False

In the dining philosophers problem, introduced by Dijkstra, five philosophers sit at a round table with one fork between each pair, and each needs both neighbouring forks to eat. If every philosopher picks up the left fork first, all five can hold one fork and wait forever for the other: a circular wait. The simulation finds such a schedule. Numbering the forks and always taking the lower-numbered fork first means the last philosopher reaches for fork 0 before fork 4, which breaks the cycle, and the simulation confirms that no schedule deadlocks.

Deadlock has relatives. In livelock, threads keep reacting to each other without progress, like two people in a corridor who both step aside in the same direction repeatedly. In starvation, a thread waits indefinitely because others keep getting the resource first. Priority inversion occurs when a low-priority thread holds a lock that a high-priority thread needs, while medium-priority threads keep the low-priority one from running; it famously caused repeated resets on the Mars Pathfinder lander in 1997.

Message passing

Message passing avoids shared state entirely. Each concurrent activity owns its data, and activities interact only by sending messages, values copied or transferred from one to another. Because nobody else can touch an activity's data, there is nothing to lock. Two styles dominate. In the communicating sequential processes style, from Tony Hoare's 1978 work and used by Go, activities communicate through channels: typed pipes into which one side sends and from which the other receives. In the actor model, from Carl Hewitt's work in 1973 and used by Erlang and Akka, each actor has a mailbox; it processes one message at a time, and in response can update its private state, send messages and create new actors.

import threading, queue

tasks, results = queue.Queue(), queue.Queue()
STOP = object()                                   # sentinel value tells workers to finish

def worker(wid):
    while True:
        item = tasks.get()
        if item is STOP:
            break
        n = item
        results.put((n, wid, sum(range(n + 1))))  # send the answer back as a message

workers = [threading.Thread(target=worker, args=(w,)) for w in range(3)]
for w in workers: w.start()
for n in [10, 100, 1000, 5, 50]:
    tasks.put(n)                                  # producer sends work
for _ in workers:
    tasks.put(STOP)
for w in workers: w.join()

answers = sorted(results.get() for _ in range(results.qsize()))
for n, _, total in answers:
    print(f"sum 0..{n} = {total}")
print("no shared variables were mutated; only queues were used")

sum 0..5 = 15
sum 0..10 = 55
sum 0..50 = 1275
sum 0..100 = 5050
sum 0..1000 = 500500
no shared variables were mutated; only queues were used

The workers never touch a shared variable. Work arrives through one queue and answers leave through another, and the queues handle all the locking internally. The sentinel object `STOP` tells each worker to finish, a common idiom for shutting down a pool. Because the workers finish in an unpredictable order, the main thread sorts the answers before printing, so the output does not depend on scheduling. The same structure works across processes with `multiprocessing.Queue` and across machines with message brokers.

package main

import (
	"fmt"
	"sort"
)

func worker(id int, jobs <-chan int, results chan<- [2]int) {
	for n := range jobs {           // receive until the channel is closed
		sum := 0
		for i := 1; i <= n; i++ {
			sum += i
		}
		results <- [2]int{n, sum}   // send the result back
	}
}

func main() {
	jobs := make(chan int)
	results := make(chan [2]int)
	for w := 1; w <= 3; w++ {
		go worker(w, jobs, results) // goroutines: lightweight concurrent functions
	}
	inputs := []int{10, 100, 1000, 5, 50}
	go func() {
		for _, n := range inputs {
			jobs <- n
		}
		close(jobs)
	}()
	var out [][2]int
	for range inputs {
		out = append(out, <-results)
	}
	sort.Slice(out, func(i, j int) bool { return out[i][0] < out[j][0] })
	for _, r := range out {
		fmt.Printf("sum 1..%d = %d\n", r[0], r[1])
	}
}

sum 1..5 = 15
sum 1..10 = 55
sum 1..50 = 1275
sum 1..100 = 5050
sum 1..1000 = 500500

Go builds channels into the language and makes concurrent functions, goroutines, so cheap that programs routinely start thousands of them. Its motto puts the paradigm in a sentence: do not communicate by sharing memory; instead, share memory by communicating. Erlang takes the idea further: actors are isolated processes inside the runtime, and if one crashes, a supervisor actor is notified and can restart it, a philosophy called let it crash that has kept telephone switches running for years at a time.