25-Comp-A5 Operating Systems · May 2015

Question 4 of 7: Necessary Conditions for Deadlock; PID-Ordered Resource Waiting; Safe vs. Unsafe States

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

Notes on this paper

98-COMP A-5 Operating Systems — National Examinations, May 2015. 3 hours, closed book (approved calculators only), 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/monitors (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 4: Necessary Conditions for Deadlock; PID-Ordered Resource Waiting; Safe vs. Unsafe States (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.

(a) The four necessary conditions for deadlock

Deadlock can only arise when all four of the following hold simultaneously: Mutual exclusion — at least one resource must be held in a non-shareable mode, so that only one process can use it at a time (e.g. a printer, or a write-lock on a database row; a read-only shared file does not qualify). Hold and wait — a process must be able to hold at least one resource while simultaneously waiting to acquire additional resources held by others (e.g. a process holds a scanner and requests a printer that another process holds). No preemption — a resource can only be released voluntarily by the process holding it, once it has finished, and cannot be forcibly taken away (e.g. the OS cannot simply strip a process of a lock it holds mid-transaction, unlike CPU time which can be preempted). Circular wait — there exists a cycle of processes $P_1,P_2,\dots,P_n$ where each $P_i$ is waiting for a resource held by $P_{i+1\bmod n}$ (e.g. process A holds resource X and waits for Y, held by process B, which waits for X). All four are necessary; removing any single one (e.g. allowing preemption, or imposing a resource-acquisition ordering that makes circular wait impossible) is sufficient to prevent deadlock.

(b) Does the PID-ordered waiting rule permit deadlock?

Given. Whenever process A requests a resource held by process B: if $\text{PID}(A) > \text{PID}(B)$, A waits for B; otherwise ($\text{PID}(A) < \text{PID}(B)$), A is terminated and restarted (it never waits). PIDs are unique.

Find. Whether a deadlock (circular wait among blocked processes) can occur under this rule.

Approach. A deadlock requires a cycle in the wait-for graph. Show that the PID rule makes every edge of that graph point in a consistent direction (high PID $\to$ low PID), which makes a cycle numerically impossible.

Set up the wait-for graph. Draw a directed edge $P_i \to P_j$ whenever process $P_i$ is waiting (blocked, not terminated) for a resource held by $P_j$. By the given rule, an edge $P_i\to P_j$ can exist only when $\text{PID}(P_i) > \text{PID}(P_j)$ — a lower-PID requester is never allowed to wait at all (it is terminated and restarted instead), so it can never appear as the source of a wait-for edge.
Assume a cycle exists and derive a contradiction. Suppose, for contradiction, a directed cycle $P_1\to P_2\to\cdots\to P_k\to P_1$ exists in the wait-for graph ($k\ge2$). By Step 1, each edge $P_i\to P_{i+1}$ implies $\text{PID}(P_i)>\text{PID}(P_{i+1})$, and the closing edge $P_k\to P_1$ implies $\text{PID}(P_k)>\text{PID}(P_1)$. Chaining these: $$\text{PID}(P_1) > \text{PID}(P_2) > \cdots > \text{PID}(P_k) > \text{PID}(P_1)$$ $$\boxed{\text{PID}(P_1) > \text{PID}(P_1)\ \text{--- a contradiction, since PIDs are real-valued and distinct}}$$
Conclusion. No directed cycle can exist in the wait-for graph, so no circular wait is possible, and therefore no deadlock can occur on this system. The scheme is in fact a textbook deadlock-prevention technique (the "wait–die" scheme, using PID as a total order in place of a timestamp): forcing every wait-for edge to point strictly downward in a fixed total order (here, by PID) makes a cycle numerically impossible, at the cost of restarting (aborting) some lower-priority requesters rather than letting them wait.

Final Results — Question 4(b)
Question	Answer
Can deadlock occur?	No. Every wait-for edge points from a higher PID to a lower PID, so a cycle (which would require the sequence to return to a larger value) is impossible.
What scheme is this?	The "wait–die" deadlock-prevention scheme, with PID used as the total order in place of a timestamp.

(c) Safe, unsafe, and deadlock states

A system is in a safe state if there exists at least one ordering (a "safe sequence") of all currently active processes such that, run in that order, each process's maximum possible future resource demand can always be met from the resources currently available plus whatever is released by processes earlier in the sequence as they finish — the system, in other words, can guarantee every process will eventually complete no matter what any process actually requests, up to its stated maximum. An unsafe state is simply any state that is not safe: no such guaranteed-completion ordering exists, which means some future sequence of requests could lead to deadlock — but it does not mean deadlock is certain, since the processes might never actually request their full stated maximums. A deadlock state is a concrete, already-occurred standstill: a specific set of processes are each actually blocked, waiting on one another, with no path forward at all. The relationship is one-directional: every deadlocked state is (trivially) unsafe, but an unsafe state need not ever become an actual deadlock — it is a state of risk, not of certain failure. This is exactly the distinction the Banker's Algorithm exploits: it refuses any request that would move the system from a safe state into an unsafe one, which is strictly more conservative (and gives up some resource utilization) compared to only detecting deadlock after it has actually happened.

Topic: The four necessary conditions for deadlock; deadlock prevention via a total wait-for ordering (wait–die); safe/unsafe/deadlock states.

Key relations: Deadlock $\iff$ mutual exclusion $\wedge$ hold-and-wait $\wedge$ no preemption $\wedge$ circular wait (all four, simultaneously). A safe state guarantees a completion ordering exists for the stated maximum claims; deadlock $\Rightarrow$ unsafe, but unsafe $\nRightarrow$ deadlock.

Why this works: Any scheme that imposes a strict total order on which direction "waiting" is allowed to flow (by resource type, by timestamp, or as here by PID) makes circular wait — and hence deadlock — structurally impossible, because a cycle in a strict total order is a logical contradiction, not merely unlikely. This is the same underlying idea as the classical "always request resources in increasing numeric order" prevention technique, just applied to processes instead of resources.

Common pitfall: Concluding that the wait–die-style scheme in (b) is deadlock-free "because processes get terminated instead of deadlocking," without identifying why termination is forced exactly when it is (i.e., without noting that termination only occurs on the low-PID side, which is precisely the direction that would otherwise complete the cycle). Also: confusing "unsafe" with "deadlocked" — a system can sit in an unsafe state indefinitely and still finish all its processes successfully if the worst-case demand pattern never materializes.

Source: Silberschatz, Galvin & Gagne, Operating System Concepts, ch. 8 §8.2 (necessary conditions), §8.4 (deadlock prevention, wait–die/wound–wait), §8.5 (deadlock avoidance, safe states, Banker's Algorithm).

← Question 3 Next: Question 5 →