Operating SystemsOS Design & Interview

Conceptual Questions

LevelIntermediate

Duration120 mins

TopicOS Design & Interview

3 / 5

Deadlock Conditions

The System That Froze Forever

Imagine a traffic intersection where four cars arrive simultaneously from four directions. Each car needs to cross, but each is blocked by the car to its right. No car can move; no car will yield. They wait forever. This is a deadlock.

In operating systems, deadlocks occur when processes hold resources while waiting for other resources held by other waiting processes, forming a circular dependency that can never resolve. Understanding deadlock—its causes, conditions, prevention, and resolution—is fundamental to operating systems knowledge and a frequent interview topic.

The deceptive simplicity of the question "What are the conditions for deadlock?" belies the depth required for a complete answer. This page provides that depth.

What You Will Master

By the end of this page, you will understand: (1) the precise definition of deadlock and its relationship to resource allocation, (2) the four necessary conditions (Coffman conditions) and why each is necessary, (3) strategies for prevention, avoidance, detection, and recovery, (4) real-world examples and their solutions, and (5) how to articulate this knowledge clearly in interviews.

What Is Deadlock?

A deadlock is a state in which a set of processes are blocked because each process is holding a resource and waiting for a resource held by another process in the set. The processes are stuck in a circular wait, and without external intervention, they will remain blocked forever.

Formal Definition

A set of processes {P₁, P₂, ..., Pₙ} is deadlocked if:

Each process Pᵢ is waiting for a resource Rⱼ
That resource Rⱼ is held by another process Pₖ in the set
The waiting relationships form a cycle

System Model for Deadlock

To analyze deadlock precisely, we model the system as:

Resources: Items that processes need and must request before use

Physical: CPU cycles, memory, I/O devices, files
Logical: Locks, semaphores, database records, network connections

Resource types: Categories of identical resources

Example: "Printers" might have 3 instances; "Mutex A" has 1 instance

Processes: Active entities that request, use, and release resources

Request → Use → Release lifecycle

Resource allocation: The mapping of resources to processes

Represented by a resource-allocation graph

Resource-allocation graph representation

text

Resource-Allocation Graph:
 
Nodes:
  - Process nodes: P₁, P₂, P₃ (circles)
  - Resource nodes: R₁, R₂, R₃ (squares with dots for instances)
 
Edges:
  - Request edge: Pᵢ → Rⱼ  (process wants resource)
  - Assignment edge: Rⱼ → Pᵢ  (resource held by process)
 
Example (Deadlock):
 
     ┌──────────────────────────────────┐
     │           wants                  │
     ▼                                  │
   ┌───┐         ┌───┐         ┌───┐   │
   │ P₁ │ ──────→ │ R₂ │ ──────→ │ P₂ │ ──┘
   └───┘  wants   └───┘  held by └───┘
     ▲                            │
     │    held by                 │ wants
   ┌───┐                        ┌───┐
   │ R₁ │ ←───────────────────── │ R₁ │
   └───┘                        └───┘
 
Cycle: P₁ → R₂ → P₂ → R₁ → P₁
This cycle indicates deadlock (with single-instance resources).

Deadlock vs. Similar Concepts

Deadlock vs. Livelock:

Deadlock: Processes blocked, doing nothing
Livelock: Processes active but making no progress (constantly responding to each other)
Example: Two people in a hallway, both stepping left then right to avoid each other, forever

Deadlock vs. Starvation:

Deadlock: No progress possible; circular wait
Starvation: Progress possible but one process never gets resources
Deadlock is absolute; starvation is relative

Deadlock vs. Race Condition:

Deadlock: No progress, deterministic outcome (stuck)
Race condition: Unintended behavior due to timing, non-deterministic
Different problems, sometimes related (incorrect locking causes both)

The Four Necessary Conditions (Coffman Conditions)

In 1971, E.G. Coffman, M.J. Elphick, and A. Shoshani identified four conditions that must all hold simultaneously for deadlock to occur. These are the Coffman conditions:

Condition 1: Mutual Exclusion

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

Explanation: If resources could be shared by all processes simultaneously, no process would need to wait. Mutual exclusion creates the possibility of waiting.

Examples:

A printer can only print one job at a time
A write lock on a database record excludes other writers
A mutex can only be held by one thread

Why it's necessary: Without mutual exclusion, there's no waiting—processes access resources freely. No waiting means no deadlock.

Mutual Exclusion and Resource Type

Whether mutual exclusion applies depends on the resource. Read-only files can be shared; write access requires exclusion. CPUs can be preempted; printers cannot midway through a job. Understanding which resources truly require exclusion is key to deadlock analysis.

Condition 2: Hold and Wait

Statement: A process must be holding at least one resource and waiting to acquire additional resources currently held by other processes.

Explanation: Processes don't just wait—they wait while holding. This "holding" is what creates the blocking chain.

Examples:

Process holds Lock A, waiting for Lock B (held by another)
Thread holds file handle, waiting for database connection
Transaction holds row lock, waiting for table lock

Why it's necessary: If processes released everything before waiting for more, no process would block another. The "hold" part enables blocking.

Condition 3: No Preemption

Statement: Resources cannot be forcibly taken from a process; they must be released voluntarily by the holder.

Explanation: If the system could take resources away, it could break any blocking chain. Non-preemptability means waits can last indefinitely.

Examples:

Printer mid-job cannot be preempted without corrupting output
Memory can be preempted (swapped out), but locks cannot
File locks cannot be forcibly revoked without data corruption

Why it's necessary: If resources could be preempted, the OS could break cycles by taking resources from one process and giving to another.

Condition 4: Circular Wait

Statement: There must exist a set of waiting processes {P₀, P₁, ..., Pₙ} such that P₀ waits for a resource held by P₁, P₁ waits for a resource held by P₂, ..., and Pₙ waits for a resource held by P₀.

Explanation: The circular dependency is the "trap" that makes deadlock permanent. Without a cycle, eventually some process completes and releases resources.

Example:

P₀ holds R₀, wants R₁
P₁ holds R₁, wants R₂
P₂ holds R₂, wants R₀

Cycle: P₀ → R₁ → P₁ → R₂ → P₂ → R₀ → P₀

Why it's necessary: Circular wait is the defining characteristic. A wait chain that doesn't form a cycle will eventually resolve.

The Four Coffman Conditions Summary
Condition	Description	Key Insight
Mutual Exclusion	Resources cannot be shared	Creates the need to wait
Hold and Wait	Processes hold resources while waiting for more	Enables blocking chains
No Preemption	Resources cannot be forcibly taken	Waits can be indefinite
Circular Wait	Circular chain of processes waiting	Traps processes in loop

All Four Must Hold

Deadlock requires ALL FOUR conditions simultaneously. Breaking any one condition prevents deadlock. Most deadlock prevention strategies focus on eliminating exactly one condition—the easiest one to remove given the system's constraints.

A Classic Deadlock Example

Let's trace a deadlock scenario in detail to see all four conditions in action.

The Dining Philosophers Problem

Five philosophers sit at a round table. Between each pair of philosophers is a single chopstick (5 chopsticks total). Philosophers alternate between thinking and eating. To eat, a philosopher needs both chopsticks adjacent to them.

The problematic algorithm:

while (true) {
    think();
    pick_up(left_chopstick);
    pick_up(right_chopstick);
    eat();
    put_down(right_chopstick);
    put_down(left_chopstick);
}

Deadlock scenario:

All 5 philosophers become hungry simultaneously
Each picks up their left chopstick
Each tries to pick up their right chopstick
No chopstick is available (each is held by the left neighbor)
All 5 philosophers wait forever

Dining philosophers deadlock

text

     P₀ (has C₀, wants C₁)
      ↓
   ┌─────┐
   │ C₀  │━━━━━━━━━━━━━━━━━━━━┓
   └─────┘                   ┃
      ↑                      ▼
   P₄ (has C₄, wants C₀)  ┌─────┐
                          │ C₁  │
                          └─────┘
                             ↓
      ┌─────┐             P₁ (has C₁, wants C₂)
      │ C₄  │
      └─────┘                 ↓
         ↑                 ┌─────┐
         ┃                 │ C₂  │
   P₃ (has C₃, wants C₄)   └─────┘
         ↑                    ↓
      ┌─────┐           P₂ (has C₂, wants C₃)
      │ C₃  │ ←────────────────┛
      └─────┘
 
Cycle: P₀→C₁→P₁→C₂→P₂→C₃→P₃→C₄→P₄→C₀→P₀
 
All four conditions:
1. Mutual Exclusion: Each chopstick used by one philosopher at a time
2. Hold and Wait: Each holds left chopstick, waits for right
3. No Preemption: Cannot take chopstick from philosopher mid-meal
4. Circular Wait: Shown in the diagram above

A Real-World Database Example

Database transactions frequently encounter deadlock potential:

Transaction T₁:

BEGIN TRANSACTION;
UPDATE accounts SET balance = balance - 100 WHERE id = 'A';  -- Locks row A
UPDATE accounts SET balance = balance + 100 WHERE id = 'B';  -- Wants lock on row B
COMMIT;

Transaction T₂:

BEGIN TRANSACTION;
UPDATE accounts SET balance = balance - 50 WHERE id = 'B';   -- Locks row B
UPDATE accounts SET balance = balance + 50 WHERE id = 'A';   -- Wants lock on row A
COMMIT;

Timeline:

Time 1: T₁ acquires lock on row A
Time 2: T₂ acquires lock on row B
Time 3: T₁ requests lock on row B → BLOCKED (T₂ holds it)
Time 4: T₂ requests lock on row A → BLOCKED (T₁ holds it)

Deadlock! Neither can proceed.

Database systems detect this via wait-for graphs and abort one transaction (the victim), allowing the other to complete.

Deadlock Prevention: Breaking the Conditions

Deadlock prevention ensures that at least one of the four necessary conditions can never hold. The system is designed to make deadlock structurally impossible.

Prevention Strategy 1: Eliminate Mutual Exclusion

Approach: Allow resources to be shared rather than exclusive.

Applicability: Limited. Some resources are inherently non-sharable:

A printer cannot be shared mid-job
A write lock must be exclusive for correctness
Spooling can virtualize some resources (print jobs go to disk first)

Example: Instead of directly accessing a printer, processes spool jobs to a queue. The spooler has exclusive access; processes don't wait.

Limitation: Cannot apply to intrinsically mutually exclusive resources.

Prevention Strategy 2: Eliminate Hold and Wait

Approach: Require processes to request all resources before execution, or release all before requesting more.

Technique A: Request all resources at once before starting

request(R1, R2, R3);  // Atomic: get all or get none
// Process can only run if all resources granted

Technique B: Release everything before new requests

release(R1);
request(R2, R1);  // Request again after releasing

Advantages: Simple to implement; guaranteed no deadlock.

Disadvantages:

Low resource utilization: hold resources longer than needed
Starvation: may never get all resources simultaneously
Practicality: not always possible to know all needed resources in advance

Prevention Strategy 3: Allow Preemption

Approach: If a process requests resources it cannot get, preempt (forcibly take) resources from it or from blocking processes.

Technique: If Process P requests resource R (held by Q):

Take R from Q, give to P
Q goes back to waiting state

Applicability: Only works for resources whose state can be saved and restored:

CPU registers ✓ (context switch)
Memory pages ✓ (swap to disk)
Locks ✗ (cannot preempt without breaking invariants)
I/O operations ✗ (cannot preempt mid-transfer)

Example: Memory preemption via swapping. If a process needs memory held by another, pages can be swapped out.

Limitation: Most synchronization resources (locks, semaphores) cannot be preempted without causing inconsistency.

Prevention Strategy 4: Eliminate Circular Wait (Most Common)

Approach: Impose a total ordering on resource types. Processes must request resources in increasing order.

Technique:

Assign a unique number to each resource type: R₁=1, R₂=2, R₃=3, ...
Processes can only request resources with number > all currently held resources

Example:

lock(mutex_1);  // OK: 1 > nothing
lock(mutex_2);  // OK: 2 > 1
// lock(mutex_1); // FORBIDDEN: 1 < 2 (already hold 2)

unlock(mutex_2);
unlock(mutex_1);

Why it works: If all processes request in the same order, cycles cannot form. P₁ waiting for resource with higher number can never be blocked by process waiting for lower number.

Lock ordering prevents deadlock
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// Deadlock-prone code (inconsistent ordering):
// Thread 1:                    // Thread 2:
// lock(A); lock(B);           // lock(B); lock(A);  <-- DANGER
 
// Deadlock-free code (consistent ordering):
// Define order: A < B (A has lower number, must be acquired first)
 
void transfer(Account* from, Account* to, int amount) {
    // Always lock accounts in consistent order (e.g., by address or ID)
    Account* first = (from < to) ? from : to;
    Account* second = (from < to) ? to : from;
    
    lock(first->mutex);   // Lower-numbered resource first
    lock(second->mutex);  // Higher-numbered resource second
    
    from->balance -= amount;
    to->balance += amount;
    
    unlock(second->mutex);
    unlock(first->mutex);
}
 
// Now Thread 1 and Thread 2 both acquire locks in the same order
// No cycle can form; deadlock is impossible

Lock Ordering in Practice

Lock ordering is the most practical prevention technique for application-level deadlock. Many systems establish conventions: acquire locks in order of memory address, resource ID, or hierarchical level. The Linux kernel maintains strict locking hierarchies; lock ordering violations are detected by lockdep during development.

Deadlock Avoidance: Staying Safe Dynamically

Deadlock avoidance allows the system to dynamically decide whether to grant resource requests based on current state. Requests are granted only if the system can remain in a "safe state."

Safe State Concept

A state is safe if the system can allocate resources to each process (up to its maximum need) in some order and avoid deadlock.

Safe state: There exists a sequence of processes <P₁, P₂, ..., Pₙ> such that:

For each Pᵢ, the resources it may still request can be satisfied by currently available resources + resources held by Pⱼ for all j < i

Unsafe state: No safe sequence exists. Deadlock may (but does not necessarily) occur.

Key insight: Safe → Might deadlock? No. Unsafe → Might deadlock? Yes. Being in an unsafe state doesn't mean deadlock has occurred, but it means deadlock is possible based on future requests.

The Banker's Algorithm

The Banker's Algorithm (Dijkstra, 1965) is the classic deadlock avoidance algorithm. It's named after the way a banker must manage limited capital.

Prerequisites:

Each process declares maximum resource needs upfront
Number of resources of each type is known

Data structures:

Available[m]: Available resources of each type
Max[n][m]: Maximum claim of each process
Allocation[n][m]: Resources currently allocated
Need[n][m]: Remaining needs (Max - Allocation)

Banker's Algorithm: Safety Check
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
// Safety Algorithm: Determines if system is in safe state
bool is_safe_state() {
    bool finish[n] = {false};           // Has process finished?
    int work[m];                         // Working copy of available
    memcpy(work, available, sizeof(work));
    
    while (true) {
        // Find a process that can finish
        bool found = false;
        for (int i = 0; i < n; i++) {
            if (!finish[i] && need[i] <= work) {
                // Process i can finish: its needs can be met
                work += allocation[i];   // Release its resources
                finish[i] = true;
                found = true;
            }
        }
        if (!found) break;  // No progress possible
    }
    
    // Safe if all processes can finish
    for (int i = 0; i < n; i++) {
        if (!finish[i]) return false;  // Unsafe: process i cannot finish
    }
    return true;  // Safe: all processes can eventually finish
}
 
// Resource Request Algorithm
bool request_resources(int process_id, int request[]) {
    if (request > need[process_id]) {
        return false;  // Error: exceeds maximum claim
    }
    if (request > available) {
        return false;  // Cannot grant now: not enough available
    }
    
    // Simulate granting the request
    available -= request;
    allocation[process_id] += request;
    need[process_id] -= request;
    
    // Check if resulting state is safe
    if (is_safe_state()) {
        return true;  // Grant request
    } else {
        // Rollback: would result in unsafe state
        available += request;
        allocation[process_id] -= request;
        need[process_id] += request;
        return false;  // Deny request (process must wait)
    }
}

Banker's Algorithm Example

Consider a system with 3 resource types (A, B, C) and 5 processes:

Available: [3, 3, 2]

          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]     [2, 2, 2]   [0, 1, 1]
P4        [0, 0, 2]     [4, 3, 3]   [4, 3, 1]

Safety check:

Work = [3, 3, 2]
P1 needs [1, 2, 2] ≤ [3, 3, 2] → P1 can finish → Work = [5, 3, 2]
P3 needs [0, 1, 1] ≤ [5, 3, 2] → P3 can finish → Work = [7, 4, 3]
P4 needs [4, 3, 1] ≤ [7, 4, 3] → P4 can finish → Work = [7, 4, 5]
P0 needs [7, 4, 3] ≤ [7, 4, 5] → P0 can finish → Work = [7, 5, 5]
P2 needs [6, 0, 0] ≤ [7, 5, 5] → P2 can finish

Safe sequence: <P1, P3, P4, P0, P2>. System is in safe state.

Banker's Algorithm Limitations

The Banker's Algorithm requires knowing maximum resource needs in advance—often impractical. It's computationally expensive (O(n²m) per request). It's primarily of theoretical importance; real systems typically use prevention or detection instead.

Deadlock Detection: Finding It When It Happens

Deadlock detection allows deadlock to occur, then detects and recovers from it. This approach doesn't restrict resource usage patterns.

Detection Algorithm (Single-Instance Resources)

When each resource type has only one instance, detection uses a wait-for graph:

Nodes: Processes
Edge Pᵢ → Pⱼ: Process i is waiting for a resource held by process j
Deadlock exists if and only if the graph contains a cycle

Algorithm: Periodically run cycle detection on the wait-for graph.

DFS-based cycle detection: O(n + e) where n = processes, e = wait relationships
If cycle found, processes in the cycle are deadlocked

Detection Algorithm (Multiple-Instance Resources)

With multiple instances per resource type, we need a more sophisticated algorithm:

Multi-instance deadlock detection
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
// Detection algorithm for multiple-instance resources
// Similar to safety algorithm, but uses current requests, not max claims
 
bool detect_deadlock() {
    bool finish[n];
    int work[m];
    
    // Initialize: mark processes with no allocations as "finished"
    for (int i = 0; i < n; i++) {
        finish[i] = (allocation[i] == 0);  // No resources → cannot be deadlocked
    }
    memcpy(work, available, sizeof(work));
    
    while (true) {
        bool found = false;
        for (int i = 0; i < n; i++) {
            if (!finish[i] && request[i] <= work) {
                // Process i's current request can be satisfied
                work += allocation[i];  // Assume it finishes and releases
                finish[i] = true;
                found = true;
            }
        }
        if (!found) break;
    }
    
    // Deadlock: any process with finish[i] == false is deadlocked
    bool deadlocked = false;
    for (int i = 0; i < n; i++) {
        if (!finish[i]) {
            printf("Process %d is deadlocked\n", i);
            deadlocked = true;
        }
    }
    return deadlocked;
}

When to Run Detection

Options:

Every resource request: Maximum responsiveness, high overhead
Periodically (e.g., every second): Balance between responsiveness and overhead
When CPU utilization drops below threshold: Deadlock often manifests as processes blocking
On explicit request: Administrator or monitoring system triggers

Tradeoff: More frequent detection finds deadlocks faster but consumes CPU cycles.

Real-World Detection: Database Systems

Databases are the most common place where deadlock detection runs actively:

Oracle: Checks every 3 seconds
MySQL/InnoDB: Checks after every lock wait
PostgreSQL: Checks when configurable deadlock_timeout expires

When deadlock is detected, one transaction is selected as a victim and rolled back.

Deadlock Recovery: Breaking Free

Once deadlock is detected, the system must recover. Several strategies exist:

Recovery Strategy 1: Process Termination

Terminate all deadlocked processes:

Guaranteed to break deadlock
Expensive: loses all work done by all processes
Simple to implement

Terminate one process at a time:

Kill one process, rerun detection
If still deadlocked, kill another
Less costly but slower

Victim selection criteria:

Process priority (kill low-priority first)
Computation time (kill those with least invested work)
Resources held (kill those holding most scarce resources)
Remaining work (kill those farthest from completion)
Number of times chosen as victim (fairness)

Recovery Strategy 2: Resource Preemption

Take resources from deadlocked processes:

Select a victim process
Preempt its resources, give to other processes
Roll back victim to a safe state (or terminate)

Challenges:

Not all resources can be preempted (locks, I/O buffers)
Rollback: process must be able to restore to an earlier state
Starvation: same process might be repeatedly selected as victim

Recovery Strategy 3: Rollback

Checkpoint and rollback:

Periodically save process state (checkpoint)
When deadlock detected, roll back victim to checkpoint
Victim restarts from checkpoint, different timing may avoid deadlock

Requirement: System must support checkpointing—common in databases, rare in general OS.

Recovery Strategy Comparison
Strategy	Pros	Cons	Use Case
Kill all	Simple, guaranteed	Loses all work	Simple embedded systems
Kill one at a time	Less loss	Repeated detection	General purpose
Resource preemption	Minimal disruption	Complex, not always possible	Specialized resources
Rollback to checkpoint	Recoverable, fair	Requires checkpointing	Databases, VMs

Database deadlock recovery
SQL
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
-- When database detects deadlock:
 
-- 1. Identify deadlocked transactions (e.g., T1 and T2)
 
-- 2. Select victim (lowest cost to abort)
--    - Fewest locks held
--    - Least work done
--    - Least number of undo operations
 
-- 3. Abort victim transaction
ROLLBACK TRANSACTION T1;
 
-- 4. Release all locks held by T1
-- 5. T2 can now proceed
COMMIT TRANSACTION T2;
 
-- 6. T1 must retry from beginning
BEGIN TRANSACTION;
-- T1's SQL statements again...
COMMIT;
 
-- Note: Application must handle "deadlock victim" errors
-- and retry the transaction

Combined Approaches in Practice

Real systems typically combine multiple deadlock handling strategies, applying different approaches to different resource types.

The Ostrich Algorithm

Approach: Ignore the problem entirely. Pretend deadlock doesn't happen.

Rationale:

Deadlock is rare in practice
Prevention/avoidance overhead may exceed cost of occasional deadlock
Reboot is acceptable recovery in many contexts

Usage: Unix/Linux historically used this for many resources. Windows similarly. Web servers often rely on request timeouts.

When appropriate:

Deadlock probability is very low
Cost of detection/prevention exceeds cost of occasional restart
System is interactive and users can notice hangs

Hierarchical Approach

Modern systems use different strategies for different resource classes:

Resource-Specific Strategies

•Internal kernel resources: Prevention through lock ordering hierarchies. Linux's lockdep tool detects potential violations.
•Swappable memory: Preemption allowed—pages can be swapped out to break memory deadlocks.
•Device allocation: Spooling (virtualization) eliminates mutual exclusion for printers, etc.
•Process resources: Ignore (ostrich) and rely on timeouts or user intervention.
•Database transactions: Active detection and rollback. Transactions are atomic, so rollback is clean.
•Distributed systems: Timeouts, lease expiration, and transaction managers with global deadlock detection.

Pragmatic Engineering

The "right" deadlock strategy depends on context. Databases can't ignore deadlock (data integrity matters). Desktop OS can often ignore it (users restart). Embedded systems might prevent entirely (strict static allocation). Real-time systems may use avoidance (predictable response required). There is no universal answer.

Structuring the Interview Answer

When asked "What are the conditions for deadlock?" or "How do you handle deadlock?", structure your answer to demonstrate comprehensive understanding.

The Four Conditions Answer

Framework for Conditions Question

•State the four conditions clearly: Mutual exclusion, hold and wait, no preemption, circular wait.
•Emphasize ALL must hold: Deadlock requires all four simultaneously; breaking any one prevents deadlock.
•Give a brief example: Dining philosophers, database transactions, or simple two-lock scenario.
•Mention that prevention typically targets one condition: Lock ordering breaks circular wait; release-before-request breaks hold-and-wait.

The Handling Strategies Answer

Framework for Handling Question

•Prevention: Design system so one condition can never hold. Lock ordering is most common. Mention tradeoffs (restricts flexibility).
•Avoidance: Dynamically check if granting request keeps system safe. Banker's algorithm. Mention limitations (need max claims).
•Detection and recovery: Allow deadlock, detect cycles, kill/rollback. Common in databases. Mention when it's appropriate.
•Ignore (ostrich): If rare and recovery is cheap (reboot), ignore. Pragmatic for general-purpose OS.

Demonstrating Depth

Strong answers: (1) Know all four conditions by name and meaning, (2) Understand why ALL are necessary, (3) Can explain prevention techniques for each condition, (4) Know the difference between prevention and avoidance, (5) Can discuss real-world approaches (databases detect/rollback, kernels prevent with lock ordering, general OS ignores).

Summary: Deadlock Conditions

Deadlock is a fundamental challenge in concurrent systems. Let's consolidate the key insights:

Key Takeaways

•Deadlock requires ALL four conditions simultaneously: Mutual exclusion, hold and wait, no preemption, circular wait. Breaking any one prevents deadlock.
•Prevention eliminates a condition by design: Lock ordering (breaks circular wait) is most practical for application code.
•Avoidance checks safety before granting requests: Banker's algorithm is theoretically important but rarely used in practice.
•Detection and recovery allow deadlock, then fix it: Databases use this approach—detect cycles, abort victim, retry.
•The ostrich algorithm ignores the problem: Acceptable when deadlock is rare and restart is tolerable.
•Real systems combine strategies: Different resources get different treatment based on their characteristics.
•Lock ordering is the developer's friend: Consistent acquisition order is the simplest, most effective prevention technique.

What's Next:

Having mastered deadlock theory, we'll move to the next essential interview topic: File System Comparisons. Understanding the tradeoffs between different file system designs—journaling, copy-on-write, log-structured—demonstrates systems thinking that interviewers value.

Page Complete

You now possess complete knowledge of deadlock theory—from the four conditions through prevention, avoidance, detection, and recovery. This understanding applies to operating systems, databases, distributed systems, and any concurrent programming context.

3 / 5

Loading learning content...

Operating SystemsOS Design & Interview

Conceptual Questions

LevelIntermediate

Duration120 mins

TopicOS Design & Interview

3 / 5

Deadlock Conditions

The System That Froze Forever

The deceptive simplicity of the question "What are the conditions for deadlock?" belies the depth required for a complete answer. This page provides that depth.

What You Will Master

What Is Deadlock?

Formal Definition

A set of processes {P₁, P₂, ..., Pₙ} is deadlocked if:

Each process Pᵢ is waiting for a resource Rⱼ
That resource Rⱼ is held by another process Pₖ in the set
The waiting relationships form a cycle

System Model for Deadlock

To analyze deadlock precisely, we model the system as:

Resources: Items that processes need and must request before use

Physical: CPU cycles, memory, I/O devices, files
Logical: Locks, semaphores, database records, network connections

Resource types: Categories of identical resources

Example: "Printers" might have 3 instances; "Mutex A" has 1 instance

Processes: Active entities that request, use, and release resources

Request → Use → Release lifecycle

Resource allocation: The mapping of resources to processes

Represented by a resource-allocation graph

Resource-allocation graph representation

text

Resource-Allocation Graph:
 
Nodes:
  - Process nodes: P₁, P₂, P₃ (circles)
  - Resource nodes: R₁, R₂, R₃ (squares with dots for instances)
 
Edges:
  - Request edge: Pᵢ → Rⱼ  (process wants resource)
  - Assignment edge: Rⱼ → Pᵢ  (resource held by process)
 
Example (Deadlock):
 
     ┌──────────────────────────────────┐
     │           wants                  │
     ▼                                  │
   ┌───┐         ┌───┐         ┌───┐   │
   │ P₁ │ ──────→ │ R₂ │ ──────→ │ P₂ │ ──┘
   └───┘  wants   └───┘  held by └───┘
     ▲                            │
     │    held by                 │ wants
   ┌───┐                        ┌───┐
   │ R₁ │ ←───────────────────── │ R₁ │
   └───┘                        └───┘
 
Cycle: P₁ → R₂ → P₂ → R₁ → P₁
This cycle indicates deadlock (with single-instance resources).

Deadlock vs. Similar Concepts

Deadlock vs. Livelock:

Deadlock: Processes blocked, doing nothing
Livelock: Processes active but making no progress (constantly responding to each other)
Example: Two people in a hallway, both stepping left then right to avoid each other, forever

Deadlock vs. Starvation:

Deadlock: No progress possible; circular wait
Starvation: Progress possible but one process never gets resources
Deadlock is absolute; starvation is relative

Deadlock vs. Race Condition:

Deadlock: No progress, deterministic outcome (stuck)
Race condition: Unintended behavior due to timing, non-deterministic
Different problems, sometimes related (incorrect locking causes both)

The Four Necessary Conditions (Coffman Conditions)

In 1971, E.G. Coffman, M.J. Elphick, and A. Shoshani identified four conditions that must all hold simultaneously for deadlock to occur. These are the Coffman conditions:

Condition 1: Mutual Exclusion

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

Explanation: If resources could be shared by all processes simultaneously, no process would need to wait. Mutual exclusion creates the possibility of waiting.

Examples:

A printer can only print one job at a time
A write lock on a database record excludes other writers
A mutex can only be held by one thread

Why it's necessary: Without mutual exclusion, there's no waiting—processes access resources freely. No waiting means no deadlock.

Mutual Exclusion and Resource Type

Condition 2: Hold and Wait

Statement: A process must be holding at least one resource and waiting to acquire additional resources currently held by other processes.

Explanation: Processes don't just wait—they wait while holding. This "holding" is what creates the blocking chain.

Examples:

Process holds Lock A, waiting for Lock B (held by another)
Thread holds file handle, waiting for database connection
Transaction holds row lock, waiting for table lock

Why it's necessary: If processes released everything before waiting for more, no process would block another. The "hold" part enables blocking.

Condition 3: No Preemption

Statement: Resources cannot be forcibly taken from a process; they must be released voluntarily by the holder.

Explanation: If the system could take resources away, it could break any blocking chain. Non-preemptability means waits can last indefinitely.

Examples:

Printer mid-job cannot be preempted without corrupting output
Memory can be preempted (swapped out), but locks cannot
File locks cannot be forcibly revoked without data corruption

Why it's necessary: If resources could be preempted, the OS could break cycles by taking resources from one process and giving to another.

Condition 4: Circular Wait

Explanation: The circular dependency is the "trap" that makes deadlock permanent. Without a cycle, eventually some process completes and releases resources.

Example:

P₀ holds R₀, wants R₁
P₁ holds R₁, wants R₂
P₂ holds R₂, wants R₀

Cycle: P₀ → R₁ → P₁ → R₂ → P₂ → R₀ → P₀

Why it's necessary: Circular wait is the defining characteristic. A wait chain that doesn't form a cycle will eventually resolve.

The Four Coffman Conditions Summary
Condition	Description	Key Insight
Mutual Exclusion	Resources cannot be shared	Creates the need to wait
Hold and Wait	Processes hold resources while waiting for more	Enables blocking chains
No Preemption	Resources cannot be forcibly taken	Waits can be indefinite
Circular Wait	Circular chain of processes waiting	Traps processes in loop

All Four Must Hold

A Classic Deadlock Example

Let's trace a deadlock scenario in detail to see all four conditions in action.

The Dining Philosophers Problem

The problematic algorithm:

while (true) {
    think();
    pick_up(left_chopstick);
    pick_up(right_chopstick);
    eat();
    put_down(right_chopstick);
    put_down(left_chopstick);
}

Deadlock scenario:

All 5 philosophers become hungry simultaneously
Each picks up their left chopstick
Each tries to pick up their right chopstick
No chopstick is available (each is held by the left neighbor)
All 5 philosophers wait forever

Dining philosophers deadlock

text

     P₀ (has C₀, wants C₁)
      ↓
   ┌─────┐
   │ C₀  │━━━━━━━━━━━━━━━━━━━━┓
   └─────┘                   ┃
      ↑                      ▼
   P₄ (has C₄, wants C₀)  ┌─────┐
                          │ C₁  │
                          └─────┘
                             ↓
      ┌─────┐             P₁ (has C₁, wants C₂)
      │ C₄  │
      └─────┘                 ↓
         ↑                 ┌─────┐
         ┃                 │ C₂  │
   P₃ (has C₃, wants C₄)   └─────┘
         ↑                    ↓
      ┌─────┐           P₂ (has C₂, wants C₃)
      │ C₃  │ ←────────────────┛
      └─────┘
 
Cycle: P₀→C₁→P₁→C₂→P₂→C₃→P₃→C₄→P₄→C₀→P₀
 
All four conditions:
1. Mutual Exclusion: Each chopstick used by one philosopher at a time
2. Hold and Wait: Each holds left chopstick, waits for right
3. No Preemption: Cannot take chopstick from philosopher mid-meal
4. Circular Wait: Shown in the diagram above

A Real-World Database Example

Database transactions frequently encounter deadlock potential:

Transaction T₁:

BEGIN TRANSACTION;
UPDATE accounts SET balance = balance - 100 WHERE id = 'A';  -- Locks row A
UPDATE accounts SET balance = balance + 100 WHERE id = 'B';  -- Wants lock on row B
COMMIT;

Transaction T₂:

BEGIN TRANSACTION;
UPDATE accounts SET balance = balance - 50 WHERE id = 'B';   -- Locks row B
UPDATE accounts SET balance = balance + 50 WHERE id = 'A';   -- Wants lock on row A
COMMIT;

Timeline:

Time 1: T₁ acquires lock on row A
Time 2: T₂ acquires lock on row B
Time 3: T₁ requests lock on row B → BLOCKED (T₂ holds it)
Time 4: T₂ requests lock on row A → BLOCKED (T₁ holds it)

Deadlock! Neither can proceed.

Database systems detect this via wait-for graphs and abort one transaction (the victim), allowing the other to complete.

Deadlock Prevention: Breaking the Conditions

Deadlock prevention ensures that at least one of the four necessary conditions can never hold. The system is designed to make deadlock structurally impossible.

Prevention Strategy 1: Eliminate Mutual Exclusion

Approach: Allow resources to be shared rather than exclusive.

Applicability: Limited. Some resources are inherently non-sharable:

A printer cannot be shared mid-job
A write lock must be exclusive for correctness
Spooling can virtualize some resources (print jobs go to disk first)

Example: Instead of directly accessing a printer, processes spool jobs to a queue. The spooler has exclusive access; processes don't wait.

Limitation: Cannot apply to intrinsically mutually exclusive resources.

Prevention Strategy 2: Eliminate Hold and Wait

Approach: Require processes to request all resources before execution, or release all before requesting more.

Technique A: Request all resources at once before starting

request(R1, R2, R3);  // Atomic: get all or get none
// Process can only run if all resources granted

Technique B: Release everything before new requests

release(R1);
request(R2, R1);  // Request again after releasing

Advantages: Simple to implement; guaranteed no deadlock.

Disadvantages:

Low resource utilization: hold resources longer than needed
Starvation: may never get all resources simultaneously
Practicality: not always possible to know all needed resources in advance

Prevention Strategy 3: Allow Preemption

Approach: If a process requests resources it cannot get, preempt (forcibly take) resources from it or from blocking processes.

Technique: If Process P requests resource R (held by Q):

Take R from Q, give to P
Q goes back to waiting state

Applicability: Only works for resources whose state can be saved and restored:

CPU registers ✓ (context switch)
Memory pages ✓ (swap to disk)
Locks ✗ (cannot preempt without breaking invariants)
I/O operations ✗ (cannot preempt mid-transfer)

Example: Memory preemption via swapping. If a process needs memory held by another, pages can be swapped out.

Limitation: Most synchronization resources (locks, semaphores) cannot be preempted without causing inconsistency.

Prevention Strategy 4: Eliminate Circular Wait (Most Common)

Approach: Impose a total ordering on resource types. Processes must request resources in increasing order.

Technique:

Assign a unique number to each resource type: R₁=1, R₂=2, R₃=3, ...
Processes can only request resources with number > all currently held resources

Example:

lock(mutex_1);  // OK: 1 > nothing
lock(mutex_2);  // OK: 2 > 1
// lock(mutex_1); // FORBIDDEN: 1 < 2 (already hold 2)

unlock(mutex_2);
unlock(mutex_1);

Why it works: If all processes request in the same order, cycles cannot form. P₁ waiting for resource with higher number can never be blocked by process waiting for lower number.

Lock ordering prevents deadlock
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// Deadlock-prone code (inconsistent ordering):
// Thread 1:                    // Thread 2:
// lock(A); lock(B);           // lock(B); lock(A);  <-- DANGER
 
// Deadlock-free code (consistent ordering):
// Define order: A < B (A has lower number, must be acquired first)
 
void transfer(Account* from, Account* to, int amount) {
    // Always lock accounts in consistent order (e.g., by address or ID)
    Account* first = (from < to) ? from : to;
    Account* second = (from < to) ? to : from;
    
    lock(first->mutex);   // Lower-numbered resource first
    lock(second->mutex);  // Higher-numbered resource second
    
    from->balance -= amount;
    to->balance += amount;
    
    unlock(second->mutex);
    unlock(first->mutex);
}
 
// Now Thread 1 and Thread 2 both acquire locks in the same order
// No cycle can form; deadlock is impossible

Lock Ordering in Practice

Deadlock Avoidance: Staying Safe Dynamically

Deadlock avoidance allows the system to dynamically decide whether to grant resource requests based on current state. Requests are granted only if the system can remain in a "safe state."

Safe State Concept

A state is safe if the system can allocate resources to each process (up to its maximum need) in some order and avoid deadlock.

Safe state: There exists a sequence of processes <P₁, P₂, ..., Pₙ> such that:

For each Pᵢ, the resources it may still request can be satisfied by currently available resources + resources held by Pⱼ for all j < i

Unsafe state: No safe sequence exists. Deadlock may (but does not necessarily) occur.

The Banker's Algorithm

The Banker's Algorithm (Dijkstra, 1965) is the classic deadlock avoidance algorithm. It's named after the way a banker must manage limited capital.

Prerequisites:

Each process declares maximum resource needs upfront
Number of resources of each type is known

Data structures:

Available[m]: Available resources of each type
Max[n][m]: Maximum claim of each process
Allocation[n][m]: Resources currently allocated
Need[n][m]: Remaining needs (Max - Allocation)

Banker's Algorithm: Safety Check
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
// Safety Algorithm: Determines if system is in safe state
bool is_safe_state() {
    bool finish[n] = {false};           // Has process finished?
    int work[m];                         // Working copy of available
    memcpy(work, available, sizeof(work));
    
    while (true) {
        // Find a process that can finish
        bool found = false;
        for (int i = 0; i < n; i++) {
            if (!finish[i] && need[i] <= work) {
                // Process i can finish: its needs can be met
                work += allocation[i];   // Release its resources
                finish[i] = true;
                found = true;
            }
        }
        if (!found) break;  // No progress possible
    }
    
    // Safe if all processes can finish
    for (int i = 0; i < n; i++) {
        if (!finish[i]) return false;  // Unsafe: process i cannot finish
    }
    return true;  // Safe: all processes can eventually finish
}
 
// Resource Request Algorithm
bool request_resources(int process_id, int request[]) {
    if (request > need[process_id]) {
        return false;  // Error: exceeds maximum claim
    }
    if (request > available) {
        return false;  // Cannot grant now: not enough available
    }
    
    // Simulate granting the request
    available -= request;
    allocation[process_id] += request;
    need[process_id] -= request;
    
    // Check if resulting state is safe
    if (is_safe_state()) {
        return true;  // Grant request
    } else {
        // Rollback: would result in unsafe state
        available += request;
        allocation[process_id] -= request;
        need[process_id] += request;
        return false;  // Deny request (process must wait)
    }
}

Banker's Algorithm Example

Consider a system with 3 resource types (A, B, C) and 5 processes:

Available: [3, 3, 2]

          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]     [2, 2, 2]   [0, 1, 1]
P4        [0, 0, 2]     [4, 3, 3]   [4, 3, 1]

Safety check:

Work = [3, 3, 2]
P1 needs [1, 2, 2] ≤ [3, 3, 2] → P1 can finish → Work = [5, 3, 2]
P3 needs [0, 1, 1] ≤ [5, 3, 2] → P3 can finish → Work = [7, 4, 3]
P4 needs [4, 3, 1] ≤ [7, 4, 3] → P4 can finish → Work = [7, 4, 5]
P0 needs [7, 4, 3] ≤ [7, 4, 5] → P0 can finish → Work = [7, 5, 5]
P2 needs [6, 0, 0] ≤ [7, 5, 5] → P2 can finish

Safe sequence: <P1, P3, P4, P0, P2>. System is in safe state.

Banker's Algorithm Limitations

Deadlock Detection: Finding It When It Happens

Deadlock detection allows deadlock to occur, then detects and recovers from it. This approach doesn't restrict resource usage patterns.

Detection Algorithm (Single-Instance Resources)

When each resource type has only one instance, detection uses a wait-for graph:

Nodes: Processes
Edge Pᵢ → Pⱼ: Process i is waiting for a resource held by process j
Deadlock exists if and only if the graph contains a cycle

Algorithm: Periodically run cycle detection on the wait-for graph.

DFS-based cycle detection: O(n + e) where n = processes, e = wait relationships
If cycle found, processes in the cycle are deadlocked

Detection Algorithm (Multiple-Instance Resources)

With multiple instances per resource type, we need a more sophisticated algorithm:

Multi-instance deadlock detection
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
// Detection algorithm for multiple-instance resources
// Similar to safety algorithm, but uses current requests, not max claims
 
bool detect_deadlock() {
    bool finish[n];
    int work[m];
    
    // Initialize: mark processes with no allocations as "finished"
    for (int i = 0; i < n; i++) {
        finish[i] = (allocation[i] == 0);  // No resources → cannot be deadlocked
    }
    memcpy(work, available, sizeof(work));
    
    while (true) {
        bool found = false;
        for (int i = 0; i < n; i++) {
            if (!finish[i] && request[i] <= work) {
                // Process i's current request can be satisfied
                work += allocation[i];  // Assume it finishes and releases
                finish[i] = true;
                found = true;
            }
        }
        if (!found) break;
    }
    
    // Deadlock: any process with finish[i] == false is deadlocked
    bool deadlocked = false;
    for (int i = 0; i < n; i++) {
        if (!finish[i]) {
            printf("Process %d is deadlocked\n", i);
            deadlocked = true;
        }
    }
    return deadlocked;
}

When to Run Detection

Options:

Every resource request: Maximum responsiveness, high overhead
Periodically (e.g., every second): Balance between responsiveness and overhead
When CPU utilization drops below threshold: Deadlock often manifests as processes blocking
On explicit request: Administrator or monitoring system triggers

Tradeoff: More frequent detection finds deadlocks faster but consumes CPU cycles.

Real-World Detection: Database Systems

Databases are the most common place where deadlock detection runs actively:

Oracle: Checks every 3 seconds
MySQL/InnoDB: Checks after every lock wait
PostgreSQL: Checks when configurable deadlock_timeout expires

When deadlock is detected, one transaction is selected as a victim and rolled back.

Deadlock Recovery: Breaking Free

Once deadlock is detected, the system must recover. Several strategies exist:

Recovery Strategy 1: Process Termination

Terminate all deadlocked processes:

Guaranteed to break deadlock
Expensive: loses all work done by all processes
Simple to implement

Terminate one process at a time:

Kill one process, rerun detection
If still deadlocked, kill another
Less costly but slower

Victim selection criteria:

Process priority (kill low-priority first)
Computation time (kill those with least invested work)
Resources held (kill those holding most scarce resources)
Remaining work (kill those farthest from completion)
Number of times chosen as victim (fairness)

Recovery Strategy 2: Resource Preemption

Take resources from deadlocked processes:

Select a victim process
Preempt its resources, give to other processes
Roll back victim to a safe state (or terminate)

Challenges:

Not all resources can be preempted (locks, I/O buffers)
Rollback: process must be able to restore to an earlier state
Starvation: same process might be repeatedly selected as victim

Recovery Strategy 3: Rollback

Checkpoint and rollback:

Periodically save process state (checkpoint)
When deadlock detected, roll back victim to checkpoint
Victim restarts from checkpoint, different timing may avoid deadlock

Requirement: System must support checkpointing—common in databases, rare in general OS.

Recovery Strategy Comparison
Strategy	Pros	Cons	Use Case
Kill all	Simple, guaranteed	Loses all work	Simple embedded systems
Kill one at a time	Less loss	Repeated detection	General purpose
Resource preemption	Minimal disruption	Complex, not always possible	Specialized resources
Rollback to checkpoint	Recoverable, fair	Requires checkpointing	Databases, VMs

Database deadlock recovery
SQL
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
-- When database detects deadlock:
 
-- 1. Identify deadlocked transactions (e.g., T1 and T2)
 
-- 2. Select victim (lowest cost to abort)
--    - Fewest locks held
--    - Least work done
--    - Least number of undo operations
 
-- 3. Abort victim transaction
ROLLBACK TRANSACTION T1;
 
-- 4. Release all locks held by T1
-- 5. T2 can now proceed
COMMIT TRANSACTION T2;
 
-- 6. T1 must retry from beginning
BEGIN TRANSACTION;
-- T1's SQL statements again...
COMMIT;
 
-- Note: Application must handle "deadlock victim" errors
-- and retry the transaction

Combined Approaches in Practice

Real systems typically combine multiple deadlock handling strategies, applying different approaches to different resource types.

The Ostrich Algorithm

Approach: Ignore the problem entirely. Pretend deadlock doesn't happen.

Rationale:

Deadlock is rare in practice
Prevention/avoidance overhead may exceed cost of occasional deadlock
Reboot is acceptable recovery in many contexts

Usage: Unix/Linux historically used this for many resources. Windows similarly. Web servers often rely on request timeouts.

When appropriate:

Deadlock probability is very low
Cost of detection/prevention exceeds cost of occasional restart
System is interactive and users can notice hangs

Hierarchical Approach

Modern systems use different strategies for different resource classes:

Resource-Specific Strategies

•Internal kernel resources: Prevention through lock ordering hierarchies. Linux's lockdep tool detects potential violations.
•Swappable memory: Preemption allowed—pages can be swapped out to break memory deadlocks.
•Device allocation: Spooling (virtualization) eliminates mutual exclusion for printers, etc.
•Process resources: Ignore (ostrich) and rely on timeouts or user intervention.
•Database transactions: Active detection and rollback. Transactions are atomic, so rollback is clean.
•Distributed systems: Timeouts, lease expiration, and transaction managers with global deadlock detection.

Pragmatic Engineering

Structuring the Interview Answer

When asked "What are the conditions for deadlock?" or "How do you handle deadlock?", structure your answer to demonstrate comprehensive understanding.

The Four Conditions Answer

Framework for Conditions Question

•State the four conditions clearly: Mutual exclusion, hold and wait, no preemption, circular wait.
•Emphasize ALL must hold: Deadlock requires all four simultaneously; breaking any one prevents deadlock.
•Give a brief example: Dining philosophers, database transactions, or simple two-lock scenario.
•Mention that prevention typically targets one condition: Lock ordering breaks circular wait; release-before-request breaks hold-and-wait.

The Handling Strategies Answer

Framework for Handling Question

•Prevention: Design system so one condition can never hold. Lock ordering is most common. Mention tradeoffs (restricts flexibility).
•Avoidance: Dynamically check if granting request keeps system safe. Banker's algorithm. Mention limitations (need max claims).
•Detection and recovery: Allow deadlock, detect cycles, kill/rollback. Common in databases. Mention when it's appropriate.
•Ignore (ostrich): If rare and recovery is cheap (reboot), ignore. Pragmatic for general-purpose OS.

Demonstrating Depth

Summary: Deadlock Conditions

Deadlock is a fundamental challenge in concurrent systems. Let's consolidate the key insights:

Key Takeaways

•Deadlock requires ALL four conditions simultaneously: Mutual exclusion, hold and wait, no preemption, circular wait. Breaking any one prevents deadlock.
•Prevention eliminates a condition by design: Lock ordering (breaks circular wait) is most practical for application code.
•Avoidance checks safety before granting requests: Banker's algorithm is theoretically important but rarely used in practice.
•Detection and recovery allow deadlock, then fix it: Databases use this approach—detect cycles, abort victim, retry.
•The ostrich algorithm ignores the problem: Acceptable when deadlock is rare and restart is tolerable.
•Real systems combine strategies: Different resources get different treatment based on their characteristics.
•Lock ordering is the developer's friend: Consistent acquisition order is the simplest, most effective prevention technique.

What's Next:

Page Complete

3 / 5