25-Comp-A5 Operating Systems, December 2019, Q5

Question 5 (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.

Check: the paper states 160 tracks numbered 0–159, but its own request queue contains 160, 174 and 176 — all outside that stated range. LOOK and SSTF never reference the disk's physical end, so both are computed directly from the given queue unaffected by this inconsistency; C-SCAN's answer does depend on the physical end, so we adopt the smallest round track count consistent with the queue, 200 tracks (0–199), and flag the assumption explicitly.

Given. Head at track 139, direction of travel increasing (it just came from track 130, a lower track number). Pending queue: 96, 157, 101, 176, 104, 160, 116, 174, 150.

Find. Total head movement (tracks) for LOOK, SSTF, and C-SCAN.

Approach. LOOK services all requests in the current direction up to the farthest pending request, then reverses (never travelling to the physical disk end); SSTF always jumps to whichever pending request is nearest the current head position; C-SCAN services in the current direction all the way to the physical end, wraps to track 0 (counting the wrap distance), then continues in the same direction.

(i) LOOK. Moving up from 139, service the ascending requests $\ge139$ in order (150, 157, 160, 174, 176), then reverse and service the remainder in descending order (116, 104, 101, 96) — LOOK stops at the farthest actual request in each direction, never continuing to track 0 or 199. $$\text{Up: }139\to150\to157\to160\to174\to176\ (=37)\qquad\text{Down: }176\to116\to104\to101\to96\ (=80)$$ $$\boxed{\text{LOOK total} = 37+80 = 117\text{ tracks}}$$

Fig. Q5(a)(i) — LOOK climbs to the farthest request above (176) then reverses to the farthest below (96), never touching tracks 0 or 199.

(ii) SSTF. Always dispatch the nearest remaining request to the current head position. From 139: nearest is 150 ($|150-139|=11$, versus 23 down to 116), then from 150 nearest remaining is 157 (7), then 160 (3), then 174 (14), then 176 (2), then 116 (60), then 104 (12), then 101 (3), then 96 (5). $$11+7+3+14+2+60+12+3+5=\boxed{117\text{ tracks}}$$ (SSTF happens to tie LOOK's total here, but for an unrelated reason — SSTF's greedy nearest-neighbour walk and LOOK's two-sweep walk simply land on the same total for this particular queue.)
(iii) C-SCAN (assuming 200 tracks, 0–199 — see check note above). Continue up through all requests $\ge139$ (150, 157, 160, 174, 176), continue to the physical end (199), wrap to track 0 (the wrap distance is counted, per the standard convention), then continue up through the remaining requests in ascending order (96, 101, 104, 116). $$\underbrace{(199-139)}_{60}+\underbrace{199}_{\text{wrap }199\to0}+\underbrace{(116-0)}_{116}=\boxed{375\text{ tracks}}$$ (Some texts do not count the fast return seek as head movement; on that convention the total is $60+116=176$ tracks.)

Final Results – Question 5(a)
Algorithm	Total head movement
LOOK	117 tracks
SSTF	117 tracks
C-SCAN (0–199 assumed)	375 tracks

(b) Bit-vector free-space management. Each block on the disk is represented by one bit in a vector held in memory: 1 = free, 0 = allocated (or vice versa by convention), so an $n$-block disk needs an $n$-bit map. Advantages: extremely compact (a 1 TB disk with 4 KB blocks needs only $2^{28}$ bits $\approx32$ MB); finding one or several contiguous free blocks is fast, since most CPUs have hardware instructions to find the first set bit in a word, letting the search skip a whole word (e.g. 32/64 bits) at a time when it is all zeros; simple to implement and to keep consistent (one bit flip per allocate/free). Shortcomings: for very large disks the whole vector should be kept resident in memory for speed, which can itself become a non-trivial memory cost; a linear (word-at-a-time) scan is still $O(n)$ in the worst case when free space is scarce and scattered; and the vector conveys no information about which blocks belong to which file, so it must be maintained alongside (not instead of) the file allocation structures.

(c) Belady's anomaly. Belady's anomaly is the counter-intuitive phenomenon, observed under FIFO page replacement, where increasing the number of allocated frames can increase the number of page faults for the same reference string, instead of monotonically decreasing them as intuition (more memory should only help) suggests. It occurs because FIFO's eviction choice (oldest-loaded page) is not related to how soon that page will actually be re-referenced, so adding a frame changes the whole sequence of which pages get evicted in a way that is not guaranteed to be strictly better. Algorithms free from the anomaly: any algorithm from the "stack algorithm" class — most importantly LRU and OPT (optimal/MIN) — is provably immune, because a stack algorithm's set of resident pages for $k$ frames is always a subset of its resident set for $k+1$ frames at every point in the reference string; adding a frame can therefore only ever keep an already-resident page resident for longer, never cause an additional fault. FIFO fails this subset property (its eviction order depends on load time, not use, so the $k$-frame and $(k+1)$-frame resident sets can diverge unpredictably), which is exactly why it (like other non-stack algorithms) is vulnerable to the anomaly.

Concept & Theory

Topic. Disk-arm scheduling (LOOK/SSTF/C-SCAN), bit-vector free-space management, and Belady's anomaly / stack algorithms.

Key relations. LOOK/C-SCAN travel = sum of consecutive absolute differences along the constructed service order; stack-algorithm property: resident set for $k$ frames $\subseteq$ resident set for $k+1$ frames at every step, for LRU/OPT but not FIFO.

Why this works. C-SCAN's uniform wait-time guarantee (every track waits at most one full sweep) comes precisely from always advancing in one direction and treating the disk as circular; SSTF, while typically fast on average, has no such guarantee and can starve a request that keeps losing the "nearest" comparison to a stream of closer arrivals.

Common pitfall. Confusing LOOK (stops at the farthest actual request) with SCAN (always travels to the physical disk end even if no request is there) — the two differ by exactly the "37+80" vs a longer end-to-end sweep. For Belady's anomaly, assuming all replacement algorithms can exhibit it; only non-stack algorithms (FIFO, and some non-stack heuristics) can.

Source. Silberschatz, Galvin & Gagne, Operating System Concepts (10th ed.), Ch.11 (Mass-Storage Structure – disk scheduling), Ch.14 (File-System Implementation – free-space management), Ch.10 (Belady's anomaly, stack algorithms).

Question 5 of 7

Question 5 (20 marks)