Deadlock

operating-systems concurrency

Definition

Deadlock

A deadlock is a situation in concurrent computing where a set of processes are unable to proceed because each process is waiting for a resource held by another process in the set, forming a circular chain of dependency.

A deadlock occurs when processes “mutually obstruct” each other. For example, Process 1 holds Resource A and requests Resource B, while Process 2 holds Resource B and requests Resource A.

Examples

1. The Roundabout (Kreisverkehr)

In a roundabout with a “right of way” rule, a deadlock occurs if four cars enter the roundabout simultaneously. Each car occupies a segment of the road (resource) and is waiting for the segment in front of it to be vacated. No car can move forward, creating a circular wait.

2. Message Synchronisation

In a system using message passing, Process $P_1$ performs a blocking receive from $P_2$, while $P_2$ simultaneously performs a blocking receive from $P_1$. Since both processes are waiting for a message (consumable resource) that will never be sent, they are deadlocked.

Formal Analysis

Joint Progress Diagram

A joint progress diagram is a graphical tool used to illustrate the potential for deadlock when two processes compete for multiple resources.

• Axes: Each axis represents the progress of one process.
• Unsafe Region: A rectangular area representing states where both processes require the same resource simultaneously.
• Deadlock Potential: If the execution path (the sequence of resource acquisitions) enters a specific “no-man’s land” leading to the unsafe region, the processes will eventually block each other.

Integrated Deadlock Strategy

In practice, a single strategy is often insufficient. An integrated deadlock strategy combines different approaches by grouping resources into classes and applying the most suitable method to each:

• Circular Wait Prevention: Establish a strict linear ordering between resource classes.
• Resource Classes:
  • Swappable Space: Memory blocks on secondary storage.
  • Process Resources: I/O devices and files.
  • Main Memory: RAM assigned to processes.
• Strategy Mix: For example, using preemption for main memory (via swapping) and avoidance for complex process resources.

Conditions for Deadlock

Typically, four conditions, known as the Coffman conditions, must hold simultaneously for a deadlock to occur:

Definition

Coffman Conditions

The Coffman conditions are a set of four necessary requirements that must hold simultaneously for a deadlock to occur in a system. They were first identified by Edward G. Coffman, Jr. in 1971.

For a deadlock to exist, all four of the following conditions must be present:

1. Mutual Exclusion: At least one resource must be held in a non-shareable mode; only one process can use the resource at any given time.
2. Hold and Wait: A process must be holding at least one resource and waiting to acquire additional resources that are currently being held by other processes.
3. No Preemption: Resources cannot be forcibly removed from the processes holding them; they must be released voluntarily by the process after it has completed its task.
4. Circular Wait: A closed chain of processes exists such that each process holds at least one resource needed by the next process in the chain.

Link to original