25-Comp-A5 Operating Systems · May 2017

Question 2 of 7: Address Translation and Demand Paging

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

Notes on this paper

98-COMP A-5 Operating Systems — National Examinations, May 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); Tanenbaum, Modern Operating Systems (5th ed.), corroborating chapters on scheduling, virtual memory and file systems.

Question 2: Address Translation and Demand Paging (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. Base (relocation) register $=1200$; limit register $=1500$; logical address $=501$. Find. The physical memory address, or whether the reference is out of bounds. Approach. Base-and-limit translation is a bounds check followed by a simple addition: valid only if $0\le\text{logical}<\text{limit}$, in which case $\text{physical}=\text{base}+\text{logical}$.

Bounds check. $501 < 1500$ — the logical address is within the process's addressable range, so the reference is legal (no addressing trap).
Add the base (relocation) register. $$\boxed{\text{physical address}=1200+501=1701}$$

Final Results — Q2(a)
Quantity	Value
Bounds check	501 < 1500 → legal
Physical address	1701

(b) Given. Reference string 82, 83, 84, 85, 83, 84, 81, 86, 87, 88, 87, 88, 88, 87, 88, 81 (16 references, frames initially empty); 4 frames; FIFO replacement. Find. Total number of page faults. Approach. Simulate the FIFO queue of resident pages exactly: a fault occurs whenever the referenced page is not resident, and if all 4 frames are already occupied the page resident LONGEST (front of the FIFO queue) is evicted, regardless of how recently it was used.

FIFO trace, 4 frames (bold = fault; oldest-resident page shown first)
Ref#	Page	Outcome	Frames after (oldest→newest)
1	82	FAULT	82
2	83	FAULT	82, 83
3	84	FAULT	82, 83, 84
4	85	FAULT	82, 83, 84, 85
5	83	hit	82, 83, 84, 85
6	84	hit	82, 83, 84, 85
7	81	FAULT (evicts 82, oldest)	83, 84, 85, 81
8	86	FAULT (evicts 83)	84, 85, 81, 86
9	87	FAULT (evicts 84)	85, 81, 86, 87
10	88	FAULT (evicts 85)	81, 86, 87, 88
11	87	hit	81, 86, 87, 88
12	88	hit	81, 86, 87, 88
13	88	hit	81, 86, 87, 88
14	87	hit	81, 86, 87, 88
15	88	hit	81, 86, 87, 88
16	81	hit	81, 86, 87, 88

Count the FAULT rows. References 1–4 (compulsory misses filling the 4 empty frames) plus references 7–10 (81, 86, 87, 88 each miss and evict the then-oldest resident page) — 8 faults total; the remaining 8 references are all hits. $$\boxed{\text{FIFO page faults}=8}$$

Final Results — Q2(b)
Quantity	Value
Page faults (FIFO, 4 frames)	8 of 16 references

(c) A priority-based page replacement strategy always evicts the resident page with the numerically lowest priority value (treating priority here as "value to keep resident" — smaller means more disposable). Any classical replacement policy can be reproduced by choosing how a page's priority is set and updated:

(i) FIFO is reproduced by setting a page's priority to (the negative of, or simply) its load timestamp at the moment it is brought into memory, and never updating it again regardless of subsequent references. Example: pages A, B, C, D loaded at times 1, 2, 3, 4 keep priorities 1, 2, 3, 4 forever; whichever page is resident with the smallest timestamp (A, having been loaded longest ago) is evicted first, exactly reproducing "oldest resident page goes first" — the defining FIFO behaviour, indifferent to how often a page has actually been used since loading.

(ii) LRU is reproduced by setting a page's priority to its timestamp at every reference (not just at load time), so a page's priority is continually refreshed to "now" each time it is touched. Example: if A is loaded at $t=1$ and then referenced again at $t=10$ while B (loaded at $t=2$) is never touched again, at $t=11$ A's priority (10) is higher than B's (2), so B — the page whose most recent access is furthest in the past — is evicted first, exactly reproducing "least recently used."

(iii) LFU is reproduced by setting a page's priority to a running COUNT of how many times it has been referenced (incremented by 1 on every reference, starting at 0 or 1 on load), independent of when those references occurred. Example: page A referenced 8 times and page B referenced 2 times both currently resident — B has the lower reference count and is evicted first regardless of which one was touched more recently, exactly reproducing "least frequently used." (A pure counter never decays, so a page that was frequently used long ago but is now cold can resist eviction indefinitely — the well-known weakness of true LFU, sometimes mitigated by periodically halving all counts.)

Topic: Base-limit address translation, FIFO page replacement, and priority-value encodings of the classical replacement policies.

Key relations: $\text{physical}=\text{base}+\text{logical}$ when $0\le\text{logical}<\text{limit}$; FIFO evicts the page resident longest, irrespective of use; priority-as-timestamp-at-load $\to$ FIFO, priority-as-timestamp-at-every-reference $\to$ LRU, priority-as-reference-count $\to$ LFU.

Why this works: All three classical policies are really just "evict the minimum of some per-page scalar" — they differ only in WHAT that scalar tracks and WHEN it is updated, which is exactly why a single generic priority-replacement mechanism can implement any of them by supplying the right update rule.

Common pitfall: In the FIFO trace, evicting by RECENCY OF USE instead of recency of LOAD (that would silently turn the simulation into LRU) — FIFO never re-examines a page's position in the queue on a hit, which is exactly why pages 87/88/81 (heavily reused near the end) still eventually left the frame set once, back when they were the oldest resident page, only for a LATER reference to be a cheap hit once already resident again is irrelevant here since none of 81/86/87/88 fault twice in this particular string.

Source: Silberschatz, Galvin & Gagne, Operating System Concepts, ch. 9 (Memory Management, base/limit registers, §9.1), ch. 10 (Virtual Memory, §10.4 FIFO/LRU/LFU page replacement).

← Question 1 Next: Question 3 →