25-Comp-A5 Operating Systems · December 2015

Question 3 of 7: Paging and Page Replacement

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

Notes on this paper

98-COMP A-5 Operating Systems — National Examinations, December 2015. 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: Paging and Page Replacement (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) Given. Byte addresses 102, 1001, 1249, 8800, 9991, 2780, 2701; page size 100 bytes. Find. (i) The page reference string; (ii) the minimum possible number of page faults it can produce. Approach. Page number $=\lfloor\text{address}/\text{page size}\rfloor$; the theoretical minimum fault count (given enough frames to hold every distinct page referenced) is simply the number of distinct pages, since a page can fault at most once if it is never evicted.

(i) Divide each address by 100 and floor. $$\lfloor102/100\rfloor=1,\ \lfloor1001/100\rfloor=10,\ \lfloor1249/100\rfloor=12,\ \lfloor8800/100\rfloor=88,\ \lfloor9991/100\rfloor=99,\ \lfloor2780/100\rfloor=27,\ \lfloor2701/100\rfloor=27$$ $$\boxed{\text{Page reference string} = 1,\ 10,\ 12,\ 88,\ 99,\ 27,\ 27}$$
(ii) Count distinct pages. The last two references (2780, 2701) both fall on page 27, so the string touches only $\{1,10,12,88,99,27\}$ — 6 distinct pages. With at least 6 frames available (or unlimited frames), each distinct page faults exactly once on its first reference and every later reference to the same page is a guaranteed hit, which is the best any policy can do. $$\boxed{\text{Minimum page faults} = 6}$$

Final Results — Q3(a)
Part	Result
(i) Page reference string	1, 10, 12, 88, 99, 27, 27
(ii) Minimum page faults	6 (number of distinct pages referenced)

(b) Given. Reference string 101,112,113,114,115,113,114,111,116,117,118,117,118,118,117 (15 references, frames initially empty); 5 frames allocated. Find. Page faults under (i) LRU and (ii) Optimal (Bélády). Approach. LRU evicts the resident page whose most recent reference is oldest; Optimal evicts the resident page whose NEXT reference lies farthest in the future (or never recurs), ties broken here by evicting whichever tied page has been resident longest, for a clean deterministic trace (the tie choice never changes the total fault count).

(i) LRU trace, 5 frames (bold = fault)
Ref#	Page	Outcome	Frames after (oldest→newest use)
1–5	101,112,113,114,115	5 cold faults	101,112,113,114,115
6	113	hit	101,112,114,115,113
7	114	hit	101,112,115,113,114
8	111	fault (evict 101)	112,115,113,114,111
9	116	fault (evict 112)	115,113,114,111,116
10	117	fault (evict 115)	113,114,111,116,117
11	118	fault (evict 113)	114,111,116,117,118
12–15	117,118,118,117	4 hits	114,111,116,118,117 (final)

Faults: references 1–5, 8, 9, 10, 11 — nine total (six hits at refs 6,7,12,13,14,15).

$$\boxed{\text{LRU page faults} = 9\ \text{(of 15 references; 6 hits)}}$$

(ii) Optimal trace, 5 frames
Ref#	Page	Outcome	Frames after
1–5	101,112,113,114,115	5 cold faults	101,112,113,114,115
6	113	hit	unchanged
7	114	hit	unchanged
8	111	fault (evict 101 — never referenced again)	111,112,113,114,115
9	116	fault (evict 112 — never again)	111,116,113,114,115
10	117	fault (evict 113 — never again)	111,116,117,114,115
11	118	fault (evict 114 — never again; 117 is protected, it recurs at 12 & 15)	111,116,117,118,115
12–15	117,118,118,117	4 hits	unchanged

Faults: references 1–5, 8, 9, 10, 11 — nine total, exactly matching LRU on this particular string (Optimal is never worse than LRU; here they happen to tie because every eviction LRU made at refs 8–11 was, in fact, also a page that would never be referenced again — the theoretically correct choice).

$$\boxed{\text{Optimal page faults} = 9\ \text{(of 15 references; 6 hits)}}$$

Final Results — Q3(b)
Policy	Page faults	Hits
LRU (5 frames)	9	6
Optimal (5 frames)	9	6

(c) Compile-time binding fixes a program's logical-to-physical address mapping when the program is compiled, producing absolute code that must be loaded starting at exactly the physical address the compiler assumed; if that starting location is ever unavailable, the whole program must be recompiled. This is only practical for simple, dedicated single-program systems (e.g. early batch systems, small embedded firmware) with no relocation or multiprogramming. Execution-time (load-time / run-time) binding defers the final physical-address mapping until the program actually runs, using a base/relocation register (or, in a paged system, the page table) that the OS can set differently every time the program is loaded, or even change WHILE the program runs (enabling a process to be moved in physical memory, or swapped out and back to a different location). This is essential for multiprogrammed and virtual-memory systems, since it lets the OS place processes wherever physical memory happens to be free and relocate them later, at the one-time cost of an extra address-translation step (a register add, or a page-table lookup) on every memory reference.

Topic: Address translation, LRU vs. optimal (Bélády) page replacement, and address-binding time.

Key relations: Page number $=\lfloor\text{address}/\text{page size}\rfloor$; minimum faults (unlimited frames) = number of distinct pages; LRU evicts by oldest last-use time; Optimal evicts by farthest (or absent) future use — Optimal's fault count is a proven lower bound that no online (non-clairvoyant) policy, including LRU, can beat.

Why this works: LRU approximates Optimal by using the past as a proxy for the future (recently-used pages are likely to be used again soon), which works well under strong temporal locality; it can only fail to match Optimal when a page's past usage pattern misleads about its future usage (e.g. a page used heavily then abandoned). In this reference string LRU's proxy happens to be perfect, hence the tie with Optimal.

Common pitfall: Reporting page faults without giving both faults AND hits (they should sum to the reference count, a useful self-check); assuming LRU is always strictly worse than Optimal (it is never better, but ties, as here, are common on strings without adversarial patterns).

Source: Silberschatz, Galvin & Gagne, Operating System Concepts, ch. 9 (Memory Management, address binding §9.1) and ch. 10 (Virtual Memory, §10.4 page-replacement algorithms).

← Question 2 Next: Question 4 →