--- title: 'Deadlock and Starvation' source: 'https://academia.sh/en/courses/operating-system-concepts/deadlock-and-starvation' course: 'Operating System Concepts' language: en updated: '2026-08-17T18:08:18+00:00' license: 'CC BY-SA 4.0' --- # Deadlock and Starvation Deadlock's four conditions, detecting it through cycle detection on the wait-for graph, lock ordering's structural prevention, and its cost in waiting steps. The previous lesson measured the cost of a single lock and collected the result on a single axis: waiting steps. On that axis, a bad number means a slow program. This lesson brings out a second kind of failure that produces **no** number on that axis at all: a deadlocked thread does not slow down, it **stops**. Two locks are enough. If one thread holds the first lock and requests the second, while another thread holds the second and requests the first, neither ever advances again. This lesson **counts** when this situation arises, builds the structural form of prevention, and measures what prevention costs. ## Four Conditions **Deadlock** does not happen at random. It arises when four conditions hold **at the same time**, and breaking any one of them makes it impossible. **Mutual exclusion.** The resource cannot be shared; only one thread can hold it at a time. Removing this condition would also remove the previous lesson's correctness guarantee. **Hold and wait.** A thread requests a new resource without releasing the one it already holds. **No preemption.** A lock cannot be forcibly taken back; only the holder can release it. **Circular wait.** The waiting relationship forms a ring. **CC14.** The wait-for graph's nodes are threads, and its edges are the relation "waiting for a held lock." **CC15.** A lock is held by only one thread at a time; if the requested lock is free, there is no edge. **CC16.** Every thread holds one lock and requests another; releasing a lock cannot be forced, and recovery after detection is not modeled. The first three conditions hold in most programs by design. The one remaining target is **circular wait**, and in the language of graphs that is exactly a **cycle**. ## Cycle Detection Is Not a New Routine The depth-first search lesson in the Data Structures course built cycle detection on a directed graph, and the same distinction applies here unchanged: "visited" must not be confused with "still open." The shared definition's `has_cycle` routine carries this with three colors — 0 never seen, 1 still open, 2 branch finished. The routine is **not rebuilt**; it is called directly. The measurement below first tests five wait-for graphs, then scans a state space. ```python from itertools import permutations, product def has_cycle(waiting: dict[str, list[str]]) -> bool: """Cycle test on a directed graph. color 1 = still open, color 2 = branch done.""" color = {d: 0 for d in waiting} def visit(d): color[d] = 1 for h in waiting.get(d, []): if color.get(h, 0) == 1: return True if color.get(h, 0) == 0 and visit(h): return True color[d] = 2 return False return any(color[d] == 0 and visit(d) for d in list(waiting)) for name, graph in (("nobody waiting", {"T1": [], "T2": []}), ("chain T1 -> T2", {"T1": ["T2"], "T2": []}), ("two branches, shared target", {"T1": ["T3"], "T2": ["T3"], "T3": []}), ("ring T1 -> T2 -> T1", {"T1": ["T2"], "T2": ["T1"]}), ("ring T1 -> T2 -> T3", {"T1": ["T2"], "T2": ["T3"], "T3": ["T1"]})): print(f" {name:28s} deadlock {has_cycle(graph)}") def scan(lock_count: int, thread_count: int, ordered: bool) -> tuple[int, int]: """Each thread holds one lock and requests another. All states.""" locks = list(range(1, lock_count + 1)) states = deadlocked = 0 for held in permutations(locks, thread_count): for requested in product(locks, repeat=thread_count): if any(t == i for t, i in zip(held, requested)): continue # does not request the lock it already holds if ordered and any(i < t for t, i in zip(held, requested)): continue # ordered acquisition: only a higher number is requested owner = {k: f"T{j+1}" for j, k in enumerate(held)} graph = {f"T{j+1}": [] for j in range(thread_count)} for j, i in enumerate(requested): if i in owner: # if the requested lock is free, there is no edge graph[f"T{j+1}"].append(owner[i]) states += 1 if has_cycle(graph): deadlocked += 1 return states, deadlocked print() print("4 locks , each thread holds one lock and requests another") print(" threads acquisition states deadlocked deadlock ratio") for n in (2, 3, 4): for ordered in (False, True): d, k = scan(4, n, ordered) label = "ordered" if ordered else "free " ratio = f"{k / d:.4f}" if d else "no states" print(f" {n:7d} {label} {d:8d} {k:10d} {ratio:>16s}") ``` ``` nobody waiting deadlock False chain T1 -> T2 deadlock False two branches, shared target deadlock False ring T1 -> T2 -> T1 deadlock True ring T1 -> T2 -> T3 deadlock True 4 locks , each thread holds one lock and requests another threads acquisition states deadlocked deadlock ratio 2 free 108 12 0.1111 2 ordered 22 0 0.0000 3 free 648 264 0.4074 3 ordered 36 0 0.0000 4 free 1944 1944 1.0000 4 ordered 0 0 no states ``` The third row is the heart of the measurement: with four locks and three threads, **648** distinct waiting states can be built, and **264** of them are deadlocked. The ratio is **0.4074**. The second branch matters: at two threads the ratio is **0.1111**, at three it is **0.4074**, at four it is **1.0000**. As threads are added, deadlock **stops being the exception and becomes the rule**. The 1.0000 in the row where four threads hold four locks is not a coincidence. When every thread holds one lock and requests another, the "whose lock am I waiting for" relation builds a graph with exactly one outgoing edge per node; a finite graph of this kind, with no node lacking an outgoing edge, **always** contains a ring. ## Detection and Prevention Are Not the Same Thing The scan above is a **detection** routine: given a state, it says whether it is deadlocked. Using this in a running system requires three things: **continuously keeping the wait-for graph up to date**, **scanning the graph at regular intervals**, and **rolling back a thread** when a cycle is found. The cost of the scan was measured in the Data Structures course and is $O(V + E)$; it is not repeated here. The third step is the most expensive. Rolling back means forcibly stripping a held lock and canceling the work that thread has done — that is, **breaking the no-preemption condition** — and the canceled work has to be redone. This lesson does not model that recovery (CC16). Prevention, on the other hand, **measures nothing and scans nothing** during the run. It pays its cost at design time: locks are given an order, and that order is followed everywhere. ## Lock Ordering In the table, every `ordered` row has **0** deadlocked states. This is not an improvement; it is a **structural impossibility**, and its justification fits in one sentence. **CC17.** Locks are placed in a fixed total order; every thread requests locks **only in increasing number order**. Suppose a ring exists. Then every thread in the ring is waiting for a lock numbered **higher** than the one it holds. Walking around the ring, the numbers keep increasing; but the ring returns to where it started, and a number cannot be greater than itself. Contradiction. So no ring exists. The table shows this in two separate ways. At three threads, the state space drops from **648** to **36**, and **none** of the remaining 36 states are deadlocked. At four threads, under lock ordering, **no states remain at all** — that state cannot even be constructed. The drop from 648 to 36 here also says where prevention's cost lies: **most of the eliminated states were not deadlocked.** Lock ordering forbids not only rings but also many harmless forms of waiting. ## The Cost of Prevention The forbidden harmless states are paid for somewhere. A thread that needs a second lock must, to follow the order, **acquire the first lock early** and **hold onto it**; two separate critical sections collapse into a single one. **CC18.** Under free acquisition, two resources have two separate locks, and two threads can be in a critical section at the same time; this gives the same numbers as a semaphore with two permits. Under ordered acquisition, the two locks are held nested, so there is a single critical section. ```python def locked_run(thread_count: int, critical: int, non_critical: int, permits: int = 1) -> dict: remaining = [{"critical": critical, "outside": non_critical} for _ in range(thread_count)] inside, t, waiting, busy = [], 0, 0, 0 while any(k["critical"] or k["outside"] for k in remaining): active = 0 for j, k in enumerate(remaining): if k["outside"]: k["outside"] -= 1 active += 1 continue if not k["critical"]: continue if j in inside or len(inside) < permits: if j not in inside: inside.append(j) k["critical"] -= 1 active += 1 if not k["critical"]: inside.remove(j) else: waiting += 1 busy += active t += 1 return {"time": t, "waiting": waiting, "busy": busy, "utilization": round(busy / (t * thread_count), 4)} print("two locks , critical section 10 steps total , non-critical 10 steps") print(" threads acquisition permits time waiting utilization") for n in (2, 4, 8): for label, permits in (("free ", 2), ("ordered", 1)): k = locked_run(n, 10, 10, permits) print(f" {n:7d} {label} {permits:4d} {k['time']:4d} {k['waiting']:7d}" f" {k['utilization']:8.4f}") print() for n in (2, 4, 8): s = locked_run(n, 10, 10, 1)["time"] - locked_run(n, 10, 10, 2)["time"] b = locked_run(n, 10, 10, 1)["waiting"] - locked_run(n, 10, 10, 2)["waiting"] print(f" {n} threads -> cost of ordered acquisition: time +{s} , waiting +{b}") ``` ``` two locks , critical section 10 steps total , non-critical 10 steps threads acquisition permits time waiting utilization 2 free 2 20 0 1.0000 2 ordered 1 29 9 0.6897 4 free 2 29 18 0.6897 4 ordered 1 47 54 0.4255 8 free 2 47 108 0.4255 8 ordered 1 83 252 0.2410 2 threads -> cost of ordered acquisition: time +9 , waiting +9 4 threads -> cost of ordered acquisition: time +18 , waiting +36 8 threads -> cost of ordered acquisition: time +36 , waiting +144 ``` At four threads, lock ordering raises time from **29 to 47** and waiting steps from **18 to 54**. At eight threads, the gap widens further: time from **47 to 83**, waiting from **108 to 252**. The cost grows with the thread count — **+9, +18, +36**. These numbers make the trade explicit. Lock ordering brings the deadlock probability down from 0.4074 to **0.0000**; in return, **144 extra waiting steps** are paid at eight threads. Zero deadlock is bought at the price of a performance loss, and this trade cannot be defended without being counted. ## Starvation Deadlock is threads stopping **together**. **Starvation**, by contrast, is a single thread's turn never coming while the system keeps running. Unlike deadlock, there is no cycle in the wait-for graph; the lock keeps being granted, just always to the same threads. **CC19.** Threads request the critical section **continuously**; as soon as they finish their non-critical work, they queue again. **CC20.** When the lock frees up, one of the waiters is chosen; the selection rule takes either the lowest-numbered waiter or the longest-waiting one. ```python def continuous_run(thread_count: int, critical: int, non_critical: int, duration: int, fair: bool) -> dict: """Threads that continuously request the critical section. The lock goes to the longest waiter if fair, otherwise to the lowest-numbered waiter.""" remaining = [0] * thread_count # steps left in the critical section outside = [0] * thread_count # steps left in non-critical work request = [0] * thread_count # how long it has been waiting turns = [0] * thread_count # how many times it entered the critical section inside = None for t in range(duration): for j in range(thread_count): if outside[j]: outside[j] -= 1 elif inside != j: request[j] += 1 if inside is None: waiting = [j for j in range(thread_count) if not outside[j]] if waiting: chosen = max(waiting, key=lambda j: request[j]) if fair else min(waiting) inside, remaining[chosen], request[chosen] = chosen, critical, 0 turns[chosen] += 1 if inside is not None: remaining[inside] -= 1 if not remaining[inside]: outside[inside] = non_critical inside = None return {"turns": turns, "starved": request} # starved: steps waited since the last request print("4 threads , critical 10 , non-critical 10") print(" duration selection rule turn distribution total turns steps starved") for duration in (400, 4000): for fair in (False, True): s = continuous_run(4, 10, 10, duration, fair) label = "fair " if fair else "lowest " print(f" {duration:4d} {label} {str(s['turns']):20s} {sum(s['turns']):10d}" f" {s['starved']}") ``` ``` 4 threads , critical 10 , non-critical 10 duration selection rule turn distribution total turns steps starved 400 lowest [20, 20, 0, 0] 40 [0, 0, 400, 400] 400 fair [10, 10, 10, 10] 40 [20, 10, 0, 0] 4000 lowest [200, 200, 0, 0] 400 [0, 0, 4000, 4000] 4000 fair [100, 100, 100, 100] 400 [20, 10, 0, 0] ``` In four hundred time units, the critical section sees **40** total entries — **under both selection rules**. Throughput is the same. The distribution is not: the rule that picks the lowest-numbered waiter distributes entries as `[20, 20, 0, 0]`. The third and fourth threads **never enter** and sit starved for **400 steps**. When the duration is multiplied by ten, the result does not change: `[200, 200, 0, 0]`. Steps starved rise from 400 to **4000**. This is a failure distinct from deadlock, and it **does not pass with time**; it has no bound and grows with duration. The fair selection rule distributes the same 40 entries as `[10, 10, 10, 10]`. Total throughput does not change, so **fairness comes free here**. The reason it comes free is that the critical section is already serialized; the cost was already paid in the previous lesson. The real warning in this measurement is that a throughput metric **cannot see** starvation. The total turn count is 40 under both rules; the only thing that reveals the failure is the **distribution**. ## Three Numbers | Metric | Baseline without abstraction | Setup with abstraction | Cost | |---|---|---|---| | Deadlocked states | single lock, **0** | four locks, three threads, **264/648** | ratio 0.4074 | | After lock ordering | — | **0/36** | time +18, waiting +36 | | Starvation | single thread, **0** | four threads, unfair selection | 2 threads, **4000** steps starved | The table's second row carries the course's rule: eliminating deadlock is not a gain, it is a **trade**. At four threads, the 0.4074 deadlock ratio is zeroed out, and in return every thread waits longer. ## Summary - Deadlock arises when four conditions hold at once; in practice the only breakable condition is circular wait, which is a cycle in the wait-for graph. - Cycle detection is not a new routine; the three-color test built in the Data Structures course's depth-first search lesson is called unchanged. - With four locks and three threads, **264** of 648 waiting states are deadlocked (0.4074); as the thread count grows, the ratio rises from 0.1111 to 1.0000. - Lock ordering makes a ring structurally impossible — the state space drops from 648 to 36 and deadlocked states become **0**; the cost at eight threads is 144 extra waiting steps. - In starvation there is no cycle and throughput does not drop: in 400 time units, a total of 40 entries is the same under both selection rules; the failure shows up only in the distribution. ## Next Step Everything measured so far happened on a single core; the threads never actually advanced at the same time. The next lesson lifts that restriction. Adding a core brings the time down from 197 to 180, but a fourth core plateaus at 179, and idle core steps rise from 108 to 1355. The same lesson will also show what became of the first lesson's quantum protection: under real parallelism, the reachable interleavings climb back to 20, and 18 of them are wrong.