Deadlock

Definition

Conceptual Overview

Deadlock: state in a multi-process system where a set of processes are blocked waiting indefinitely for resources held by each other. Result: system halt or severe performance degradation.

Context in Operating Systems

Occurs during resource allocation in multitasking OS. Resources: CPU cycles, memory, I/O devices, files. Deadlock: major challenge for concurrency and synchronization.

Historical Background

First formalized by Dijkstra (1965). Subsequent studies defined conditions and strategies to handle deadlock in OS design and distributed systems.

"Deadlock is the Achilles' heel of concurrent computing." -- A. Silberschatz

Necessary Conditions

Mutual Exclusion

At least one resource must be held in non-sharable mode. Only one process can use the resource at a time.

Hold and Wait

Processes hold resources while waiting to acquire additional resources.

No Preemption

Resources cannot be forcibly taken from a process; they are released only voluntarily.

Circular Wait

Existence of a circular chain of processes, each waiting for a resource held by the next process.

Summary Table

Resource Models

Single Instance Model

Each resource type has exactly one instance. Deadlock detection simpler, modeled through allocation matrices.

Multiple Instances Model

Resource types have multiple identical instances. Processes may request multiple units simultaneously.

Graph Representation

Resource Allocation Graphs (RAGs) model resource-process relationships. Nodes: processes and resources; edges: allocation and requests.

Matrix Representation

Allocation and request matrices represent system state; basis for algorithms detecting deadlock.

Summary

Resource models define complexity and strategy for deadlock handling in OS.

Deadlock Prevention

Overview

Strategy: structurally negate at least one necessary condition to prevent deadlock.

Eliminating Mutual Exclusion

Possible only for sharable resources (e.g., read-only files). Not feasible for non-sharable resources like printers.

Eliminating Hold and Wait

Processes request all resources upfront; no resource holding during wait. Drawback: low resource utilization, possible starvation.

Eliminating No Preemption

Preempt resources from processes when needed. Requires rollback or checkpointing mechanisms.

Eliminating Circular Wait

Impose strict ordering on resource acquisition. Processes must request resources in increasing order of enumeration.

Trade-offs

Prevention techniques can reduce concurrency and efficiency.

Deadlock Avoidance

Concept

Dynamic resource allocation based on future resource needs and system state to avoid unsafe states.

Safe State

System can allocate resources to each process in some order and avoid deadlock.

Unsafe State

Potential deadlock if resource allocation proceeds; system must avoid entering such states.

Banker's Algorithm

Classic avoidance algorithm; simulates resource allocation to check if system remains safe.

Limitations

Requires advance knowledge of maximum resource demands; computational overhead high for large systems.

Initialize Available, Max, Allocation, Need matricesWhile processes remain: Find process i where Need[i] ≤ Available If found: Available += Allocation[i] Mark process i finished Else: System in unsafe state (potential deadlock) 

Deadlock Detection

Purpose

Allow deadlock to occur but detect it promptly through algorithmic checks.

Detection Algorithm (Single Instance)

Use Resource Allocation Graph cycle detection to find deadlocks.

Detection Algorithm (Multiple Instances)

Use Banker’s Algorithm variant or Wait-For Graph analysis to detect deadlocks.

Frequency

Detection invoked periodically or when resource requests are blocked beyond threshold.

Overhead

Detection algorithms consume CPU and memory; frequency balances detection latency and overhead.

Initialize Work = AvailableInitialize Finish[i] = false for all processesFind i where Finish[i] == false and Need[i] ≤ Work If found: Work += Allocation[i] Finish[i] = trueRepeat until no such i foundIf any Finish[i] == false, deadlock detected 

Deadlock Recovery

Options

Process termination, resource preemption, or rollback.

Process Termination

Terminate one or more deadlocked processes to free resources. Strategies: terminate all, terminate one at a time, terminate lowest priority.

Resource Preemption

Preempt resources from processes and rollback to safe states. Complex due to data consistency and process states.

Rollback

Return process to checkpointed state before resource acquisition; requires checkpoint mechanisms.

Trade-offs

Recovery methods can cause data loss, inconsistent states, or high overhead.

Resource Allocation Graphs

Structure

Directed bipartite graph with process nodes (circles) and resource nodes (squares).

Edges

Request edge: process → resource; Allocation edge: resource → process.

Cycle Detection

Cycle in graph indicates deadlock if each resource has a single instance.

Multiple Instances

Cycle does not guarantee deadlock; more complex analysis required.

Example

Key Algorithms

Banker’s Algorithm

Safe state detection algorithm based on resource allocation and maximum needs. Prevents unsafe allocation.

Wait-For Graph Algorithm

Simplified RAG removing resource nodes; edges represent waiting relations. Cycle detection identifies deadlock.

Ostrich Algorithm

Ignore deadlocks assuming rarity; used in non-critical systems.

Resource Allocation Graph Algorithm

Cycle detection for single instance resources; basis for many detection schemes.

Summary Table

Practical Implications

Systems Impact

Deadlocks cause system freezes, reduced throughput, poor user experience, and potential data loss.

Real-Time Systems

Deadlocks unacceptable; strict prevention and avoidance used.

Database Systems

Deadlocks common in transaction management; detection and timeout mechanisms standard.

Distributed Systems

Deadlock detection complex due to lack of global state; distributed algorithms required.

Resource Scheduling

Efficient scheduling and resource allocation critical to minimize deadlock risks.

Case Studies

Unix Operating System

Uses detection and recovery; deadlock rare but possible in file and device management.

Windows OS

Employs prevention and avoidance; resource ordering enforced in kernel drivers.

Database Management Systems (DBMS)

Use wait-die and wound-wait schemes for deadlock prevention in transaction concurrency.

Distributed Systems

Chandy-Misra-Haas algorithm used for distributed deadlock detection.

Embedded Systems

Deadlock prevention prioritized due to real-time constraints.

References

• E. G. Coffman Jr., M. J. Elphick, and A. Shoshani, "System deadlocks," ACM Computing Surveys, vol. 3, no. 2, 1971, pp. 67-78.
• A. Silberschatz, P. B. Galvin, and G. Gagne, Operating System Concepts, 10th ed., Wiley, 2018.