25-Comp-A5 Operating Systems · December 2017

Question 3 of 7: Page Replacement and Memory Allocation

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

Notes on this paper

98-COMP A-5 Operating Systems — National Examinations, December 2017. 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.) — CPU scheduling (ch. 5), process synchronization/monitors (ch. 6–7), deadlocks (ch. 8), memory management/paging (ch. 9–10), mass-storage/file-system implementation and disk scheduling (ch. 11–12), real-time systems (ch. 19); Tanenbaum, Modern Operating Systems (5th ed.), corroborating chapters on scheduling, virtual memory and file systems.

Question 3: Page Replacement and Memory Allocation (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. Page reference string of 17 references over 9 distinct pages (171, 172, 173, 174, 177, 178, 179, 275, 276); 3 frames; pure LRU replacement (no pre-loading — each frame starts empty and the first reference to a page is always a fault).

Find. Total number of page faults.

Approach. Step through the reference string one access at a time, keeping a 3-slot frame set and a recency stamp per resident page; on a miss with a full frame set, evict the page with the oldest recency stamp.

LRU trace (3 frames) — F = fault, H = hit
Ref #	Page	Frames after	Result
1	171	171	F
2	172	171,172	F
3	173	171,172,173	F
4	174	172,173,174 (evict 171)	F
5	275	173,174,275 (evict 172)	F
6	173	173,174,275	H
7	174	173,174,275	H
8	171	173,174,171 (evict 275)	F
9	276	174,171,276 (evict 173)	F
10	177	171,276,177 (evict 174)	F
11	178	276,177,178 (evict 171)	F
12	177	276,177,178	H
13	178	276,177,178	H
14	179	177,178,179 (evict 276)	F
15	177	177,178,179	H
16	178	177,178,179	H
17	179	177,178,179	H

Counting the F entries: references 1–5, 8, 9, 10, 11, 14 are faults. $$\boxed{\text{Total page faults}=10}$$

Given (b). Free list (in list order): 302K, 243K, 405K, 480K, 270K, 291K, 325K, 350K. Jobs arrive strictly in the order Job1(322K)→Job2(305K)→Job3(403K)→Job4(290K); no job releases memory during this sequence.

Find. Which hole each job is allocated under (i) best fit and (ii) first fit.

Approach. Best fit scans the whole free list for the smallest hole that is still ≥ the request; first fit scans from the head of the list and takes the first hole ≥ the request. After an allocation the hole shrinks by the request size (the leftover remainder stays in the free list at the same position); if a hole is reduced to 0 it is removed.

(i) Best fit

Best-fit allocation trace
Job	Request	Smallest sufficient hole	Remainder left behind
Job 1	322K	325K	325−322 = 3K
Job 2	305K	350K (only 350/405/480 still ≥305; 325 now only 3K)	350−305 = 45K
Job 3	403K	405K	405−403 = 2K
Job 4	290K	291K	291−290 = 1K

Free list after all four jobs (best fit): 302K, 243K, 2K, 480K, 270K, 1K, 3K, 45K — every job is placed, with four slivers (1–45K) left as unusable fragments.

(ii) First fit

First-fit allocation trace
Job	Request	First sufficient hole (scanning from list head)	Remainder left behind
Job 1	322K	405K (302K, 243K both too small)	405−322 = 83K
Job 2	305K	480K (302, 243, 83 all too small)	480−305 = 175K
Job 3	403K	none — allocation fails	—
Job 4	290K	302K (head of list)	302−290 = 12K

Result worth flagging

Under first fit, by the time Job 3 (403K) arrives the largest surviving hole is only 350K (untouched) / 175K (Job 2's remainder) — no hole reaches 403K, so Job 3 cannot be allocated at this point and must wait until a hole large enough is freed. Best fit, by contrast, successfully places all four jobs because it reserves the large 405K/480K holes for the two largest requests (Job 1 and Job 3) instead of consuming them early on smaller jobs.

Final Results – Question 3
Quantity	Value
LRU page faults (3 frames)	10
Best fit: Job1/Job2/Job3/Job4 → hole	325K / 350K / 405K / 291K (all placed)
First fit: Job1/Job2/Job3/Job4 → hole	405K / 480K / fails / 302K

Concept & Theory

Topic. LRU page replacement and dynamic-partition allocation policies (best fit vs. first fit).

Key relations. LRU evicts $\arg\min_{\text{resident }p}(\text{last-use time of }p)$; best fit minimizes leftover-hole size per allocation, first fit minimizes search time.

Why this works. LRU approximates Belady's optimal (evict the page used furthest in the future) by assuming recent past use predicts near-future use — it needs only a recency stamp, not lookahead. Best fit tends to leave many tiny, unusable slivers (visible above as four <50K remainders) but packs large holes efficiently for large requests; first fit is faster to search but can prematurely fragment the large holes it meets first, exactly what strands Job 3 here.

Common pitfall. Forgetting that a hole shrinks (rather than disappears) after a partial allocation, and re-scanning from the head each time in first fit (rather than continuing where the previous search left off, which would be next fit — a different policy).

Source. Silberschatz, Galvin & Gagne, Operating System Concepts (10th ed.), §10.4.2 (LRU approximation and exact LRU), §9.2.1 (fixed/variable partitioning, best-fit/first-fit/worst-fit).

← Question 2 Next: Question 4 →