Deadlock detection: current requests and resource bounds

Goals and model

Distinguish current deadlock detection from maximum-claim safety testing, reduce a small allocation table, and derive a single-resource deadlock-free bound. Prerequisite: the earlier resource-graph/Banker-style safety lesson. Resources are reusable and identical within a type. Outstanding requests are blocking, no resources are externally added or lost, and a process that can proceed is assumed eventually to finish and release its allocation in the reduction model. No process failures or hidden synchronization dependencies are included.

1. What is wanted now versus what might be needed later?

Think of a workshop inventory. A worker's current order is the tool set they are asking for now. Their declared maximum is the most they might need at one time during the whole job. These are different pieces of information. Banker-style avoidance uses remaining maximum Need=Max−Allocation to ask whether all maximum claims could be accommodated in some completion order. Detection uses currently outstanding Request to ask whether present waits can be resolved through possible releases.

A zero Request does not mean zero maximum demand. A successful detection reduction describes the current snapshot under its model; a later request can create a new deadlock. Conversely, a failed maximum-claim safety test does not itself prove that anyone is currently blocked.

2. Reduce the current allocation table

Start Work=Available. Mark resource-holding processes unfinished. Find an unfinished process whose Request is at most Work in every component. Assume its request can be satisfied and it can finish; mark it finished and add its pre-existing Allocation to Work. The net update is Work=Work+Allocation, because the temporarily granted Request is returned along with the old allocation. Repeat until no more processes can be removed.

For the conventional resource-holder detection formulation, a process with zero allocation can initially be marked finished: it holds nothing that can trap others in a resource cycle. It may still be blocked behind a deadlocked group; that is not a claim that it has actually terminated. In this algorithm “finished” is a bookkeeping marker for reduction, not an observed CPU event. Every process in the following numerical examples holds a nonzero allocation, so all initially start unfinished.

3. Worked detection with a release outside the apparent cycle

Use resource types (A,B), Available=(0,0), and this current state:

Process	Allocation	Current Request
P0	(1,0)	(0,1)
P1	(0,1)	(1,0)
P2	(1,1)	(0,0)

Total resources=(2,2). P0 and P1 cannot proceed initially, but P2 requests nothing more. Remove P2 and update Work=(1,1). Now P0's request (0,1) fits; after it finishes Work=(2,1). P1's request (1,0) fits, and Work=(2,2). Thus all can be reduced in order P2,P0,P1. A dependency between P0 and P1 alone was insufficient to prove deadlock: P2 can release other instances. The final Work equals total resources, an independent arithmetic check.

Now change only P2's current Request to (1,1). Work is still (0,0), and all three requests are nonzero and cannot fit. No process can release under the stated blocking/finish model. All three resource-holding processes remain unfinished and are deadlocked. Available=(0,0) alone was not the criterion; the outstanding requests changed the answer.

4. Unsafe can still mean nobody is blocked now

Consider one resource type with two instances. P0 and P1 each hold one, so Available=0. Each has declared maximum 2, so remaining maximum Need=1 for each. No Banker safe sequence exists if both may still demand their maxima. But suppose both current Requests are 0 and their actual remaining execution makes no further request. Either can finish and release, then the other finishes: no current deadlock. If instead both now request one more while retaining their allocations, they deadlock. Always label a vector as current Request or remaining maximum Need.

5. Derive a resource bound instead of memorizing it blindly

Take n processes sharing one resource type. Each process's maximum simultaneous claim is k≥1, requests never exceed that claim, a process granted its remaining needs can finish and release, and there are no other causes of blocking. A sufficient worst-case resource count is R=n(k−1)+1.

Why? The largest allocation in which all n processes are still one unit short of k is n(k−1). One additional unit ensures enough resources to let at least one process reach its maximum in the worst distribution; it can then finish and release for the others. More generally, if no process's remaining claim fits the available units, summing each held count plus its shortfall contradicts R>n(k−1). This is a resource-deadlock guarantee under the model, not a guarantee against an unfair scheduler or unrelated locks.

For n=3,k=3, R=7 suffices. R=6 does not guarantee freedom: allocate 2 units to each process and let each request its third. All six are held and everyone waits. This counterexample shows 7 is the minimum count guaranteeing resource-deadlock freedom for all such allocation patterns. With different maxima k_i, the analogous bound is 1+Σ(k_i−1), under the same assumptions. Do not apply these single-type formulas by merely adding unlike resources together.

6. Detection needs a separate recovery decision

Finding a deadlocked set does not itself release anything. Recovery may abort selected processes, roll back work or preempt a resource only when its state can safely be preserved/restored. Lost work and repeated victim selection are costs; always choosing the same victim can cause starvation. Changing CPU time slices alone does not release a resource held by a blocked process. These are policy consequences, not actions this lesson performs.

Exam checklist

Keep Current Request and Need in separate columns. Check total resource conservation, compare vectors componentwise, record each Work update and state what remaining unfinished holders mean. For a resource bound, state all single-type/max-claim assumptions and exhibit a failure distribution one below the claimed guarantee.

Original practice: six single-correct MCQs

Choose exactly one option. Each question states its own required assumptions.

DD01. A current resource-deadlock detection reduction should test which vector against Work to see who can proceed now?

A. Declared Max directly B. Current outstanding Request C. Only the sum of Allocation D. Process identifier

Answer: B

A: Max is total declared claim, not the current outstanding request.

B: Detection reduces the current waits using Request≤Work componentwise.

C: Allocation totals do not identify unmet current requests.

D: A PID does not measure needed resources.

DD02. Available=(0,0). P0,P1,P2 allocations are (1,0),(0,1),(1,1), and current requests are (0,1),(1,0),(0,0). A process can finish after its request is granted and release all resources. Which reduction order works?

A. P0,P1,P2 B. P1,P0,P2 C. P2,P0,P1 D. No process can ever finish

Answer: C

A: P0 initially needs B, which is unavailable.

B: P1 initially needs A, which is unavailable.

C: P2 releases (1,1); P0 then releases (1,0); P1 can follow.

D: P2 currently requests nothing and can finish under the model.

DD03. Available=(0,0). Allocations of P0,P1,P2 are (1,0),(0,1),(1,1); their blocking current requests are (0,1),(1,0),(1,1). None can release until its request is granted. What does detection find?

A. Only P2 can finish first B. All three holders remain deadlocked C. No deadlock because total resources are (2,2) D. All requests already fit

Answer: B

A: P2 requests resources too; unlike a zero-request case it cannot proceed.

B: No nonzero current request fits zero Available and nobody can release.

C: Held resources are not currently available; total alone is insufficient.

D: All three requests require at least one unavailable unit.

DD04. One resource type has two instances. P0 and P1 each hold one, each declares Max=2, but each currently requests zero and will finish without further requests. What is true?

A. Currently deadlocked because remaining Max need is 1 each B. Unsafe under maximum claims, but no current deadlock in the stated execution C. Safe under maximum claims because Request=0 D. Neither process holds any resource

Answer: B

A: Need and current Request are different.

B: No maximum-claim safe sequence exists at Available=0, yet a zero-request process can finish and release.

C: Maximum-claim safety still considers Need=1 for each.

D: Each is explicitly holding one instance.

DD05. Three processes share one identical resource type. Each may hold at most 3 instances, can finish once its remaining claim is granted, and has no other blocking dependencies. What minimum total guarantees freedom from resource deadlock for every allocation pattern?

A. 3 B. 6 C. 7 D. 9

Answer: C

A: Each could hold one and still wait for more.

B: Each can hold two and request one more, leaving no free instance.

C: n(k−1)+1=3×2+1=7; six has the stated counterexample.

D: Nine suffices but is not the minimum guarantee.

DD06. During detection, Work=(2,1). A process holds Allocation=(1,2) and has Request=(1,1), which is granted temporarily before it completes and releases everything. What is the net new Work?

A. (3,3) B. (3,2) C. (4,4) D. (1,0)

Answer: A

A: Subtract Request then return Allocation+Request: net Work+Allocation=(3,3).

B: This adds only Request rather than the pre-existing allocation.

C: This double-counts the temporary request grant.

D: This is Work just after granting, before completion and release.

Sources and scope

This original lesson extends the existing OS foundations in the GATE 2026 course. It maps to Section 8 of the official 2026 syllabus; it is not a claim of complete OS coverage or GATE 2027 completeness. Practice questions are original, not past-exam questions.

• Official GATE 2026 CS syllabus, Section 8
• MIT Operating Systems Lecture Notes: Deadlock, Martin C. Rinard

Sources checked 2026-10-14.