25-Comp-A5 Operating Systems · May 2018

Question 4 of 7: Deadlocks and Disk Scheduling

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

Notes on this paper

17-COMP A-5 Operating Systems — National Examinations, May 2018. 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.) — process synchronization/monitors (ch. 6–7), CPU scheduling (ch. 5), deadlocks (ch. 8), memory management/paging (ch. 9–10), mass-storage/file-system implementation and disk scheduling (ch. 11–12), protection (ch. 14); Tanenbaum, Modern Operating Systems (5th ed.), corroborating chapters on synchronization, scheduling, memory and file systems.

Question 4: Deadlocks 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.

(a) Resource-allocation graph (RAG) components and the cycle–deadlock question. A RAG is a directed graph with two kinds of vertices — processes (circles) and resource types (rectangles, one node per box, one dot per instance of that type) — and two kinds of edges: a request edge $P_i\to R_j$ (process $P_i$ is waiting for an instance of $R_j$) and an assignment edge $R_j\to P_i$ (an instance of $R_j$ is currently held by $P_i$). Deadlock corresponds to a set of processes each waiting on an edge that (transitively) leads back to itself with no way out.

A cycle in the RAG is a necessary condition for deadlock (no cycle $\Rightarrow$ no deadlock), but it is sufficient only when every resource type in the cycle has a single instance. If some resource type involved has multiple instances, a cycle does not necessarily imply deadlock, because an instance released by a process outside the cycle can free up a resource for a process inside it. Example: $R_1$ has two instances, held by $P_1$ and $P_2$; $P_1$ also holds $R_2$ (single instance) and requests $R_1$'s second instance while $P_2$ requests $R_2$ — the graph shows a cycle $P_1\to R_1\to P_2\to R_2\to P_1$, but if a third process $P_3$ also holds an instance of $R_1$ and is about to finish and release it, that release breaks the cycle's deadlock without any process in the cycle itself acting, so the cycle alone did not guarantee deadlock.

(b) Deadlock prevention. Prevention works by structurally ruling out at least one of the four necessary conditions (mutual exclusion, hold-and-wait, no preemption, circular wait) so that deadlock becomes structurally impossible, at some cost in resource utilization or concurrency:

Attack hold-and-wait — require a process to request and be granted all the resources it will ever need before it starts (or require it to release everything it currently holds before requesting anything new). Example: a batch job must declare "2 tape drives + 1 printer" up front; if not all are simultaneously available it is not started at all, ensuring it never holds some resources while blocked waiting for others.
Attack no-preemption — if a process holding resources requests another that cannot be immediately granted, preempt (take away) all its currently held resources instead of blocking it; those resources are only returned once it can be granted everything it needs at once. Example: a process holding a printer that requests a scanner has its printer allocation revoked and added back to its "resources still needed" list rather than being left blocked while holding the printer.
Attack circular wait — impose a total ordering on all resource types and require every process to request resources in strictly increasing order of that numbering. Example: if tape drives are numbered lower than printers, a process may request a tape drive then a printer, but never the reverse order; since a cycle in the wait-for relation would require some edge to go from a higher-numbered to a lower-numbered resource, no cycle can ever form.

(Attacking mutual exclusion is generally impractical for genuinely non-shareable devices like a printer, so it is rarely used in practice, unlike the three above.)

Given (c). 250 tracks (0–249). Last-served track 95, head currently at track 153 (so the head is moving upward). Pending FIFO queue: 94, 175, 80. No further arrivals.

Find. (i) total head movement under C-LOOK; (ii) total head movement under SSTF.

Approach. C-LOOK services all pending requests in the current direction of travel, then jumps directly (no service en route) to the lowest pending request on the other side and continues in the same original direction — it never travels all the way to the physical disk end (that would be plain LOOK/SCAN). SSTF greedily services whichever pending request is nearest the current head position at each step.

(i) C-LOOK. Moving up from 153, only 175 lies ahead ($94,80<153$). Service 175, then jump (circularly, no service) down to the lowest pending request 80, then continue upward through 94. $$\text{Movement}=(175-153)+(175-80)+(94-80)=22+95+14$$ $$\boxed{\text{Total head movement (C-LOOK)}=131\ \text{tracks, order }175\to80\to94}$$
(ii) SSTF. From 153: distances are $|175-153|=22$, $|94-153|=59$, $|80-153|=73$ → nearest is 175. From 175: remaining distances $|94-175|=81$, $|80-175|=95$ → nearest is 94. From 94: distance to 80 is 14. $$\text{Movement}=22+81+14$$ $$\boxed{\text{Total head movement (SSTF)}=117\ \text{tracks, order }175\to94\to80}$$

Fig. Q4(c) — track positions on the 0–249 platter. The head is moving up (last served 95 → current 153). C-LOOK services 175 first, then jumps directly (no service) down to the lowest pending request 80 and continues upward through 94 — total 22+95+14 = 131 tracks.

Final Results – Question 4(c)
Quantity	Value
Total head movement, C-LOOK	131 tracks (order 175, jump, 80, 94)
Total head movement, SSTF	117 tracks (order 175, 94, 80)

Concept & Theory

Topic. Resource-allocation graphs and deadlock conditions, deadlock prevention strategies, C-LOOK vs. SSTF disk scheduling.

Key relations. Single-instance RAG: cycle $\Leftrightarrow$ deadlock. Multi-instance RAG: cycle is necessary but not sufficient. C-LOOK total $=$ (distance to last request in current direction) $+$ (that request $-$ lowest pending) $+$ (subsequent ascending distances).

Why this works. Each prevention strategy removes one of Coffman's four necessary conditions, which are individually necessary and jointly sufficient for deadlock — removing any single one makes deadlock structurally impossible, though each has a real utilization cost (idle pre-allocated resources, preemption overhead, or restricted request ordering). C-LOOK's saving over full SCAN comes from never travelling all the way to the physical disk boundary; here it still loses to SSTF (131 vs. 117) because C-LOOK is committed to clearing every up-direction request before reversing, while a greedy nearest-first choice happens to match the request geometry better on this particular queue — SSTF is not always the better of the two in general, since its greedy choices can also strand a request far behind at the wrong moment on other queues.

Common pitfall. Confusing C-LOOK with plain LOOK/SCAN — C-LOOK's defining feature is the circular jump to the far end without reversing direction, which is not free (it still counts the full jump distance as head movement) but never counts distance to the physical disk boundary itself.

Source. Silberschatz, Galvin & Gagne, Operating System Concepts (10th ed.), §8.2–8.4 (RAG, deadlock conditions), §8.5 (deadlock prevention), §11.4 (disk-scheduling algorithms).

← Question 3 Next: Question 5 →