25-Comp-A5 Operating Systems · December 2014

Question 3 of 7: Protection, Security, 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 2014. 3 hours, closed book, 100 marks. 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.) — scheduling (ch. 5), process synchronization/monitors (ch. 6–7), deadlocks (ch. 8), memory management/paging (ch. 9–10), file systems and disk scheduling (ch. 11–12); Tanenbaum, Modern Operating Systems (5th ed.), corroborating chapters on scheduling and file systems.

Question 3: Protection, Security, 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) Security is the outward-facing concern of defending the system as a whole against threats originating outside its trust boundary — authenticating that a would-be user really is who they claim to be, resisting network intrusion, malware, and physical tampering. Protection is the inward-facing mechanism that governs what an already-authenticated subject (a user or a process acting on their behalf) is permitted to do to which resources once inside the system — it is a matter of internal policy enforcement, not external defence. A useful way to state the distinction: security asks "is this really Alice?"; protection asks "is Alice allowed to write to this file?"

On a multi-user file system, access control is the mechanism that implements protection: every file carries metadata (an access-control list, or the coarser Unix owner/group/other + read/write/execute bits) that the operating system consults on every open/read/write/execute request and compares against the requesting subject's identity and group memberships. This lets the system enforce least privilege (each user gets only the access they need), supports controlled sharing (a user can grant specific others read or write access without exposing the file to everyone), and creates an audit trail (accesses can be logged against the identity that access control already had to check). Without access control, any authenticated user could read or corrupt any other user's files, so protection would collapse into pure security (all-or-nothing system access) with no meaningful separation between users sharing the same machine.

(b) Given. 100 tracks, numbered 0–99; head currently at track 61, having just serviced a request at track 40 (so the head was travelling in the direction of increasing track numbers immediately before this point); pending request queue in FIFO arrival order: 98, 58, 11, 87, 99, 62, 18, 40; no further arrivals during service.

Check: assumes classic (elevator) SCAN, in which the head continues to the physical end of the disk (track 99) before reversing, and that "just finished a request at track 40" establishes the head's direction of travel immediately before t=61 as increasing.

Find. Total head movement, in tracks, to service all eight pending requests under (i) SSTF and (ii) SCAN.

Approach. For SSTF, repeatedly dispatch whichever pending request is numerically closest to the head's current position. For SCAN, continue in the head's current direction (increasing) servicing every request passed along the way and the disk's far end, then reverse and sweep back through the remaining requests.

(i) SSTF. From 61, the closest request is 62 (distance 1) — move there. From 62, closest remaining is 58 (distance 4). From 58, closest is 40 (distance 18). From 40, closest is 18 (distance 22). From 18, closest is 11 (distance 7). From 11, the two survivors 87 and 99 are far away; closest is 87 (distance 76). From 87, closest is 98 (distance 11). Finally 99 (distance 1). $$\text{Moves: }61\to62\to58\to40\to18\to11\to87\to98\to99$$ $$\boxed{\text{Ops}_{SSTF}=1+4+18+22+7+76+11+1=140\ \text{tracks}}$$
(ii) SCAN. The head is moving in the increasing direction, so it continues upward, servicing every pending request it passes: $61\to62\ (+1)\to87\ (+25)\to98\ (+11)\to99\ (+1)$, reaching the disk's far end at track 99 — a net $99-61=38$ tracks for this leg (the intermediate stops don't add extra distance since the sweep is monotonic). At 99 the head reverses and sweeps downward through the remaining requests in decreasing order: $99\to58\ (+41)\to40\ (+18)\to18\ (+22)\to11\ (+7)$, a net $99-11=88$ tracks for this leg. $$\boxed{\text{Ops}_{SCAN}=38+88=126\ \text{tracks}}$$

Fig. Q3(b)-i — SSTF head movement (numbered in dispatch order). Note step 6 (11→87, 76 tracks) is a costly long jump SSTF cannot avoid once it has greedily consumed every nearby request.

Fig. Q3(b)-ii — SCAN head movement. The head sweeps up to the disk end (99) before reversing, servicing every request exactly once each direction.

Final Results — Q3(b)
Algorithm	Service order	Total head movement
SSTF	62, 58, 40, 18, 11, 87, 98, 99	140 tracks
SCAN	62, 87, 98, 99, 58, 40, 18, 11	126 tracks

(c) Two standard ways multiple disks are combined to tolerate failures:

Mirroring (RAID 1). Every block written to one disk is duplicated, in full, on a second disk. If either disk fails, the surviving mirror has a complete, immediately usable copy of all data, so recovery is instant (just keep operating on the survivor and rebuild the failed disk from it later). The cost is 100% storage overhead — two disks buy the usable capacity of one.
Parity-based redundancy (RAID 4/5). Data is striped across $N$ disks and a parity block (the bitwise XOR of the corresponding data blocks) is stored on one disk (RAID 4, a dedicated parity disk) or rotated across all disks (RAID 5, avoiding a single parity-disk write bottleneck). If any single disk fails, its lost blocks are reconstructed on the fly by XOR-ing the corresponding blocks on the remaining disks with the parity block. This tolerates any one disk failure at a much lower storage overhead (1/$N$ of total capacity) than mirroring, at the cost of a slower rebuild and a write penalty (updating one data block also requires recomputing and rewriting its parity block).

Topic: Protection vs. security, disk-arm scheduling (SSTF/SCAN), and RAID-style fault tolerance.

Key relations: SSTF: greedily minimize $|next-current|$ each step. SCAN: total movement = (distance to the far end in the current direction) + (distance from the far end back to the farthest remaining request on the other side). RAID 5 parity: $P = D_1\oplus D_2\oplus\cdots\oplus D_{N-1}$, so any single missing $D_i = P\oplus(\text{all other }D_j)$.

Why this works: SSTF minimizes movement per step but is not globally optimal and can starve far-away requests (illustrated here by the costly 11→87 jump); SCAN bounds worst-case wait by guaranteeing every request is serviced within one full sweep, at the cost of sometimes travelling further than SSTF would for a given request set (126 vs. 140 tracks here, SCAN happens to win, but this is not universal). RAID 5's XOR reconstruction works because XOR is its own inverse: XOR-ing a value out and back in twice returns the original.

Common pitfall: Forgetting that SCAN's classic definition travels all the way to the disk boundary even when no request sits there (as opposed to the LOOK variant, which reverses immediately after the last request in the current direction) — using LOOK here would give a different, smaller total. For protection/security, students often conflate the two terms outright; remember protection presupposes the subject is already authenticated (security's job).

Source: Silberschatz, Galvin & Gagne, Operating System Concepts, ch. 11–12 (Mass-Storage/File-System Implementation, §12.4 disk scheduling, RAID structures) and ch. 13–14 (Protection, Security, access-control lists).

← Question 2 Next: Question 4 →