25-Comp-A5 Operating Systems · December 2013

Question 5 of 7: Multi-Resource Systems and Disk-Head Scheduling

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

Question 5: Multi-Resource Systems and Disk-Head 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) Multiple CPUs give the obvious advantage of true parallel execution (more work done per unit wall-clock time, not just better utilization of one CPU during I/O waits) and improved throughput/reliability (one CPU failing need not halt the whole system, if the OS supports graceful degradation). The overheads are: cache-coherence traffic between CPUs sharing memory; the added scheduling complexity of placement and affinity (Q1(b) above); and synchronization overhead, since shared data structures now need real mutual exclusion across CPUs (not just against a single CPU's own interrupts). Multiple disks give the advantage of parallel I/O (independent requests to different disks can be serviced simultaneously rather than queueing behind each other on one spindle) and, via RAID-style striping/mirroring, both higher aggregate throughput and fault tolerance against a single disk failure. The overheads are: the cost of the extra hardware itself; for mirroring, doubled storage and doubled write traffic; for parity schemes, the "small write penalty" (read-modify-write of both data and parity, i.e. up to 4 I/Os for what would be 1 I/O on a single disk); and, at the OS level, the added bookkeeping of deciding how to spread (stripe) a file's blocks across multiple physical disks.

Given. Head just completed a request at track 50 and is now at track 53 (i.e., moving in the direction of increasing track number). Pending FIFO queue: 38, 66, 92. 100 tracks numbered 0–99. No further arrivals during service.

Find. Total head movement to service all three pending requests under (i) SSTF, (ii) SCAN, and (iii) the order that minimizes total head movement.

Approach. SSTF always jumps to whichever pending request is currently nearest; SCAN continues in the head's current direction of travel to the physical end of the disk, then reverses; the true minimum-movement order for points on a line, visited from a fixed start with no requirement to return, is obtained by sweeping toward the NEARER extreme first, then reversing all the way to the FARTHER extreme (at most one reversal is ever needed).

1. (i) SSTF. From 53: distances to $\{38,66,92\}$ are $15,13,39$ — nearest is 66 (move 13). From 66: distances to $\{38,92\}$ are $28,26$ — nearest is 92 (move 26). From 92: only 38 remains (move 54). $$\boxed{\text{Total SSTF movement} = 13+26+54 = 93\ \text{tracks}}$$
2. (ii) SCAN. The head is moving upward (came from 50, now at 53), so SCAN continues upward, servicing $66$ then $92$ in increasing order, then travels on to the physical disk boundary at track 99 (true SCAN always reaches the boundary before reversing), then reverses and sweeps downward to service $38$. $$\text{Up: } 53\to99 = 99-53 = 46,\qquad \text{Down: } 99\to38 = 99-38 = 61$$ $$\boxed{\text{Total SCAN movement} = 46+61 = 107\ \text{tracks}}$$
3. (iii) Minimum-movement order. All three requests lie on a line relative to the start (53): one below (38, distance 15) and two above (66, 92; farthest is 92, distance 39). Visiting all requests with at most one reversal, the minimum is achieved by sweeping toward the NEARER extreme first, then reversing all the way to the FARTHER extreme — i.e., go DOWN to 38 first (distance 15), then reverse and sweep UP through 66 to 92 (distance $92-38=54$). Going the other way (up to 92 first, distance 39, then down to 38, distance 54) costs $39+54=93$ instead — worse, because the longer leg (up to the far extreme) would then be travelled twice in different pieces rather than once. Serving order: 38, then 66 (passed en route, serviced without any detour), then 92. $$\boxed{\text{Order } 38\to66\to92,\quad \text{Total movement} = 15+54 = 69\ \text{tracks}}$$ Notably, this beats BOTH SSTF (93) and SCAN (107) — neither named algorithm is actually optimal for this particular request set, since SSTF's greedy nearest-first choice and SCAN's boundary-reaching rule both travel to track 99 unnecessarily (SCAN) or strand the head on the wrong side (SSTF) before finally trekking back for 38.

(c) Execution-time address binding is the strategy of delaying the translation of a process's logical (virtual) addresses into physical memory addresses until the instant each memory reference is actually made at run time, rather than fixing the mapping at compile time or at load time. It requires hardware support — typically a base (relocation) register that is added to every logical address generated by the running process — and it is the ONLY binding strategy that allows a process to be moved (relocated) in physical memory after it has started executing, simply by changing the value in its base register, since no address inside the process's own code or data ever hardcodes an absolute physical location. This is what makes it possible for the OS to swap a process out to disk and back into a DIFFERENT physical location, or to compact memory to fight external fragmentation (Q4(a) above), without having to rewrite the process's code.