Deadlocks, Livelocks, Starvation and Priority Inversion

Learning Objectives

Define deadlock and state the four Coffman conditions; draw resource-allocation and wait-for graphs; recognise circular wait, lock-order inversion and nested locks.

Apply prevention, avoidance, and detection-and-recovery; use timed acquisition and try_lock knowing their limits.

Recognise livelock, starvation, unfairness/barging, priority inversion (and inheritance/ceiling protocols) and convoys.

Diagnose blocked threads, design lock hierarchies, acquire multiple locks safely, and review code with a deadlock checklist.

Plain-Language Explanation

Two people meet in a narrow corridor. Each waits for the other to step aside — forever. That is a deadlock. If both step aside to the same side at the same time, again and again, nobody is stuck but nobody gets through — a livelock. If one polite person always lets everyone else go first and never passes, that is starvation. And if a VIP is stuck behind someone who has been pushed out of the way by a crowd of less important people, that is priority inversion.

Precise Technical Explanation

A set of threads is deadlocked when each is waiting for an event (usually a resource release) that only another thread in the set can cause. None can proceed, ever, without outside intervention.

All four must hold simultaneously for a resource deadlock (Coffman et al., 1971):

Mutual exclusion — a resource can be held by only one thread at a time.

Hold and wait — a thread holds resources while waiting for others.

No preemption — resources cannot be taken away; only the holder releases them.

Circular wait — a cycle of threads each waiting for a resource held by the next.

Breaking any one prevents deadlock.

Resource allocation graphs A resource-allocation graph has thread nodes and resource nodes; an edge *R → T* means T holds R, *T → R* means T waits for R. With single-instance resources, a cycle means deadlock. Collapsing resources gives the wait-for graph (T₁ → T₂ when T₁ waits for something T₂ holds).

The cycle itself: T₁ waits for T₂, T₂ waits for … Tₙ, Tₙ waits for T₁.

The most common deadlock in practice: one code path locks A then B, another locks B then A. Each thread gets its first lock and waits forever for the second (demonstrated below).

Any time code holds one lock while acquiring another — directly or by calling a function that locks — nested acquisition creates ordering constraints. Callbacks and virtual calls made while holding a lock are hidden nesting.

Design so one Coffman condition can never hold: a global lock order (no circular wait — the standard technique); acquire all locks at once (no hold-and-wait — std::scoped_lock, std::lock); allow preemption (try-lock and release on failure); avoid locks (lock-free structures, message passing).

Grant requests only if the system stays in a *safe state* (Dijkstra's banker's algorithm). It requires knowing maximum demands in advance, so it is used in some resource managers but rarely in application code.

Deadlock detection and recovery Let deadlocks happen, detect cycles in the wait-for graph (databases do this constantly), and recover by aborting a victim (rolling back its transaction) or preempting resources. The JVM can detect monitor deadlocks on demand (example below).

try_lock_for, tryLock(timeout), acquire(timeout=…): a thread that cannot get a lock within a deadline gives up, releases what it holds and retries or reports an error. Turns a hang into an error you can handle.

try_lock and its limitations Non-blocking try-lock enables back-off protocols but: it can livelock (everyone backs off and retries in lockstep), it can starve unlucky threads, and it complicates code. It does not detect deadlock; it avoids waiting.

Threads keep changing state in response to each other without making progress — e.g. two threads that each take lock A, fail to get B, release A and retry at the same rhythm. Fixes: randomised back-off (jitter), ordering, or a single coordinator.

A thread is perpetually denied a resource it needs although the system as a whole progresses: unfair locks, readers starving writers, low-priority threads starved by high-priority ones.

Fairness and barging Barging: a thread that releases a lock and immediately requests it again often re-acquires it before a sleeping waiter wakes. That maximises throughput (no context switch) but can starve waiters. Fair (FIFO) locks hand the lock to the longest waiter, at a large throughput cost.

A high-priority thread H waits for a lock held by a low-priority thread L; a medium-priority thread M, which needs no lock, preempts L — so H effectively waits for M. Unbounded inversion famously reset the Mars Pathfinder lander in 1997.

Priority inheritance and priority ceiling Priority inheritance: while L holds a lock H wants, L temporarily runs at H's priority, so M cannot preempt it (PTHREAD_PRIO_INHERIT, RTOS mutexes).

Priority ceiling: a lock has a ceiling priority equal to its highest user; any holder runs at the ceiling (PTHREAD_PRIO_PROTECT, Ada's ceiling locking). Also prevents some deadlocks.

When a lock is contended, threads queue behind it; even after the original cause disappears, the queue persists because each thread re-requests the lock while others wait (lock convoys). Throughput collapses to one-at-a-time.

Diagnosing blocked threads Take a snapshot of every thread's stack: jstack/jcmd Thread.print (Java reports deadlocks automatically), dotnet-stack, gdb -p PID → thread apply all bt, py-spy dump, Go SIGQUIT or /debug/pprof/goroutine?debug=2. Look for threads blocked in lock acquisition and match them to holders.

Designing lock hierarchies Assign each lock a level; a thread may acquire a lock only at a level lower (or higher, consistently) than any it already holds. Enforce in debug builds (lock-order checkers, the Linux kernel's lockdep, Abseil's deadlock detection).

Safe multi-lock acquisition std::scoped_lock with several mutexes uses a deadlock-avoidance algorithm (lock one, try the others, back off and retry in a different order) so that *this acquisition* cannot deadlock with another scoped_lock of the same mutexes in any order. It does not make every possible lock interaction in the whole program deadlock-proof — a thread that already holds a and then calls update_both can still deadlock.

Deadlock review checklist See Best Practices below.

std::mutex a;
std::mutex b;

void update_both() {
    std::scoped_lock lock(a, b);
    // Safely hold both mutexes for this scope.
}

Why It Matters in Real Systems

Deadlocks freeze services until restarted; livelocks burn CPU while doing nothing; starvation produces requests that never finish; priority inversion breaks real-time deadlines. Databases ship deadlock detectors because applications constantly produce lock-order inversions.

Key Terms

Cyclic waiting; no thread in the cycle can proceed Mutual exclusion, hold-and-wait, no preemption, circular wait Edges from waiting threads to holders

Two paths acquire the same locks in opposite orders Activity without progress One thread never gets what it needs

A releasing thread re-acquires ahead of waiters High priority effectively waits for lower priority Priority inheritance / ceiling Protocols that bound inversion

Syntax and API Overview

This is a concurrency concept, not a language construct; the APIs that help are multi-lock acquisition (std::scoped_lock, std::lock), timed locks, and runtime detectors (ThreadMXBean.findDeadlockedThreads).

Complete Code Example

A real lock-order inversion (G++ 11.2). Each thread takes its first lock, sleeps 50 ms so the other can take its first, then requests the second. The run is given a 3-second deadline and then killed — it never finishes on its own:

The fix — acquire both with std::scoped_lock (or always in the same order):

The order of "transfer done" and "report done" depends on which thread acquires the pair first; "both finished" always comes last because of the joins.

The JVM detects monitor deadlocks for you (Temurin JDK 21):

#include <chrono>
#include <iostream>
#include <mutex>
#include <thread>

std::mutex accounts_lock, audit_lock;

void transfer() {                                   // path 1: accounts -> audit
    std::lock_guard a(accounts_lock);
    std::this_thread::sleep_for(std::chrono::milliseconds(50));
    std::lock_guard b(audit_lock);
    std::cout << "transfer done\n";
}

void report() {                                     // path 2: audit -> accounts (inverted)
    std::lock_guard b(audit_lock);
    std::this_thread::sleep_for(std::chrono::milliseconds(50));
    std::lock_guard a(accounts_lock);
    std::cout << "report done\n";
}

int main() {
    std::cout << "starting transfer and report" << std::endl;
    std::thread t1(transfer), t2(report);
    t1.join();
    t2.join();
    std::cout << "never printed\n";
}

starting transfer and report
bash: line 1:    55 Killed                  timeout -s KILL 3 ./m05_deadlock
[no progress after 3 s — the process was killed]

#include <chrono>
#include <iostream>
#include <mutex>
#include <thread>

std::mutex accounts_lock, audit_lock;

void transfer() {
    std::scoped_lock both(accounts_lock, audit_lock);   // deadlock-avoiding acquisition
    std::this_thread::sleep_for(std::chrono::milliseconds(50));
    std::cout << "transfer done\n";
}

void report() {
    std::scoped_lock both(audit_lock, accounts_lock);   // different argument order is fine here
    std::this_thread::sleep_for(std::chrono::milliseconds(50));
    std::cout << "report done\n";
}

int main() {
    std::thread t1(transfer), t2(report);
    t1.join();
    t2.join();
    std::cout << "both finished\n";
}

report done
transfer done
both finished

import java.lang.management.ManagementFactory;
import java.lang.management.ThreadInfo;
import java.lang.management.ThreadMXBean;
import java.util.concurrent.CountDownLatch;

public class DeadlockDetector {
    static final Object A = new Object(), B = new Object();

    public static void main(String[] args) throws Exception {
        CountDownLatch bothHoldOne = new CountDownLatch(2);
        Thread t1 = new Thread(() -> { synchronized (A) { bothHoldOne.countDown(); await(bothHoldOne); synchronized (B) { } } }, "worker-1");
        Thread t2 = new Thread(() -> { synchronized (B) { bothHoldOne.countDown(); await(bothHoldOne); synchronized (A) { } } }, "worker-2");
        t1.setDaemon(true);
        t2.setDaemon(true);
        t1.start();
        t2.start();
        Thread.sleep(200);                                   // let them block

        ThreadMXBean mx = ManagementFactory.getThreadMXBean();
        long[] ids = mx.findDeadlockedThreads();
        System.out.println("deadlocked threads found: " + (ids == null ? 0 : ids.length));
        for (ThreadInfo info : mx.getThreadInfo(ids)) {
            System.out.println("  " + info.getThreadName() + " is " + info.getThreadState()

…

deadlocked threads found: 2
  worker-1 is BLOCKED waiting for a lock held by worker-2
  worker-2 is BLOCKED waiting for a lock held by worker-1

Line-by-Line Explanation

In the deadlock program transfer locks accounts→audit, report locks audit→accounts; the 50 ms sleeps make both first acquisitions happen before either second one, so the cycle forms every time.

std::endl flushes the first line before the threads start, so it appears even though the process is later killed.

std::scoped_lock both(x, y) acquires both mutexes as one operation using a deadlock-avoidance algorithm.

In Java, a CountDownLatch makes the two threads hold one monitor each before requesting the other — a deterministic deadlock. findDeadlockedThreads walks the JVM's monitor ownership graph and reports the cycle; daemon threads let the JVM exit afterwards.

Output

Shown under each program. The Java output's line order for the two workers may vary (it follows the order of the ids array).

Interleaving or State Trace

requests audit → blocks requests accounts → blocks t1 → t2, t2 → t1: cycle

Correctness and Safety Analysis

All four Coffman conditions hold in the broken program. scoped_lock removes *hold-and-wait*: neither thread ends up holding one mutex while blocked on the other. A global order (always accounts before audit) would remove *circular wait*.

Detecting cycles in a wait-for graph, and simulating livelock and priority inversion deterministically (CPython 3.13.1; these are simulations, not real threads):

Without inheritance, H waits for M's entire six-tick burst although M never touches the lock; with inheritance, L finishes its critical section at high priority and H runs as soon as the lock is free.

def find_cycle(waits_for):
    """waits_for: thread -> thread it waits on. Returns a cycle or None (DFS with colouring)."""
    state, stack = {}, []
    def visit(t):
        state[t] = "active"; stack.append(t)
        nxt = waits_for.get(t)
        if nxt is not None:
            if state.get(nxt) == "active":
                return stack[stack.index(nxt):] + [nxt]
            if nxt not in state:
                found = visit(nxt)
                if found:
                    return found
        state[t] = "done"; stack.pop()
        return None
    for t in waits_for:
        if t not in state:
            c = visit(t)
            if c:
                return c
    return None

print("wait-for T1->T2->T3->T1:", " -> ".join(find_cycle({"T1": "T2", "T2": "T3", "T3": "T1"})))
print("wait-for T1->T2->T3    :", find_cycle({"T1": "T2", "T2": "T3"}))

# livelock: two polite threads each grab their first lock, see the other one, release, retry - in lockstep
def polite(jitter):
    import random
    rnd = random.Random(7)
    for attempt in range(1, 21):
        a_backoff = rnd.randint(0, 2) if jitter else 1
        b_backoff = rnd.randint(0, 2) if jitter else 1
        if a_backoff !
…

wait-for T1->T2->T3->T1: T1 -> T2 -> T3 -> T1
wait-for T1->T2->T3    : None
livelock, fixed back-off : no progress after 20 attempts (livelock)
livelock, random back-off: made progress on attempt 1
priority inversion  : LLMMMMMMLHH  (H first runs at tick 9)
priority inheritance: LLLHHMMMMMM  (H first runs at tick 3)

Common Mistakes and Misconceptions

"scoped_lock makes my program deadlock-free." Only that acquisition.

Calling callbacks, logging frameworks or virtual methods while holding a lock (hidden nested locking).

Using timeouts as the *only* defence — the system then fails intermittently instead of hanging.

Fixing livelock by retrying immediately.

Assuming the OS scheduler prevents priority inversion (it does only with inheritance-enabled mutexes).

Failure Modes and Debugging Steps

Capture all thread stacks while hung (thread dump / debugger).

For each blocked thread, find the lock it waits for and the thread holding it; draw the wait-for graph.

Find the cycle; identify the two code paths and their lock orders.

Fix by ordering, combined acquisition, or restructuring so that one path never holds a lock while acquiring another.

Performance and Scalability Implications

Fair locks and strict ordering can reduce throughput; deadlock detection costs graph traversals (databases run it periodically or on lock-wait timeouts); lock convoys collapse throughput — shorter critical sections and fewer shared locks prevent them.

Security Considerations

A deadlock in a request path is a denial-of-service vulnerability if an attacker can trigger the interleaving. Timeouts and watchdogs limit the impact; review lock ordering in security-sensitive code especially carefully.

Platform and Runtime Caveats

Java detects deadlocks among synchronized monitors and ownable synchronizers (ReentrantLock) but not, for example, among threads waiting on condition variables or I/O.

POSIX priority inheritance requires pthread_mutexattr_setprotocol(PTHREAD_PRIO_INHERIT) and real-time scheduling to matter; most desktop mutexes do not inherit priority.

Go's runtime reports "all goroutines are asleep - deadlock!" only when *every* goroutine is blocked.

Real-World Applications

Database deadlock detection and victim rollback; kernel lock hierarchies (lockdep); RTOS mutexes with priority inheritance; Java application servers' automatic deadlock reports in thread dumps.

Best Practices

[ ] Document the global lock order; enforce it with a checker in debug builds.

[ ] Acquire multiple locks with std::scoped_lock/std::lock or in the documented order.

[ ] Never call unknown code (callbacks, I/O) while holding a lock.

[ ] Use timeouts plus randomised back-off for retries.

[ ] Use priority-inheriting mutexes in real-time systems.

[ ] Capture thread dumps automatically when a watchdog fires.

Exercises

E1 · Beginner. Which Coffman condition does "always acquire locks in alphabetical order" break?

Answer: Circular wait: a cycle would require some thread to request a lock that sorts before one it already holds.

E2 · Intermediate. Five philosophers each pick up their left fork then their right. Explain the deadlock and give two fixes.

Answer: If all pick up their left fork simultaneously, each waits for a right fork held by a neighbour — a cycle. Fixes: number the forks and always pick up the lower-numbered first (one philosopher picks right-then-left), or allow at most four philosophers at the table (a semaphore of 4).

E3 · Advanced challenge. Why can try-lock with immediate retry livelock, and how does randomised exponential back-off fix it?

Answer: Symmetric threads that fail, release and retry at identical intervals collide again on every attempt. Random back-off makes their timings diverge so one completes its acquisition; growing the back-off window reduces collisions further under heavy contention.

Quiz

? Which condition is NOT one of Coffman's deadlock conditions?
- Mutual exclusion :: It is one of the four.
- Hold and wait :: It is one of the four.
+ Preemptive scheduling :: The condition is "no preemption" of resources, not CPU scheduling.
- Circular wait :: It is one of the four.

? What does priority inheritance do?
+ Temporarily raises a lock holder's priority to that of the highest-priority waiter. :: So medium-priority work cannot preempt it.
- Lets high-priority threads steal locks. :: Locks are not preempted.
- Lowers the priority of waiting threads. :: It raises the holder's.
- Makes locks FIFO-fair. :: Fairness is a separate property.

? Which reliably prevent the transfer/report deadlock? (select all that apply)
+ Acquiring both mutexes with std::scoped_lock in both functions :: Deadlock-avoiding combined acquisition.
+ Always locking accounts before audit everywhere :: Removes circular wait.
- Adding a longer sleep between the two acquisitions :: Makes the deadlock even more likely.
- Making the mutexes recursive :: Different threads still wait for each other.

Summary

Deadlock needs mutual exclusion, hold-and-wait, no preemption and circular wait; break one — usually circular wait via lock ordering, or hold-and-wait via combined acquisition. Detection with wait-for graphs and recovery by aborting a victim is the database approach. Livelock, starvation, convoys and priority inversion are the other progress failures; randomised back-off, fairness and priority inheritance address them.