6. Deadlocks, Livelocks, and Resource Contention

Introduction and Context

An operating system coordinates processes that execute concurrently while sharing processors, memory, files, devices, locks, communication channels, and other resources. Concurrency improves utilization and responsiveness, but it also creates dependencies. A process may need one resource before it can release another; two or more processes may therefore wait for one another indefinitely. Other failures are less obvious: processes may remain active yet make no useful progress, or a low-priority task may be unable to obtain a resource because higher-priority tasks repeatedly overtake it.

These phenomena are central to operating-system correctness and performance. Deadlock is a permanent waiting condition caused by cyclic resource dependencies. Livelock occurs when processes continue changing state but fail to advance toward completion. Starvation is indefinite postponement of a process, often because scheduling or allocation continually favors others. Priority inversion arises when a high-priority task is delayed by a lower-priority task holding a needed resource. Resource contention is the broader condition in which multiple activities compete for limited resources, whether or not that competition becomes pathological.

The distinction matters in both operating systems and production platforms. A database transaction system, cloud scheduler, embedded controller, distributed service, or multithreaded application may fail even when CPU and memory utilization appear normal. Effective design requires models for representing allocation, conditions for recognizing unsafe states, policies for prevention and avoidance, mechanisms for detection and recovery, and operational methods for diagnosing contention.

Learning Objectives

After studying this chapter, the learner should be able to:

1. Model processes, resources, requests, allocations, and dependencies using graphs and matrices.

2. Explain the necessary conditions for deadlock and distinguish deadlock from starvation and livelock.

3. Apply deadlock prevention, avoidance, detection, and recovery strategies.

4. Use safe-state reasoning and the Banker’s algorithm for resource-allocation decisions.

5. Analyze priority inversion, fairness, lock contention, and production incidents.

6. Evaluate trade-offs among safety, throughput, latency, utilization, and implementation complexity.

7. Recommend monitoring, synchronization, and governance practices for concurrent systems.

A Vocabulary of Waiting and Progress

A resource is any entity required by a process to perform work. Resources may be reusable, such as a mutex, CPU core, printer, or database connection, or consumable, such as a message, interrupt, or signal. A reusable resource returns to the available pool after release; a consumable resource is produced and then consumed.

A process or thread requests resources, holds resources, performs computation, and releases resources. A resource instance is one unit of a resource type. For example, a system may have eight instances of a buffer pool, while a particular lock may have only one.

Mutual exclusion means that only one process can use a resource instance at a time. Hold and wait describes a process holding at least one resource while waiting for another. Preemption is the forced removal of a resource from a process. Circular wait is a cycle of processes in which each process waits for a resource held by the next process.

A deadlock exists when a set of processes is permanently blocked because every member waits for an event—usually resource release—that can be caused only by another blocked member. Deadlock is a safety failure: the system has entered a state from which the affected processes cannot complete without intervention.

A safe state is one in which the operating system can identify an order, called a safe sequence, allowing every process to obtain its remaining resources and finish. An unsafe state is not necessarily deadlocked, but it provides no guarantee that all processes can complete.

Starvation or indefinite postponement occurs when a process waits for an unbounded period while other processes continue to receive service. Unlike deadlock, the system as a whole may continue making progress. Livelock occurs when processes repeatedly respond to one another—for example, backing off, retrying, and changing state—without completing useful work. Contention is competition for a limited resource; it may be healthy at moderate levels but harmful when it produces long queues, excessive context switching, or poor latency.

Modeling Resource Allocation

The resource-allocation graph is a useful abstraction. It contains process nodes and resource nodes. A directed edge from a process to a resource represents a request; an edge from a resource to a process represents an allocation. With a single instance of each resource type, a cycle in the graph implies deadlock. With multiple instances, a cycle indicates possible deadlock but is not by itself conclusive.

For larger systems, matrix notation is more practical. Let:

• Available[j] denote the number of currently available instances of resource type j.
• Allocation[i][j] denote the resources of type j currently held by process i.
• Max[i][j] denote the maximum claim of process i for resource type j.
• Need[i][j] = Max[i][j] − Allocation[i][j] denote the remaining claim.

These structures support both avoidance and detection. They also clarify an important engineering issue: the operating system can make informed decisions only when resource claims, releases, and ownership are visible and trustworthy. Hidden allocation inside libraries or external services weakens the model.

Consider two threads, T1 and T2, and two mutexes, M1 and M2. T1 acquires M1 and requests M2; T2 acquires M2 and requests M1. The resulting cycle is T1 → M2 → T2 → M1 → T1. If neither thread can release its first mutex before obtaining the second, deadlock is inevitable.

The Four Necessary Conditions

The classical characterization identifies four conditions that must hold simultaneously for deadlock to occur:

1. Mutual exclusion: at least one resource is non-shareable.

2. Hold and wait: a process holds resources while requesting additional resources.

3. No preemption: resources cannot be forcibly taken away; they must be released voluntarily.

4. Circular wait: a circular chain of processes and resources exists.

These conditions are necessary, not four independent types of deadlock. Prevention works by ensuring that at least one condition can never hold. For example, imposing a global order on locks prevents circular wait; requiring a process to request all resources at once eliminates hold and wait; permitting preemption can break no-preemption. The design cost may, however, be substantial.

Four Families of Deadlock Handling

Prevention

Deadlock prevention imposes structural restrictions on resource use. A system may require a process to request every resource before execution begins. This is simple but can reduce utilization because resources remain reserved while not actively used. It may also be impractical when a process cannot predict its future needs.

A more flexible method is to impose a total ordering on resource types. If every thread acquires locks only in increasing order—for example, L1 before L2 before L3—then a cycle cannot form. Lock ordering is particularly effective in kernels, databases, and large codebases, but it requires documentation, code review, and discipline across modules.

Preemption is appropriate for some resources, such as memory pages or CPU time, but not for every resource. A lock cannot generally be removed safely from a thread in the middle of updating a data structure. Rollback, compensation, or transactional mechanisms may be necessary when preemption is attempted.

Avoidance

Deadlock avoidance allows flexible requests but evaluates each request before granting it. The system grants a request only if the resulting state remains safe. This requires knowledge of each process’s maximum possible demand, which is often available in controlled batch systems but difficult to obtain for general-purpose applications.

The Banker’s algorithm is the standard example. When process Pi requests vector Request[i], the system first checks that Request[i] ≤ Need[i] and Request[i] ≤ Available. It then simulates the allocation. If a safe sequence can still be found, the request is granted; otherwise, the process waits.

The safety test initializes Work to Available and Finish[i] to false. It repeatedly searches for a process whose Need[i] ≤ Work. If found, it assumes that process finishes and returns its allocation: Work = Work + Allocation[i]. Finish[i] becomes true. If all processes can be marked true, the state is safe. If some cannot, the state is unsafe.

Avoidance is not the same as prevention. Prevention disallows certain patterns in advance; avoidance examines each allocation dynamically. Avoidance can improve utilization but adds computation, bookkeeping, and dependence on accurate maximum claims.

Detection

Detection permits deadlocks to occur and periodically searches for them. This policy is useful when deadlocks are infrequent, prevention would be too restrictive, or recovery is feasible. For single-instance resource types, cycle detection in a wait-for graph is effective. A wait-for graph has only process nodes, with an edge Pi → Pj when Pi waits for a resource held by Pj.

For multiple instances, detection resembles the safety algorithm but interprets the data differently. The system attempts to identify processes whose remaining requests can be satisfied from current availability. Processes that cannot be eliminated belong to a potentially deadlocked set.

Detection frequency is a policy decision. Frequent checks reduce the duration of deadlocks but consume resources and may generate false alarms during legitimate long-running operations. In distributed systems, detection is harder because there is no single instantaneous view of allocations and network delays can resemble failure.

Recovery

Once deadlock is confirmed, the system must restore progress. One approach is process termination: terminate all affected processes or select victims one at a time until the cycle disappears. Another is resource preemption, in which resources are taken from selected processes and reassigned. Preemption may require rollback to a checkpoint and can cause repeated victimization or starvation.

Victim selection may consider process priority, amount of work completed, number and type of resources held, restart cost, and interactive importance. Recovery must also address consistency. Terminating a thread that holds a lock may leave shared data partially updated; terminating a transaction may require undo logging or compensation. Thus, recovery is often an application-level protocol rather than a purely kernel-level action.

Beyond Deadlock: Livelock, Starvation, and Priority Inversion

Livelock is common in polite retry algorithms. Imagine two threads that detect a conflict, release their locks, wait for a random interval, and retry. If they repeatedly choose similar intervals, both may continue yielding at the same time. They are not blocked, but their useful work remains near zero. Randomized backoff, bounded retries, ownership protocols, and escalation paths can reduce livelock.

Starvation often results from unfair scheduling, reader-preference locks, priority queues, or repeated failed allocation attempts. Aging addresses scheduling starvation by gradually increasing the priority of a waiting process. Fair locks, ticket locks, FIFO queues, and bounded waiting provide stronger guarantees, although they may reduce throughput in some workloads.

Priority inversion occurs when a high-priority task H waits for a lock held by low-priority task L, while medium-priority tasks repeatedly run and prevent L from releasing the lock. The high-priority task is indirectly delayed by medium-priority work. Priority inheritance temporarily raises L’s priority to that of H. Priority ceiling protocols assign a ceiling to locks and restrict acquisition based on task priorities. These mechanisms are important in real-time systems, where unbounded priority inversion can violate deadlines.

These conditions can coexist. A system may avoid deadlock yet suffer severe starvation, or eliminate starvation while still experiencing high contention. Correct diagnosis therefore requires observing both dependency and progress.

Resource Contention as a Performance Problem

Contention is not automatically a correctness failure. A lock protecting a short critical section may be contended but efficient. Problems arise when critical sections are long, locks are held during blocking I/O, one global lock protects unrelated data, or the workload creates a hot spot. Symptoms include increased wait time, reduced parallelism, context-switch overhead, cache-line bouncing, and tail-latency spikes.

Useful measures include lock acquisition latency, hold time, queue length, failed try-lock attempts, runnable-thread count, CPU utilization, and the proportion of time spent blocked. For storage or network resources, queue depth, service time, and saturation are also relevant. A low CPU utilization reading does not prove that the system is healthy; threads may simply be waiting on a database connection pool or a mutex.

Contention can be reduced through finer-grained locking, partitioning or sharding, read-write locks, lock-free or wait-free structures where justified, batching, asynchronous I/O, admission control, and reducing shared mutable state. Each technique has costs. Fine-grained locks increase complexity and deadlock risk; lock-free algorithms require careful memory-order reasoning; batching improves throughput but may increase latency.

A Practical Diagnostic and Design Process

A disciplined investigation begins by defining the resource and the progress obligation. Ask what each task holds, what it requests, who can release it, and what event permits completion. Capture thread dumps, lock ownership, wait-for relationships, scheduler priorities, queue depths, and timestamps. A snapshot should be supplemented with traces because transient contention may disappear before a diagnostic command runs.

Next, distinguish the failure mode. A cycle with no possible release indicates deadlock. A process that waits while others repeatedly succeed suggests starvation. High activity with repeated retries suggests livelock. A high-priority task blocked behind a lower-priority owner indicates priority inversion. Long queues without cycles usually indicate saturation or contention rather than deadlock.

The remedy should match the cause. Establish lock ordering for cycles, fairness for starvation, backoff and coordination for livelock, priority inheritance for inversion, and capacity or partitioning for ordinary contention. After applying a remedy, test not only average throughput but also worst-case waiting time, tail latency, recovery behavior, and correctness under cancellation and failure.

Illustrative Case Study: Deadlock in a Payment Service

Background

This illustrative case concerns a service that processes transfers between customer accounts. Each transfer updates two account records and writes an audit entry. To protect consistency, the application locks both account records before modifying balances.

Situation

A transfer from Account A to Account B acquires the lock for A first and then B. Another concurrent transfer from B to A acquires B first and then A. During a traffic spike, both requests remain active, CPU utilization falls, and the request queue grows. Thread inspection shows that each request is waiting for a lock held by the other.

Analysis

The incident satisfies mutual exclusion, hold and wait, no preemption, and circular wait. It is not a database outage or processor shortage. Restarting service instances releases the locks, but indiscriminate restarts risk duplicate requests unless operations are idempotent.

The team also discovers a second problem: the audit subsystem uses a separate lock and occasionally acquires it before an account lock, creating additional dependency paths. The original informal assumption that “transfers always lock two accounts” is therefore incomplete.

Strategy and Solution

The service adopts a canonical lock order based on account identifier: the lower identifier is always locked first. The audit lock is removed from the account-update critical section; audit records are appended through a transactional outbox and processed asynchronously. Lock acquisition has a bounded timeout, after which the request is retried with an idempotency key. Metrics record lock-wait duration, lock-hold duration, retry count, and abandoned requests.

Code review rules document lock ordering, and stress tests generate transfers in both directions under high concurrency. The database transaction remains the final consistency boundary, while application-level retries are designed so that a completed transfer is not applied twice.

Outcome

The canonical order removes the circular-wait path. The outbox reduces the duration for which account locks are held, and bounded timeouts prevent indefinitely occupied request threads. The solution does not eliminate all contention, but it converts a correctness failure into a measurable performance issue that can be capacity-managed.

Learning Points

The case demonstrates that deadlock prevention is a system-wide property. A local locking rule can fail when another component introduces a hidden dependency. It also shows why recovery, idempotency, observability, and data consistency must be designed together rather than treated as separate operational concerns.

Limitations, Risks, and Common Mistakes

A frequent mistake is to assume that every cycle is a deadlock. With multiple resource instances, a cycle may be resolvable through another available instance. Conversely, absence of a visible cycle in one snapshot does not prove that no deadlock occurred earlier.

Another mistake is to use timeouts as a complete solution. Timeouts detect prolonged waiting but do not explain ownership, guarantee consistency, or prevent repeated retry storms. Retrying many requests simultaneously can create a livelock or amplify overload. Backoff, jitter, retry budgets, and circuit breakers are needed in distributed applications.

Avoidance algorithms are limited by the requirement for reliable maximum claims. Static lock ordering is powerful but difficult to enforce across independently developed services and third-party libraries. Lock-free programming avoids some blocking but introduces risks involving the memory model, the ABA problem, reclamation, and starvation.

Recovery can lose work or violate application invariants if state is not transactional. Forced termination should therefore be treated as a controlled failure mechanism, not a routine substitute for correct synchronization. Fairness mechanisms may lower peak throughput, while aggressive priority schemes can create their own inversion and starvation effects.

Governance, Ethics, and Professional Practice

Concurrency failures can affect financial transfers, medical records, industrial control, and emergency response. Engineers must therefore treat progress guarantees as part of system safety, not merely as a performance optimization. Designs should state whether waiting is bounded, whether operations are idempotent, how cancellation behaves, and what data may be lost during recovery.

Operational governance should define who may restart processes, alter scheduler priorities, increase connection pools, or disable safety checks. Changes that reduce waiting by increasing concurrency may instead overload a downstream service. Logs and traces should avoid exposing sensitive data while retaining enough identifiers to reconstruct causal dependencies. In regulated environments, auditability of retries, rollbacks, and administrative intervention may be essential.

Technology and Emerging Directions

Modern observability platforms combine distributed tracing, profiling, thread dumps, eBPF-based kernel instrumentation, and metrics correlation to identify wait paths across application and operating-system boundaries. Static analyzers and lock-order checkers can detect inconsistent acquisition patterns before deployment. Runtime detectors can report long-held locks and potential cycles, although dynamic analysis cannot prove absence of all failures.

Container orchestration introduces additional contention for CPU quotas, memory, storage, network bandwidth, and shared service pools. Autoscaling may relieve capacity contention but cannot repair a lock cycle. In distributed systems, leases, fencing tokens, consensus protocols, and failure detectors address coordination, but network partitions and delayed messages complicate the meaning of ownership.

Machine-learning techniques may help forecast queue growth or identify anomalous wait-time patterns, but predictions should support—not replace—formal invariants and deterministic recovery. A model that labels a dependency as benign cannot safely authorize breaking a lock without understanding the protected state.

Best Practices for Concurrent-System Design

• Define resource ownership and release responsibilities explicitly.
• Establish and enforce a global lock-ordering policy where feasible.
• Keep critical sections short and never hold locks across avoidable blocking operations.
• Prefer immutable state, partitioning, message passing, or transactions when they reduce shared mutable state.
• Provide fairness or bounded waiting when starvation is unacceptable.
• Use priority inheritance or ceiling protocols in real-time and priority-sensitive systems.
• Make retries bounded, idempotent, and randomized where appropriate.
• Monitor wait time, hold time, queue depth, and tail latency—not only utilization.
• Test cancellation, failure, overload, and recovery paths under adversarial concurrency.
• Document assumptions about resource capacity, maximum claims, and consistency guarantees.

Chapter Summary

Deadlocks arise when mutual exclusion, hold and wait, no preemption, and circular wait occur together. Resource-allocation graphs, wait-for graphs, and allocation matrices provide models for reasoning about dependencies. Prevention breaks a necessary condition, avoidance grants requests only when the resulting state remains safe, detection searches for existing cycles or unresolvable waits, and recovery terminates, preempts, or rolls back selected work.

Deadlock is only one form of progress failure. Livelock involves active but useless retries, starvation involves indefinite unfair waiting, and priority inversion occurs when priority relationships are disrupted by resource ownership. Resource contention may be a normal performance condition or may become a source of latency and instability. Effective engineering combines synchronization rules, fairness, priority protocols, observability, bounded recovery, and application-level consistency. In production, the central question is not merely whether a resource is busy, but whether the system continues to make safe, fair, and useful progress.

Key Terms

Resource: An entity required by a process, such as a lock, device, memory region, or connection.

Resource instance: One unit of a resource type available for allocation.

Mutual exclusion: A condition in which only one process can use a resource instance at a time.

Hold and wait: Holding allocated resources while waiting for additional resources.

No preemption: The condition that a resource cannot be forcibly removed from its holder.

Circular wait: A cycle in which each process waits for a resource held by another process in the cycle.

Deadlock: Permanent blocking caused by mutually dependent waiting processes.

Safe state: A state with at least one sequence in which all processes can obtain remaining resources and finish.

Unsafe state: A state that does not guarantee completion of all processes; it may or may not be deadlocked.

Resource-allocation graph: A graph representing resource requests and allocations.

Wait-for graph: A process-only graph showing which process is waiting for another.

Deadlock prevention: Structurally restricting allocation so at least one necessary condition cannot occur.

Deadlock avoidance: Evaluating each request to ensure that the resulting state remains safe.

Deadlock detection: Searching for deadlock after allocations have been permitted.

Deadlock recovery: Actions such as termination, preemption, or rollback used to restore progress.

Livelock: Repeated activity and state changes without useful progress.

Starvation: Indefinite postponement while other processes continue receiving service.

Priority inversion: Delay of a high-priority task because a lower-priority task holds a needed resource.

Contention: Competition among processes or tasks for a limited resource.

Priority inheritance: Temporarily raising a resource holder’s priority to that of a blocked higher-priority task.

Review Questions

Short Answer Questions

1. State the four necessary conditions for deadlock.

2. How does a safe state differ from an unsafe state?

3. Distinguish livelock from deadlock.

4. What information is represented by a wait-for graph?

5. Define priority inversion and name one method for controlling it.

Long Answer Questions

1. Explain deadlock prevention, avoidance, detection, and recovery, including the trade-offs of each approach.

2. Describe the Banker’s algorithm and explain how its safety test determines whether a request may be granted.

3. Discuss how lock ordering prevents circular wait and identify practical difficulties in enforcing a global order.

4. Compare starvation, livelock, and resource contention in terms of symptoms, causes, and remedies.

5. Explain why deadlock recovery must consider application consistency, rollback, idempotency, and operational governance.

Analytical / Application Questions

1. Threads T1 and T2 each hold one of two mutexes and request the other. Model the situation as a wait-for graph, identify the deadlock conditions, and propose two different remedies.

2. A high-priority real-time task waits for a lock held by a low-priority task while medium-priority tasks continue executing. Analyze the scheduling failure and recommend an appropriate protocol.

3. A service shows low CPU utilization, growing request queues, frequent retries, and long lock-wait times but no persistent dependency cycle. Determine whether the dominant problem is deadlock, livelock, starvation, or contention, and justify an investigation and remediation plan.

22. Multiple Choice Questions with Answers

Question 1

Which combination of conditions is necessary for a classical deadlock?

A. Mutual exclusion, hold and wait, no preemption, and circular wait

B. Preemption, fairness, high utilization, and aging

C. Sharing, immediate release, preemption, and FIFO scheduling

D. Circular scheduling, paging, starvation, and priority inheritance

Correct Answer: A. Mutual exclusion, hold and wait, no preemption, and circular wait

Question 2

In a resource-allocation graph with a single instance of every resource type, what does a cycle imply?

A. The system is necessarily free of deadlock

B. Deadlock exists among the processes in the cycle

C. Only starvation is possible

D. The resources are being fairly allocated

Correct Answer: B. Deadlock exists among the processes in the cycle

Question 3

What is the principal decision rule in deadlock avoidance?

A. Grant every request immediately

B. Terminate the requesting process

C. Grant a request only if the resulting state is safe

D. Preempt all resources before allocation

Correct Answer: C. Grant a request only if the resulting state is safe

Question 4

A state is unsafe when:

A. At least one resource is currently unavailable

B. The system has no guaranteed sequence allowing every process to finish

C. All processes are actively using the CPU

D. A process has released its maximum claim

Correct Answer: B. The system has no guaranteed sequence allowing every process to finish

Question 5

Two threads repeatedly detect conflict, back off, and retry at nearly the same time without completing work. This is best described as:

A. Deadlock

B. Livelock

C. Priority inheritance

D. Safe-state execution

Correct Answer: B. Livelock

Question 6

Which design rule directly prevents circular wait among locks?

A. Allowing every thread to acquire locks in arbitrary order

B. Requiring all locks to be held until process termination

C. Imposing a consistent global order for lock acquisition

D. Increasing the number of runnable threads

Correct Answer: C. Imposing a consistent global order for lock acquisition

Question 7

What is the purpose of priority inheritance?

A. To lower the priority of every waiting task

B. To raise the resource holder’s priority temporarily

C. To eliminate mutual exclusion

D. To guarantee that no resource is ever preempted

Correct Answer: B. To raise the resource holder’s priority temporarily

Question 8

Which observation most strongly indicates starvation rather than deadlock?

A. Two processes form a permanent wait cycle

B. All processes in a set wait for one another

C. One process waits indefinitely while others repeatedly receive service

D. No process changes state after allocation

Correct Answer: C. One process waits indefinitely while others repeatedly receive service

Question 9

Why can a timeout alone be an inadequate solution to deadlock?

A. Timeouts always increase lock hold time

B. Timeouts cannot detect any prolonged waiting

C. Retries after timeout may cause inconsistency, retry storms, or livelock

D. Timeouts make all resources shareable

Correct Answer: C. Retries after timeout may cause inconsistency, retry storms, or livelock

Question 10

Which metric is most directly useful for diagnosing lock contention?

A. Screen resolution

B. Lock acquisition wait time and hold time

C. Number of installed applications

D. File-name length

Correct Answer: B. Lock acquisition wait time and hold time