25-Comp-A5 Operating Systems · May 2013

Question 4 of 7: Virtual Memory and Fragmentation

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

Notes on this paper

98-COMP A-5 Operating Systems — National Examinations, May 2013. 3 hours, closed book, 100 marks. 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.) — scheduling (ch. 5), process synchronization/monitors (ch. 6–7), deadlocks (ch. 8), memory management/paging (ch. 9–10), file systems and disk scheduling (ch. 11–12); Tanenbaum, Modern Operating Systems (5th ed.), corroborating chapters on scheduling and file systems.

Question 4: Virtual Memory and Fragmentation (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 (17 references): 51, 52, 53, 54, 55, 53, 54, 51, 56, 57, 58, 57, 58, 59, 57, 58, 59; three page frames; demand paging (a page is loaded only on first reference/fault); all three frames start empty.

Find. (i) The page-fault count under LRU. (ii) The minimum possible page-fault count for any replacement algorithm with 3 frames (Belady's optimal / MIN algorithm).

Approach. Step through the reference string maintaining the 3-frame contents; for LRU evict the frame least recently referenced; for the optimal bound evict the frame whose page is referenced farthest in the future (or never again) — Belady proved this minimizes faults for any fixed frame allocation.

(i) LRU trace. The first three distinct pages (51, 52, 53) fault to fill the empty frames. Page 54 faults and evicts 51 (least recently used of the three). Page 55 faults and evicts 52. References 53 and 54 are now hits (both present). Page 51 faults again and evicts 55 (now the LRU page, since 53 and 54 were just re-touched). Pages 56, 57, 58 each fault in turn, evicting 53, 54, 51 respectively (each was the least-recently-used at that moment). References 57 and 58 hit. Page 59 faults, evicting 56. The final three references (57, 58, 59) are all hits. Counting the faults: 51, 52, 53, 54, 55, 51, 56, 57, 58, 59 — ten faults (full frame-by-frame trace in the table below). $$\boxed{\text{LRU faults} = 10}$$
(ii) Optimal (Belady/MIN) trace. The same first three faults (51, 52, 53) fill the frames. At reference 54, the frame holding 52 is evicted because 52 is never referenced again (farthest possible future use), while 51 is due back at position 8 and 53 at position 6 — both closer. At reference 55, 51's next use (position 8) is farther away than 53's (position 6) or 54's (none remaining before the end other than at position 7), so the frame holding 51 is evicted. References 53 and 54 hit next. At reference 51 (position 8), a fault occurs; among the resident {55, 53, 54} none is used again (55 never again; 53 never again after position 6; 54 never again after position 7 which has passed), so any of them may be evicted — evict 55. Pages 56, 57, 58 each fault; 56 is evicted at the very next fault (page 59) because it is never referenced again, while 57 and 58 both recur. References 57, 58 hit, then 59 faults and evicts 56, and the last three references (57, 58, 59) are all hits. This also totals ten faults. $$\boxed{\text{OPT faults} = 10}$$ The optimal bound equals the LRU count here — LRU already achieves the minimum possible for this particular reference string and frame count (this does not hold in general; it is a property of this specific string's strong locality).

LRU frame-by-frame trace (3 frames)
Ref #	Page	Hit/Fault	Frames after
1	51	Fault	51
2	52	Fault	51, 52
3	53	Fault	51, 52, 53
4	54	Fault (evict 51)	54, 52, 53
5	55	Fault (evict 52)	54, 55, 53
6	53	Hit	54, 55, 53
7	54	Hit	54, 55, 53
8	51	Fault (evict 55)	54, 51, 53
9	56	Fault (evict 53)	54, 51, 56
10	57	Fault (evict 54)	57, 51, 56
11	58	Fault (evict 51)	57, 58, 56
12	57	Hit	57, 58, 56
13	58	Hit	57, 58, 56
14	59	Fault (evict 56)	57, 58, 59
15	57	Hit	57, 58, 59
16	58	Hit	57, 58, 59
17	59	Hit	57, 58, 59

Final Results — Q4(a)
Algorithm	Page faults (3 frames)
LRU	10
Optimal (Belady/MIN) — the minimum achievable	10

(b) Thrashing occurs when the CPU spends more time servicing page faults (swapping pages in and out) than doing useful computation, because the set of pages a process is actively using (its working set) does not fit in the frames currently allocated to it. Example: suppose the operating system, seeing low CPU utilization, responds by admitting more processes to increase multiprogramming; each new process needs its own working set resident, so the total frames demanded across all processes now exceeds physical memory. Every process starts faulting constantly, each fault forces a slow disk I/O, CPU utilization drops further (because processes are blocked waiting on page-in), and the OS's own low-utilization response is to admit still more processes — a positive-feedback collapse. Detecting thrashing is typically done by monitoring the page-fault rate (or CPU utilization) per process or system-wide: a fault rate rising sharply while CPU utilization simultaneously falls is the signature of thrashing (as opposed to a fault rate rising because a process's actual demand grew, where utilization would stay healthy). Controlling it is done via the working-set model (track each process's actual referenced-page set over a trailing window $\Delta$ and only allocate a process CPU time if its whole working set can be resident) or via local/priority replacement combined with load control (reduce the degree of multiprogramming — suspend or swap out one or more processes entirely when a system-wide fault-rate threshold is exceeded, freeing their frames for the remaining processes).

(c) External fragmentation is the accumulation of free memory as many small, non-contiguous holes scattered throughout memory, such that the total free space may be large but no single hole is big enough to satisfy a new request — the fragmentation is "external" to any allocated block (as opposed to internal fragmentation, which is wasted space inside an allocated block). It arises naturally under variable-partition (contiguous) allocation as processes of different sizes are repeatedly loaded and removed, leaving irregular gaps. One standard control method is compaction: periodically relocate the resident processes so that all free memory is coalesced into one contiguous block (typically requiring relocatable code, e.g. via a base/relocation register, since every process's addresses shift). A more common modern alternative that avoids compaction's cost is paging itself — by allocating memory in fixed-size frames rather than variable contiguous partitions, external fragmentation is eliminated entirely (replaced by, at most, internal fragmentation of at most one page per process).

Topic: Page-replacement algorithms (LRU, Belady's optimal), thrashing, and external fragmentation.

Key relations: Belady's optimality theorem: evicting the page with the farthest-future (or no future) reference minimizes faults for a fixed frame count. Working-set size $WSS(t,\Delta)$ = number of distinct pages referenced in the window $(t-\Delta, t]$.

Why this works: LRU approximates OPT by using recency of past reference as a proxy for "will not be needed again soon," which works well under temporal locality (as this reference string exhibits, hence LRU and OPT tying at 10 faults) but can be fooled by reference patterns with poor locality (e.g. large sequential scans), where LRU can fault on every single reference (Belady's anomaly is a related but distinct phenomenon — LRU is immune to it, but FIFO is not). Thrashing is fundamentally a resource-allocation feedback problem, not a replacement-algorithm problem — no replacement policy fixes it once the aggregate working sets exceed physical memory.

Common pitfall: Confusing "more frames always means fewer faults" — true for stack algorithms like LRU and OPT, but famously false for FIFO (Belady's anomaly), so the guarantee does not generalize to every replacement policy. Also, confusing external fragmentation (fixable by compaction or paging) with internal fragmentation (fixable only by using smaller allocation units).

Source: Silberschatz, Galvin & Gagne, Operating System Concepts, ch. 10 (Virtual Memory) §10.4 (page replacement), §10.6 (thrashing, working-set model); ch. 9 §9.3 (fragmentation).

← Question 3 Next: Question 5 →