Deadlocks and Resource Allocation

Introduction

An operating system coordinates processes that compete for finite resources such as processors, main memory, files, database locks, printers, network connections, and devices. Resource allocation is straightforward when each process requests, uses, and releases resources independently. It becomes difficult when processes hold some resources while waiting for others. In such situations, a set of processes may become permanently blocked: each process is waiting for an event that only another blocked process can cause. This condition is called a deadlock.

Deadlocks are important in operating systems, databases, distributed systems, transaction processing, and concurrent software. They can reduce throughput, prevent service completion, and cause financial or safety consequences. A robust operating system must therefore decide whether to prevent deadlocks, avoid unsafe allocations, detect deadlocks after they occur, or recover from them. These strategies involve trade-offs among safety, resource utilization, performance, and implementation complexity.

This chapter develops formal models of resource allocation, explains the necessary conditions for deadlock, presents prevention and avoidance techniques, derives the Banker's algorithm, and discusses detection, recovery, starvation, and practical design considerations.

Learning Objectives

By the end of this chapter, you should be able to:

1. Model processes, resource types, instances, requests, allocations, and releases.

2. Explain the four necessary conditions for deadlock.

3. Represent deadlocks using resource-allocation graphs.

4. Compare deadlock prevention, avoidance, detection, and recovery.

5. Apply the safety algorithm and Banker's algorithm to allocation decisions.

6. Distinguish deadlock from starvation, livelock, and ordinary blocking.

7. Evaluate practical resource-management policies in operating systems and concurrent applications.

1. Resource-Allocation Model

A resource type is a category of interchangeable resources. Examples include printers, tape drives, locks, or identical memory buffers. A resource type may have one instance or multiple instances. Let the resource types be \(R_1, R_2, \ldots, R_m\), and let \(E_j\) denote the total number of instances of type \(R_j\).

A process generally follows this sequence:

1. Request: It asks the operating system for resources.

2. Use: It operates while holding the resources.

3. Release: It returns the resources.

A request can be granted only if the requested resources are available and granting them does not violate the operating system's policy. A process may need several resources simultaneously. For example, a database transaction might hold a lock on one table while requesting a lock on another.

For a system with \(n\) processes and \(m\) resource types, common data structures are:

• Available: A vector whose element \(Available[j]\) is the number of currently free instances of resource type \(R_j\).
• Max: A matrix in which \(Max[i][j]\) is the maximum number of instances of \(R_j\) that process \(P_i\) may ever need.
• Allocation: A matrix in which \(Allocation[i][j]\) is the number of instances of \(R_j\) currently held by \(P_i\).
• Need: A matrix representing the remaining possible demand:

\[

Need[i][j] = Max[i][j] - Allocation[i][j]

\]

This equation applies when maximum claims and current allocations are expressed in the same units and the maximum claim includes resources already allocated. Every entry must be non-negative because a process cannot hold more than its declared maximum claim.

The model assumes that resource instances of the same type are interchangeable. If individual instances differ in capability, they should be represented as separate resource types or modeled with a more detailed matching system.

2. Deadlock and Related Conditions

A deadlock exists when every process in a set is waiting for an event that can be caused only by another process in the same set. Usually, the event is the release of a resource. Since none of the processes can proceed, none can release its held resources.

Deadlock must be distinguished from related conditions:

• Blocked process: A process is waiting, but the wait may eventually end.
• Starvation: A process waits indefinitely because resources or scheduling opportunities repeatedly go to other processes.
• Livelock: Processes continue changing state but make no useful progress, often because they repeatedly respond to one another.
• Deadlock: Processes remain blocked in a circular dependency and cannot make progress without external intervention.

The Four Necessary Conditions

The following four conditions must hold simultaneously for a traditional deadlock to occur:

1. Mutual exclusion: At least one resource is non-shareable; only one process can use it at a time.

2. Hold and wait: A process holds at least one resource while waiting for additional resources held by other processes.

3. No preemption: Resources cannot be forcibly taken from a process; they are released voluntarily after use.

4. Circular wait: A cycle exists in which \(P_1\) waits for a resource held by \(P_2\), \(P_2\) waits for one held by \(P_3\), and so on, with \(P_k\) waiting for a resource held by \(P_1\).

These conditions are necessary, not individually sufficient. If even one condition is eliminated, deadlock cannot occur under the model.

3. Resource-Allocation Graphs

A resource-allocation graph represents relationships among processes and resources. Process nodes are usually circles, resource-type nodes are rectangles, and edges have two meanings:

• A directed edge from process \(P_i\) to resource \(R_j\) means that \(P_i\) is requesting \(R_j\).
• A directed edge from resource \(R_j\) to process \(P_i\) means that an instance of \(R_j\) has been allocated to \(P_i\).

For a single-instance resource type, a cycle in the graph implies deadlock. For multiple-instance resource types, a cycle indicates the possibility of deadlock but does not necessarily prove it. A cycle may exist while another instance of a resource can satisfy a request and allow a process to finish.

A graph can also include a claim edge, shown conceptually as a dashed edge, indicating that a process may request a resource in the future. Avoidance algorithms use such claims to reason about whether a future allocation could lead to an unsafe state.

4. Strategies for Handling Deadlocks

Operating systems commonly use one of four broad approaches.

4.1 Ignore the Problem

Some general-purpose systems do not apply a comprehensive deadlock policy to every resource. They assume that deadlocks are uncommon or delegate responsibility to applications. This approach has low overhead but can leave users with hung programs and requires administrative or application-level recovery.

4.2 Deadlock Prevention

Prevention structurally eliminates at least one necessary condition. It provides a strong guarantee but may reduce concurrency or resource utilization.

Eliminating mutual exclusion. Some resources can be made shareable. For example, read-only files can be accessed concurrently. Physical devices such as printers cannot generally be shared directly, although spooling allows processes to write output to a disk queue while a printer service controls the device.

Eliminating hold and wait. A process may be required to request all resources before it begins, or to release all resources before requesting additional ones. The first policy can cause poor utilization because resources remain held before they are needed. The second can require repeated acquisition and may be impractical for workflows with unpredictable demands.

Allowing preemption. If a process requests a resource that is unavailable, resources it already holds may be taken away and restored later. This works for resources whose state can be saved and restored, such as some computational data, but is unsuitable for many devices or locks protecting externally visible operations.

Eliminating circular wait. Assign each resource type a unique ordering. A process must request resources only in increasing order. If resource types have order \(F(R_1) < F(R_2)\), a process holding \(R_1\) may request \(R_2\), but it may not later request \(R_1\). A circular chain would require an impossible strictly increasing sequence that returns to its starting point.

Resource ordering is often a practical prevention technique. Its challenge is that a global order must be agreed upon and maintained across modules, libraries, and sometimes different services.

4.3 Deadlock Avoidance

Avoidance permits the four conditions to exist but makes allocation decisions using information about future maximum demands. The operating system grants a request only if the resulting state is safe.

A state is safe if there exists an ordering of all processes, called a safe sequence, such that each process can obtain its remaining resources, finish, and release its allocation, allowing the next process to finish. A safe state is not necessarily free of current waiting, but it guarantees that some completion order exists under the model. An unsafe state is not necessarily already deadlocked; it means the system can no longer guarantee that deadlock will be avoided.

Avoidance requires processes to declare maximum claims or otherwise provide reliable upper bounds. This requirement is often difficult for interactive, dynamic, or third-party software.

4.4 Detection and Recovery

Detection allows allocations to proceed and periodically checks whether deadlock has occurred. If it detects a deadlock, the operating system recovers by terminating processes, preempting resources, or rolling back work. This approach can provide better utilization when deadlocks are rare, but detection and recovery impose costs and may cause lost work.

5. The Safety Algorithm

The safety algorithm tests whether a state is safe. It uses the vectors and matrices defined earlier.

Set:

• \(Work = Available\), representing resources currently available for hypothetical allocation.
• \(Finish[i] = false\) for every process initially.

Repeatedly find a process \(P_i\) such that:

\[

Finish[i] = false \quad \text{and} \quad Need[i] \leq Work

\]

The inequality is componentwise: the remaining demand must not exceed the currently available amount for any resource type. When such a process is found, simulate its completion:

\[

Work = Work + Allocation[i]

\]

and set \(Finish[i] = true\). Continue until either all processes finish or no eligible process remains. If all \(Finish[i]\) values become true, the state is safe. Otherwise, it is unsafe.

The algorithm is a feasibility test, not a prediction of the exact execution order. Several safe sequences may exist.

6. The Banker's Algorithm

The Banker's algorithm is a deadlock-avoidance method for multiple instances of resource types. It is called a banker’s algorithm because a banker grants loans only when the bank can still satisfy all customers according to their declared maximum needs.

When process \(P_i\) requests vector \(Request_i\), the operating system performs these checks:

1. Verify \(Request_i \leq Need_i\). A process must not request more than its declared maximum.

2. Verify \(Request_i \leq Available\). The resources must currently be available.

3. Temporarily allocate the request:

\[

Available = Available - Request_i

\]

\[

Allocation_i = Allocation_i + Request_i

\]

\[

Need_i = Need_i - Request_i

\]

4. Run the safety algorithm.

5. Permanently grant the request only if the resulting state is safe. Otherwise, restore the old state and make the process wait.

The algorithm does not simply grant every currently available request. A request can be available now yet make future completion impossible.

Worked Example: Safety Test

Assume three resource types \(A, B, C\), five processes, and the following state:

\[

Available = (3, 3, 2)

\]

| Process | Allocation | Max | Need |

|---|---:|---:|---:|

| P0 | (0, 1, 0) | (7, 5, 3) | (7, 4, 3) |

| P1 | (2, 0, 0) | (3, 2, 2) | (1, 2, 2) |

| P2 | (3, 0, 2) | (9, 0, 2) | (6, 0, 0) |

| P3 | (2, 1, 1) | (4, 2, 2) | (2, 1, 1) |

| P4 | (0, 0, 2) | (5, 3, 3) | (5, 3, 1) |

The Need matrix is obtained by subtracting Allocation from Max. Begin with \(Work=(3,3,2)\).

• \(P1\) can finish because \((1,2,2) \leq (3,3,2)\). After it finishes, \(Work=(3,3,2)+(2,0,0)=(5,3,2)\).
• \(P3\) can finish because \((2,1,1) \\leq (5,3,2)\). Then \(Work=(5,3,2)+(2,1,1)=(7,4,3)\).
• \(P4\) can finish because \((5,3,1) \\leq (7,4,3)\). Then \(Work=(7,4,3)+(0,0,2)=(7,4,5)\).
• \(P0\) can finish because \((7,4,3) \\leq (7,4,5)\). Then \(Work=(7,4,5)+(0,1,0)=(7,5,5)\).
• \(P2\) can finish because \((6,0,0) \\leq (7,5,5)\).

A safe sequence is \(\langle P1,P3,P4,P0,P2\rangle\). Therefore, the state is safe. The sequence is not unique; another eligible process could sometimes be selected without invalidating safety.

7. Deadlock Detection

Detection algorithms differ according to whether resources have one or several instances.

Single Instance of Each Resource Type

A wait-for graph can be constructed by removing resource nodes. An edge \(P_i \rightarrow P_j\) means that \(P_i\) waits for a resource held by \(P_j\). A cycle in this graph is both necessary and sufficient for deadlock under the single-instance assumption. Cycle detection can be performed using standard graph algorithms such as depth-first search.

Multiple Instances

For multiple instances, a detection algorithm resembles the safety algorithm but uses current requests rather than declared maximum claims. Let Request represent the outstanding requests. Set \(Work=Available\) and mark processes with no allocation as finished. Repeatedly find an unfinished process whose current request is no greater than \(Work\), then simulate its completion by adding its allocation to \(Work\). Processes remaining unfinished at the end are deadlocked under the model.

Detection frequency is a policy choice. Frequent detection limits the duration of deadlocks but consumes processor time. Infrequent detection reduces overhead but allows more blocked work to accumulate.

8. Recovery from Deadlock

Once a deadlock is confirmed, recovery must break the cycle.

Process Termination

The system may terminate every deadlocked process, which is simple but potentially destructive. Alternatively, it may terminate processes one at a time until the cycle disappears. Victim selection can consider priority, execution time already completed, resources held, resources still needed, restart cost, and the number of processes affected.

Resource Preemption

The system may take resources from selected processes and give them to others. This requires:

• Selecting a victim.
• Saving enough state to restart or resume the victim.
• Rolling back the victim to a safe checkpoint.
• Preventing repeated selection of the same process.

Preemption is inappropriate when a resource cannot be safely removed, such as a device performing an indivisible physical operation.

Rollback and Checkpointing

A process or transaction can periodically save state. After deadlock, it is rolled back to a checkpoint, releases resources, and retries later. Checkpointing improves recoverability but requires storage, coordination, and careful handling of external side effects.

Recovery and Fairness

Recovery can create starvation if the same low-priority process is repeatedly terminated or preempted. Systems should record victim history, increase the effective cost of repeatedly selecting the same process, or use aging and bounded retry policies.

9. Starvation, Fairness, and Livelock Control

Deadlock prevention does not automatically prevent starvation. For example, a process might always lose a resource race even though the system as a whole continues making progress.

Common controls include:

• FIFO or queue-based lock acquisition: Requests are served in arrival order where appropriate.
• Aging: A waiting process gradually receives higher priority.
• Bounded waiting: The design specifies a maximum number of times other processes may enter a critical section before a waiting process is served.
• Fair reader-writer policies: Prevent either readers or writers from being postponed indefinitely.
• Backoff with randomness: Reduces repeated collisions, although it does not itself prove fairness.
• Admission control: Limits the number of competing operations.

Livelock requires different treatment. Processes may need randomized delays, stronger arbitration, or a protocol that guarantees progress rather than merely avoiding simultaneous action.

10. Applied Case: Deadlock in a Transaction and Service Platform

The following is an illustrative case.

Background

An online retail platform uses two services. The inventory service locks an item record before reducing stock. The payment service locks a customer-credit record before authorizing payment. A purchase workflow calls both services.

Problem

Workflow A locks the inventory record and then requests the customer-credit record. At nearly the same time, workflow B locks the customer-credit record and then requests the inventory record. Each waits for the other. Request queues grow, transaction latency rises, and eventually both workflows time out.

Analysis

The resources are logical database locks. Mutual exclusion exists because conflicting updates cannot occur simultaneously. Hold and wait exists because each transaction retains its first lock while requesting the second. Database lock managers generally do not preempt an active update without rollback, satisfying no preemption. The two lock requests form a circular wait.

Approach and Solution

The engineering team adopts a global lock order: inventory locks must be acquired before customer-credit locks. The order is enforced in shared libraries and reviewed during code changes. The database also retains deadlock detection and aborts a selected transaction if an unexpected cycle occurs. Aborted transactions retry with bounded exponential backoff and an idempotency key so that repeating the operation does not charge the customer twice.

The platform monitors deadlock-abort rate, transaction age, lock-wait time, retry count, and failed business operations. Long transactions are redesigned to hold locks for a shorter interval, and external network calls are removed from lock-held sections.

Outcome

The ordering rule eliminates the known circular-wait pattern. Detection remains a safety net for future code and cross-service interactions. Idempotent retry and bounded backoff reduce the risk that recovery creates duplicate payments or retry storms.

Learning Points

The case shows that deadlock control is not only an operating-system concern. Lock ordering, short critical sections, observability, transaction design, safe retry, and business-level consistency must work together. A technically correct rollback policy can still be unacceptable if it creates duplicate external effects.

11. Practical Design and Professional Implications

Deadlock policies should be selected according to resource characteristics and workload requirements.

• Use prevention when a simple ordering rule or nonblocking design is available and predictable behavior is important.
• Use avoidance when maximum claims are known, resources are reusable, and the cost of unsafe allocation is high.
• Use detection and recovery when deadlocks are uncommon, utilization is important, and rollback or termination is acceptable.
• Use timeouts as a defensive mechanism, not as proof that deadlock has been solved. A timeout can mistake a slow operation for a deadlock and can cause unnecessary rollback.

Good engineering practice includes documenting lock order, keeping critical sections short, avoiding calls to unknown code while holding locks, releasing resources through structured cleanup, instrumenting wait graphs, testing adverse interleavings, and designing recovery to be idempotent.

In AI and machine-learning systems, deadlock can occur in data pipelines, distributed parameter updates, accelerator scheduling, worker pools, and resource managers. GPU memory, communication channels, file locks, and task dependencies can all participate in cycles. AI workloads do not change the fundamental deadlock conditions, but their scale and distributed execution make diagnosis harder. Dependency graphs, scheduling policies, timeout telemetry, and deterministic resource ordering are therefore valuable in ML platforms.

12. Limitations and Contemporary Developments

The classic resource-allocation model makes simplifying assumptions. Maximum demands may be unknown, resources may be dynamically created, processes may interact through messages rather than explicit locks, and resources may have different quality or capability. Distributed systems also face incomplete information and communication delays; a detected cycle may reflect stale observations.

Modern systems increasingly use:

• Static lock-order analysis and type systems that encode ownership.
• Runtime lock-dependency graphs and deadlock detectors.
• Transactional memory and optimistic concurrency, which reduce locking in selected workloads.
• Lease-based distributed locks, where expiration limits indefinite ownership but introduces clock and failure concerns.
• Structured concurrency and cancellation, which make ownership and cleanup more explicit.
• Formal verification and model checking for safety-critical synchronization protocols.

These techniques complement rather than replace sound resource modeling. A timeout, lease, or automated retry must be evaluated for false positives, fairness, data consistency, and side effects.

Ethically and operationally, organizations should ensure that deadlock recovery does not silently discard user work, corrupt records, duplicate financial transactions, or disadvantage particular users. Audit logs, transparent failure reporting, access controls, and tested recovery procedures are part of responsible resource management.

Chapter Summary

Deadlock is permanent blocking caused by a circular dependency among processes competing for resources. It requires mutual exclusion, hold and wait, no preemption, and circular wait. Resource-allocation graphs model requests and assignments; cycles prove deadlock for single-instance resources but may only indicate possibility for multiple instances.

Deadlock prevention eliminates at least one necessary condition, commonly through resource ordering or restrictions on holding resources. Avoidance uses future claims and grants requests only when the resulting state is safe. The safety algorithm searches for a sequence in which every process can obtain its remaining needs and release its allocation. The Banker's algorithm applies this test to each request. Detection allows possible deadlocks and identifies them later, while recovery uses termination, preemption, rollback, or combinations of these methods.

Deadlock is distinct from starvation and livelock, so fair scheduling, aging, bounded waiting, and progress-oriented protocols are also required. In professional systems, lock ordering, short critical sections, observability, idempotent retries, and careful recovery are essential. The classic model remains foundational, but distributed systems, cloud platforms, databases, and AI workloads require additional attention to incomplete information, dynamic resources, and externally visible side effects.

Key Terms

Deadlock: A condition in which processes wait indefinitely for events caused by one another.

Resource type: A category of interchangeable resource instances.

Mutual exclusion: A condition in which a resource can be held by only one process at a time.

Hold and wait: Holding at least one resource while waiting for another.

No preemption: The inability to forcibly remove a resource from its holder.

Circular wait: A cycle of processes, each waiting for a resource held by the next.

Resource-allocation graph: A graph representing processes, resources, requests, and allocations.

Wait-for graph: A graph in which an edge indicates that one process waits for another.

Safe state: A state with at least one completion order for all processes.

Unsafe state: A state in which the system cannot guarantee avoidance of deadlock.

Safe sequence: An ordering in which every process can obtain its remaining resources and finish.

Deadlock prevention: Elimination of at least one necessary deadlock condition.

Deadlock avoidance: Selective allocation based on future claims and state safety.

Deadlock detection: Identification of deadlock after allocations have been made.

Recovery: Actions that break a detected deadlock.

Banker's algorithm: A multiple-instance deadlock-avoidance algorithm using maximum claims.

Starvation: Indefinite postponement of a process despite system progress.

Livelock: Repeated activity without useful progress.

Preemption: Taking a resource from a process before it voluntarily releases it.

Rollback: Returning a process or transaction to an earlier saved state.

Review Questions

Short Answer Questions

1. Define deadlock and distinguish it from starvation.

2. List and explain the four necessary conditions for deadlock.

3. What is the difference between a safe state and an unsafe state?

4. Why does a cycle prove deadlock for single-instance resource types but not necessarily for multiple-instance types?

5. State the purpose of the Need matrix in the Banker's algorithm.

Long Answer Questions

1. Compare deadlock prevention, avoidance, detection, and recovery in terms of assumptions, overhead, utilization, and guarantees.

2. Explain how imposing a total order on resource types prevents circular wait. Include a suitable example.

3. Describe the safety algorithm and explain how it is used by the Banker's algorithm.

4. Discuss process termination, resource preemption, and rollback as recovery techniques, including their risks.

5. Explain how an operating system can control starvation and livelock in addition to deadlock.

Analytical / Application Questions

1. Given a resource-allocation graph with multiple instances of one resource type, determine whether a cycle represents definite deadlock or only a possible deadlock, and justify your reasoning.

2. A transaction system acquires locks in inconsistent orders and experiences periodic timeouts. Design a deadlock-control policy covering lock ordering, detection, retry, monitoring, and idempotency.

3. Using a supplied Available, Allocation, and Max table, calculate Need, find a safe sequence, and evaluate whether a proposed request should be granted under the Banker's algorithm.

Multiple Choice Questions with Answers

Question 1

Which condition requires a process to retain resources while waiting for additional resources?

A. Mutual exclusion

B. Hold and wait

C. No preemption

D. Circular wait

Correct Answer: B. Hold and wait

Question 2

For a resource type with a single instance, what does a cycle in the wait-for graph indicate?

A. Starvation only

B. A safe state

C. Deadlock

D. Livelock only

Correct Answer: C. Deadlock

Question 3

If Max[i][j] = 8 and Allocation[i][j] = 3, what is Need[i][j]?

A. 5

B. 11

C. 24

D. 3

Correct Answer: A. 5

Question 4

What does the safety algorithm add to Work when it simulates completion of a process?

A. The process's Max vector

B. The process's Need vector

C. The process's Allocation vector

D. The original Available vector

Correct Answer: C. The process's Allocation vector

Question 5

A state is safe when:

A. No process is currently waiting

B. Every resource is completely unused

C. There is an order in which all processes can finish

D. All processes have identical maximum claims

Correct Answer: C. There is an order in which all processes can finish

Question 6

Which policy directly prevents circular wait?

A. Allowing arbitrary lock acquisition

B. Requiring resources to be requested in a fixed global order

C. Increasing the number of processes

D. Disabling process termination

Correct Answer: B. Requiring resources to be requested in a fixed global order

Question 7

What is the first logical check when a process submits a request under the Banker's algorithm?

A. Whether Request exceeds Need

B. Whether the process has already finished

C. Whether all resources are free

D. Whether Max equals Available

Correct Answer: A. Whether Request exceeds Need

Question 8

Which condition distinguishes starvation from deadlock?

A. Starvation always involves a resource cycle

B. Starvation can occur while other processes continue making progress

C. Starvation requires no resource competition

D. Starvation can be solved only by termination

Correct Answer: B. Starvation can occur while other processes continue making progress

Question 9

Which recovery method returns a process to a previously saved execution state?

A. Spooling

B. Rollback

C. Resource ordering

D. Aging

Correct Answer: B. Rollback

Question 10

For multiple-instance resources, a cycle in a resource-allocation graph generally means:

A. Deadlock is guaranteed

B. Deadlock is impossible

C. Deadlock is possible but requires further analysis

D. All processes are starving

Correct Answer: C. Deadlock is possible but requires further analysis