Deadlock: the four conditions and resource-allocation graphs

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

1. What did the two-flag attempt suffer from? from Lesson 3.1.2
2. What happens if all five philosophers pick up the left chopstick? from Lesson 3.2.2
3. P1 does wait(S); wait(Q) and P2 does wait(Q); wait(S). What can happen? from Lesson 3.2.1

1 · The Hook

Four cars reach a crossroads at the same moment; each waits for the car on its right to go first. Nobody moves, ever. That is a deadlock, and we have already met it three times in Phase 3. This phase studies it properly: the four conditions that must all be true for it to happen, a drawing that shows it (the resource-allocation graph), and what an OS can do about it. GATE asks a deadlock question nearly every year, often a numerical one.

3 · Core Concept

Predict First — the answer

Deadlock: each waits for something the other holds, for ever.

In plain words

A set of processes is deadlocked when each one is waiting for something that only another process in the same set can give. Since they are all waiting, nobody gives anything, and they wait for ever. A deadlock needs four things to be true together; remove any one and it cannot happen.

1. Resources

A resource is anything a process must get before using: a printer, a file, a lock, memory. A resource type may have several identical instances (e.g. 3 printers). A process uses a resource in three steps: request (wait if not available) → use → release.

2. The four necessary conditions (Coffman conditions)

All four must hold at the same time for a deadlock:

1. Mutual exclusion: at least one resource can be used by only one process at a time.
2. Hold and wait: a process holds at least one resource while waiting for another.
3. No pre-emption: a resource can't be taken away; the holder must release it voluntarily.
4. Circular wait: there is a cycle P1 → P2 → … → Pn → P1 where each waits for a resource held by the next.

Break any one and deadlock is impossible.

3. Resource-allocation graph (RAG)

• A circle for each process, a box for each resource type, with one dot per instance.
• Request edge P → R: P is waiting for R.
• Assignment edge R → P: an instance of R is held by P.

Reading the graph:

With several instances, check whether some process in the cycle can still finish: a process outside the cycle (or one whose requests can be met) may release an instance and break the wait.

4. Deadlock vs starvation

• Deadlock: a group waits for each other; nobody can ever proceed.
• Starvation: one process waits indefinitely while others keep running (e.g. low priority without aging).

Deadlock implies the waiting processes starve, but starvation can happen without deadlock.

4 · Visual

In (b), P3 is not waiting. When it finishes it releases its R1, P2 takes it and finishes, then P1 gets R2.

5 · Worked Examples

Example 1 Easy

P1 holds R1 and requests R2; P2 holds R2 and requests R1. Each resource has one instance. Deadlock?

Solution

Yes: the graph has the cycle P1 → R2 → P2 → R1 → P1 and every resource has one instance.

Example 2 Medium

Same as Easy, but R1 has two instances and the second one is held by P3, which is not waiting for anything. Deadlock?

Solution

No. P3 finishes and releases its R1; P2 gets it, finishes, and releases R2; then P1 gets R2.

Example 3 GATE

Which condition is broken if the OS forces every process to request all its resources at once, before it starts?

Solution

Hold and wait: a process never holds something while waiting for more.

6 · GATE Traps

• All four conditions are necessary; a deadlock needs every one of them.
• A cycle means deadlock only when every resource in it has a single instance.
• Edge directions: request P → R, assignment R → P.
• Starvation is not the same as deadlock.

7 · Memory Hook

"Mutual exclusion, Hold and wait, No pre-emption, Circular wait: all four, or no deadlock." (M-H-N-C: "My Hands Never Cooperate".)

8 · Connect the Dots

If all four conditions are needed, the OS can make sure one of them never holds (prevention), or carefully refuse requests that might lead to trouble (avoidance, the banker's algorithm). That is the next lesson.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1 · MSQ · 2 mark(s) — Conditions

Which of these are necessary conditions for deadlock?

1. (A) Hold and wait
2. (B) Pre-emption of resources
3. (C) Circular wait
4. (D) Mutual exclusion

Q2 · MCQ · 1 mark(s) — RAG

A resource-allocation graph has a cycle, and every resource type has exactly one instance. Then:

1. (A) the graph is invalid
2. (B) there is no deadlock
3. (C) there may or may not be a deadlock
4. (D) there is a deadlock

Q3 · MCQ · 1 mark(s) — RAG edges

In a resource-allocation graph, an edge from resource R to process P means:

1. (A) R is waiting for P
2. (B) an instance of R is held by P
3. (C) P is requesting R
4. (D) P has released R

Q4 · MCQ · 1 mark(s) — Starvation

Which statement is true?

1. (A) Deadlocked processes cannot proceed, but starvation can happen without deadlock
2. (B) Deadlock needs only circular wait
3. (C) Starvation and deadlock are the same thing
4. (D) Every starvation is a deadlock

Q5 · MCQ · 2 mark(s) — Multiple instances

R1 has 2 instances held by P1 and P3; R2 has 1 instance held by P2. P1 requests R2, P2 requests R1, and P3 requests nothing. Is the system deadlocked?

1. (A) Cannot be decided
2. (B) Yes, because there is a cycle
3. (C) No, because P3 can finish and release R1
4. (D) Yes, because R2 has one instance

10 · Rule Card

• Deadlock: each process in a set waits for something only another in the set can give.
• Four necessary conditions: mutual exclusion, hold and wait, no pre-emption, circular wait.
• RAG: request P → R, assignment R → P. No cycle → no deadlock; cycle + single instances → deadlock; cycle + multiple instances → maybe.
• Starvation ≠ deadlock.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

deadlockresources and instancesrequest–use–releasemutual exclusionhold and waitno pre-emptioncircular waitresource-allocation graphrequest and assignment edgescycles with single vs multiple instancesdeadlock vs starvation