Search Knowledge

© 2026 LIBREUNI PROJECT

Operating Systems Engineering/Concurrency and liveness
Page 11 of 29

Deadlock, Liveness, and Priority Inversion

Wait-for graphs, lock ordering, prevention and recovery, starvation, livelock, and priority-aware synchronization.

Lesson briefConcurrency and liveness · 5 h 30 min · 4 outcomes

Required knowledge

  • Locks, atomics, and memory ordering
  • Condition variables and semaphores
  • CPU scheduling metrics and priorities

Learning outcomes

  • Construct resource-allocation and wait-for graphs and state when a cycle proves deadlock.
  • Distinguish deadlock, starvation, livelock, and priority inversion from a finite execution trace.
  • Prove a lock hierarchy excludes circular wait and identify operations that violate the hierarchy through callbacks or re-entry.
  • Evaluate prevention, avoidance, detection/recovery, timeout, priority inheritance, and priority ceiling under explicit assumptions.

Assessment target

Given an unseen multi-resource trace, derive the wait-for relation, classify the liveness failure, prove or refute a proposed prevention rule, and select a recovery or priority protocol with bounded claims.

Scope boundary

  • Formal temporal logic, distributed deadlock detection, and complete real-time schedulability analysis require dedicated courses.
  • The lesson does not claim that one priority protocol makes arbitrary blocking code deterministic.

Thread A holds the process-table lock and requests the filesystem-cache lock. Thread B holds the filesystem-cache lock and calls a helper that requests the process-table lock. Both locks work exactly as designed: each excludes the other thread forever.

Safety mechanisms can destroy progress when their acquisition dependencies form a cycle. Liveness analysis asks not only whether state remains valid, but whether required operations retain a path to completion.

Classify the stalled system before repairing it

Definition 3.4.1Four distinct progress failures
  • Deadlock: a nonempty set of participants is permanently blocked because each waits for an event that only another participant in the set can cause.
  • Starvation: one participant can remain unable to make progress while other participants continue completing work.
  • Livelock: participants continue taking steps and changing protocol state, but the required operation never completes.
  • Priority inversion: a higher-priority task is blocked, directly or transitively, by work owned by a lower-priority task; the inversion is unbounded when unrelated intermediate-priority work can extend that delay without a protocol bound.

These categories overlap in symptoms, not definitions. “The service hung” supplies no diagnosis.

TraceClassificationDecisive evidence
A waits for L2 held by B; B waits for L1 held by Adeadlockclosed wait-for cycle; neither owner can release
reader-preferred lock admits a stream of readers while one writer waitspossible writer starvationsystem completes reads; one enabled class is postponed indefinitely
two polite workers repeatedly release and retry in synchronylivelockboth run and mutate state; neither commits
high-priority H waits for a mutex held by low-priority L while medium M preempts Lpriority inversionM delays the owner that could unblock H

Prediction — answer before expanding. A low-priority thread is preempted for 2 ms while holding a mutex needed by a high-priority thread. Is that fact alone deadlock, starvation, or priority inversion? Predict the classification and required evidence before revealing the answer.

AnswerExpand

It is priority inversion during that interval. A finite delay does not establish deadlock or starvation. To claim an unbounded inversion, show that unrelated work can keep the owner from running without a protocol bound. To claim starvation, show an allowed infinite execution in which the waiting thread never completes while others do.

Classifying progress failures

0 / 4 answered

Evaluate each statement regarding concurrency, deadlocks, and liveness failures:

Classify each option as correct or incorrect, or leave uncertain options unanswered (“I don't know”) and verify at any time.

1
Deadlock can be eliminated by adding identical fixed sleep intervals before retrying without reordering locks.
2
Livelock occurs when threads repeatedly change state and execute instructions without completing their operation.
3
A cycle in a resource-allocation graph with multiple resource units always guarantees an active deadlock.
4
Priority inheritance temporarily raises the scheduling priority of a lock holder to match its highest waiter.

Resource graphs expose ownership and demand

A resource-allocation graph has thread nodes and resource nodes. An edge T→RT \rightarrow R means T requests R; an edge R→TR \rightarrow T means an instance of R is assigned to T. For single-instance reusable resources, collapse each request through the current owner into a wait-for edge Ti→TjT_i \rightarrow T_j

Code
left to right direction
rectangle "thread A" as A
rectangle "thread B" as B
hexagon "process-table lock Lp" as LP
hexagon "filesystem-cache lock Lf" as LF
LP --> A : assigned
A --> LF : requests
LF --> B : assigned
B --> LP : requests
note bottom of A
wait-for projection:
A → B → A
end note
thread Athread Bprocess-table lock Lpfilesystem-cache lock Lfwait-for projection:A → B → Aassignedrequestsassignedrequests

In a wait-for graph where every resource has one instance and blocked requests cannot be withdrawn, a directed cycle is necessary and sufficient for deadlock among the cycle’s threads. With multiple interchangeable instances, a cycle is necessary but may not be sufficient: a thread outside the cycle can release another instance and satisfy a request. State the resource model before interpreting a cycle.

Worked trace: multi-instance wait-for graph. A holds one of two database connections and waits for a log slot. B holds the log slot and waits for a database connection. The graph contains A→B and B→A if edges are projected only through the currently observed connection owner. Yet a third thread C can return the second connection, allowing B to proceed. The projected cycle did not prove deadlock because the resource had another instance and another release path.

The four classical conditions describe a resource regime in which deadlock can arise:

  1. mutual exclusion: at least one resource cannot be shared simultaneously;
  2. hold and wait: a participant holds resources while requesting more;
  3. no forced preemption: resources are released by their owners rather than safely taken away; and
  4. circular wait: a closed chain of participants each waits for a resource held by the next.

All four are necessary for deadlock in that model. Their availability as system policies is not proof that a particular execution is deadlocked; construct the current ownership and wait relation.

A lock order is a proof, not a comment

Assign every lock a rank in a strict total order and require a thread to acquire locks only in increasing rank. Suppose a deadlock cycle exists:

T1→L2→T2→⋯→Tk→L1→T1.T_1 \rightarrow L_2 \rightarrow T_2 \rightarrow \cdots \rightarrow T_k \rightarrow L_1 \rightarrow T_1.

Each thread holds one lock and requests the next, so the order rule implies

rank(L1)<rank(L2)<⋯<rank(Lk)<rank(L1),rank(L_1) < rank(L_2) < \cdots < rank(L_k) < rank(L_1),

which is impossible for a strict order. The policy eliminates circular wait.

Code
start
:need locks for process P and inode I;
:map each lock to documented rank;
if (current maximum rank < next rank?) then (yes)
:acquire next lock;
:revalidate objects protected before acquisition;
else (no)
:release, reorder, or redesign operation;
:never call through an unknown callback while holding the lock;
endif
:restore every protected invariant;
:release locks;
stop
need locks for process P andinode Imap each lock to documentedrankcurrent maximum rank < nextrank?yesnoacquire next lockrevalidate objects protectedbefore acquisitionrelease, reorder, or redesignoperationnever call through an unknowncallback while holding the lockrestore every protected invariantrelease locks

Worked transfer operation. To move a page from source cache bucket 9 to destination bucket 3, the semantic order “source then destination” conflicts with numeric rank. Acquire bucket 3 then bucket 9, regardless of transfer direction. Because the source was inspected before both locks were held, revalidate that the page remains in bucket 9 and that the destination does not already contain it. Lock order prevents deadlock; revalidation preserves correctness.

Counterexample: hidden acquisition. Code holds rank-20 lock L and invokes a callback supplied by another subsystem. The callback acquires rank-10 lock K. The local source file shows no descending acquisition, but the dynamic call graph violates the proof. Solutions include forbidding callbacks under L, splitting prepare/commit phases, passing immutable data, or making the callback’s lock contract explicit and mechanically checked.

Application. A recursive tree traversal acquires each child lock while retaining its parent lock. Does “parent before child” define a global order when another operation can rotate the tree?

AnalysisExpand

Only if parent/child relationships remain stable for the entire acquisition and no operation needs child-before-parent. Rotation changes topology, so a relation derived from mutable structure may cease to be acyclic or consistently observed. Stable object IDs, address/rank order, lock coupling with revalidation, or a coarser tree lock can supply a defensible order. The answer must include object lifetime: comparing addresses is unsafe if objects can be freed and reused while a contender waits.

Prevention, avoidance, and recovery solve different contracts

StrategyRequired knowledge or powerUseful caseBoundary
prevent hold-and-waitrequest all resources together or release before requesting moresmall known resource setlowers concurrency; all-or-nothing acquisition may be impossible
prevent circular waitstable global rankkernel lock hierarchieshidden callbacks and dynamic resources complicate ranking
avoidancedeclared maximum future demand; grant only if state remains safecontrolled batch/resource systemsinaccurate maximum claims make policy unusable or unsafe
detection and recoveryobservable allocation state plus a victim/rollback mechanismtransactions, killable jobskernel locks and irreversible I/O may not be safely revoked
timeoutclock and abort pathbounds one caller’s wait when abort is validdoes not prove the cycle is gone; synchronized retries can livelock

Avoidance asks whether there exists a safe completion sequence after a proposed grant. A state can be safe even when not every thread could complete next; at least one sequence lets all finish within declared maximum demands. Banker’s-style reasoning is meaningful only when maximum claims and resource counts are trustworthy.

Worked safe-state check. Two processes share three identical buffers. A holds one and may need at most one more; B holds one and may need at most two more. One buffer is free. Grant it to A: A can finish and release two, then B can obtain its remaining demand. Grant it to B: B would hold two and need one, A would hold one and need one, and none would be free; under the declared maxima, no completion sequence remains. The second grant is unsafe, though no one is deadlocked at the instant before either makes its next request.

Detection does not imply recovery. Killing a process that holds a user-space mutex may be acceptable if robust-mutex recovery marks protected state inconsistent. Killing a kernel thread halfway through device programming may leave hardware and memory in an unrepairable protocol state. Define the rollback boundary before choosing “detect and abort.”

Backoff can replace deadlock with livelock

Two transfer threads each trylock one account, fail on the second, release, wait exactly 1 ms, and retry. Their lockstep behavior can continue forever. There is no blocked cycle because each releases; there is no progress because both repeat the same collision.

Starvation requires a fairness argument. A test-and-set spin lock can repeatedly admit a nearby core while a remote core loses cache-line races. A reader-preferred reader/writer lock can admit an endless stream of readers ahead of a writer. FIFO admission bounds overtaking but can create convoying when the head waiter is descheduled. Liveness and throughput objectives can conflict.

Transfer. Define a test that distinguishes deadlock from livelock without declaring every slow run a failure.

Test designExpand

Instrument protocol state and completed operations. In a controlled schedule, deadlock reaches a stable wait-for cycle with no enabled participant that can release a required resource. Livelock continues producing state transitions or retries while a completion counter remains unchanged. Use a finite watchdog only to trigger capture; classify from the captured wait-for and transition evidence. A wall-clock timeout alone cannot distinguish load, preemption, deadlock, and livelock.

Priority inversion is a dependency-scheduling problem

Let H have high priority, M medium priority, and L low priority:

  1. L acquires mutex R.
  2. H becomes runnable, preempts L, then blocks on R.
  3. M becomes runnable. Because M outranks L, M runs.
  4. H is effectively delayed by M even though H and M share no lock.
Code
hide footbox
participant "high H" as H
participant "medium M" as M
participant "low L" as L
participant "mutex R" as R
L -> R : acquire
H -> R : request; block behind L
M -> M : runs while L cannot release R
R --> H : wait extends with M&#039;s execution
note over H,L
Priority inheritance temporarily raises L to H&#039;s priority,
so L can finish the critical section and unblock H.
end note
L -> R : release
R --> H : acquire
high Hmedium Mlow Lmutex Rhigh Hmedium Mlow Lmutex Racquirerequest; block behind Lruns while L cannotrelease Rwait extends with M'sexecutionPriority inheritance temporarilyraises L to H's priority,so L can finish the criticalsection and unblock H.releaseacquire

Under priority inheritance, L temporarily inherits the highest priority of a waiter on R. If L itself blocks on a mutex owned by another task, the boost may propagate along that dependency chain. The boost is removed when the relevant dependency ends. This bounds interference from unrelated medium-priority work under the protocol’s scheduler assumptions; it does not shorten L’s critical section or cure a deadlock cycle.

A priority-ceiling protocol associates a ceiling with each resource based on the highest-priority task that may lock it. Variants can prevent certain deadlocks and bound a task’s blocking by restricting acquisitions according to active ceilings. Those guarantees assume fixed-priority scheduling, declared resource use, bounded critical sections, and the specified protocol. They are not inherited by an arbitrary mutex with a “priority” field.

Worked nested inversion. H waits for R1 held by L. L waits for R2 held by X. Boosting only L does not help because X remains preemptible by M. A transitive PI implementation propagates H’s effective priority through L to X; X releases R2, L resumes and releases R1, then H proceeds. The chain also shows why PI implementation needs cycle detection and careful priority restoration.

Section Exercises

Deep Practice

Solve these problems to test and consolidate your understanding. Complete worked solutions and diagnostic hints are available for each problem.

Exercise 3.4.1: Evaluating the Four Coffman Necessary Conditions

Verificationapplication

State the four Coffman conditions necessary for a system deadlock to arise. For each condition, describe how a concrete operating system mechanism directly invalidates that condition.

HintExpand

Recall mutual exclusion, hold and wait, no preemption, and circular wait.

Worked solutionExpand

The four necessary conditions established by Coffman, Elphick, and Shoshani (1971) are:

  1. Mutual exclusion: at least one resource must be held in a non-shareable mode. Invalidation: Use lock-free data structures (e.g., atomic compare-and-swap) or read-only shared access where multiple threads proceed concurrently without mutual exclusion.
  2. Hold and wait: a thread currently holding at least one resource may request additional resources. Invalidation: Require a thread to request all needed resources simultaneously in a single atomic operation, or release all held resources before requesting new ones.
  3. No preemption: resources cannot be forcibly confiscated from a thread; they can only be released voluntarily by the holding thread. Invalidation: Implement preemption protocols where the OS kernel or runtime revokes a resource (or aborts and restarts a transaction) if an additional request cannot be immediately satisfied.
  4. Circular wait: a closed chain of threads {T0,T1,…,Tk−1}\{T_0, T_1, \dots, T_{k-1}\} exists such that TiT_i waits for a resource held by T(i+1) mod kT_{(i+1) \bmod k} Invalidation: Impose a strict global partial or total ordering on all resource classes, mandating that resources are acquired only in increasing order.

Breaking any single condition renders deadlock mathematically impossible.

Exercise 3.4.2: Cycle Detection in Multi-Unit Resource Graphs

Constructionapplication

Construct a concrete resource-allocation graph with two thread nodes T1,T2T_1, T_2 and two resource nodes R1,R2R_1, R_2 where R1R_1 has 2 available units and R2R_2 has 1 available unit. Show that a directed cycle exists in the graph, yet the system is not deadlocked.

HintExpand

Give R1 two units held by different threads or an unallocated unit that allows one thread to finish.

Worked solutionExpand

Let resource R1R_1 possess 2 units and resource R2R_2 possess 1 unit. Introduce a third thread T3T_3 to illustrate the distinction between single-unit and multi-unit resource graphs:

  • R1R_1 allocation edges: R1→T1R_1 \rightarrow T_1 and R1→T3R_1 \rightarrow T_3 (both units allocated).
  • R2R_2 allocation edge: R2→T2R_2 \rightarrow T_2 (its single unit allocated).
  • Request edges: T1→R2T_1 \rightarrow R_2 T1T_1 requests R2R_2 and T2→R1T_2 \rightarrow R_1 T2T_2 requests R1R_1

Notice the directed cycle: T1→R2→T2→R1→T1T_1 \rightarrow R_2 \rightarrow T_2 \rightarrow R_1 \rightarrow T_1

However, thread T3T_3 holds a unit of R1R_1 and has no outstanding requests. Thread T3T_3 executes to completion and releases its unit of R1R_1 The newly freed unit of R1R_1 is allocated to T2T_2 satisfying T2T_2‘s request. T2T_2 completes and releases both its unit of R1R_1 and R2R_2 Finally, R2R_2 is allocated to T1T_1 allowing T1T_1 to complete.

Hence, while a cycle is necessary and sufficient for deadlock in single-unit resource graphs, in multi-unit graphs a cycle is merely necessary, not sufficient. A knot (or absence of reducible sinks) is required for deadlock in general graphs.

Exercise 3.4.3: Proving Deadlock Freedom via Global Lock Hierarchies

Proofsynthesis

Let L={L1,L2,…,Lm}\mathcal{L} = \{L_1, L_2, \dots, L_m\} be a finite set of mutex locks with a strict total order ≺\prec defined over them. Suppose every thread acquires locks strictly in ascending order: if a thread holds lock LiL_i and requests lock LjL_j then Li≺LjL_i \prec L_j Prove that circular wait cannot occur.

HintExpand

Assume a cycle of waiters exists and examine the ordering of the held locks.

Worked solutionExpand

Assume for contradiction that a circular wait exists among k≥2k \ge 2 threads {T0,T1,…,Tk−1}\{T_0, T_1, \dots, T_{k-1}\}

For each thread TiT_i let Hi⊆LH_i \subseteq \mathcal{L} be the set of locks currently held by TiT_i and let max⁡(Hi)\max(H_i) denote the maximum lock held by TiT_i with respect to ≺\prec Suppose thread TiT_i is blocked requesting lock RiR_i which is held by thread T(i+1) mod kT_{(i+1) \bmod k}

By the strict ordering protocol, because TiT_i requests RiR_i while holding max⁡(Hi)\max(H_i) we must have:

max⁡(Hi)≺Ri.\max(H_i) \prec R_i.

Furthermore, since Ri∈H(i+1) mod kR_i \in H_{(i+1) \bmod k} by definition of the maximum element:

Ri⪯max⁡(H(i+1) mod k).R_i \preceq \max(H_{(i+1) \bmod k}).

Combining these inequalities yields:

max⁡(Hi)≺max⁡(H(i+1) mod k)for all i∈{0,1,…,k−1}.\max(H_i) \prec \max(H_{(i+1) \bmod k}) \quad \text{for all } i \in \{0, 1, \dots, k-1\}.

Chaining this strict inequality along the entire cycle from T0T_0 to Tk=T0T_k = T_0

max⁡(H0)≺max⁡(H1)≺max⁡(H2)≺⋯≺max⁡(Hk−1)≺max⁡(H0).\max(H_0) \prec \max(H_1) \prec \max(H_2) \prec \dots \prec \max(H_{k-1}) \prec \max(H_0).

By transitivity of the strict total order ≺\prec this implies max⁡(H0)≺max⁡(H0)\max(H_0) \prec \max(H_0) which violates the irreflexivity of strict orders.

Thus, no circular wait can form, proving that the system is guaranteed deadlock-free.

Exercise 3.4.4: Deterministic Retry Traps versus Randomized Exponential Backoff

Descriptionapplication

Explain why two threads using non-blocking try_lock() with identical, deterministic sleep intervals can enter livelock. Explain how randomized exponential backoff breaks the synchronization lockstep.

HintExpand

Contrast deterministic phase alignment with probabilistic symmetry breaking.

Worked solutionExpand

When two threads attempt to acquire two locks L1L_1 and L2L_2 using try_lock():

  1. Thread AA acquires L1L_1 and Thread BB acquires L2L_2
  2. Both attempt to try_lock() the second lock and fail.
  3. Both release their held lock to avoid deadlock and immediately execute a fixed deterministic sleep (e.g., sleep(1ms)).
  4. Because both threads wake up at identical offsets, they repeat the acquisition in perfect lockstep: Thread AA gets L1L_1 Thread BB gets L2L_2 both fail on the second lock, both release, and both sleep again.

This is livelock: CPU cycles and state transitions occur continuously, but the aggregate operation makes zero forward progress.

Randomized exponential backoff breaks this deterministic symmetry by selecting a sleep duration uniformly at random from a dynamically doubling window: tsleep∼U[0,2k⋅τ]t_{\text{sleep}} \sim U[0, 2^k \cdot \tau] on the kk-th failure. With high probability, one thread draws a significantly shorter delay, awakens earlier, and acquires both locks uncontested before the other thread wakes up.

Exercise 3.4.5: Priority Inheritance Protocol Bounds on Priority Inversion Chains

Formalisationtransfer

Consider three threads with priorities π(H)>π(M)>π(L)\pi(H) > \pi(M) > \pi(L) Thread LL acquires mutex RR after which thread HH arrives and blocks requesting RR Thread MM becomes runnable and does not need RR

  1. Formalize the duration of priority inversion experienced by HH without priority inheritance.
  2. Formalize the maximum blocking time under the basic priority inheritance protocol.
HintExpand

Without inheritance, M can preempt L indefinitely. With inheritance, L runs at effective priority pi(H).

Worked solutionExpand
  1. Without priority inheritance: Thread HH is blocked awaiting mutex RR held by LL However, thread MM has higher priority than LL π(M)>π(L)\pi(M) > \pi(L) and is ready to run. The scheduler preempts LL to execute MM If a set of medium-priority threads M\mathcal{M} arrives, thread LL cannot execute until all threads in M\mathcal{M} complete or block. The blocking time experienced by HH is:

    Tblock(H)=tcrit(L)+∑Mj∈Mtexec(Mj),T_{\text{block}}(H) = t_{\text{crit}}(L) + \sum_{M_j \in \mathcal{M}} t_{\text{exec}}(M_j),

    where ∑texec(Mj)\sum t_{\text{exec}}(M_j) can be unbounded if new medium-priority tasks continue arriving. This is unbounded priority inversion (the classic Mars Pathfinder hazard).

  2. Under basic priority inheritance protocol (PIP): When HH blocks on mutex RR held by LL the kernel elevates LL‘s effective priority:

    πeff(L)=max⁡(π(L),π(H))=π(H).\pi_{\text{eff}}(L) = \max(\pi(L), \pi(H)) = \pi(H).

    Now πeff(L)>π(M)\pi_{\text{eff}}(L) > \pi(M) for all M∈MM \in \mathcal{M} The scheduler cannot preempt LL with medium-priority work. LL executes its critical section without interference from M\mathcal{M} releases RR restores its original priority π(L)\pi(L) and immediately unblocks HH The maximum blocking duration for HH is strictly bounded by the execution time of LL‘s critical section:

    Tblock(H)≤tcrit(L).T_{\text{block}}(H) \le t_{\text{crit}}(L).

References & Further Reading