25-Comp-A5 Operating Systems · December 2013

Question 3 of 7: Deadlock Possibility with a Single Resource Type

Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)

Notes on this paper

98-COMP A-5 Operating Systems — National Examinations, December 2013. 3 hours, closed book, 100 marks. Candidates were instructed to answer any five of the seven questions; all seven are answered below as a complete study resource.

Reference texts: Silberschatz, Galvin & Gagne, Operating System Concepts (10th ed.) — scheduling (ch. 5), process synchronization (ch. 6–7), deadlocks (ch. 8), memory management/paging (ch. 9–10), file systems and disk scheduling (ch. 11–12); Tanenbaum, Modern Operating Systems (5th ed.), corroborating chapters on scheduling and file systems.

Question 3: Deadlock Possibility with a Single Resource Type (20 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. $R=11$ identical resource instances; each of $P$ concurrent processes may hold at most $k=3$ instances at once; requests/releases are one instance at a time; no deadlock avoidance/prevention is used (a request is blocked only if zero instances are free).

Find. (i) Whether deadlock is possible for $P=2$. (ii) Whether deadlock is possible for $P=14$. (iii) The largest $P$ for which deadlock is provably impossible under every request pattern.

Approach. Deadlock is IMPOSSIBLE for a given $P$ if, even in the worst case where every process holds one short of its maximum ($k-1$ each), the total held is still strictly less than $R$ — because that guarantees at least one resource remains free, which lets at least one process obtain its last needed instance, finish, and release all $k$ of its instances, which in turn frees enough resources to let the next process finish, and so on (a cascading guarantee). Formally: deadlock is impossible whenever $P(k-1) < R$.

(i) P = 2. Worst case: both processes hold $k-1=2$ each, total held $=2\times2=4$, leaving $11-4=7$ resources free — far more than enough for either process to obtain its 3rd (final) needed instance and finish. Since $P(k-1)=4 < 11=R$, deadlock is impossible no matter how requests are interleaved. $$\boxed{P=2:\ \text{deadlock CANNOT occur}}$$
(ii) P = 14. Since $P(k-1)=14\times2=28\ge11=R$, the safety guarantee no longer holds, and an explicit deadlock configuration can be constructed: allocate at most 2 resources to each of as many processes as the 11 instances allow — e.g. 5 processes hold 2 instances each (10 total) and 1 more process holds the remaining 1 instance, using up all 11; the other $14-6=8$ processes hold 0. If every one of the 14 processes has already requested (and is blocked waiting for) one more instance than it currently holds — which is a legitimate request pattern the problem statement allows — then zero instances are free and no process can ever obtain the resource it is waiting for, since obtaining it requires another process to finish and release first, and none can finish. All 14 processes are then permanently blocked. $$\boxed{P=14:\ \text{deadlock CAN occur (explicit configuration exists)}}$$
(iii) Maximum P with deadlock provably impossible. Solve $P(k-1)

Final Results — Q3(a)
Case	Condition checked	Deadlock possible?
P = 2	$2(2)=4 < 11$	No
P = 14	$14(2)=28 \ge 11$	Yes (explicit configuration exists)
Maximum safe P	Largest integer with $2P<11$	P = 5

(b) A deadlock can occur only if all four Coffman conditions hold simultaneously, and the resource system above illustrates each cleanly using its own $P=6$ deadlock configuration. Mutual exclusion: each of the 11 resource instances can be held by only one process at a time (given, since resources are not shareable). Hold-and-wait: in the deadlock configuration, each of the six processes already holds 1 or 2 instances while simultaneously blocked waiting to request one more — it is not required to release what it holds before asking for more. No preemption: the system description explicitly states "no deadlock handling technique is employed" and resources are only released voluntarily by the holding process, never forcibly reclaimed by the OS — so a stuck process's held resources can never be taken away to unblock someone else. Circular wait: although there is only one resource TYPE, a circular wait can still form among instances of it — e.g., with all 11 instances allocated and every one of the six processes waiting for a release, we can order them $P_1\to P_2\to\cdots\to P_6\to P_1$ where each $P_i$ is "waiting on" a resource instance that will only become free once $P_{i+1}$ (arbitrarily assigned in this cycle) finishes and releases, closing the cycle back to $P_1$; this satisfies the circular-wait condition even though every instance is functionally identical. All four conditions holding together is necessary (removing any one, e.g. by prevention or avoidance, makes deadlock impossible), which is exactly what the safe bound $P(k-1)

Topic: The safe bound $P(k-1)

Key relations: Deadlock impossible whenever $\sum_i (\text{max}_i - 1) < R$; for uniform $\text{max}_i=k$ this reduces to $P(k-1)

Why this works: If every process holds strictly fewer than $\text{max}_i-1$... the sum of "worst case just-short-of-max" holdings staying below $R$ guarantees at least one resource is always free, which lets the process nearest its max acquire its last unit, finish, and release ALL its resources — cascading this argument shows every process can eventually finish in some order, which is precisely a safe-state guarantee (stronger than merely "not currently deadlocked").

Common pitfall: Concluding that a single resource TYPE cannot participate in circular wait because "there's only one kind of resource" — circular wait is about instances and processes forming a cycle of "waiting for release," which is entirely possible with multiple instances of one type, as the $P=6$ configuration shows.

Source: Silberschatz, Galvin & Gagne, Operating System Concepts, ch. 8 §8.2 (necessary conditions), §8.6 (this exact style of safe-bound argument appears as an exercise on deadlock-free resource-allocation bounds).

← Question 2 Next: Question 4 →