Deadlock and Starvation

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.

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.

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.

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.