Deadlock Questions in GATE CSE: Conditions, Formula, Banker's

Deadlock is the Operating Systems topic where the whole mark turns on one arithmetic step. Either the minimum-units inequality is off by one or it is not, either the safety algorithm is run to the end or abandoned halfway. There is no long derivation and little interpretation. The method below covers every shape the paper has used, on one small table you can reuse.

Key takeaways

• All four conditions must hold at once. Prevention permanently removes exactly one.
• For $n$ processes each needing at most $k$ units of a single resource type, deadlock is impossible when the total is at least $n(k - 1) + 1$. The largest total that still permits deadlock is $n(k - 1)$.
• With unequal maximum needs, sum $(\text{need}_i - 1)$ over all processes and add 1.
• $\text{Need} = \text{Max} - \text{Allocation}$. Safe implies deadlock-free, but unsafe does not imply deadlock.
• One instance per type makes a cycle equivalent to deadlock. Multiple instances make a cycle necessary but not sufficient.

Where deadlock sits in the paper

The 2027 syllabus names it in one word. Section 8 lists deadlock as its own sentence between synchronization and CPU scheduling, and that single word carries the four conditions, prevention, avoidance, detection and recovery.

Third-party analyst compilations put Operating Systems at 6 to 16 marks per paper across 2009 to 2026, averaging near 8.8. Split the series and 2009 to 2017 averages about 9.3 while 2018 to 2026 averages about 8.3, so the direction is slightly falling. The 16 in 2009 is not a trend, it reflects a 100-mark paper with no General Aptitude section. One analyst's count for the 2026 shift-2 paper put Operating Systems at five questions. Treat this as approximate and unofficial, since analysts differ by two or three marks on borderline questions. The cross-subject picture is in the guide to subject-wise weightage in GATE CSE.

Inside the subject, deadlock is a frequent item rather than a perennial one, appearing in roughly half the papers in some form. The ranking that places it against scheduling, paging and synchronization is in the Operating Systems important topics guide. Mark splits change every year, so check the current notification and the official question paper pattern.

The four conditions and what each strategy breaks

Deadlock needs all four of these simultaneously. Remove one permanently and deadlock cannot form.

The common one-mark item is a statement mapping. Resource ordering breaks circular wait, not hold and wait. Requesting everything up front breaks hold and wait, not circular wait. Priority scheduling breaks nothing. Avoidance breaks none of the four: it lets them all remain possible and instead refuses requests that would leave an unsafe state.

The minimum-units formula

This is the highest-frequency deadlock calculation in the paper and it is almost always a numerical answer.

Take $n$ processes, one resource type, each needing at most $k$ units to finish. Build the worst state you can: give every process $k - 1$ units, one short of its need. Nobody can finish, and that uses $n(k - 1)$ units. Add one more unit and some process reaches $k$, finishes, and releases everything it held, unblocking the rest.

So deadlock is impossible when the total $m$ satisfies

and the largest $m$ that still permits deadlock is $n(k - 1)$.

Worked small case: 4 processes, each needing at most 3 units. Then $n(k - 1) = 4 \times 2 = 8$ units can still deadlock, with each process holding 2 and waiting for a third. With 9 units deadlock cannot occur. The same inequality answers the question asked backwards. Given $m = 11$ and $k = 3$, the largest $n$ that is still guaranteed deadlock-free satisfies:

The variant with unequal needs uses the same construction. Give each process $\text{need}_i - 1$ units, sum those, add one. If three processes need at most 3, 4 and 5 units, the threshold is $2 + 3 + 4 + 1 = 10$. With 9 units a deadlock can still be arranged. With 10 it cannot. These are maximum needs, not current allocations, and the formula applies to a single resource type only.

Banker's algorithm and safe sequences

Avoidance requires every process to declare its maximum claim in advance. The state is then three matrices, and the first thing you compute is $\text{Need} = \text{Max} - \text{Allocation}$, element by element. Getting that wrong, or comparing a request against Max instead of Need, is the most expensive error in the topic.

Here is a three-process, two-resource state. Total units are $A = 6$ and $B = 5$.

Allocated totals are $(5, 4)$, so $\text{Available} = (6, 5) - (5, 4) = (1, 1)$.

Now run the safety algorithm. Look for any process whose Need is componentwise at most Available. P0 and P1 both need $(2, 1)$ and fail on A. P2 needs $(1, 1)$ and passes. Assume P2 finishes and returns its allocation, so Available becomes $(1, 1) + (2, 2) = (3, 3)$.

Repeat. P0 needs $(2, 1)$, which fits, and returns $(1, 1)$, giving $(3, 3) + (1, 1) = (4, 4)$. P1 needs $(2, 1)$, which fits, and returns $(2, 1)$, giving $(4, 4) + (2, 1) = (6, 5)$. Every process is marked finished, so the state is safe and P2, P0, P1 is a safe sequence.

Count carefully when the question asks how many safe sequences exist. Only P2 can start. After it finishes, P0 and P1 can run in either order, so there are exactly two, not one. The usual error is to stop at the first sequence found.

Now the request half. Suppose P1 requests $(1, 0)$. Three checks run in order. Is $\text{Request} \le \text{Need}$? Yes. Is $\text{Request} \le \text{Available}$? Yes. Now pretend to grant it: P1's Allocation becomes $(2, 1) + (1, 0) = (3, 1)$, its Need becomes $(2, 1) - (1, 0) = (1, 1)$, and Available becomes $(1, 1) - (1, 0) = (0, 1)$. Re-run safety. P0 needs $(2, 1)$, P1 needs $(1, 1)$, P2 needs $(1, 1)$, and none fits inside $(0, 1)$. Nothing can start, so the pretend state is unsafe and the request is denied. P1 waits even though the units are physically sitting there.

One conceptual point is tested directly. A safe state is sufficient for deadlock freedom, not necessary. An unsafe state is not a deadlocked state. It only means the algorithm can no longer guarantee an ordering if every process claims its full maximum, and many unsafe states finish without trouble.

Resource-allocation graphs and detection

In a resource-allocation graph, a request edge runs from a process to a resource type and an assignment edge runs from a resource instance back to a process.

When every resource type has exactly one instance, a cycle is equivalent to deadlock, and finding the cycle is the whole answer. When at least one type has several instances, a cycle is necessary but not sufficient: a process on the cycle may be waiting on a type whose other instance is held by a process outside the cycle, and that process can finish and release it. For multiple instances, reduce the graph or run the detection algorithm.

Detection uses Allocation and Request matrices, where Request is the outstanding demand right now rather than a declared maximum. The procedure is the safety algorithm with Request in place of Need, and any process not marked finished at the end is deadlocked. A wait-for graph is the single-instance shortcut, obtained by collapsing each resource node so an edge runs straight from a waiting process to the holder.

Keep the four responses separate, because a one-mark statement question turns on exactly this. Prevention removes a condition by design. Avoidance uses declared maximums to refuse dangerous requests. Detection permits deadlock and finds it afterwards. Recovery clears it by preempting resources, rolling a process back to a checkpoint, or terminating processes until the cycle breaks.

The traps in one list

• Off-by-one in the formula. $n(k - 1)$ still deadlocks, $n(k - 1) + 1$ does not.
• Using current allocation instead of declared maximum need.
• Computing Need as Max rather than $\text{Max} - \text{Allocation}$.
• Checking a request against Available but not Need, or the reverse.
• Reporting one safe sequence when the question asks how many exist.
• Treating an unsafe state as a deadlocked state.
• Reading a cycle as deadlock when a type has multiple instances.
• Matching a prevention strategy to the wrong condition.

The cross-subject version of this list is in common mistakes that cost marks in GATE CSE, and the compact statements of both deadlock inequalities sit in the GATE CSE formula sheet.

Exam technique

Most deadlock items are numerical answer questions, which changes how you play them. A single off-by-one costs the entire mark, because there is no partial credit and no nearby option to check yourself against. Write the inequality in symbols first, then substitute once.

The other half of that fact is friendlier. There is no negative marking on numerical answer questions, so an attempted answer is free. If a deadlock numerical is the last thing left and the matrices are half-solved, enter your best figure rather than leaving it blank. The rules for deciding this across question types are in the guide to MSQ, NAT and MCQ strategy, and the marking scheme is set afresh each year, so confirm it in the current notification.

How to practise

Reuse one three-process, two-resource table. Change a number in Allocation and re-run safety. Change a number in Max and watch a safe state turn unsafe. Ask how many safe sequences exist each time, not just whether one exists.

For the formula, drill both directions: given $n$ and $k$ find $m$, given $m$ and $k$ find the largest $n$, then repeat with unequal needs. The Operating Systems chapter of the GATE CSE 2027 book carries a full deadlock question bank with worked safety runs, safe-sequence counts and request-grant decisions, solved step by step.