25-Comp-A5 Operating Systems, December 2019, Q3

Question 3 (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. Reference string of 20 accesses over 7 distinct pages {11,…,17}; base register = 1500, limit register = 1600.

Find. (a)(i)/(ii) the best- and worst-case fault counts achievable for any frame allocation; (b) the OPT fault count with exactly 3 frames; (c) physical address or addressing error for two logical addresses.

Approach. (i) the absolute floor on faults is one per distinct page (a page must be loaded the first time it is touched, however many frames exist); (ii) the absolute ceiling occurs with a single frame, which faults on every reference except an immediate repeat of the currently-resident page; (b) simulate Belady's optimal algorithm (evict the resident page whose next use is farthest in the future, or never reused) frame-by-frame; (c) an address is valid iff $0\le \text{logical}<\text{limit}$, and the physical address is then $\text{base}+\text{logical}$.

(a)(i) Minimum faults = number of distinct pages. The reference string touches pages $\{11,12,13,14,15,16,17\}$ — 7 distinct pages. With at least 7 frames available, every page faults exactly once (on first touch) and never again, so $$\boxed{f_{\min}=7}$$
(a)(ii) Maximum faults = length of the string, provided no two consecutive references repeat. With a single frame, a reference faults unless it requests the page currently resident (i.e. the immediately preceding reference). Scanning all 19 consecutive pairs of the 20-long string shows no pair repeats (11-12, 12-13, 13-14, 14-12, …, 13-16 are all distinct pairs), so every single reference is a fault under 1 frame: $$\boxed{f_{\max}=20}$$
(b) OPT with 3 frames — walk the string, evicting the resident page used farthest in the future. The first three distinct pages (11,12,13) fill the empty frames for free (3 faults). Each subsequent fault picks the resident page with no future use, or the largest next-use index, to evict.

OPT trace, 3 frames (F = fault)
Ref #	Page	Frames after	Fault?	Evicted (reason)
1	11	11,–,–	F	—
2	12	11,12,–	F	—
3	13	11,12,13	F	—
4	14	11,12,14	F	13 (next use furthest away, ref #12)
5	12	11,12,14	hit	—
6	11	11,12,14	hit	—
7	15	11,12,15	F	14 (never referenced again)
8	16	11,12,16	F	15 (never referenced again)
9–11	12,11,12	11,12,16	hit×3	—
12	13	12,13,16	F	11 (next use furthest away, ref #17)
13	17	13,16,17	F	12 (next use furthest away, ref #16)
14–15	16,13	13,16,17	hit×2	—
16	12	13,16,12	F	17 (never referenced again)
17	11	13,11,12	F	16 (next use furthest away, ref #20)
18–19	12,13	13,11,12	hit×2	—
20	16	16,11,12	F	13 (last reference — any resident page ties)

$$\boxed{f_{\text{OPT},3\text{ frames}}=11}$$

(c) Base/limit address translation. An address is valid iff $0\le L<\text{limit}=1600$; the physical address is then $\text{base}+L=1500+L$. (i) $L=607$: $607<1600$, valid. $\text{PA}=1500+607=\boxed{2107}$. (ii) $L=1702$: $1702\ge 1600$, outside the limit → addressing error / trap (segmentation fault) — no physical address is generated.

Final Results – Question 3
Quantity	Value
Minimum page faults (any allocation)	7
Maximum page faults (1 frame)	20
OPT page faults, 3 frames	11
Physical address for logical 607	2107 (valid)
Logical address 1702	Addressing error (limit exceeded)

Concept & Theory

Topic. Bounds on achievable page-fault counts, Belady's optimal (MIN) replacement algorithm, base/limit address protection.

Key relations. $f_{\min}=|\{\text{distinct pages}\}|$; $f_{\max}=$ reference-string length when no immediate repeats exist; OPT evicts $\arg\max(\text{next-use index})$, treating "never reused" as $+\infty$; $\text{PA}=\text{base}+\text{LA}$ valid iff $0\le \text{LA}<\text{limit}$.

Why this works. Belady's MIN algorithm is provably optimal because delaying the eviction of a soon-to-be-reused page can never help and evicting a never-reused (or furthest-reused) page can never hurt future fault counts — a straightforward exchange argument. Base/limit registers implement protection cheaply because the check is a single comparison plus an addition, entirely in hardware, needing no page table.

Common pitfall. Confusing "minimum faults" with "faults under a specific small frame count" — the true floor requires enough frames to hold every distinct page at once. For (c), forgetting that the limit register bounds the logical address (not the physical one), so $L=1600$ itself would already be invalid ($L<\text{limit}$ strictly).

Source. Silberschatz, Galvin & Gagne, Operating System Concepts (10th ed.), Ch.10 (Virtual Memory – optimal page replacement) and Ch.9 (Main Memory – base and limit registers).

Question 3 of 7

Question 3 (20 marks)