What are common examiner traps in Deadlock?

Confusing 'Unsafe state' with 'Deadlocked state' (an unsafe state does not guarantee that deadlock will definitely occur; it only means safety cannot be guaranteed). Assuming a cycle in a Resource Allocation Graph always implies deadlock (true only for single-instance resource systems; for multi-instance, it is necessary but not sufficient). Mixing up RAG edge directions: Pi → Rj is a Request/Claim edge, whereas Rj → Pi is an Assignment edge. Confusing Deadlock Avoidance (e.g., Banker's Algorithm dynamically checking safe states) with Deadlock Prevention (static invalidation of Coffman conditions). Off-by-one errors in worst-case formulas: forgetting the '+ 1' needed to allow at least one process to finish execution. Assuming multiple threads/locks are mandatory for deadlock: a single thread holding a non-reentrant lock and requesting it again will self-deadlock (x=1, y=1).

GATE CSE Deadlock PYQs

Standard yield9.4% of Operating Systems

Across GATE CS exams from 2014 to 2026, the Deadlock topic is tested through three main angles: mathematical resource bounds using the pigeonhole principle, alg… Read the guide

Take topic test

Questions: 11
Asked: since 2014
Total marks: 18
Marks / paper: 0.7

11 GATE CSE Deadlock PYQs with solutions, from Operating Systems. Browse all GATE CSE PYQs.

Questions

Every official paper that asked this topic, newest first.

GATE CSE 2026 Set 1 · Q29With respect to deadlocks in an operating system, which of the following statements is/are FALSE?MSQ1 markEasySolve
GATE CSE 2026 Set 1 · Q35Consider a system consisting of $k$ instances of a resource $R$ , being shared by 5 processes. Assume that each process requires a maximum of two instances of resource $R$ and a process can request or release only one instance at a time. Further, a process can request the second instance of the resource only…NAT1 markEasySolve
GATE CSE 2025 Set 2 · Q48 $P = \{P_1, P_2, P_3, P_4\}$ consists of all active processes in an operating system. $R = \{R_1, R_2, R_3, R_4\}$ consists of single instances of distinct types of resources in the system. The resource allocation graph has the following assignment and claim edges. Assignment edges: $R_1 \rightarrow P_1$ , $R_2 \rightarrow P_2$ …MSQ2 marksMediumSolve
GATE CSE 2022 · Q26Which of the following statements is/are TRUE with respect to deadlocks?MSQ1 markMediumSolve
GATE CSE 2021 Set 2 · Q43Consider a computer system with multiple shared resource types, with one instance per resource type. Each instance can be owned by only one process at a time. Owning and freeing of resources are done by holding a global lock (L). The following scheme is used to own a resource instance :function OWNRESOURCE(Resource R) Acquire lock L // a global lock if R is available then Acquire R Release lock L else if R is owned by another process P then Terminate P, after releasing all resources owned by P Acquire R Restart P Release lock L end if end if end function…MSQ2 marksMediumSolve
GATE CSE 2018 · Q24Consider a system with 3 processes that share 4 instances of the same resource type. Each process can request a maximum of $K$ instances. Resource instances can be requested and released only one at a time. The largest value of $K$ that will always avoid deadlock is _______.NAT1 markEasySolve
GATE CSE 2017 Set 1 · Q27A multithreaded program $P$ executes with $x$ number of threads and uses $y$ number of locks for ensuring mutual exclusion while operating on shared memory locations. All locks in the program are *non-reentrant*, i.e., if a thread holds a lock $l$ , then it cannot re-acquire lock $l$ without releasing it. If…MCQ2 marksMediumSolve
GATE CSE 2017 Set 2 · Q33A system shares 9 tape drives. The current allocation and maximum requirement of tape drives for three processes are shown below: Which of the following best describes current state of the system?MCQ2 marksEasyDiagramSolve
GATE CSE 2015 Set 3 · Q52Consider the following policies for preventing deadlock in a system with mutually exclusive resources. I. Processes should acquire all their resources at the beginning of execution. If any resource is not available, all resources acquired so far are released II. The resources are numbered uniquely, and processes are…MCQ2 marksEasySolve
GATE CSE 2014 Set 1 · Q31An operating system uses the *Banker's algorithm* for deadlock avoidance when managing the allocation of three resource types X, Y, and Z to three processes P0, P1, and P2. The table given below presents the current system state. Here, the *Allocation* matrix shows the current number of resources of each type…MCQ2 marksMediumDiagramSolve
GATE CSE 2014 Set 3 · Q31A system contains three programs and each requires three tape units for its operation. The minimum number of tape units which the system must have such that deadlocks never arise is ________.NAT2 marksEasySolve

What GATE tests in Deadlock

Concepts, patterns, formulas and traps distilled from past papers.

Across GATE CS exams from 2014 to 2026, the Deadlock topic is tested through three main angles: mathematical resource bounds using the pigeonhole principle, algorithmic simulation of Banker's safety and request algorithms, and rigorous conceptual analysis of Coffman conditions, prevention schemes, and Resource Allocation Graphs (RAG). The topic frequently yields both 1-mark and 2-mark questions, with a significant recent pivot toward multi-select questions (MSQ) and code/graph analysis.

Core concepts

Four Coffman necessary conditions: Mutual Exclusion, Hold & Wait, No Preemption, Circular Wait
Deadlock Prevention techniques (strict linear ordering of resources, holding all resources upfront)
Deadlock Avoidance via Banker's Safety Algorithm and Resource-Request Algorithm
Safe state vs. Unsafe state vs. Deadlocked state hierarchy
Resource Allocation Graph (RAG) vs. Wait-For Graph (WFG) and single- vs multi-instance cycle sufficiency
Non-reentrant locks and single-thread self-deadlock
Deadlock recovery via process termination and preemptive restarts leading to livelock or starvation

Recurring question patterns

Minimum Resources or Maximum Demand for Deadlock Freedom
CommonNAT1 marks2026, 2018, 2014
Given $N$ processes each requiring a maximum of $M$ (or $K$ ) instances of a single resource type, calculate the minimum total resources $R$ or the maximum demand $K$ that guarantees the system is deadlock-free using the worst-case allocation principle $\sum (M_i - 1) + 1 \le R$ .
Banker's Algorithm State and Request Evaluation
CommonMCQ2 marks2017, 2014
Given Allocation and Max matrices along with Available resources, evaluate whether the current state is safe, or simulate dynamic resource request vectors to determine if granting them leaves the system in a safe state with a valid execution sequence.
Resource Allocation Graph (RAG) and Cycle Analysis
OccasionalMSQ2 marks2026, 2025, 2022
Given a formal set of assignment edges ( $R_j \rightarrow P_i$ ) and request/claim edges ( $P_i \rightarrow R_j$ ) with single or multiple instances, detect cycles, evaluate deadlock presence, and determine which process terminations resolve all deadlocked cycles.
Deadlock Prevention, Coffman Conditions, and Algorithmic Schemes
CommonMSQ2 marks2026, 2022, 2021, 2017
Evaluating formal statements or pseudocode implementations against the four Coffman conditions (Mutual Exclusion, Hold and Wait, No Preemption, Circular Wait), distinguishing avoidance from prevention, and identifying side-effects like livelock and starvation.

Formulas GATE uses

Deadlock-Free Resource Condition (Pigeonhole / Worst-Case Allocation)

R \ge \sum_{i=1}^{N} (\text{Max}_i - 1) + 1

Used to find the minimum resources $R$ or maximum demand $K$ among $N$ processes to guarantee that deadlock can never occur under single-resource type systems.

Identical Process Demand Deadlock-Free Bound

R \ge N(K - 1) + 1 \iff N(K - 1) < R

Used when all $N$ processes have an identical maximum resource claim $K$ .

Banker's Need Matrix Formula

\text{Need}[i][j] = \text{Max}[i][j] - \text{Allocation}[i][j]

Used as the first step in Banker's safety and resource-request algorithms to check if $\text{Request}_i \le \text{Need}_i$ and $\text{Need}_i \le \text{Work}$ .

Examiner traps in Deadlock

Confusing 'Unsafe state' with 'Deadlocked state' (an unsafe state does not guarantee that deadlock will definitely occur; it only means safety cannot be guaranteed).
Assuming a cycle in a Resource Allocation Graph always implies deadlock (true only for single-instance resource systems; for multi-instance, it is necessary but not sufficient).
Mixing up RAG edge directions: Pi → Rj is a Request/Claim edge, whereas Rj → Pi is an Assignment edge.
Confusing Deadlock Avoidance (e.g., Banker's Algorithm dynamically checking safe states) with Deadlock Prevention (static invalidation of Coffman conditions).
Off-by-one errors in worst-case formulas: forgetting the '+ 1' needed to allow at least one process to finish execution.
Assuming multiple threads/locks are mandatory for deadlock: a single thread holding a non-reentrant lock and requesting it again will self-deadlock (x=1, y=1).

How questions are asked

Worst-case resource/demand NAT computation
Banker's algorithm request granting feasibility MCQ
Banker's safety state determination MCQ
RAG edge listing and cycle termination MSQ
Coffman conditions and prevention schemes MSQ/MCQ
Pseudocode protocol concurrency analysis MSQ

Paper trends

Shift from standard single-choice tabular Banker's algorithm questions to multi-select conceptual questions (MSQs) testing subtle definitional boundaries and pseudocode analysis.
2026, 2025, 2022, 2021
Introduction of pseudocode implementations involving concurrency primitives (locks, preempt-and-restart schemes) to evaluate livelock, starvation, and deadlock simultaneously.
2021, 2017
Consistent presence of single-resource worst-case capacity numerical questions (NAT) as reliable 1-mark or 2-mark scoring items.
2026, 2018, 2014

Difficulty notes

Easy questions typically involve direct evaluation of the worst-case pigeonhole formula ( $R \ge \sum(M_i - 1) + 1$ ) or direct standard definitions of Coffman conditions. Medium questions require multi-step Banker's algorithm calculations with tentative state updates, tracing multiple simultaneous cycles in single-instance RAGs to test process abortion subsets, or analyzing pseudocode with locks for livelock and preemption properties.