Deadlock, Livelock, Starvation, Priority Inversion

This chapter covers the four classic concurrency pathologies: deadlock, livelock, starvation, and priority inversion.

Why This Matters

These are the failure modes that make concurrent code "hang," "spin forever," "never get a turn," or "block a high-priority task." Recognizing and preventing them is essential for building reliable concurrent systems.

Prerequisites

• c.conc.3 — mutexes and synchronization.

Core Concept

Deadlock

Two or more threads each hold a lock and wait for a lock held by another, forming a cycle. All are permanently stuck.

Thread A: lock X, then lock Y
Thread B: lock Y, then lock X

Livelock

Threads repeatedly change state in response to each other but make no progress (they are "busy" but stuck), often in a spin/retry loop.

Starvation

A thread never gets the resources it needs because others always win (e.g., a readers-preferred rwlock starving writers).

Priority inversion

A low-priority thread holds a lock needed by a high-priority thread, and a medium-priority thread preempts the low-priority holder, so the high-priority thread waits behind the medium one. This famously caused the Mars Pathfinder bug.

Examples

Deadlock

mtx_lock(&a);
mtx_lock(&b);   /* B */
/* ... */
mtx_unlock(&b);
mtx_unlock(&a);

/* other thread */
mtx_lock(&b);
mtx_lock(&a);   /* A */
/* ... */

If both threads acquire their first lock, each blocks forever on the second.

Priority inversion (embedded/RTOS)

A low-priority task holds a mutex; a high-priority task blocks on it; a medium-priority task (which does not need the mutex) runs, delaying the low task and therefore the high task.

How It Works

Deadlock is a cyclic wait graph. Livelock is a cycle of reactions. Starvation is a fairness failure. Priority inversion is an interaction between locking and scheduling priorities.

Variations

Deadlock prevention strategies

• Lock ordering: always acquire locks in a fixed order.
• Trylock and back off: use trylock to avoid blocking while holding a

lock.

• Lock-free design: avoid locks entirely (c.conc.8).

Priority inheritance

An RTOS can temporarily raise the low-priority holder's priority to that of the high-priority waiter, breaking priority inversion.

Common Mistakes

• Acquiring multiple locks in inconsistent order.
• Holding a lock while waiting for another (or doing slow I/O).
• Ignoring fairness (causing starvation).

Undefined Behavior

• None inherent (these are liveness issues, not UB), but a data race in the

shared state is UB.

Portability

• The concepts are universal. Priority inversion is most visible in RTOS

scheduling (c.rtos.priority-inversion).

Under the Hood

The OS scheduler and lock implementation determine the exact behavior. Tools like helgrind/TSan can detect deadlocks/races.

Practical Usage

• Enforce a global lock order.
• Keep critical sections short and never do blocking I/O inside.
• Use trylock/backoff and timeouts.
• In RTOS, use priority-inheritance mutexes.

Exercises

1. Write a two-thread deadlock and observe the hang. 2. Fix it with consistent lock ordering. 3. Write a livelock (two threads retrying) and fix it with backoff. 4. Explain priority inversion and priority inheritance.

Deep Challenge

Implement a deadlock detector that tracks lock acquisitions and detects cycles in the wait-for graph. Explain its overhead and limitations.

Related Concepts

• c.conc.3 — mutexes.
• c.conc.8 — lock-free.
• c.rtos.priority-inversion — RTOS priority inversion.

References

• "Operating Systems: Three Easy Pieces" (locks/condition variables), RTOS

priority-inheritance literature.

Verification

• Deadlock/livelock/starvation/priority-inversion definitions. VERIFIED
• No example was executed during generation unless noted. `Execution not

verified.`

Progress

• [ ] Read
• [ ] Understand
• [ ] Complete examples
• [ ] Complete exercises
• [ ] Complete deep challenge

Concept checkboxes

• [ ] Deadlock
• [ ] Livelock
• [ ] Starvation
• [ ] Priority inversion

Mastery levels