Topic 1
When processes get stuck: the four conditions and the resource graph
Two programs each hold one file and wait for the other's file. Neither will let go, so neither can finish. The machine is not slow; it is stuck for ever. This is a deadlock.
What you will learn
- State the four conditions that must all hold for a deadlock.
- Draw a resource-allocation graph and read a cycle in it.
- Tell when a cycle means deadlock and when it does not.
The idea
Think of a narrow one-lane bridge. A car enters from each end at the same time. Each car needs the other to back up, and neither will. Both drivers are polite, both are waiting, and nobody moves.
Processes in an operating system behave the same way with resources: files, printers, memory buffers, locks. A process takes a resource, keeps it while it works, and may ask for another. If two or more processes end up waiting for each other in a closed loop, none of them can ever continue.
The important word is loop. One process waiting for another is normal: it waits, the other finishes, life goes on. A deadlock is a ring of waiting where every process in the ring waits for the next one, so the waiting never ends.
Where the picture breaks: The bridge breaks down in one way: a real driver can reverse. In the operating system, a process cannot give a resource back on its own unless the system allows it. That is exactly the 'no pre-emption' condition below.
Deadlock and its four necessary conditions
A set of processes is deadlocked when every process in the set is waiting for an event (usually a resource being released) that only another process in the same set can cause. A deadlock can happen only if all four conditions below hold at the same time. Remove any one, and deadlock is impossible.
- 1Mutual exclusion: at least one resource can be used by only one process at a time.
- 2Hold and wait: a process holds at least one resource while waiting for another.
- 3No pre-emption: a resource cannot be taken away from a process; the process must release it itself.
- 4Circular wait: there is a chain P1 → P2 → … → Pn → P1 where each process waits for a resource held by the next.
In depth
Kinds of resources
A reusable resource (CPU, memory, a file, a lock, a printer) is used and then given back; it is not used up. A consumable resource (a message, a signal) disappears once taken. Classic deadlock questions are about reusable resources.
A resource is pre-emptable if it can be taken away and given back without harm (CPU time, memory pages that can be swapped). It is non-pre-emptable if taking it away breaks the work (a printer halfway through a page, a lock in the middle of an update). Deadlocks come from non-pre-emptable resources.
Reading the graph precisely
A resource-allocation graph has two kinds of vertices: processes (circles) and resource types (rectangles, one dot per instance).
- Request edge P → R: the process is waiting for one instance of R.
- Assignment edge R → P: one instance of R is held by P (drawn from a dot).
- Claim edge P ⇢ R (dashed, used in avoidance): P may ask for R in the future.
- A process with no outgoing request edge is not waiting for anything; it can run to completion.
Why the cycle test needs care
With one instance per resource, every edge in a cycle points to the only holder of what is wanted, so nobody on the cycle can ever be served: cycle means deadlock.
With several instances, a process outside the cycle may hold an instance of a resource on the cycle. When it finishes, that instance frees someone on the cycle and the ring opens. So the cycle is necessary but not enough; you must reduce the graph.
Where deadlocks really happen
Databases: two transactions each lock a row the other needs. Multithreaded programs: two threads take two mutexes in opposite orders. Operating systems: a process holding a buffer waits for a device held by a process waiting for that buffer. All four conditions are present each time.
Step by step
- 1
Draw every process as a circle and every resource type as a rectangle. Put one dot inside the rectangle for each instance of that resource.
- 2
If a process is waiting for a resource, draw a request edge from the process to the rectangle (P → R).
- 3
If an instance of a resource is given to a process, draw an assignment edge from that instance's dot to the process (R → P).
- 4
Now follow the arrows. If you can start at a process and come back to it, the graph has a cycle.
- 5
If every resource on that cycle has exactly one instance, the cycle is a deadlock. If some resource on the cycle has more than one instance, the cycle only says a deadlock is possible; you must check further (the reduction method in Example 2).
Think: Why does an extra instance of a resource break the 'cycle means deadlock' rule?
Because a process outside the cycle may hold the extra instance. When it finishes and releases it, a process on the cycle can get what it is waiting for, and the ring opens.
Worked example, GATE level
A three-process ring
Given: Every resource has one instance. P1 holds R1 and asks for R2. P2 holds R2 and asks for R3. P3 holds R3 and asks for R1.
Find: Is the system deadlocked? If yes, which processes are involved?
- 1
Draw the edges: R1 → P1, P1 → R2, R2 → P2, P2 → R3, R3 → P3, P3 → R1.
- 2
Follow the arrows from P1: P1 → R2 → P2 → R3 → P3 → R1 → P1. We are back at P1, so there is a cycle.→ Cycle found
- 3
Check the instances on the cycle: R1, R2 and R3 each have one instance.
- 4
With single-instance resources, a cycle is enough for a deadlock. Each process waits for a resource held by the next one in the ring, and no process outside the ring can release anything to help.
Answer: Yes. P1, P2 and P3 are deadlocked.
Check it another way: Try removing any one edge, for example P3's request for R1. The ring opens, P3 can finish, release R3, then P2 can finish, then P1. So all four conditions were needed.
Worked example, edge case
A cycle that is not a deadlock
Given: R1 has 2 instances, R2 has 1. P1 holds one R1 and asks for R2. P2 holds R2 and asks for R1. P3 holds the other R1 and asks for nothing.
Find: Is there a deadlock?
- 1
There is a cycle: P1 → R2 → P2 → R1 → P1. But R1 has two instances, so the cycle alone does not decide it.
- 2
Use reduction: find a process whose requests can all be met right now, let it finish, and give back what it held. P3 asks for nothing, so P3 can finish.→ P3 finishes, one R1 becomes free
- 3
P2 is waiting for one R1. One R1 is now free, so P2 gets it, finishes, and releases R1 and R2.→ P2 finishes
- 4
P1 is waiting for R2, which is now free. P1 gets it and finishes.→ P1 finishes
- 5
Every process could finish in the order P3, P2, P1. If all processes can be removed this way, there is no deadlock.
Answer: No deadlock. A safe finishing order is P3 → P2 → P1.
Check it another way: Change one fact: suppose P3 also asks for R2. Now P3 cannot finish first, P1 and P2 still wait for each other, and nobody can be reduced. That version is a deadlock.
- P3 finishesfrees one R1
- P2 finishesgets R1, frees R1 + R2
- P1 finishesgets R2
- No deadlockevery process reduced
Worked example, GATE level
A long chain is not a deadlock
Given: Single instances. P1 holds R1 and asks for R2. P2 holds R2 and asks for R3. P3 holds R3 and asks for nothing. P4 asks for R1.
Find: Is any process deadlocked?
- 1
Draw the waits: P1 waits for P2 (R2), P2 waits for P3 (R3), P4 waits for P1 (R1).
- 2
P3 asks for nothing, so it can run and release R3.→ P3 finishes
- 3
P2 gets R3, finishes, releases R2 and R3. Then P1 gets R2, finishes, releases R1 and R2. Then P4 gets R1.→ everyone finishes
- 4
There is a long chain of waiting, but no cycle: the chain ends at P3, which can move.
Answer: No deadlock. A chain of waits ending at a process that can run always unwinds.
Check it another way: Add one edge, P3 asks for R1, and the chain closes into a cycle P1 → P2 → P3 → P1: now P1, P2 and P3 are deadlocked.
Try it yourself
Your turn
Every resource has one instance. P1 holds R1 and asks for R2. P2 holds R2 and asks for nothing.
- Draw the edges: R1 → P1, P1 → R2, R2 → P2.
- Is there a cycle starting at P1?
- So is the system deadlocked?
Trap
Any cycle in a resource-allocation graph means deadlock.
Why it feels right: A cycle looks exactly like processes waiting on each other in a ring.
Why it is wrong: With more than one instance of a resource, a process outside the cycle can release an instance and open the ring (Example 2).
Rule: Single instance: cycle ⇔ deadlock. Multiple instances: cycle is necessary, not sufficient; reduce the graph to decide.
Trap
Deadlock and starvation are the same thing.
Why it feels right: In both, a process waits and does not finish.
Why it is wrong: In starvation the system keeps making progress; one unlucky process is always passed over. In deadlock no process in the set can ever move.
Rule: Deadlock: a closed ring where nobody progresses. Starvation: others progress, one waits for ever.
Trap
If a deadlock happened, removing mutual exclusion is always the fix.
Why it feels right: It is listed first, so it looks like the easiest condition to break.
Why it is wrong: Many resources (a printer, a write lock) cannot be shared by nature. Making them shareable is often impossible.
Rule: Pick the condition that is cheap to break for that resource; mutual exclusion usually is not.
How GATE asks it
GATE tests this topic mostly as 1-mark and 2-mark conceptual MCQs and MSQs: which conditions are necessary, what a cycle in a graph implies, and whether a described allocation is deadlocked. Practise reading the graph quickly and always check the number of instances before deciding.
Recall cards (tap to reveal)
The four necessary conditions for deadlock
Mutual exclusion, hold and wait, no pre-emption, circular wait
Single-instance resources: what does a cycle mean?
A deadlock (cycle ⇔ deadlock)
Multiple instances: what does a cycle mean?
Deadlock is possible; reduce the graph to decide
Check yourself
Question 1 · MCQ, pick one · 1 mark · −1/3 if wrong
Which of these is NOT one of the four necessary conditions for deadlock?
Question 2 · MSQ, pick all that apply · 2 marks · no negative marks
In a resource-allocation graph where every resource has exactly one instance, which statements are true?
Question 3 · NAT, type a number · 2 marks · no negative marks
Every resource has one instance. P1 holds R1 and asks for R2. P2 holds R2 and asks for R1. P3 holds R3 and asks for R1. P4 holds nothing and asks for R3. How many processes lie on a cycle of the graph?
Question 4 · MCQ, pick one · 1 mark · −1/3 if wrong
Which statement correctly separates deadlock from starvation?
Question 5 · MCQ, pick one · 2 marks · −2/3 if wrong
R1 has 2 instances and R2 has 1. P1 holds one R1 and requests R2. P2 holds R2 and requests R1. P3 holds one R1 and requests nothing. Which is true?
Question 6 · MCQ, pick one · 1 mark · −1/3 if wrong
Which of these resources is usually pre-emptable?
Question 7 · NAT, type a number · 2 marks · no negative marks
Single instances. P1 holds R1 and asks for R2. P2 holds R2 and asks for R3. P3 holds R3 and asks for R1. P4 holds R4 and asks for nothing. How many processes are deadlocked?
How this connects
Needs
- Process states and the ready/waiting queues
- Locks and semaphores (Synchronisation)
Used later in
- Deadlock prevention: breaking one condition
- Banker's algorithm (avoidance)
- Detection with a wait-for graph
Other subjects
- Algorithms: cycle detection in a directed graph (DFS)
- Databases: wait-for graphs between transactions holding locks
Where to go next

