Deadlock, Livelock and Starvation: Coffman Conditions, Lock Ordering and Priority Inversion

Version note: The code in this post was built and run with .NET 10 (C# 14); tests use xUnit v3 4.0.3. The outputs were taken on ARM64; the priority inversion behaviour of Windows and Linux is based on their official documentation.

Guess First

Bookstore, the online bookstore used as the shared example across this site's series, has two warehouses, in Istanbul and Ankara. A stock transfer first takes the lock of the source warehouse, then the lock of the target warehouse. One thread moves 100,000 books from Istanbul to Ankara while another moves 100,000 from Ankara to Istanbul at the same time. How long does the job take?

Emre from the team sees the deadlock risk and suggests taking the locks with a 1 millisecond timeout: if you cannot get it, let go and try again. Does this finish the transfers? Last question: why did the computer of Pathfinder, which landed on Mars in 1997, restart itself every few days, and how did the engineers fix it from Earth? In the previous post we accepted that a thread cannot make progress while waiting for a lock; in this post we look at cases where the wait never ends.

Two Warehouses, Two Locks: A Real Deadlock

The transfer code looks innocent at first. Lock the source warehouse, lock the target warehouse, move the stock:

// Locks "from" first, then "to": two opposite transfers can wait for each other forever
public static void Move(Warehouse from, Warehouse to, string isbn, int quantity)
{
    lock (from.Gate)
    {
        lock (to.Gate)
        {
            Apply(from, to, isbn, quantity);
        }
    }
}

The experiment command runs two threads in opposite directions and waits at most 5 seconds:

dotnet run -c Release --project src/Bookstore.ConcurrencyLab -- transfer naive 100000

naive: not finished after 5 s; timeouts=0, east=Background, WaitSleepJoin, west=Background, WaitSleepJoin

Both threads are in the WaitSleepJoin state, meaning they are waiting for a lock, and that wait will never end. East holds Istanbul's lock and waits for Ankara; West holds Ankara and waits for Istanbul. I made the threads background threads so the process could exit; in a web application, the locks held by these two threads would also keep every request touching those warehouses waiting forever. The CLR does not detect deadlocks on Monitor locks: no exception, no log, only hanging requests. We showed how to find the threads holding the locks in a hung process with Parallel Stacks in the multi-thread debugging post of the Debugging and Problem Solving series.

Coffman's Four Conditions

In their 1971 paper "System Deadlocks", published in ACM Computing Surveys, Edward Coffman, Michael Elphick and Arie Shoshani showed that a deadlock can only occur when four conditions hold at the same time. What makes this valuable is that each condition is a door to a fix: break any one of the four and deadlock becomes impossible.

The first three conditions are almost always true in programs with locks; a lock exists for mutual exclusion, nested locks are hold and wait, and a lock cannot be taken from you. That is why the condition broken most often in practice is the fourth: circular wait.

The Resource Allocation Graph and Cycles

The standard way to visualize deadlock is the resource allocation graph: threads and resources are nodes, and "holds" and "waits for" relations are edges. If you remove the resource nodes and keep only edges like "T1 waits for T2", you get the wait-for graph. When each resource has a single instance, a cycle in the wait-for graph means a deadlock:

Looking for a cycle is a simple depth-first search. At its core, this is what database deadlock detection does too:

// Depth-first search; returns the first cycle found, or an empty list
private List<string> Visit(string node, List<string> path, HashSet<string> done)
{
    int index = path.IndexOf(node);
    if (index >= 0)
        return [.. path[index..], node];
    if (!done.Add(node))
        return [];
    path.Add(node);
    foreach (string next in _edges.GetValueOrDefault(node) ?? [])
    {
        List<string> cycle = Visit(next, path, done);
        if (cycle.Count > 0)
            return cycle;
    }
    path.RemoveAt(path.Count - 1);
    return [];
}

dotnet run -c Release --project src/Bookstore.ConcurrencyLab -- wait-for

cycle: T1 (Istanbul->Ankara) -> T2 (Ankara->Istanbul) -> T1 (Istanbul->Ankara)

I also added a report thread (T3) that waits for T1. T3 is not part of the cycle, but it waits forever too: a deadlock stops not only the threads in the cycle but everything that depends on them.

Prevention: Global Lock Ordering

The way to break circular wait is to give all locks an order and make every thread take locks only in that order. The warehouses' Id is a natural order:

// Global lock order: always the smaller Id first, whatever the direction
public static void MoveOrdered(Warehouse from, Warehouse to, string isbn, int quantity)
{
    (Warehouse first, Warehouse second) = from.Id < to.Id ? (from, to) : (to, from);
    lock (first.Gate)
    {
        lock (second.Gate)
        {
            Apply(from, to, isbn, quantity);
        }
    }
}

dotnet run -c Release --project src/Bookstore.ConcurrencyLab -- transfer ordered 100000

ordered: finished in 25 ms, total stock=2,000,000, timeouts=0

200,000 transfers finished in 25 ms, and the total stock was preserved. You can see why it works in the figure too: both threads ask for Istanbul's lock first. The loser waits while holding no lock, and the winner gets the second lock because nobody holds it. Since the locks a thread holds are always smaller than the lock it waits for, waits always move in the direction of growing Ids and the cycle can never close.

The classic Dining Philosophers problem generalizes the same idea. Dijkstra posed it as an exam question in 1965, and Hoare spread it with today's story of a table and forks: five philosophers sit at a round table with five forks between them, and eating takes two forks. If everyone takes the left fork first and then the right one, a cycle can form where everyone holds one fork and waits for the other. The fix is ordering again: everyone takes the lower-numbered fork first. That means the last philosopher takes the right fork first, and the cycle breaks:

dotnet run -c Release --project src/Bookstore.ConcurrencyLab -- philosophers

left then right  table froze (deadlock)
ordered forks    all ate in 166 ms

Avoidance, Detection and Timeouts

Prevention makes deadlock impossible by design. Avoidance instead asks on every lock request: "if I grant this, could we end up in a deadlock later?" The best-known example is Dijkstra's Banker's algorithm: each thread declares in advance the maximum resources it will ask for, and the system grants a request only if there is still an order in which everyone can finish afterwards. Like a banker who, when lending, keeps enough cash in the vault to meet everyone's needs one after another. It is rare in practice, because application code does not know in advance which locks it will need and how many, and doing this calculation on every request is expensive.

Detection and recovery lets deadlock happen, then finds and resolves it. Databases choose this path: SQL Server periodically looks for cycles in the wait-for graph, and when it finds one it picks a transaction as the victim and rolls it back, and the application gets error 1205. We covered this with the deadlock graph and retries in .NET in the deadlock post of the SQL Server Derinlemesine series. Application code has no such mechanism for locks; that is why you have to prevent it by design.

The third path is a timeout: if you cannot get the lock in time, release what you hold. This breaks the no preemption condition; the thread gives the resource back voluntarily:

// Timeout instead of waiting forever: the caller decides what to do on failure
public static bool TryMove(Warehouse from, Warehouse to, string isbn, int quantity, TimeSpan timeout)
{
    if (!Monitor.TryEnter(from.Gate, timeout))
        return false;
    try
    {
        if (!Monitor.TryEnter(to.Gate, timeout))
            return false;
        try
        {
            Apply(from, to, isbn, quantity);
            return true;
        }
        finally { Monitor.Exit(to.Gate); }
    }
    finally { Monitor.Exit(from.Gate); }
}

I applied Emre's suggestion as is: on failure, try again immediately. The second version sleeps a random 0–2 ms after a failure:

dotnet run -c Release --project src/Bookstore.ConcurrencyLab -- transfer timeout 100000
dotnet run -c Release --project src/Bookstore.ConcurrencyLab -- transfer timeout-backoff 100000

timeout: not finished after 5 s; timeouts=621,187, east=Background, WaitSleepJoin, west=Background, WaitSleepJoin
timeout-backoff: finished in 16 ms, total stock=2,000,000, timeouts=3

No deadlock, but the job did not finish either: 621,187 timeouts in 5 seconds. Both threads take their first lock at the same time, both time out on the second lock, both release and try again at the same time. This is deadlock's sibling, livelock: the threads are not blocked, they keep doing something, but nobody makes progress. When I tried with 1,000 transfers, the job finished in 184 ms with 8,368 timeouts; so it does not stop completely, but progress is left to chance. Random backoff breaks the symmetry, and the same job finishes in 16 ms with 3 timeouts. Ethernet's random wait after a collision is based on the same idea.

Livelock and Starvation

To see livelock more clearly, I wrote two polite threads: each holds its own lock and tries the other's without waiting; if it fails, it releases its own lock and tries again immediately. Like two people meeting in a corridor who both step aside to the same side at the same time:

dotnet run -c Release --project src/Bookstore.ConcurrencyLab -- livelock 100000

retry at once   transfers=200,000 retries=73,258 time=12 ms
random backoff  transfers=200,000 retries=682 time=3 ms

The version that retries immediately backed off 73,258 times for 200,000 transfers; the version that waits randomly backed off 682 times. In this experiment both finish, because the OS scheduler does not run the threads perfectly symmetrically. In real systems, livelock usually shows up not as "it stopped completely" but as "throughput suddenly collapses as load grows".

Starvation is when the system as a whole makes progress but a particular thread keeps falling behind. The test-and-set lock in the previous post did not provide bounded waiting; an unlucky thread can keep losing the race. According to the documentation of .NET's Monitor, the thread that takes the lock when it is released does not have to be the one that was signalled; so there is no ordering guarantee. This is a deliberate choice for throughput: giving the lock to a running thread that asks for it right now is faster than waking a sleeping thread and waiting for it. If you need fairness (for example, institutional customers' requests must not wait forever behind individual customers'), expect it from an explicit queue design, not from the lock.

Priority Inversion: Mars Pathfinder

A special kind of starvation appears when threads have priorities. Low-priority L holds a lock, and high-priority H waits for the same lock. Meanwhile medium-priority M, which has nothing to do with the lock, becomes ready to run. Because the scheduler looks at priorities, it puts M ahead of L; L cannot run, so it cannot release the lock, and H waits because of M, which has a lower priority than itself. The priorities are effectively inverted.

The best-known case is Mars Pathfinder. The spacecraft landed on Mars on 4 July 1997, and a few days later its computer started restarting itself from time to time. According to the account written in December 1997 by Glenn Reeves, the engineer responsible for the flight software, in the software running on the VxWorks real-time operating system a high-priority task managing the data bus was waiting for a mutex held by a low-priority task carrying meteorological data; medium-priority tasks kept running ahead of the low-priority one, so the high-priority task could not finish in time, and the timing check that noticed this reset the system. The team reproduced the bug in less than 18 hours on a replica on Earth, using the trace facility deliberately left in the flight software. The fix was to turn on the priority inheritance option, which was off for the semaphores involved, by changing a global variable; the change was sent to the spacecraft as a patch and the resets stopped.

The idea of priority inheritance is simple: a thread holding a lock temporarily inherits the highest priority of the threads waiting for that lock. L runs with H's priority, M cannot pass it, L releases the lock and its priority drops back. According to the "Priority Inversion" page on Microsoft Learn, Windows does this with a feature called AutoBoost: it tracks resource ownership and gives the lock owner the highest priority of its waiters as a floor. On Linux, this protocol is explicitly chosen for pthread mutexes with PTHREAD_PRIO_INHERIT. The lesson for .NET applications: playing with Thread.Priority is rarely a good idea; giving different priorities to threads that share the same lock means building this problem with your own hands.

In Production

Write lock ordering down as a rule and enforce it in code. If "warehouse locks are taken in Id order" lives in a code review comment, it is forgotten six months later. Write a single helper method that takes the locks (like our MoveOrdered) and forbid nesting two locks by hand.

Do not call outside code while holding a lock. Raising an event, calling a callback or calling a virtual method from inside a lock leaves the lock order to whoever writes that code. If you raise a StockChanged event while holding a Warehouse lock and a subscriber takes another warehouse's lock for reporting, a nested lock appears that is nowhere visible in your code. Raise the event after leaving the lock.

Watch hanging requests as a metric. Deadlock produces no exception; its symptom is a particular endpoint's duration suddenly hitting the timeout limit and the thread pool growing. In that situation, taking a dump of the process and looking at which locks the waiting threads hold is faster than guessing.

Common Pitfalls

Treating a timeout as a deadlock fix. In the experiment the timeout removed the deadlock but replaced it with a livelock of 621,187 timeouts in 5 seconds. A timeout only helps together with random backoff and an upper retry limit; the real fix is lock ordering.

Missing nested locks in code review. When you see a lock inside another lock, or a method call that takes a lock, ask two questions: are these two locks taken in the opposite order somewhere else, and is this order based on a written rule? Most deadlocks are the combination of two innocent methods in two different files.

Seeing a deadlock in tests only if you are lucky. In our experiment the naive transfer deadlocked every time, because we started two threads together with a barrier and tried 100,000 times. In real code the same two transfers arrive at the same moment once a day, and the deadlock happens once a month. That is why the protection against deadlock is not testing but the ordering rule itself.

A Small Experiment

★☆☆ Add a sixth philosopher to the table in the ordered solution of the philosophers command and verify that it still does not freeze. Explain in one sentence why it works regardless of the number of forks.

★★☆ Set up a three-warehouse scenario: T1 Istanbul→Ankara, T2 Ankara→Izmir, T3 Izmir→Istanbul. Watch a three-thread cycle form with the naive transfer, build the same cycle with WaitForGraph and print the path FindCycle returns.

★★★ Add exponentially growing random backoff and at most 10 attempts to TryMove; if it fails after 10 attempts, it should throw an exception. Measure the total time and the number of timeouts with initial waits of 1, 10 and 100 microseconds, and discuss which factors decide the best value.

In the first four posts we always assumed "what one thread writes, the other sees"; only with Peterson did we see that assumption break. In the next post of the series we go down to the hardware itself: store buffers, cache coherence, sequential consistency, and why the memory ordering models of x64 and ARM64 behave differently.