Deadlocks

Two processes are frozen, eternally waiting for each other. Neither can proceed, the system is stuck. This is a deadlock - one of the most insidious problems in parallel programming. How is it prevented or detected?

• **Banking systems:** two threads simultaneously transfer money between the same accounts in different directions - both lock one mutex and wait for the second. The system hangs.
• **Databases:** transaction A locks row X and waits for row Y, transaction B locks Y and waits for X. The DBMS must detect the deadlock and roll back one of the transactions.
• **Operating systems:** processes compete for resources (memory, files, printers). The OS must either prevent deadlocks through smart scheduling or detect and resolve them.

Цели урока

• Name the four Coffman conditions: mutual exclusion, hold-and-wait, no preemption, circular wait
• Draw a resource allocation graph and locate the cycle
• Apply prevention (lock ordering), avoidance (Banker's), detection (wait-for graph in DBs)
• Distinguish deadlock, livelock, and starvation
• Recognize the classics: dining philosophers, reader-writer, sleeping barber

Deadlock Conditions

**Deadlock** is a situation where two or more processes are indefinitely waiting for resources held by each other. The processes are blocked and cannot continue execution.

In 1971, Edward Coffman formulated **four necessary conditions** for the occurrence of a deadlock. All four conditions must be met simultaneously.

**Coffman conditions:** 1. **Mutual Exclusion** - a resource can be used by only one process 2. **Hold and Wait** - a process holds a resource and waits for others 3. **No Preemption** - a resource cannot be forcibly taken away 4. **Circular Wait** - there is a circular chain of resource waiting

Each condition in detail:

**1. Mutual Exclusion** The resource is in a non-shareable mode - only one process can use it at a time. Examples: printer, file in write mode, critical section.

**2. Hold and Wait** A process holding at least one resource is waiting to acquire additional resources held by other processes.

**3. No Preemption** A resource can only be released voluntarily by the process holding it. The operating system cannot forcibly take away the resource.

**4. Circular Wait** There is a circular chain of processes {P₀, P₁, ..., Pₙ}, where P₀ waits for a resource from P₁, P₁ waits for a resource from P₂, ..., Pₙ waits for a resource from P₀.

Resource Graph

**Resource Allocation Graph** is a directed graph for visualizing the system state and detecting deadlocks.

**Graph Elements:** - **Processes (P)** - round nodes - **Resources (R)** - square nodes - **Edges:** - **Request edge** (P → R): process requests a resource - **Assignment edge** (R → P): resource is allocated to a process - Dots inside a resource - number of instances

**Deadlock Theorem:** If the graph **contains no cycles** - deadlock is impossible. If the graph **contains a cycle**: - For resources with **one instance** - deadlock exists - For resources with **multiple instances** - deadlock is possible (but not guaranteed)

**Cycle Detection Algorithm** in the resource allocation graph:

The resource allocation graph reduces deadlock detection to cycle detection on a directed graph: an O(V+E) DFS over the state. The OS kernel can run this periodically to spot deadlocks at runtime.

Deadlock Prevention

**Deadlock Prevention** is a strategy to prevent deadlocks by violating at least one of the four Coffman conditions.

**Methods of deadlock prevention:** 1. **Violate Mutual Exclusion** - make resources shareable 2. **Violate Hold and Wait** - acquire all resources at once 3. **Violate No Preemption** - allow resources to be taken away 4. **Violate Circular Wait** - order resources

**1. Violate Mutual Exclusion** Make resources shareable where possible. Suitable for read-only resources.

**2. Violate Hold and Wait** A process must request all needed resources simultaneously before starting execution.

**3. Violate No Preemption** If a process cannot acquire a resource, it releases all held resources and tries later.

**4. Violate Circular Wait by ordering resources** The most practical method: assign a global order to all resources and always acquire them in this order.

**Banker's Algorithm** A more complex prevention method - the system pre-checks if resource allocation will lead to an unsafe state.

**Choosing a prevention method:** - **Resource ordering** - most practical for most cases - **RW-locks** - for read-heavy loads - **Banker's Algorithm** - when maximum safety is needed (critical systems) - **tryLock + backoff** - for distributed systems

Deadlock Detection

**Deadlock Detection** is a strategy where the system allows deadlocks to occur but periodically detects them and restores operation.

**Detection + Recovery Approach:** 1. **Detection** - periodically check for deadlocks 2. **Recovery** - if detected, resolve it **Recovery Methods:** - Terminate one or more processes - Preempt resources from processes

**Wait-For Graph** For systems with one instance of each resource, the Resource Allocation Graph can be simplified to a Wait-For Graph:

**Deadlock detection for resources with multiple instances:** An algorithm similar to the Banker's Algorithm is used, but it works with the current state:

**Recovery after deadlock detection:**

**When to run Detection?** Trade-off between overhead and response time:

**Detection Frequency:** 1. **Timer-based** - every N seconds - Simple implementation - May miss short deadlocks 2. **Event-based** - when a process blocks - Fast detection - High overhead 3. **Adaptive** - more frequent under high load - Performance balance - More complex to implement

**Detection vs Prevention:** **Prevention:** - ➕ Deadlock never occurs - ➖ Low resource utilization - ➖ Restrictions on request order **Detection + Recovery:** - ➕ High resource utilization - ➕ No restrictions on requests - ➖ Overhead on detection - ➖ Requires recovery mechanism

Key Ideas

• **Coffman's Four Conditions:** all four are needed for a deadlock - mutual exclusion, hold and wait, no preemption, circular wait. Violating at least one prevents deadlock.
• **Resource Allocation Graph:** visualization of the system state. A cycle in the graph indicates a potential (single instance) or possible (multiple instances) deadlock.
• **Prevention vs Detection:** prevention restricts the system to guarantee no deadlock, detection allows more freedom but requires detection and recovery mechanisms.
• **Practical Methods:** resource ordering (violates circular wait) - the simplest and most effective method for most cases. Banker's Algorithm - for critical systems. Detection via wait-for graph - for high-load systems.

Related Topics

Deadlocks are closely related to other concepts of parallelism and synchronization:

• Process Synchronization — Deadlock arises from improper synchronization of access to shared resources
• Semaphores & Mutexes — Basic synchronization primitives, improper use of which leads to deadlock
• CPU Scheduling — The scheduler must consider deadlocks and priorities when allocating CPU

Вопросы для размышления

• Why is the Banker's Algorithm not used in most modern operating systems (Linux, Windows) even though it guarantees no deadlock?
• How should a resource management system for a multithreaded web server be designed? Which strategy is better - prevention or detection?
• In a distributed system (multiple servers), how is a deadlock detected when processes run on different machines and do not share memory?

Связанные уроки

• os-05-sync — Deadlock is the pathological outcome of incorrect synchronization
• os-03-threads — Deadlock is only possible under concurrent access to resources
• os-17-locks-advanced — Lock ordering and lock-free structures are the practical answers to deadlocks
• db-15-locks