25-Comp-A5 Operating Systems · May 2014

Question 3 of 7: Working Sets, FIFO Paging, 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 2014. 3 hours, closed book (approved calculator only). 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 3: Working Sets, FIFO Paging, 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.

(a) The working set model defines, for each process at time $t$, the set $WS(t,\Delta)$ of distinct pages it has referenced in the most recent $\Delta$ references (the "working set window") — an operational approximation of the process's locality of reference at that moment. The OS tracks each running process's working-set size and only keeps a process resident (fully loaded and eligible to run) if the sum of all resident processes' working sets fits within physical memory; if a process's working set would not fit, that process is suspended (swapped out entirely) rather than left to run with too few frames. It prevents thrashing — the pathological state where the system spends nearly all its time servicing page faults rather than doing useful work, because every process has fewer frames than its own current locality requires — precisely by refusing to over-commit memory in the first place: the working-set admission test is a direct, continuously-recomputed measurement of how many frames each active process genuinely needs right now, so the degree of multiprogramming is throttled down (processes suspended) exactly when the combined working sets would exceed physical memory, before thrashing can start, rather than reacting after CPU utilization has already collapsed.

Given. Page reference string (17 references): 71, 72, 73, 74, 75, 73, 74, 71, 76, 77, 78, 77, 78, 79, 77, 78, 79; three page frames, all empty at the start; demand paging (a page loads only on the reference that first faults it in); FIFO replacement.

Find. The total number of page faults incurred by FIFO with 3 frames.

Approach. Step through the reference string maintaining the 3 resident frames as a FIFO queue; on a fault with all frames full, evict whichever resident page was loaded longest ago (regardless of how recently it was actually used — this is what distinguishes FIFO from LRU).

FIFO trace. The first three distinct pages (71, 72, 73) fault to fill the empty frames in load order [71, 72, 73]. Page 74 faults and evicts 71 (the oldest-loaded), giving [72, 73, 74]. Page 75 faults and evicts 72, giving [73, 74, 75]. References 73 and 74 are hits (both still resident). Page 71 faults again — even though 73 and 74 were just referenced, FIFO evicts strictly by load order, and 73 is now the oldest-loaded of the three, so 73 is evicted, giving [74, 75, 71]. Page 76 faults and evicts 74 (oldest), giving [75, 71, 76]. Page 77 faults and evicts 75, giving [71, 76, 77]. Page 78 faults and evicts 71, giving [76, 77, 78]. References 77 and 78 hit. Page 79 faults and evicts 76 (the oldest-loaded), giving [77, 78, 79]. The final three references (77, 78, 79) are all hits. Counting the faulting references: 71, 72, 73, 74, 75, 71, 76, 77, 78, 79 — ten faults (full frame-by-frame trace below). $$\boxed{\text{FIFO faults} = 10}$$

FIFO frame-by-frame trace (3 frames, load order shown oldest→newest)
Ref #	Page	Hit/Fault	Frames after (oldest→newest)
1	71	Fault	71
2	72	Fault	71, 72
3	73	Fault	71, 72, 73
4	74	Fault (evict 71)	72, 73, 74
5	75	Fault (evict 72)	73, 74, 75
6	73	Hit	73, 74, 75
7	74	Hit	73, 74, 75
8	71	Fault (evict 73)	74, 75, 71
9	76	Fault (evict 74)	75, 71, 76
10	77	Fault (evict 75)	71, 76, 77
11	78	Fault (evict 71)	76, 77, 78
12	77	Hit	76, 77, 78
13	78	Hit	76, 77, 78
14	79	Fault (evict 76)	77, 78, 79
15	77	Hit	77, 78, 79
16	78	Hit	77, 78, 79
17	79	Hit	77, 78, 79

(c) Fragmentation in memory management comes in two forms. External fragmentation arises with variable-sized partition allocation (or contiguous memory generally): as processes are loaded and removed, free memory becomes broken into many small, non-adjacent holes, and even though their total may be more than enough for a new request, no single hole is large enough to satisfy it. It is controlled by compaction (periodically sliding all allocated regions together to consolidate free space into one block — costly, since it typically requires relocating running processes) or, more fundamentally, by abandoning contiguous allocation altogether in favour of paging, which allocates memory in fixed-size frames so any free frame can satisfy any request, eliminating external fragmentation by design. Internal fragmentation is the flip side: with fixed-size allocation units (pages, or fixed partitions), a process's last page is usually only partially used, wasting the unused remainder of that page/partition; it is controlled by choosing a smaller page size (reduces the average per-process waste, at the cost of a larger page table) or, for partitions, choosing partition sizes that better match typical process sizes. Fragmentation in disk block allocation is conceptually the same family of problem: contiguous disk allocation suffers external fragmentation identically to contiguous memory (free disk space breaks into scattered extents, requiring disk compaction/defragmentation utilities), while fixed-block allocation (the norm for disks) suffers internal fragmentation whenever a file's size is not an exact multiple of the block size, wasting the unused tail of its last block — the same smaller-block-size trade-off applies, and clustering strategies (allocating in multi-block "extents" for large files) trade a little internal fragmentation back for reduced external fragmentation and fewer, larger disk transfers.

Topic: Working-set memory management and thrashing prevention; FIFO page replacement (Belady's-anomaly-prone); internal vs. external fragmentation in memory and on disk.

Key relations: Working set $WS(t,\Delta)$ = distinct pages referenced in the last $\Delta$ references; thrashing avoided when $\sum_{\text{resident processes}} |WS_i| \le$ total frames. FIFO evicts by load order, not recency of use.

Why this works: The working set is a direct, continuously updated proxy for "how much memory does this process need right now," so gating admission on it is a preventive (not reactive) control — unlike simply watching CPU utilization drop and only then reducing multiprogramming, by which point thrashing has already begun.

Common pitfall: Assuming FIFO behaves like LRU because both evict "old" pages — FIFO's age is measured from load time, not last use, which is why a heavily-reused page (like 73/74/77/78 above) can still be evicted while it is actively popular, and why FIFO is also the algorithm subject to Belady's anomaly (more frames can, perversely, produce more faults). For fragmentation, a common error is treating "small allocation unit" as a free lunch — it trades external fragmentation for more internal fragmentation and a larger metadata (page-table/block-map) overhead, not eliminating waste altogether.

Source: Silberschatz, Galvin & Gagne, Operating System Concepts, ch. 10 (Virtual Memory) §10.4 (FIFO), §10.6.2 (thrashing), §10.6.3 (working-set model); ch. 9 §9.2 (fragmentation); ch. 11 §11.4 (disk allocation methods).

← Question 2 Next: Question 4 →