Deadlock, Livelock, and Starvation

Concurrency safety asks whether anything bad happens: corrupted state, duplicate ownership, or an invalid transition. Liveness asks whether useful work eventually happens at all. A program can protect every shared field correctly and still stop making progress because tasks wait in a cycle, repeatedly avoid one another, or continually favor other work.

Deadlock, livelock, and starvation are often grouped together because all three look like “the request is stuck.” Their mechanisms and remedies differ. A deadlocked participant is waiting for an event that cannot occur within the waiting set. A livelocked participant remains active but repeatedly changes state without completing. A starved participant is continually denied a resource while the system as a whole may keep succeeding.

The practical thesis is that progress must be designed as an explicit protocol. Resource acquisition needs an order, retries need a symmetry-breaking rule, queues need a fairness contract, and operations need enough identity and state to detect prolonged waiting. Adding a timeout can limit impact, but it does not explain or remove the underlying progress failure.

Classify the Progress Failure Before Treating It #

The same latency graph can arise from very different states. Classification starts by asking what each participant is doing and whether anyone else is completing useful operations.

A slow operation is not automatically starved. It may be executing expensive work. A long wait is not automatically deadlock; an owner may be healthy and eventually release the resource. High retry count is not automatically livelock if retries make monotonic progress toward completion. Diagnosis requires a state model, not one threshold.

Safety and liveness also interact. A common safety repair is to add a lock around a larger region. That may remove a race while introducing a cycle or unacceptable convoy. A liveness repair that skips locking can restore throughput by sacrificing correctness. Both properties must be stated and tested together.

Progress claims need assumptions. “Every waiter eventually enters” may assume that the runtime schedules ready threads, owners eventually leave critical sections, and no participant crashes while holding a non-recoverable resource. Write those assumptions down. Otherwise an implementation is blamed for guarantees its environment never provided, or worse, credited with guarantees it cannot make.

Model Deadlock with a Wait-For Graph #

A wait-for graph makes resource dependencies concrete. Each node represents a task or transaction. Add a directed edge $A \rightarrow B$ when A cannot proceed until B releases a resource or performs an action. A directed cycle means every participant in that cycle waits, directly or transitively, on itself.

For resources with one owner at a time, a cycle is the characteristic deadlock condition. With multiple interchangeable resource instances, a simple cycle may not be sufficient because another instance could satisfy a waiter; detection must account for available counts and outstanding requests. Condition variables and message protocols can also create logical waits without a conventional mutex, so the graph should represent actual progress dependencies rather than only lock objects.

The classic necessary conditions help organize prevention:

1. Mutual exclusion: at least one resource cannot be shared simultaneously.
2. Hold and wait: a participant holds one resource while waiting for another.
3. No forced preemption: the resource cannot simply be taken away safely.
4. Circular wait: participants form a cycle of dependencies.

Break any one condition and this form of deadlock cannot occur. Not every condition is negotiable. A file update may require exclusive ownership, and forcibly taking a half-mutated object can violate safety. Engineering usually targets hold-and-wait through atomic acquisition or circular wait through a global order.

Wait-for edges should include ownership context: resource ID, acquisition site, owner task, waiter task, wait start, and whether the wait is interruptible. That information turns a cycle report into a repairable explanation. Raw thread stacks alone often show where tasks wait but not who holds what or how the cycle closes.

Worked Example: Two Transfers, Two Lock Orders #

Suppose account transfers use one mutex per account. The initial implementation locks the source first and the destination second:

type Account = {
  id: string;
  balance: number;
  mutex: Mutex;
};

async function transferUnsafe(
  source: Account,
  destination: Account,
  amount: number,
): Promise<void> {
  await source.mutex.lock();
  try {
    await destination.mutex.lock();
    try {
      if (source.balance < amount) throw new Error('Insufficient funds');
      source.balance -= amount;
      destination.balance += amount;
    } finally {
      destination.mutex.unlock();
    }
  } finally {
    source.mutex.unlock();
  }
}

Run T1 = transferUnsafe(A, B, 10) and T2 = transferUnsafe(B, A, 5). This schedule deadlocks:

1. T1 locks A.
2. T2 locks B.
3. T1 waits for B, which T2 owns.
4. T2 waits for A, which T1 owns.

Both tasks use finally, but neither reaches it because neither second acquisition finishes. Cleanup code is necessary for exceptions and cancellation; it cannot resolve a closed wait cycle that prevents control from reaching cleanup.

The repair chooses lock order from stable account identity, independent of transfer direction:

async function transferOrdered(
  source: Account,
  destination: Account,
  amount: number,
): Promise<void> {
  if (source.id === destination.id) return;

  const [first, second] =
    source.id < destination.id ? [source, destination] : [destination, source];

  await first.mutex.lock();
  try {
    await second.mutex.lock();
    try {
      if (source.balance < amount) throw new Error('Insufficient funds');
      source.balance -= amount;
      destination.balance += amount;
    } finally {
      second.mutex.unlock();
    }
  } finally {
    first.mutex.unlock();
  }
}

Both T1 and T2 now request A before B when A.id < B.id. One may wait for A, but it holds no B lock while doing so, so the two-node cycle cannot form. The ordering key must be total, stable for the resource lifetime, and used by every code path that acquires the same resource class. Locale-sensitive names, mutable priorities, or inconsistent numeric/string comparisons are poor keys.

This proof covers two account locks and extends to any finite set: deduplicate resources, sort by the same total key, acquire in ascending order, and release in reverse. Dynamic discovery complicates the protocol. If code learns that it needs a lower-ordered resource after taking a higher one, it must release and retry from the complete set or use another transaction mechanism. Quietly violating the order “just once” invalidates the global argument.

Prevent Deadlock Without Creating New Hazards #

Lock ordering is effective, but it is not the only prevention strategy. Acquire-all-or-none asks a resource manager to grant the complete set atomically. It eliminates hold-and-wait but may reduce concurrency and requires the full set to be known. Resource confinement sends all operations through one owner, replacing lock cycles with a queue; this simplifies ownership but can concentrate load. Smaller critical sections reduce overlap, provided invariants do not escape half-updated.

Try-lock protocols acquire available resources and release everything if any acquisition fails. They avoid blocking while holding a partial set, but naive retries can become livelock. Add a deterministic winner, queued reservation, or contention manager rather than assuming random timing will separate contenders.

Timeouts can recover capacity from a deadlock if waiting is cancellable and cancellation reliably releases every held resource. They do not prevent the cycle, can abort healthy operations during ordinary contention, and may repeatedly choose the same victim. Treat a lock timeout as a diagnostic and recovery boundary, not proof of a deadlock.

Avoid calling unknown or blocking code while holding a resource. Callbacks, logging sinks, user hooks, and synchronous cross-component requests can acquire resources in an order the caller cannot see. Copy required immutable state under protection, release, and invoke the external operation afterward when the invariant permits it.

Hierarchy can encode ordering at an architectural level: acquire tenant before document, parent before child, or metadata before data. Document whether same-level resources use a secondary order. Automated checks can track a per-task acquisition rank in test builds and fail immediately when code attempts to acquire a lower rank while holding a higher one.

Every prevention choice trades something. Coarse ownership reduces deadlock surface but limits parallelism. Atomic multi-resource acquisition adds coordinator complexity. Releasing and retrying wastes work. A strict order can force acquisition earlier than data locality would prefer. Choose based on invariant and contention evidence, then verify the progress claim.

Recognize and Break Livelock #

In livelock, participants react to contention but their reactions keep the system from committing. Imagine two transfer tasks using try-lock. Each acquires its first account, fails to acquire the second, releases, yields politely, and retries. If both execute in phase, they can repeat forever: neither blocks, CPU remains active, locks change owners, and no transfer completes.

The telltale trace is periodic or repeated state with rising attempt count:

T1: acquire A, fail B, release A, retry
T2: acquire B, fail A, release B, retry
T1: acquire A, fail B, release A, retry
T2: acquire B, fail A, release B, retry

Break symmetry with a rule that makes one participant yield decisively. A total lock order removes the conflicting acquisition pattern. A contention manager can compare stable transaction IDs and require one loser to wait. A FIFO reservation can hand the complete resource set to one waiter. Randomized backoff reduces repeated collision probability but does not provide a deterministic bounded-wait guarantee, and synchronized pseudo-random seeds can recreate symmetry.

Retry policy should include a limit or budget and surface exhaustion as a distinct outcome. However, failing both participants after ten collisions is containment, not progress. Observe useful completions per attempt, repeated state hashes, and time spent executing versus committing. High CPU plus flat completion rate is a stronger livelock signal than CPU alone.

Optimistic concurrency can livelock under heavy conflict when every transaction repeatedly reads, computes, loses validation, and restarts. Remedies include serializing a hot key, adding winner priority, combining updates, reducing transaction scope, or applying admission control. Blindly increasing retry speed usually intensifies contention.

Design Fairness to Bound Starvation #

Starvation is asymmetric: some operations complete while one eligible operation waits indefinitely or beyond its contractual bound. An unfair mutex may repeatedly admit arriving threads ahead of an old waiter. Reader-preference locking may keep a writer waiting while readers continually overlap. A priority queue may never run low-priority maintenance while urgent work keeps arriving.

Fairness has levels. Weak fairness says an action that remains continuously enabled eventually runs. Strong fairness also considers an action enabled infinitely often but not continuously. Production APIs more often define concrete policies such as FIFO among equal-priority waiters, maximum queue delay, or a quota that reserves capacity for a class.

Strict FIFO bounds overtaking but can reduce throughput through convoying: the first waiter may be slow to wake while a later one could proceed. Reader-writer fairness can alternate phases, cap consecutive readers, or prioritize a waiting writer. Priority queues can age waiting tasks by raising effective priority over time. Weighted queues reserve service shares but require explicit behavior when a class is idle.

Priority inversion is a related mechanism: a high-priority task waits for a resource held by a low-priority task, while medium-priority work prevents the owner from running and releasing it. Priority inheritance can temporarily raise the owner’s priority where the runtime supports it. It is not a substitute for short ownership or a consistent acquisition protocol.

Measure fairness as a distribution, not an average. Track wait age, maximum overtakes, completions by class, and oldest eligible operation. Aggregate throughput can look excellent while one tenant or task class receives no service. Avoid unbounded cardinality in telemetry; preserve detailed traces only for sampled or threshold-crossing waits.

Detect Deadlock and Recover Deliberately #

When prevention is impractical, detect cycles in a resource manager’s wait-for graph. Add an edge when a task begins waiting and remove it when the wait ends or ownership changes. Cycle detection can run on each blocking edge for small graphs or periodically for larger ones. The snapshot and update protocol must be consistent enough to avoid reporting a cycle assembled from states that never coexisted.

Detection needs a victim policy. A database can abort one transaction, roll back its writes, release its locks, and let the others continue. Choose a victim by rollback cost, age, attempts, priority, or number of dependents. Repeatedly selecting the same low-cost transaction can starve it, so include retry history or aging.

General application tasks may not be safely preemptible. Killing a thread that holds process memory invariants can make recovery worse. Prefer cooperative cancellation at well-defined transaction boundaries, process isolation for work that can be terminated, or fail-fast restart when state cannot be trusted. Recovery must establish that every resource is released and every partial external effect is reconciled.

Operational diagnostics should capture the cycle, owner and waiter stacks, resource identities, hold and wait durations, operation classes, and recent acquisition events. For livelock, capture retry transitions and contention peers. For starvation, capture queue position changes and overtakes. Redact business payloads while preserving stable correlation IDs.

Alerts should distinguish a long holder from a cycle, a retry storm, and an aging waiter. These conditions have different responders and mitigations. Temporary concurrency reduction may contain contention, but only the dependency or fairness evidence points to a durable fix.

Test Progress Properties and Failure Recovery #

Deterministic scheduling makes small counterexamples reliable. For the transfer bug, barriers can pause T1 after locking A and T2 after locking B, then release both second acquisitions. The unsafe version should produce a cycle in the test lock manager. The ordered version should make that state unreachable: one task cannot hold B while waiting for A.

Test both safety and liveness invariants. Total balance remains constant, no account becomes invalid, each successful transfer applies once, and every admitted transfer reaches a terminal state under a fair finite schedule. Inject cancellation and failure after each acquisition to verify reverse-order release. Assert the lock ownership table is empty after settlement.

For livelock, script both contenders to collide repeatedly. Verify the symmetry-breaking rule selects one winner within a stated number of decisions, then lets the loser retry. For starvation, enqueue an old low-priority task while continuously adding favored work. Advance the scheduler deterministically and assert the aging or quota policy admits the old task within its bound.

Stress tests remain useful for larger graphs and runtime behavior. Record task IDs, acquisition order, retry count, and seeds. Use watchdogs to collect state, not merely terminate a hanging test. Race detectors find unsafe shared access but do not prove progress; a race-free program can deadlock perfectly.

The durable review questions are direct: Can acquisition dependencies form a cycle? Can collision responses repeat without commitment? Can new work overtake an existing waiter without bound? What evidence detects each case, and what recovery restores invariants?

Deadlock is circular waiting, livelock is futile activity, and starvation is indefinite exclusion amid progress elsewhere. Their common cure is not a larger timeout. It is an explicit progress protocol: ordered or atomic acquisition, deterministic contention resolution, bounded fairness, observable wait state, and tested recovery. When those rules are part of the design, “stuck” becomes a diagnosable state rather than a mystery discovered only under load.