All four conditions must coexist
Mutual exclusion, hold and wait, no preemption, and circular wait are all necessary for deadlock.
There are no items in your cart
Add More
Add More
| Item Details | Price | ||
|---|---|---|---|
Deadlock toolkit
Six rules that unlock most deadlock PYQs
Keep these six rules in working memory. They eliminate many of the most common deadlock traps.
Prevention breaks a condition
If a policy guarantees that even one necessary condition cannot hold, deadlock is prevented by design.
Unsafe is not the same as deadlocked
An unsafe state means future deadlock cannot be ruled out. It does not automatically mean the system is stuck now.
Read RAG arrows correctly
P → R means request. R → P means allocation. Reversing these changes the dependency story completely.
Single-instance cycle means deadlock
When every resource type has one instance, a cycle is both necessary and sufficient for deadlock. With multiple instances, a cycle alone is not enough.
Avoidance asks one question
If this request is granted now, does the resulting state remain safe? That is the logic behind Banker-style decisions.
Fast distinction:Prevention changes the rules of allocation. Avoidance evaluates whether a particular allocation keeps the system safe.
Recognition first
What does the question give you?
Some PYQs combine ideas from more than one pattern. Use the strongest visible clue to choose your first useful solving move.
Statements / theoryConditions and Prevention
Min / max resource countMinimum Resources
Max + Allocation + AvailableSafe State and Banker
Who holds / who waitsRAG and Detection
wait, signal, mutex, lockDeadlocks in Code
One rule before every PYQ
Separate the surface from the dependency structure
A tape-drive question and a semaphore question can both be deadlock questions, but they should not be solved the same way. The pattern tells you what abstraction to use: a worst-case count, a safety sequence, a resource dependency graph, or a hold-wait trace through code.
01
Pattern 1 · 9 PYQs
Conditions, Prevention and Conceptual Traps
How to recognize it
The question is statement-heavy: necessary conditions, prevention versus avoidance, safe versus unsafe, or whether a cycle proves deadlock.
Your first move
Name the exact deadlock condition or state property being tested before judging the options.
Pattern playbook
Four conditionsMutual exclusion, hold and wait, no preemption, circular wait.
PreventionBreak at least one necessary condition by design.
AvoidanceAllow requests only if the resulting state stays safe.
Cycle ruleFor single-instance resource types, a cycle means deadlock. With multiple instances, a cycle alone is not enough.
State trapUnsafe does not mean currently deadlocked.
GATE CSE PYQs in Pattern 1
| Question | What it tests |
|---|---|
| GATE CSE 1990 Q2-iii | Circular wait as the deadlock association. |
| GATE CSE 1991 Q03-xi | Whether monitors guarantee freedom from deadlock. |
| GATE CSE 1997 Q75 | Timestamp-based resource policy, deadlock and starvation behavior. |
| GATE CSE 2000 Q2.23 | Identify a scheme that is not valid deadlock prevention. |
| GATE CSE 2008 Q65 | Deadlock prevention versus deadlock avoidance. |
| GATE CSE 2015 Set 3 Q52 | Which resource-allocation policies prevent deadlock. |
| GATE CSE 2021 Set 2 Q43 | Resource ownership policy, deadlock, livelock and starvation. |
| GATE CSE 2022 Q16 | Necessary conditions, graph cycles, unsafe and deadlocked states. |
| GATE CSE 2026 Set 1 Q19 | Prevention, avoidance, safe states and Resource Allocation Graph concepts. |
What ties these PYQs together
Concept-first questions reward precise definitions
Pattern 1 questions often look easy because there is little arithmetic. They are also where one imprecise definition can cost the mark. Before checking options, write the rule in one line: which Coffman condition is affected, whether the system is safe or only not deadlocked, and whether the graph uses single or multiple instances.
Common trap for Pattern 1
Do not treat deadlock prevention, avoidance, and detection as interchangeable. They act at different stages and use different information.
02
Pattern 2 · 9 PYQs
Minimum Resources and Deadlock-Free Guarantees
How to recognize it
The question gives identical resource instances, process demands, or asks for a minimum resource count or maximum process count that guarantees no deadlock.
Your first move
Construct the worst case where every process is one resource short of completion, then add one resource that lets at least one process finish.
Pattern playbook
General guaranteeFor peak demands M_i, a standard worst-case guarantee is sum(M_i - 1) + 1 resources.
Equal demandIf n processes each need at most k instances, use n(k - 1) + 1 for the minimum guaranteed count.
Reverse questionsIf total resources are fixed, invert the same worst-case logic to bound the number of processes or maximum demand.
Why +1 mattersThe extra resource lets one process finish and release everything it holds.
Check assumptionsUse the shortcut only for the matching identical-resource setup.
GATE CSE PYQs in Pattern 2
| Question | What it tests |
|---|---|
| GATE CSE 1992 Q02-xi | Maximum process count that remains deadlock-free with identical resources. |
| GATE CSE 1993 Q7.9 | Peak demands with identical resources and a deadlock-free resource threshold. |
| GATE CSE 1997 Q6.7 | Minimum identical resources required to guarantee no deadlock. |
| GATE CSE 1998 Q1.32 | Maximum number of processes with six tape drives and peak demand two. |
| GATE CSE 2005 Q71 | Sufficient resource condition for arbitrary process peak demands. |
| GATE CSE 2014 Set 3 Q31 | Minimum tape units needed to ensure deadlock cannot arise. |
| GATE CSE 2015 Set 2 Q23 | Number of competing processes that can lead to deadlock. |
| GATE CSE 2018 Q24 | Largest maximum demand that still guarantees deadlock avoidance. |
| GATE CSE 2026 Set 1 Q25 | Minimum identical resources needed for five processes with peak demand two. |
What ties these PYQs together
The repeated numerical idea is a worst-case allocation
Imagine every process has already received as many resources as possible without being able to finish. If the system has one additional resource beyond that worst-case holding pattern, at least one process can complete. Its released resources then make progress possible for others.
Common trap for Pattern 2
Do not memorize n(k - 1) + 1 without checking whether all processes have the same maximum demand and whether the question really uses identical instances of one resource type.
03
Pattern 3 · 6 PYQs
Safe State and Banker's Algorithm
How to recognize it
You see Allocation, Max, Available, Need, a safe-sequence question, or a request that may or may not be granted.
Your first move
Compute Need = Max - Allocation, then repeatedly find a process whose remaining need can be met by the current work vector.
Pattern playbook
Need matrixNeed = Max - Allocation.
Safety testFind Need_i <= Work, finish that process, then add its Allocation back to Work.
Safe sequenceIf every process can be completed in some order, the state is safe.
Request testPretend to grant the request first, update the matrices, then rerun the safety check.
InterpretationA safe sequence proves existence of one completion order, not the only legal execution order.
GATE CSE PYQs in Pattern 3
| Question | What it tests |
|---|---|
| GATE CSE 1988 Q11 | Safe state and safe-sequence reasoning from allocation data. |
| GATE CSE 1996 Q22 | Banker's Algorithm and whether a new request should be granted. |
| GATE CSE 2007 Q57 | Available resources, completion order and deadlock status. |
| GATE CSE 2014 Set 1 Q31 | Banker's Algorithm, safe state and request granting. |
| GATE CSE 2017 Set 2 Q33 | Safe versus unsafe and deadlocked versus not deadlocked. |
| GATE CSE 2018 Q39 | Allocation/Max tables and the resource addition needed for safety. |
What ties these PYQs together
Banker questions are mechanical once the table is normalized
Do not scan the original Max and Allocation tables repeatedly. Build Need once. Then treat Available as a running Work vector. Every completed process returns its current Allocation, which can unlock another process. The question becomes a sequence-building exercise instead of a visual puzzle.
Common trap for Pattern 3
Unsafe and deadlocked are different. Banker's Algorithm is about avoiding entry into unsafe states, not merely detecting a deadlock that has already formed.
04
Pattern 4 · 7 PYQs
RAG, Detection, Recovery and Resource-State Analysis
How to recognize it
The question tells you who holds which resource, who is waiting, gives a Resource Allocation Graph, or asks which process must be aborted.
Your first move
Translate the state into dependencies, identify which processes can still complete, and repeatedly release the resources of any process that can finish.
Pattern playbook
Request edgeProcess -> Resource means the process is requesting that resource.
Assignment edgeResource -> Process means that instance is allocated to the process.
Single instanceA cycle is sufficient for deadlock when every resource type has one instance.
Multiple instancesUse a completion or detection procedure instead of declaring deadlock from a cycle alone.
RecoveryTerminate or preempt strategically to break the blocked dependency set.
GATE CSE PYQs in Pattern 4
| Question | What it tests |
|---|---|
| GATE CSE 1989 Q11(a) | Construct a deadlocking order and reason about prevention. |
| GATE CSE 1994 Q28 | Resource Allocation Graph, deadlock status and safe completion. |
| GATE CSE 2006 Q66 | Current holdings and outstanding requests needed for continued progress. |
| GATE CSE 2009 Q30 | Timed resource requests and identification of deadlocked processes. |
| GATE CSE 2010 Q46 | Resource-request ordering and whether deadlock is possible. |
| GATE CSE 2019 Q39 | Which remaining processes can or cannot complete after releases. |
| GATE CSE 2025 Set 2 Q38 | RAG deadlock detection and recovery by aborting process sets. |
What ties these PYQs together
Think in terms of progress, not just circles
A graph is useful only if it tells you who can move next. Start from available resources. If some process can satisfy its remaining request, let it finish and return what it holds. If no unfinished process can move, the remaining blocked set is the deadlock set for that state.
Common trap for Pattern 4
A graph cycle and a deadlock are equivalent only in the single-instance case. This is one of the most repeated conceptual traps around Resource Allocation Graphs.
05
Pattern 5 · 15 PYQs
Deadlocks in Code: Semaphores, Locks and Synchronization
How to recognize it
The question gives wait/signal, P/V, mutexes, locks, barriers, Dining Philosophers, Producer-Consumer code, or a custom critical-section algorithm.
Your first move
For each process or thread, write two things: what it already holds and what it is waiting to acquire. Then look for a closed dependency cycle.
Pattern playbook
HoldMark every resource or permit already acquired.
WaitMark the next acquisition that blocks.
DependencyIdentify which other process can release what is needed.
CycleIf the dependency chain returns to the starting process and nobody can advance, deadlock is possible.
Ordering fixA consistent global acquisition order is a common way to remove circular wait.
GATE CSE PYQs in Pattern 5
| Question | What it tests |
|---|---|
| GATE CSE 1996 Q2.19 | Dining Philosophers and removal of circular wait. |
| GATE CSE 2000 Q1.21 | Mutex acquisition order that can create circular wait. |
| GATE CSE 2001 Q19 | Resource acquisition in code and whether a deadlock can occur. |
| GATE CSE 2002 Q18-b | TEST-AND-SET solution, deadlock freedom and starvation freedom. |
| GATE CSE 2004 Q48 | Semaphore acquisition order that avoids deadlock. |
| GATE CSE 2006 Q78 | Reusable barrier behavior that may deadlock. |
| GATE CSE 2007 Q58 | Mutual-exclusion algorithm that can leave both processes waiting. |
| GATE CSE 2009 Q33 | TEST-AND-SET critical section and deadlock-freedom property. |
| GATE CSE 2013 Q16 | Semaphore ordering that makes the execution deadlock-free. |
| GATE CSE 2014 Set 2 Q31 | Producer-Consumer ordering that can create deadlock. |
| GATE CSE 2015 Set 3 Q10 | Synchronization solution, mutual exclusion and deadlock prevention. |
| GATE CSE 2016 Set 1 Q50 | Critical-section algorithm and whether it can cause deadlock. |
| GATE CSE 2017 Set 1 Q27 | Self-deadlock with a non-reentrant lock. |
| GATE CSE 2021 Set 1 Q46 | Counting semaphore permits and a deadlock involving all threads. |
| GATE CSE 2024 Set 2 Q36 | Semaphore blocking while holding a permit another thread needs. |
What ties these PYQs together
Convert code into a wait-for story
Do not brute-force every possible instruction interleaving first. Find the dangerous point where a process blocks while still holding something useful to another process. This compresses semaphore and lock code into the same hold-wait-cycle reasoning used in resource graphs.
Common trap for Pattern 5
Deadlock does not have to be the textbook two-lock pattern. It can be indirect, can involve counting semaphores, and with a non-reentrant lock it can even be self-deadlock.
PYQ tracker
Track your Deadlock PYQ practice
Mark each PYQ as you practise it.
Open PYQ tracker46 questions
Fast self-check
Can you choose the route before you solve?
Decide the pattern first. Then open the card to check your reasoning.
A question gives four statements about circular wait, safe states and Resource Allocation Graph cycles. Which pattern should you try first?
Pattern 1. It is primarily a conceptual conditions and traps question.
A system has 7 identical tape drives and every process may need at most 3. The question asks for the maximum safe process count.
Pattern 2. This is a minimum-resource or maximum-process guarantee setup.
You are given Max, Allocation and Available matrices.
Pattern 3. Build Need = Max - Allocation and run a safety sequence.
A graph shows P1 requesting R2 while R1 is assigned to P1.
Pattern 4. Translate request and assignment edges, then analyze progress or cycles.
Two threads call wait() on semaphores in different orders.
Pattern 5. Track what each thread holds when it blocks and look for a closed dependency cycle.
The state is unsafe. Is it necessarily deadlocked right now?
No. Unsafe means deadlock cannot be ruled out for future requests. It does not automatically mean the current state is already deadlocked.
Master revision sheet
Five routes. Six rules worth remembering.
Coffman conditions
ME + Hold & Wait + No Preemption + Circular WaitPrevention
Break at least one necessary conditionState distinction
Unsafe ≠DeadlockedBanker
Need = Max - AllocationIdentical-resource guarantee
R_min = sum(M_i - 1) + 1Single-instance RAG
Cycle ⇔ Deadlock| If you see | Think | First move |
|---|---|---|
| Necessary conditions, prevention, safe/unsafe statements | Pattern 1 | Name the exact condition or state rule. |
| Minimum resources, maximum processes, maximum demand | Pattern 2 | Build the worst case where everyone is one resource short. |
| Allocation, Max, Available | Pattern 3 | Compute Need and construct a safe sequence. |
| RAG, current holdings, requests, abort/recovery | Pattern 4 | Find who can finish and release resources. |
| Semaphore, mutex, lock or synchronization code | Pattern 5 | Write Hold -> Wait -> Dependency -> Cycle. |
Final takeaway
Classify first. Solve second.
Deadlock questions change their disguise. Your job is to identify the route, then use the matching abstraction.
ConceptsName the exact condition or state rule.
ResourcesBuild the worst case, then force one completion.
BankerNeed first, safe sequence second.
RAGAsk who can still progress and release resources.
CodeTrack what is held when blocking happens.