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.
(a) Given. Six byte addresses (100, 1001, 1250, 8800, 9990, 2780); page size 200 bytes. Find. The page number each address falls in. Approach. Page number $=\lfloor \text{address}/\text{page size}\rfloor$ (integer division), since page $k$ spans bytes $[200k,\ 200k+199]$.
Divide each address by the page size and floor.
$$\lfloor 100/200\rfloor=0,\quad \lfloor 1001/200\rfloor=5,\quad \lfloor 1250/200\rfloor=6,\quad \lfloor 8800/200\rfloor=44,\quad \lfloor 9990/200\rfloor=49,\quad \lfloor 2780/200\rfloor=13$$
$$\boxed{\text{Page reference string} = 0,\ 5,\ 6,\ 44,\ 49,\ 13}$$
(8800 divides exactly to 44.0, i.e. address 8800 is the very first byte of page 44.)
(b) Given. Reference string 71, 102, 103, 104, 105, 103, 104, 101, 106, 107, 108, 107, 108, 108, 107, 108, 101 (17 references); 4 frames, initially empty; LFU replacement. Find. The total number of page faults. Approach. Track a per-resident-page reference count (frequency), reset when a page is reloaded; on a fault with all frames full, evict the resident page with the lowest frequency, breaking ties by evicting whichever tied page was least recently touched (the standard LFU tie-break, since a pure frequency count alone cannot distinguish among equally-infrequent pages).
References 1–4 (71, 102, 103, 104) are compulsory (cold-start) faults — frames are empty, so each of the first four distinct pages simply fills a free frame. Frames after ref 4: {71:1, 102:1, 103:1, 104:1} (frequency shown after each page).
Reference 5 (105): not resident, frames full — fault. All four resident pages tie at frequency 1; the LRU tie-break picks the one touched longest ago, which is 71 (loaded at ref 1, never referenced again). Evict 71, load 105. Frames: {102:1, 103:1, 104:1, 105:1}.
References 6–7 (103, 104): hits — both are resident; bump their frequencies to 2 each. Frames: {102:1, 103:2, 104:2, 105:1}.
Reference 8 (101): fault. Lowest frequency (1) is tied between 102 (last touched ref 2) and 105 (last touched ref 5, more recent) — evict the older, 102. Frames: {103:2, 104:2, 105:1, 101:1}.
Reference 9 (106): fault. Lowest frequency (1) tied between 105 (ref 5) and 101 (ref 8, more recent) — evict 105. Frames: {103:2, 104:2, 101:1, 106:1}.
Reference 10 (107): fault. Tie at freq 1 between 101 (ref 8) and 106 (ref 9) — evict 101. Frames: {103:2, 104:2, 106:1, 107:1}.
Reference 11 (108): fault. Tie at freq 1 between 106 (ref 9) and 107 (ref 10) — evict 106. Frames: {103:2, 104:2, 107:1, 108:1}.
References 12–16 (107, 108, 108, 107, 108): all hits — 107 and 108 climb to frequency 3 and 4 respectively while 103 and 104 sit untouched at frequency 2. Frames unchanged: {103:2, 104:2, 107:3, 108:4}.
Reference 17 (101): fault. Lowest frequency (2) tied between 103 (last touched ref 6) and 104 (last touched ref 7, more recent) — evict 103 (older). Frames end at {104:2, 107:3, 108:4, 101:1}.
Counting the faulting references (1,2,3,4,5,8,9,10,11,17) against the 7 hits (6,7,12,13,14,15,16) accounts for all 17 references.
(c) A priority-based replacement engine always evicts the resident page with the extreme (minimum or maximum, per policy) priority value; each classical policy falls out of a specific rule for computing and updating that value:
(i) FIFO. Priority = the page's load time, assigned once when the page enters memory and never updated again. Evict the minimum-priority (oldest-loaded) resident page. Example: pages A, B, C, D loaded at times 1, 2, 3, 4 keep those priorities forever, regardless of how often they are re-referenced afterward — a fault evicts A first no matter how recently A was used, which is exactly FIFO's (sometimes counter-intuitive) behaviour.
(ii) LRU. Priority = the timestamp of the page's most recent reference, updated on every hit as well as on load. Evict the minimum-priority (least-recently-touched) resident page. Example: with pages A(last used t=5), B(t=9), C(t=2), D(t=7) resident, a fault evicts C, since t=2 is the oldest "last used" time even though C might have been loaded before or after the others.
(iii) Most Frequently Used (MFU). Priority = a running reference count, incremented on every hit (like LFU) — but MFU evicts the maximum-priority (most-referenced) page, on the reasoning that a page already referenced many times has "used up" its locality and is less likely to be needed again soon than a page that has barely been touched. Example: A referenced 6 times, B referenced 1 time — MFU evicts A, the opposite choice from LFU (which would evict B).
(iv) Optimal (Bélády's algorithm). Priority = the distance, in references, until the page is next used (a page never referenced again gets priority $+\infty$); this requires foreknowledge of the future reference string and so is unimplementable online, serving only as a theoretical lower bound. Evict the maximum-priority (farthest-future-use, or never-again-used) resident page. Example: if A is not referenced again for the rest of the string while B is referenced two steps from now, Optimal evicts A.
