Concurrency, Synchronization & Deadlock

Concurrency introduces a class of bug that testing cannot reliably find, because the failure depends on timing rather than on input.

The organising fact is that every concurrency bug is a claim about an interleaving, and every solution is a restriction on which interleavings the system may produce. A race condition is the assertion that some ordering of instructions from different executions produces a wrong result. A lock is the assertion that certain orderings are now impossible.

This reframing is what makes the topic tractable. To show code is broken, exhibit one bad interleaving. To show it is correct, argue that no bad interleaving remains.

The second organising fact is that deadlock is not a bug in any single process. Each participant is following a perfectly reasonable rule; the failure is a property of the set. That is why deadlock is analysed with graphs and matrices rather than by reading code.

The third is that all four necessary conditions must hold simultaneously, so every prevention technique works by denying exactly one of them.

1. The Critical Section Problem

A critical section is a region of code that accesses shared data and must not be executed by two threads at once.

Any correct solution must satisfy three requirements, and questions frequently ask which one a given attempt violates.

Mutual exclusion: at most one thread is inside the critical section at any time.

Progress: if no thread is in the critical section and some threads want to enter, the choice of who enters cannot be postponed indefinitely, and threads not wanting to enter cannot participate in the decision.

Bounded waiting: there is a bound on how many times other threads may enter after a thread has requested entry and before that request is granted.

Mutual exclusion alone is easy and worthless. A solution that lets nobody in satisfies it perfectly. Progress is what rules out that degenerate answer, and bounded waiting is what rules out starvation.

A fourth property, often listed separately, is that no assumption may be made about relative speeds of the threads or the number of processors.

2. Software and Hardware Solutions

Peterson's algorithm solves the problem for two threads using two shared variables: a boolean flag per thread signalling intent, and a turn variable breaking ties.

A thread sets its own flag, sets turn to the other thread, and then waits while the other's flag is set and it is the other's turn.

Setting turn to the other thread is the counterintuitive step that makes it work. Each thread politely yields, so whichever writes turn last loses the tie, and exactly one proceeds.

Peterson's algorithm satisfies all three requirements but assumes sequentially consistent memory. On real processors with write reordering it needs memory barriers, which is why it is a teaching device rather than an implementation.

Hardware provides atomic instructions that do a read and a write indivisibly.

Test-and-set returns the old value of a memory word and sets it to true, atomically. A lock is acquired by spinning until test-and-set returns false.

Compare-and-swap takes an expected value and a new value, and writes the new value only if the current value matches the expected one, returning what it found. It is strictly more powerful and is the basis of lock-free data structures.

Plain test-and-set locks do not guarantee bounded waiting, since an unlucky thread can lose every race forever. Adding a waiting array and a round-robin handoff restores it.

Spinning wastes CPU, which is acceptable only when the expected wait is shorter than a context switch. Otherwise the thread should block.

3. Semaphores

A semaphore is an integer with two atomic operations and a queue of blocked threads.

Wait, also called P or down, decrements the value and blocks if the result is negative. Signal, also called V or up, increments the value and wakes a blocked thread if any are waiting.

A binary semaphore takes values 0 and 1 and acts as a lock. A counting semaphore holds a resource count and admits that many holders.

When the value is negative, its magnitude is the number of blocked threads, which is a useful invariant for solving numerical questions.

Semaphores are powerful and error-prone in equal measure. Omitting a signal deadlocks; omitting a wait breaks mutual exclusion; reversing two waits can deadlock even though both are present.

The bounded buffer uses three semaphores: a counting semaphore for empty slots initialised to the buffer size, a counting semaphore for full slots initialised to zero, and a binary mutex.

The order of the two waits in the producer is not a style choice. Waiting on the mutex before waiting on empty slots allows a producer to hold the mutex while blocking on a full buffer, which prevents any consumer from ever draining it.

4. Monitors and Condition Variables

A monitor packages shared data with the procedures that operate on it, and guarantees that at most one thread is active inside the monitor at a time.

Mutual exclusion becomes structural rather than a matter of discipline, which removes the most common semaphore error.

Condition variables handle waiting. A thread that cannot proceed calls wait on a condition variable, which releases the monitor and blocks. Another thread calls signal to wake it.

A condition variable has no value and no memory. Signalling when nobody is waiting does nothing, unlike a semaphore signal which is remembered in the count.

Two signalling disciplines exist. Under signal-and-wait, sometimes called Hoare semantics, the signaller yields the monitor immediately to the woken thread. Under signal-and-continue, or Mesa semantics, the signaller keeps the monitor and the woken thread merely becomes eligible.

Mesa semantics is what real systems implement, and it forces a specific coding rule: always re-test the condition in a while loop, never an if, because the condition may have been falsified between the signal and the wakeup.

5. Classical Problems

Producer-consumer is the bounded buffer described above, and its lesson is the ordering of waits.

Readers-writers allows any number of concurrent readers but requires a writer to have exclusive access.

The naive solution starves writers. If readers keep arriving while others are reading, the read count never reaches zero and a waiting writer never proceeds. A writer-preference variant fixes this by blocking new readers once a writer is waiting, which then risks starving readers, and a fair variant queues both in arrival order.

Dining philosophers has five philosophers, five forks, and each needing both neighbouring forks to eat.

The obvious solution, picking up the left fork then the right, deadlocks when all five take their left fork simultaneously.

Three standard fixes exist, and each denies a different deadlock condition. Allowing at most four philosophers at the table denies hold-and-wait in effect. Requiring both forks be picked up atomically denies hold-and-wait directly. Making one philosopher pick up the right fork first denies circular wait.

6. Deadlock and Its Four Conditions

Deadlock is a state in which every process in a set is waiting for an event that only another process in that set can cause.

Four conditions must all hold simultaneously.

Mutual exclusion: at least one resource is non-shareable.

Hold and wait: a process holding a resource is waiting to acquire another.

No preemption: a resource cannot be taken from a process; it must be released voluntarily.

Circular wait: a cycle of processes exists, each waiting for a resource held by the next.

Circular wait implies hold and wait, but not conversely, which is why the four are stated as necessary together rather than independent.

A resource allocation graph has processes and resources as nodes, request edges from process to resource, and assignment edges from resource to process.

With one instance per resource type, a cycle is necessary and sufficient for deadlock. With multiple instances, a cycle is necessary but not sufficient, because another holder of the same type may release and break it.

7. Handling Deadlock

Four strategies exist, and systems in practice choose the last one.

Prevention denies one of the four conditions structurally. Requesting all resources at once denies hold and wait but hurts utilisation. Allowing preemption of resources whose state can be saved denies no-preemption. Imposing a total order on resource types and requiring increasing acquisition denies circular wait, and is the technique used in real kernels.

Avoidance uses advance knowledge of maximum needs to stay in safe states. A state is safe if some ordering of the processes exists in which each can obtain its maximum need from currently available resources plus those released by its predecessors.

The banker's algorithm implements avoidance. It grants a request only if the resulting state is safe, computed by repeatedly finding a process whose remaining need is satisfiable and pretending it finishes.

An unsafe state is not a deadlock, only a state from which deadlock is possible. Avoidance is therefore conservative and refuses some requests that would have been fine.

Detection lets deadlock happen and finds it afterwards, running a reducibility algorithm on the allocation matrices periodically.

Recovery then aborts processes or preempts resources, choosing victims by cost, and must handle rollback and the risk of starving the same victim repeatedly.

Ignoring the problem is what most operating systems do. Deadlock is rare enough that a reboot is cheaper than the machinery, an approach honestly named the ostrich algorithm.

8. Worked Examples

Example 1. Show that the two-flag solution without a turn variable violates progress, and that Peterson's fix repairs it.

The flawed version has each thread set its flag to true and then wait while the other's flag is true.

Consider the interleaving where both threads set their flags before either tests. Thread A sets its flag; thread B sets its flag; A tests B's flag and finds it true, so waits; B tests A's flag and finds it true, so waits.

Neither can proceed and neither is in the critical section, so the progress requirement fails. This is deadlock, not merely inefficiency.

Peterson's algorithm adds a turn variable written after the flag. Thread A sets its flag, then sets turn to B. Thread B sets its flag, then sets turn to A.

Whichever write to turn happens second is the one that persists, since the two writes are to the same location.

Suppose A wrote turn last, so turn is B. A's wait condition is that B's flag is set and turn is B, which is true, so A waits. B's condition is that A's flag is set and turn is A, and turn is B, so B enters.

Exactly one thread proceeds and the symmetry is broken by the memory location itself, which is why progress holds.

Bounded waiting also holds: when B leaves it clears its flag, so A enters immediately, and B cannot re-enter ahead of A because re-entering sets turn back to A.

Example 2. In the bounded buffer, the producer executes wait(mutex) before wait(empty). Exhibit a deadlock.

The correct producer waits on empty first, then on mutex. The swapped version does the reverse.

Fill the buffer completely, so the empty semaphore has value zero.

A producer now runs. It executes wait(mutex) successfully, acquiring exclusive access, then executes wait(empty), which blocks because there are no empty slots.

The producer is now blocked while holding the mutex.

A consumer arrives and executes wait(full), which succeeds since the buffer is full, then executes wait(mutex), which blocks because the producer holds it.

Neither can proceed. The producer waits for a slot only the consumer can free; the consumer waits for a mutex only the producer can release.

Map this onto the four conditions. Mutual exclusion holds on the mutex, hold-and-wait holds because the producer holds the mutex while waiting on empty, no preemption holds since semaphores are not seizable, and circular wait holds between the two.

The general rule this illustrates: never block on a resource-counting semaphore while holding a mutex. Acquire the count first and the mutex second, always in that order.

9. More Worked Examples

Example 3. A system has 3 resource types A, B, C with 10, 5, 7 instances. Current allocation and maximum are as follows. Is the state safe?

Available is total minus allocated, which is $10-7=3$ for A, $5-2=3$ for B, and $7-5=2$ for C, giving (3, 3, 2).

Find any process whose need is at most available.

P0 needs (7, 4, 3), which exceeds available on every component. Skip.

P1 needs (1, 2, 2), which fits. Run it and reclaim its allocation, giving available (5, 3, 2).

P3 needs (0, 1, 1), which fits. Available becomes (7, 4, 3).

P4 needs (4, 3, 1), which fits. Available becomes (7, 4, 5).

P0 needs (7, 4, 3), which now fits. Available becomes (7, 5, 5).

P2 needs (6, 0, 0), which fits. Available becomes (10, 5, 7).

A complete ordering exists, so the state is safe, with safe sequence P1, P3, P4, P0, P2.

Note that the sequence is not unique and any valid one earns the mark.

Example 4. In the state above, P1 requests (1, 0, 2). Should the banker grant it?

Three checks are made in order.

First, is the request within P1's declared need of (1, 2, 2)? Yes, since (1, 0, 2) is componentwise smaller.

Second, is the request within available (3, 3, 2)? Yes.

Third, pretend to grant it and test safety. Available becomes (2, 3, 0), P1's allocation becomes (3, 0, 2) and its need becomes (0, 2, 0).

Now search for a safe sequence. P1 needs (0, 2, 0), which fits in (2, 3, 0), so run it, releasing (3, 0, 2) to give available (5, 3, 2).

P3 needs (0, 1, 1), fits, giving (7, 4, 3). P4 needs (4, 3, 1), fits, giving (7, 4, 5). P0 needs (7, 4, 3), fits, giving (7, 5, 5). P2 needs (6, 0, 0), fits.

The state is safe, so the request is granted.

Had the third check failed, the process would wait even though the resources were physically available, which is exactly the conservatism of avoidance.

Example 5. Three processes each need a maximum of 4 units of a single resource type. What is the smallest total number of units that guarantees the system cannot deadlock?

Deadlock requires every process to be holding units and still needing more.

The worst case is that each process holds one unit fewer than its maximum, since that is the most any can hold while still being blocked.

With 3 processes each holding 3 units, the total held is 9 and every process still needs 1 more.

If the system has exactly 9 units, that state is reachable and is a deadlock.

With 10 units, one unit remains after the worst case, so some process can complete, release all 4, and unblock the rest.

The general formula is that $n$ processes each with maximum need $m$ cannot deadlock if the total is at least $n(m-1)+1$.

Here that is $3\times 3+1=10$.

The formula generalises to unequal maximums as the sum of all maximums minus the number of processes plus one, which reduces to the same expression when the maximums are equal.

Example 6. Why does a cycle in a resource allocation graph imply deadlock with single-instance resources but not with multiple instances?

With one instance per type, an assignment edge identifies the unique holder. A cycle then means every process in it waits for a resource held by the next, and no process outside the cycle can release any of those resources, because it does not hold them.

The wait is therefore permanent and the cycle is sufficient.

With multiple instances, an assignment edge points from one instance to its holder, and a request edge does not name which instance will satisfy it.

A process in the cycle may be waiting for a type of which some other instance is held by a process outside the cycle.

When that outside process finishes and releases its instance, the waiting process proceeds and the cycle dissolves without anyone in it having done anything.

So a cycle is necessary but not sufficient, and detection with multiple instances requires the reduction algorithm on allocation and request matrices rather than a graph search.

Summary

Every concurrency bug is a claim about an interleaving and every solution restricts which interleavings are possible; to disprove correctness exhibit one bad ordering.

A correct critical section solution needs mutual exclusion, progress and bounded waiting. Mutual exclusion alone is satisfied by a solution that admits nobody, which is why the other two exist.

Peterson's algorithm works by having each thread set turn to the other, so the second write loses the tie. It needs memory barriers on real hardware. Test-and-set and compare-and-swap provide atomicity in hardware, and plain test-and-set locks lack bounded waiting.

A semaphore is an integer plus a blocked queue; when negative, its magnitude counts blocked threads. In the bounded buffer, waiting on the mutex before the counting semaphore deadlocks, which is the ordering rule to remember.

Monitors make mutual exclusion structural. Condition variables have no memory, and under Mesa semantics the woken thread must re-test its condition in a while loop.

Readers-writers starves writers in the naive form; dining philosophers deadlocks under uniform left-then-right acquisition, and each standard fix denies a different deadlock condition.

Deadlock needs mutual exclusion, hold and wait, no preemption and circular wait, all at once. Prevention denies one structurally, with resource ordering the practical choice. The banker's algorithm implements avoidance and refuses requests leading to unsafe states, though unsafe is not the same as deadlocked. Detection plus recovery, or simply ignoring the problem, is what real systems do.

With single-instance resources a cycle means deadlock; with multiple instances it does not. And $n$ processes with maximum need $m$ cannot deadlock given $n(m-1)+1$ units.