OS - CH8 Deadlocks

Deadlock

A situation where a set of processes are blocked because each is holding a resource and waiting for another resource acquired by some other process in the set.

Four Conditions for Deadlock

1. Mutual Exclusion 2. Hold and Wait 3. No Preemption 4. Circular Wait

Mutual Exclusion

Only one process at a time can use a resource (e.g., printer, mutex lock).

Hold and Wait

A process holds at least one resource while waiting for additional resources held by other processes.

No Preemption

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

Circular Wait

A set of processes {P0, P1, …, Pn} exists where P0 waits for P1, P1 waits for P2, …, Pn waits for P0.

Resource-Allocation Graph (RAG)

A directed graph with processes (P), resources (R), request edges (P→R), and assignment edges (R→P).

Deadlock Prevention

Design a system to negate at least one of the four deadlock conditions (e.g., enforce resource ordering to break circular wait).

Deadlock Avoidance

Dynamically checks if granting a resource request could lead to an unsafe state (e.g., Banker's Algorithm).

Safe State

A state where the system can allocate resources to each process in some order to avoid deadlock (i.e., a safe sequence exists).

Banker's Algorithm

A deadlock avoidance algorithm that checks for safe states using matrices for Available, Max, Allocation, and Need.

Deadlock Detection

Allows deadlocks to occur, then detects them using algorithms (e.g., wait-for graphs for single-instance resources).

Wait-for Graph

A reduced RAG where nodes are processes, and edges (Pi→Pj) indicate Pi is waiting for Pj to release a resource.

Recovery from Deadlock

1. Process Termination: Abort all or one process at a time. 2. Resource Preemption: Roll back processes and reassign resources.

Resource Ordering (Prevention)

Assign a total order to resource types; processes must request resources in increasing order to prevent circular wait.

Unsafe State

A state where no safe sequence exists; may lead to deadlock if processes request resources aggressively.

Starvation in Recovery

A process is repeatedly chosen as the victim for preemption, causing it to never complete.

Ostrich Algorithm

Ignore deadlocks (used by some OSes like UNIX for low-probability scenarios).

Claim Edge (RAG)

A dashed line (Pi→Rj) indicating Pi may request Rj in the future (used in avoidance).

Detection Algorithm Complexity

O(m×n²) operations for m resource types and n processes.

Example of Circular Wait

Thread 1 holds Lock A and waits for Lock B; Thread 2 holds Lock B and waits for Lock A.

Preemption (Recovery)

Forcibly take resources from a victim process and allocate them to others.

Banker's Algorithm: Need Matrix

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

Deadlock vs. Starvation

• Deadlock: All processes in the set are blocked.
• Starvation: A process is indefinitely delayed due to resource allocation policies.

Single-Instance Deadlock Detection

Use a wait-for graph and check for cycles.

Multi-Instance Deadlock Detection

Use a detection algorithm similar to the Banker's Algorithm.

Process Termination Criteria

Consider priority, runtime, resource usage, and interactivity when choosing a victim.

Safe Sequence

An order of process execution where each process can obtain needed resources without deadlock.

Example of Safe State

Available = [3,3,2], and processes can complete in order

No Preemption (Prevention)

If a process can't get a resource, it releases all held resources and restarts.

Hold and Wait (Prevention)

Require processes to request all resources upfront or release all before new requests.

Mutual Exclusion (Prevention)

Only applicable to non-sharable resources (e.g., printers). Sharable resources (e.g., read-only files) don't need it.

Banker's Algorithm: Safety Algorithm

Checks if a safe sequence exists by simulating resource allocation.

Banker's Algorithm: Resource-Request Algorithm

Grants a request only if it leaves the system in a safe state.

Deadlock Detection Frequency

Trade-off between overhead (frequent checks) and undetected deadlocks (infrequent checks).

Example of Deadlock Avoidance

Grant P1's request (1,0,2) only if it leads to a safe state.

Rollback (Recovery)

Reset a victim process to a prior state and reassign its resources.

Priority Inheritance (Deadlock Prevention)

Temporarily raise a low-priority process's priority if it holds a resource needed by a high-priority process.

Deadlock in Databases

Transactions waiting for locks (e.g., T1 locks A, T2 locks B; T1 waits for B, T2 waits for A).

Phantom Deadlock

False detection due to transient conditions (e.g., delayed messages in distributed systems).

Livelock

Processes keep changing state but make no progress (e.g., repeated preemption and restart).

Deadlock Ignorance

Assumes deadlocks are rare (e.g., Ostrich Algorithm).

Example of Hold and Wait

Process holds a scanner while waiting for a printer.

Example of No Preemption

A process holding a mutex lock cannot be forced to release it.

Example of Circular Wait

P0 waits for P1's file, P1 waits for P2's CPU, P2 waits for P0's memory.

Deadlock in Real Systems

Common in databases, OS kernels, and multithreaded applications.

Prevention vs. Avoidance vs. Detection

• Prevention: Static rules (e.g., resource ordering).
• Avoidance: Dynamic checks (e.g., Banker's Algorithm).
• Detection: Periodic cycle checks.

Practical Deadlock Handling

Most OSes use detection + recovery or ignore (due to low frequency).