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 is waiting for a resource held by another in the set, forming a circular chain of dependency.

For example, $P_1$ holds Resource A and requests Resource B, while $P_2$ holds Resource B and requests Resource A.

Examples

Roundabout

In a roundabout with “right of way” rules, a deadlock occurs if four cars enter simultaneously. Each occupies a road segment (resource) and waits for the next segment to be vacated. No car can move, creating a circular wait.

Message Passing

$P_1$ performs a blocking receive from $P_2$, while $P_2$ simultaneously performs a blocking receive from $P_1$. Both wait for a message (consumable resource) that will never arrive.

Joint Progress Diagram

Definition

Joint Progress Diagram

A joint progress diagram (process progress diagram) is a graphical tool illustrating deadlock potential when two processes compete for resources. It maps each process’s progress along perpendicular axes to identify unsafe regions where deadlock becomes unavoidable.

Link to original

Integrated Strategy

An integrated deadlock strategy combines approaches by grouping resources into 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

Apply the most suitable method per class: preemption for main memory (via swapping), avoidance for process resources, ordering to prevent circular wait.

Conditions for Deadlock

Definition

Coffman Conditions

The Coffman conditions are four necessary requirements that must hold simultaneously for a deadlock to occur. Identified by E. G. Coffman, Jr. in 1971.

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

1. Mutual Exclusion: At least one resource is non-shareable; only one process may use it at a time.
2. Hold and Wait: A process holds at least one resource while waiting to acquire others held by different processes.
3. No Preemption: Resources cannot be forcibly removed; they must be released voluntarily.
4. Circular Wait: A closed chain exists where each process holds a resource needed by the next in the chain.

Link to original