25-Comp-A5 Operating Systems · May 2013

Question 6 of 7: File Protection and Disk Scheduling

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

Question 6: File Protection 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) File protection is motivated by the fact that a general-purpose system stores files belonging to many different users (or serving many different purposes) on shared storage, and without protection any user's process could read, modify, or destroy any other user's data — whether by accident (a bug, a wrong path) or by malice. Protection provides confidentiality (unauthorized users cannot read), integrity (unauthorized users cannot modify or delete), and controlled sharing (specific other users or groups can be granted exactly the access the owner intends, no more).

An access list (access control list, ACL) attaches to each file an explicit list of (user-or-group, permission-set) pairs, e.g. a file report.docx might carry the list {(alice, read/write), (bob, read), (project-team, read)} — each entry names exactly who may do what. When a process attempts to open the file, the system walks the list looking for an entry matching the requester's identity (or group membership) and grants the intersection of the requested and listed permissions. Merits: access lists give fully general, per-user (or per-group), per-permission control — any subset of users can be granted any subset of {read, write, execute}, which is far more flexible than a single owner/group/other scheme. Deficiencies: the list can grow arbitrarily long (one entry per authorized user), consuming storage and slowing the lookup on every open; maintaining consistency is awkward when a user leaves an organization (every file they were granted access to must be found and updated); and, unlike a capability-based scheme, revoking one user's access requires editing the file's list directly rather than simply invalidating a token the user holds.

Given. Head currently at track 151, arriving from track 140 (i.e., moving in the direction of increasing track number). Pending FIFO queue: 96, 157, 191, 187, 104, 160, 112, 185, 140 (nine requests). 200 tracks, numbered 0–199. No further arrivals during service.

Find. Total head movement (sum of track distances travelled) to service all nine pending requests under (i) SCAN and (ii) SSTF.

Approach. SCAN continues in the head's current direction of travel, servicing every request it passes, all the way to the end of the disk, then reverses and sweeps back, servicing the remaining requests; SSTF always jumps to whichever pending request is currently closest to the head, regardless of direction.

1. (i) SCAN. The head is moving upward (140→151), so SCAN continues upward, servicing requests $\ge 151$ in increasing order — 157, 160, 185, 187, 191 — then travels on to the physical end of the disk at track 199 before reversing (true SCAN always reaches the disk boundary, unlike the LOOK variant which reverses at the last request). It then sweeps downward, servicing the remaining requests in decreasing order — 140, 112, 104, 96. $$\text{Up: } 151 \to 199 \;=\; 199-151 = 48$$ $$\text{Down: } 199 \to 96 \;=\; 199-96 = 103$$ $$\boxed{\text{Total SCAN movement} = 48 + 103 = 151\ \text{tracks}}$$
2. (ii) SSTF. From each position, jump to the closest remaining request. From 151: closest is 157 (distance 6). From 157: closest is 160 (3). From 160: closest is 140 (20, versus 185 at 25). From 140: closest is 112 (28, versus 185 at 45). From 112: closest is 104 (8). From 104: closest is 96 (8). From 96: closest of the three remaining {191,187,185} is 185 (89). From 185: closest is 187 (2). From 187: last remaining is 191 (4). $$\text{Distances: } 6+3+20+28+8+8+89+2+4 = 168$$ $$\boxed{\text{Total SSTF movement} = 168\ \text{tracks}}$$

(c) A standard method for handling disk failures is RAID (Redundant Array of Independent Disks) — most simply, mirroring (RAID 1), where every block written is duplicated onto a second physical disk, or block-interleaved parity (RAID 4/5), where one disk's worth of capacity across the array is used to store parity computed (XOR) across the corresponding blocks of the other disks. If any single disk fails, mirroring simply switches all reads to the surviving copy; parity-based schemes reconstruct the missing disk's data by XOR-ing the surviving disks and the parity block. Merits: the system continues operating (and, depending on the level, continues serving reads and writes) transparently through a single-disk failure, with no data loss, and the failed disk can be swapped and rebuilt while the system stays online (hot-swap/rebuild). Overheads: mirroring costs 100% extra storage (and extra write bandwidth, since every write is doubled); parity schemes cost only $1/N$ extra storage but pay a write penalty (a small write requires reading the old data block and old parity, then writing new data and new parity — four disk operations instead of one) and cannot tolerate a second simultaneous failure without a higher redundancy level (RAID 6, dual parity).