25-Comp-A5 Operating Systems · December 2017

Question 4 of 7: Deadlock Feasibility and Disk Scheduling

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

Notes on this paper

98-COMP A-5 Operating Systems — National Examinations, December 2017. 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 4: Deadlock Feasibility and Disk Scheduling (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 (a). $R=10$ identical resources; $P$ processes, each may hold up to $K$ resources simultaneously; requests/releases are one unit at a time; no deadlock-avoidance/detection scheme runs.

Find. (i) whether $P=15,K=3$ can deadlock; (ii) the largest $P$ (at $K=3$) that is deadlock-proof.

Approach. Use the standard sufficient condition for deadlock-freedom in a single-resource-type system: if $\sum_i(\text{max}_i-1) < R$, no process can ever be pushed into a state where it holds its maximum minus one and still finds zero available — hence deadlock is provably impossible. With uniform $K$, this is $P(K-1) < R$. If the inequality fails, an explicit deadlocking allocation can be constructed.

(i) Test the sufficient condition for $P=15,K=3$. $P(K-1)=15\times2=30$, and $30 \ge R=10$, so the safety guarantee does not hold — a deadlock is possible. Construct one explicitly: let 10 of the 15 processes each acquire exactly 1 resource (all $R=10$ units now held, 0 available). Every process (all 15, including the 5 that hold none) now requests one more unit. Since 0 are available, every request blocks. No process can reach its goal, so none can ever release what it holds — the system is deadlocked. $$\boxed{\text{P=15, K=3: a deadlock CAN occur}}$$
(ii) Solve for the largest safe $P$ at $K=3$. Require $P(K-1) < R \Rightarrow P(2) < 10 \Rightarrow P < 5$, so the largest integer satisfying this strictly is $P=4$. Check the boundary: at $P=5$, $P(K-1)=10=R$, which is not less than $R$, and indeed a deadlock can be built (all 5 processes acquire 2 of their 3 allowed resources, consuming all 10 units, and each then requests its 3rd unit and blocks forever). At $P=4$, $P(K-1)=8<10$: even in the worst case where all four processes simultaneously hold $K-1=2$ resources each (8 total, 2 still available), at least one process is guaranteed to be able to obtain its 3rd (final) resource, finish, and release all 3 — freeing enough resources to let every other process eventually complete in turn. No allocation sequence can deadlock this system. $$\boxed{P_{\max}=4}$$

Final Results – Question 4(a)
Quantity	Value
P=15, K=3, R=10 — deadlock possible?	Yes
Maximum deadlock-free P (K=3, R=10)	4

Given (b). 200 tracks (0–199); last serviced track 110, head currently at track 153 (so the head has just moved upward); pending FIFO queue: 137, 165, 192; no further arrivals.

Find. (i) total head movement under true SCAN; (ii) the serving order that minimizes total head movement.

Approach. SCAN continues in the current direction of travel to the physical end of the disk before reversing, regardless of whether a request lies exactly there. For (ii), compare the two "sweep to one extreme, then to the other" strategies directly, since visiting three collinear points from a starting point is minimized by picking an end to visit first.

(i) True SCAN: continue upward to track 199, then reverse. Since the head is moving from 110 towards 153 (increasing), SCAN keeps moving up, serving 165 then 192 along the way, continues to the physical end of the disk at track 199, then reverses and moves all the way down to the lowest pending request, 137. $$\text{Movement}=(199-153)+(199-137)=46+62$$ $$\boxed{\text{Total head movement (SCAN)}=108\ \text{tracks}}$$
(ii) Minimizing total movement need not follow strict SCAN. The head only has to visit $\{137,165,192\}$ once each; it need not travel all the way to track 199 first. Comparing the two possible "one direction then the other" strategies from the current position 153: $$\text{Up-first (192, then back down to 137)}: (192-153)+(192-137)=39+55=94$$ $$\text{Down-first (137, then up to 192)}: (153-137)+(192-137)=16+55=71$$ Serving 137 first (reversing direction immediately) is cheaper because it uses the short 16-track hop down before making the one unavoidable full sweep across the 55-track span from 137 to 192; going up first wastes an extra $2\times(153-137)$-equivalent by visiting 192 before backtracking past 153 down to 137. $$\boxed{\text{Optimal order: }137\to165\to192,\ \text{total movement}=71\ \text{tracks}}$$

Final Results – Question 4(b)
Quantity	Value
Total head movement, true SCAN	108 tracks (order 165, 192, then reverse via 199 to 137)
Minimum possible total head movement	71 tracks (order 137, 165, 192)

Fig. Q4(b) — track positions on the 0–199 platter. True SCAN sweeps all the way to track 199 (108 total); reversing immediately at 192 instead (order 137→165→192) costs only 71.

(c) Execution-time address binding. Address binding is the process of mapping the logical (program-relative) addresses a process uses to actual physical memory addresses. Execution-time (dynamic) binding defers this mapping until the instant each memory reference is actually made during execution, rather than fixing it at compile time or at load time. It requires hardware support — typically a base/relocation (or page-table) register that the MMU adds to every logical address on the fly — and its defining advantage is that a process's physical location can change while it is running (e.g. it can be swapped out and reloaded into a different physical location, or its pages can be scattered across arbitrary frames as in demand paging) without any change to the program's code, because the CPU never uses a fixed physical address directly. This is precisely the binding scheme that makes paging, segmentation, and swapping possible.

Concept & Theory

Topic. Necessary/sufficient deadlock-freedom bounds for single-resource-type systems, SCAN disk scheduling, and address-binding times.

Key relations. Deadlock-free guarantee: $\sum_i(\max_i-1)<R$; SCAN total movement (bidirectional to the disk end) $=(\text{end}-\text{current})+(\text{end}-\min(\text{queue}))$ when moving up.

Why this works. The deadlock bound comes from the worst case where every process holds one short of its maximum simultaneously — if that worst case still leaves at least one spare resource, some process can always complete and release, which unblocks the rest by induction. SCAN's "always sweep to the physical end" rule bounds worst-case wait time (fairness) at the cost of extra travel when few requests lie near the end, which is exactly the gap Q4(b)(ii) exploits.

Common pitfall. Treating $P(K-1)<R$ as an "if and only if" deadlock predicate — it is only a sufficient condition for safety; failing it means deadlock is possible, not certain. For SCAN, a common mistake is stopping at the last request instead of continuing to the physical disk boundary (that variant is LOOK, not SCAN).

Source. Silberschatz, Galvin & Gagne, Operating System Concepts (10th ed.), §8.9 (deadlock-avoidance bounds, exercises), §11.4 (SCAN/C-SCAN disk scheduling), §9.1.2 (address binding).

← Question 3 Next: Question 5 →