25-Comp-A5 Operating Systems · May 2014

Question 6 of 7: Protection, Disk Scheduling, and Disk Redundancy

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

Question 6: Protection, Disk Scheduling, and Disk Redundancy (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) (i) Main memory protection is achieved with per-process base and limit registers (or, more generally, hardware address translation via paging/segmentation): every memory address a process generates is checked in hardware against that process's allocated range before the access is allowed, and any access outside it raises a protection-fault trap to the OS, so no user process can read or overwrite another process's (or the kernel's) memory. Paging strengthens this further with per-page protection bits (read/write/execute) checked on every memory reference by the MMU, catching finer-grained violations (e.g. writing to a page mapped read-only) with essentially zero added runtime cost since the check piggybacks on the address-translation hardware that already runs on every access. (ii) File-system protection is achieved through access-control mechanisms attached to each file/directory: a common scheme is owner/group/other permission bits (read/write/execute) checked by the OS on every open/access call, with a more general model being an access-control list (ACL) naming exactly which users or groups may perform which operations on a given file. Both approaches rely on the OS trusting its own kernel-mode enforcement (the check cannot be bypassed by a user-mode process) the same way memory protection relies on the MMU being inaccessible to user code.

Given. 200 tracks (0–199); head currently at track 161, having just finished a request at track 140 (so the head's most recent motion was upward, from 140 to 161 — the direction LOOK continues in). Pending queue in FIFO arrival order: 98, 158, 111, 187, 104, 162, 112, 188, 140 (note 140 recurs as a fresh pending request even though the head was just there — a different process may legitimately request the same track again). No further arrivals during service.

Find. Total head movement, in tracks, to service all nine pending requests under (i) LOOK and (ii) FCFS.

Approach. FCFS simply visits the queue in the order given, summing $|{\text{next}-\text{current}}|$ each step. LOOK sorts the pending requests and sweeps in the head's current direction of travel (upward) servicing every request ≥ the current position in increasing order, then reverses and services every request < the current position in decreasing order — unlike SCAN, it never travels past the last actual request to the physical end of the disk.

1. (i) LOOK. Sort the nine requests: 98, 104, 111, 112, 140, 158, 162, 187, 188. The head is at 161 moving upward, so it first services every request ≥ 161 in increasing order: $161\to162\to187\to188$. At 188 (the highest pending request — LOOK never overshoots to track 199 since nothing is requested past 188), the head reverses and services every request < 161 in decreasing order: $188\to158\to140\to112\to111\to104\to98$. $$\text{Up leg} = |162-161|+|187-162|+|188-187| = 1+25+1 = 27$$ $$\text{Down leg} = |158-188|+|140-158|+|112-140|+|111-112|+|104-111|+|98-104| = 30+18+28+1+7+6 = 90$$ $$\boxed{\text{Total}_{LOOK} = 27+90 = 117 \text{ tracks}}$$ (Equivalently, the up leg is $188-161=27$ and the reversed sweep spans the full range down to the lowest request, $188-98=90$, giving the same 117 total — a useful cross-check.)
2. (ii) FCFS. Service strictly in arrival order, starting from 161: $161\to98\to158\to111\to187\to104\to162\to112\to188\to140$. $$|98{-}161|+|158{-}98|+|111{-}158|+|187{-}111|+|104{-}187|+|162{-}104|+|112{-}162|+|188{-}112|+|140{-}188|$$ $$=63+60+47+76+83+58+50+76+48$$ $$\boxed{\text{Total}_{FCFS} = 561 \text{ tracks}}$$ FCFS's lack of reordering makes it revisit the low end of the disk (98, then back up to 158) and the high end (187, then back down to 104) repeatedly, which is exactly the wasted back-and-forth motion LOOK eliminates by sorting first.

(c) Disk failures are handled by RAID (Redundant Array of Independent Disks), which spreads data across multiple physical disks and adds redundancy so that the failure of one drive does not lose data. Mirroring (RAID 1) writes every block to two (or more) disks simultaneously; on a single-disk failure, the mirror still holds every block, and the failed disk is simply replaced and re-mirrored — the merit is fast recovery and no computation needed to reconstruct data, but the overhead is that only 50% of raw disk capacity is usable data (100% capacity overhead). Parity-based redundancy (RAID 5) stripes data across $N$ disks and stores a computed parity block (XOR of the corresponding blocks on the other disks) rotated across all $N$ disks; on a single-disk failure, every lost block can be reconstructed on the fly by XOR-ing the surviving blocks in that stripe with the parity block. Its merit is far better capacity efficiency than mirroring (only $1/N$ of capacity spent on parity, versus 50% for mirroring), but its overheads are a write penalty (every write must also read and rewrite the affected parity block — the "small write problem") and a slow, I/O-intensive rebuild after a disk failure that leaves the array running in a degraded, unprotected state until the rebuild finishes (during which a second failure would be unrecoverable, unlike RAID 6's two-parity-block scheme). Both schemes trade extra disk capacity and/or write overhead for the ability to survive a hardware failure without losing data — the appropriate choice depends on whether the workload is more sensitive to capacity cost (favouring parity) or to write latency and rebuild-time exposure (favouring mirroring).