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).

Deadlock

11 Qs · since 2014 · 18 marks · 0.7 marks/paperStandard yield

Take topic test

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… Guide

Type

GATE CSE 2026 Set 1Q29MSQ1 markEasyWith respect to deadlocks in an operating system, which of the following statements is/are FALSE?
GATE CSE 2026 Set 1Q35NAT1 markEasyConsider 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…
GATE CSE 2025 Set 2Q48MSQ2 marksMedium $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$ …
GATE CSE 2022Q26MSQ1 markMediumWhich of the following statements is/are TRUE with respect to deadlocks?
GATE CSE 2021 Set 2Q43MSQ2 marksMediumConsider 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…
GATE CSE 2018Q24NAT1 markEasyConsider 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 _______.
GATE CSE 2017 Set 1Q27MCQ2 marksMediumA 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…
GATE CSE 2017 Set 2Q33MCQ2 marksEasyDiagramA 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?
GATE CSE 2015 Set 3Q52MCQ2 marksEasyConsider 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…
GATE CSE 2014 Set 1Q31MCQ2 marksMediumDiagramAn 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…
GATE CSE 2014 Set 3Q31NAT2 marksEasyA 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 ________.

Topic guide

What does GATE test in Deadlock?

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
common · NAT · 1 marks · 2026, 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
common · MCQ · 2 marks · 2017, 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
occasional · MSQ · 2 marks · 2026, 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
common · MSQ · 2 marks · 2026, 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.

Deadlock

11 Qs · since 2014 · 18 marks · 0.7 marks/paperStandard yield

Take topic test

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… Guide

Type

Topic guide

What does GATE test in Deadlock?

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
common · NAT · 1 marks · 2026, 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
common · MCQ · 2 marks · 2017, 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
occasional · MSQ · 2 marks · 2026, 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
common · MSQ · 2 marks · 2026, 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