25-Comp-A5 Operating Systems · May 2018

Question 5 of 7: Demand Paging and Page Reference Strings

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

Notes on this paper

17-COMP A-5 Operating Systems — National Examinations, May 2018. 3 hours, closed book (one approved pocket calculator only). 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.) — process synchronization/monitors (ch. 6–7), CPU scheduling (ch. 5), deadlocks (ch. 8), memory management/paging (ch. 9–10), mass-storage/file-system implementation and disk scheduling (ch. 11–12), protection (ch. 14); Tanenbaum, Modern Operating Systems (5th ed.), corroborating chapters on synchronization, scheduling, memory and file systems.

Question 5: Demand Paging and Page Reference Strings (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.

Given (a). 17-reference string over 9 distinct pages: 271, 272, 273, 274, 375, 273, 274, 271, 376, 277, 278, 277, 278, 279, 277, 278, 279.

Find. (i) minimum possible page faults; (ii) FIFO faults with 4 frames.

Approach. (i) With unlimited/sufficient frames, the only unavoidable faults are the first reference to each distinct page — every later reference to an already-resident page can be a hit. (ii) Step through the string with a 4-slot FIFO queue, evicting the longest-resident page on a miss with a full frame set.

1. (i) Minimum faults = number of distinct pages. The distinct pages referenced are $\{271,272,273,274,277,278,279,375,376\}$. $$\boxed{\text{Minimum page faults}=9}$$
2. (ii) FIFO trace, 4 frames.

   FIFO trace (4 frames) — F = fault, H = hit

   Ref #	Page	Frames after	Result
   1	271	271	F
   2	272	271,272	F
   3	273	271,272,273	F
   4	274	271,272,273,274	F
   5	375	272,273,274,375 (evict 271)	F
   6	273	272,273,274,375	H
   7	274	272,273,274,375	H
   8	271	273,274,375,271 (evict 272)	F
   9	376	274,375,271,376 (evict 273)	F
   10	277	375,271,376,277 (evict 274)	F
   11	278	271,376,277,278 (evict 375)	F
   12	277	271,376,277,278	H
   13	278	271,376,277,278	H
   14	279	376,277,278,279 (evict 271)	F
   15	277	376,277,278,279	H
   16	278	376,277,278,279	H
   17	279	376,277,278,279	H

   Counting the F entries (references 1–5, 8, 9, 10, 11, 14): $$\boxed{\text{FIFO page faults (4 frames)}=10}$$

Final Results – Question 5(a)

Quantity	Value
Minimum page faults (unlimited frames)	9
FIFO page faults (4 frames)	10

Given (b). Address sequence: 25, 175, 178, 177, 282, 283, 285, 25, 196, 199. Page size $=75$ words; addresses numbered from 0.

Find. The page reference string (page number = address ÷ page size).

Approach. Page boundaries fall at 0–74 (page 0), 75–149 (page 1), 150–224 (page 2), 225–299 (page 3), …; page number $=\lfloor \text{address}/75\rfloor$.

1. Translate each address. $25\to\lfloor25/75\rfloor=0$; $175,178,177\to\lfloor\cdot/75\rfloor=2$ (all in 150–224); $282,283,285\to3$ (in 225–299); $25\to0$; $196,199\to2$ (in 150–224). $$\boxed{\text{Page reference string}=0,2,2,2,3,3,3,0,2,2}$$
2. Reduced form. By the usual convention of collapsing immediately-repeated references to the same page (a resident page needs no fresh fault-decision on a back-to-back re-reference), the reduced string used for subsequent fault analysis is $$\boxed{\text{Reduced}=0,2,3,0,2}$$

Final Results – Question 5(b)

Quantity	Value
Full page reference string	0, 2, 2, 2, 3, 3, 3, 0, 2, 2
Reduced (no consecutive repeats)	0, 2, 3, 0, 2

---