25-Comp-A5 Operating Systems · December 2015

Question 5 of 7: Reliability and Deadlock Analysis

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

Notes on this paper

98-COMP A-5 Operating Systems — National Examinations, December 2015. 3 hours, closed book (one approved pocket calculator only). 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.) — CPU scheduling (ch. 5), process synchronization/monitors (ch. 6–7), deadlocks (ch. 8), memory management/paging (ch. 9–10), mass-storage/file-system implementation and disk scheduling (ch. 11–12), real-time systems (ch. 19); Tanenbaum, Modern Operating Systems (5th ed.), corroborating chapters on scheduling, virtual memory and file systems.

Question 5: Reliability and Deadlock Analysis (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) Multiple CPUs improve reliability through redundancy at the processing level: if one CPU fails, the OS can migrate its runnable processes to a surviving CPU and continue operating (graceful degradation) rather than the whole system halting, as a single-CPU failure would cause. Multiprocessor designs also allow one CPU to continuously monitor the health of the others (a watchdog/heartbeat scheme), catching failures faster than an external observer could. Multiple disks improve reliability primarily through data redundancy: mirroring (RAID 1) keeps a live duplicate of every block on a second disk, and parity schemes (RAID 4/5) let any single disk's lost data be reconstructed from the survivors' XOR parity, so a disk failure causes no data loss and (with hot-swappable drives) little to no downtime. Multiple disks also let the OS spread I/O load across several spindles, reducing the chance that a single mechanical failure takes down the only copy of critical data.

(b) Given. Four resource-allocation scenarios, all involving a single resource TYPE with $R$ identical units shared among $P$ processes, each process capped at holding at most $k$ units simultaneously. Find. Whether each is deadlock-free. Approach. Apply the standard sufficient-and-necessary threshold for a single resource type with identical per-process maxima: the system is guaranteed deadlock-free if and only if $R\ge P(k-1)+1$ — because that many units guarantee at least one process can always obtain its full need and finish, which then frees enough resources to unblock the rest. When $R\le P(k-1)$, a deadlock CAN be constructed: let enough processes each grab $(k-1)$ units to exhaust $R$, then have every one of them request one more unit.

(i) R=5, P=4, k=2 (non-sharable). $$P(k-1)+1 = 4(2-1)+1 = 5 = R$$ Since $R\ge P(k-1)+1$ holds with equality, even in the worst case where all 4 processes simultaneously hold their maximum-minus-one (1 each, using 4 units), 1 unit remains free — enough to satisfy whichever process requests next, let it finish, and release its resources to unblock the others. $$\boxed{\text{(i) Deadlock-free: mutual exclusion holds, but resources are always sufficient to avoid the wait condition maturing into a cycle}}$$
(ii) R=10, P=8, k=3 (non-sharable). $$P(k-1)+1 = 8(3-1)+1 = 17 > R=10$$ The guarantee fails. A concrete deadlock: let 5 of the 8 processes each acquire 2 units ($5\times2=10=R$, exhausting every unit); all resources are now held and 0 remain free. Each of those 5 processes then requests a 3rd unit (still within its cap of 3) and blocks, since none is available — and none can ever become available, because releasing requires a process to finish, which requires the very resource nobody can obtain. $$\boxed{\text{(ii) Deadlock CAN occur (all 4 conditions are met: mutual exclusion, hold-and-wait, no preemption, circular wait among the 5 processes)}}$$
(iii) R=2, P=10, read-only files, k=2. The resource here is a read-only file — a shareable resource: any number of processes may read it concurrently with no conflict, since reading never modifies it. The mutual exclusion condition (at least one resource must be held in a non-sharable, exclusive-access mode) is one of the four NECESSARY conditions for deadlock; if it never holds for a resource type, no process ever has to wait for another to release that resource, so a wait-for cycle can never form over it — regardless of how many processes (10) or how many "resources" (2, in the sense of distinct files) are involved. $$\boxed{\text{(iii) Deadlock CANNOT occur, for any R, P, or per-process max, because condition 1 (mutual exclusion) never holds for shareable/read-only resources}}$$
(iv) R=10, P=8, k=3, but 2 processes are high-priority and may preempt a resource from a low-priority holder. This preemption rule removes only the WAIT edges that would otherwise run FROM a high-priority process TO a resource held by a LOW-priority process (the high-priority process simply takes it instead of waiting) — i.e. it breaks the no preemption condition, but only across that one specific direction (high-over-low). It does nothing for waits among the 6 low-priority processes themselves, nor between the 2 high-priority processes if they contend with each other. The deadlock constructed in (ii) used only 5 processes holding 2 units each; choosing those 5 entirely from the 6 available low-priority processes builds exactly the same deadlock, completely untouched by the preemption rule (no high-priority process, and hence no preemption opportunity, is involved at all). $$\boxed{\text{(iv) Deadlock CAN still occur (constructed entirely among the low-priority process subset, where the preemption escape valve never applies)}}$$

Final Results — Q5(b)
Case	P(k−1)+1	Deadlock-free?
(i) R=5, P=4, k=2	5	Yes (R = threshold)
(ii) R=10, P=8, k=3	17	No — can deadlock
(iii) R=2, P=10, read-only, k=2	n/a (shareable)	Yes, unconditionally
(iv) R=10, P=8, k=3, 2 preemptive-high	17 (for the 6-process low-priority subset: threshold=11)	No — can still deadlock among low-priority processes

Topic: Reliability through redundancy, and the resource-count threshold for guaranteed deadlock-freedom.

Key relations: For $n$ processes sharing $m$ identical units of one resource type, each capped at $k$: deadlock-free is guaranteed iff $m\ge n(k-1)+1$. The four necessary conditions for deadlock are mutual exclusion, hold-and-wait, no preemption, and circular wait — removing ANY ONE for a given resource/process pairing prevents deadlock over that pairing.

Why this works: The threshold formula is the exact point past which it becomes IMPOSSIBLE for every process to simultaneously hold "one short of enough" — at $m=n(k-1)+1$ the pigeonhole principle guarantees at least one process holds its full need. Below the threshold, that same pigeonhole reasoning tells you exactly how many processes are needed to construct an explicit deadlock (as done for (ii) and (iv)).

Common pitfall: Applying the $n(k-1)+1$ threshold using the FULL process count $P$ when a subset of processes is exempt from ordinary contention (as in (iv)) — the correct move is to re-apply the threshold to the SUBSET that still faces ordinary (non-preemptible) contention, not to conclude that any preemption rule anywhere makes the whole system safe.

Source: Silberschatz, Galvin & Gagne, Operating System Concepts, ch. 8 (Deadlocks, §8.2 necessary conditions, §8.6 multiple-instance resource-allocation reasoning) and ch. 11 (RAID/reliability).

← Question 4 Next: Question 6 →