High yield ●●●

🚧 Deadlock

Why it matters: A steady source of marks: Banker's safe sequence, minimum resources for deadlock freedom, and cycle questions on resource allocation graphs.

Subtopics

Each subtopic has its own page: idea, why, how, example, play, check. Mark each one understood when it clicks. 0 of 4 done.

Formulas

Coffman conditions
mutual exclusion, hold and wait, no preemption, circular wait
Need matrix
Need = Max − Allocation
Safety test
find Pᵢ with Needᵢ ≤ Work; Work += Allocationᵢ; repeat until all finish or none fits
Deadlock-free with n processes needing ≤ m each
R ≥ n(m − 1) + 1
Different needs mᵢ
R ≥ Σ (mᵢ − 1) + 1 = Σ mᵢ − n + 1
Max processes for given R, each needing m
n ≤ (R − 1) / (m − 1)

What GATE asks from this

Question types seen repeatedly in past papers. More stars means more frequent.

★★★
Is the system in a safe state / how many safe sequences
Compute Need, run the safety test; count distinct valid orders if asked.
★★★
Minimum number of resources to avoid deadlock
R = n(m − 1) + 1, or the generalisation with different maximums.
★★★
Is there a deadlock in this allocation graph
Single instance: look for a cycle. Multiple instances: run detection.
★★★
Statements about prevention vs avoidance vs detection
Which condition does an ordering or an all-at-once request break?

Ratings are approximate, based on recurring patterns in past GATE CSE papers.

Previous year questions

9 real questions from the official GATE CSE papers (2013 to 2025), newest first, each with the official answer key and a worked solution. Questions are the property of the GATE organising institutes; this copy is for your personal study.

9 questions · 0 correct of 0 attempted · marks 0 / 15

Year:
GATE 2025 CS2 · Q48MSQ2 marks
P = {P1, P2, P3, P4} consists of all active processes in an operating system. R = {R1, R2, R3, R4} 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: R1 → P1, R2 → P2, R3 → P3, R4 → P4 (the assignment edge R1 → P1 means resource R1 is assigned to process P1, and so on for others). Claim edges: P1 → R2, P2 → R3, P3 → R1, P2 → R4, P4 → R2 (the claim edge P1 → R2 means process P1 is waiting for resource R2, and so on for others). Which of the following statement(s) is/are CORRECT?

One or more options may be correct. Select all that apply, then submit.

GATE 2022 · Q26MSQ1 mark
Which of the following statements is/are TRUE with respect to deadlocks?

One or more options may be correct. Select all that apply, then submit.

GATE 2019 Set 2 · Q39MCQ2 marks
Consider the following snapshot of a system running n concurrent processes. Process i is holding Xi instances of a resource R, 1 ≤ i ≤ n. Assume that all instances of R are currently in use. Further, for all i, process i can place a request for at most Yi additional instances of R while holding the Xi instances it already has. Of the n processes, there are exactly two processes p and q such that Yp = Yq = 0. Which one of the following conditions guarantees that no other process apart from p and q can complete execution?
GATE 2018 · Q24NAT1 mark
Consider 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 2018 · Q39MCQ2 marks
In a system, there are three types of resources: E, F and G. Four processes P0, P1, P2 and P3 execute concurrently. At the outset, the processes have declared their maximum resource requirements using a matrix named Max. The number of instances of the resources allocated to the various processes is given by a matrix named Allocation. Allocation (E F G): P0 1 0 1, P1 1 1 2, P2 1 0 3, P3 2 0 0. Max (E F G): P0 4 3 1, P1 2 1 4, P2 1 3 3, P3 5 4 1. Consider the state with the Allocation matrix above in which 3 instances of E and 3 instances of F are the only resources available (no G is available). From the perspective of deadlock avoidance, which one of the following is true?
GATE 2017 Set 1 · Q27MCQ2 marks
A 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 a thread is unable to acquire a lock, it blocks until the lock becomes available. The minimum value of x and the minimum value of y together for which execution of P can result in a deadlock are:
GATE 2016 Set 1 · Q50MCQ2 marks
Consider the following proposed solution for the critical section problem. There are n processes: P0 ... Pn−1. In the code, function pmax returns an integer not smaller than any of its arguments. For all i, t[i] is initialized to zero. Code for Pi:
do {
  c[i] = 1;
  t[i] = pmax(t[0], ..., t[n−1]) + 1;
  c[i] = 0;
  for every j ≠ i in {0, ..., n−1} {
    while (c[j]);
    while (t[j] != 0 && t[j] <= t[i]);
  }
  Critical Section;
  t[i] = 0;
  Remainder Section;
}  while (true);
Which one of the following is TRUE about the above solution?
GATE 2014 Set 1 · Q31MCQ2 marks
An 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. Allocation (X Y Z): P0 0 0 1, P1 3 2 0, P2 2 1 1. Max (X Y Z): P0 8 4 3, P1 6 2 0, P2 3 3 3. There are 3 units of type X, 2 units of type Y and 2 units of type Z still available. The system is currently in a safe state. Consider the following independent requests for additional resources in the current state: REQ1: P0 requests 0 units of X, 0 units of Y and 2 units of Z. REQ2: P1 requests 2 units of X, 0 units of Y and 0 units of Z. Which one of the following is TRUE?
GATE 2013 Code A · Q16MCQ1 mark
Three concurrent processes X, Y, and Z execute three different code segments that access and update certain shared variables. Process X executes the P operation (i.e., wait) on semaphores a, b and c; process Y executes the P operation on semaphores b, c and d; process Z executes the P operation on semaphores c, d, and a before entering the respective code segments. After completing the execution of its code segment, each process invokes the V operation (i.e., signal) on its three semaphores. All semaphores are binary semaphores initialized to one. Which one of the following represents a deadlock-free order of invoking the P operations by the processes?

Common traps

Unsafe ≠ deadlock. A system in an unsafe state may still finish if processes happen to release resources early.
A cycle with several instances does not prove deadlock.
For the formula R = n(m − 1) + 1 the resources must all be of one type.
Banker's algorithm needs each process's maximum claim in advance: detection does not.