25-Comp-A5 Operating Systems · December 2015

Question 2 of 7: Demand Paging and Effective Access Time

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 2: Demand Paging and Effective Access Time (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) A demand-paged virtual memory system divides a process's logical address space into fixed-size pages, but loads a page into a physical memory frame only when it is actually referenced for the first time (on demand), rather than loading the entire process up front. A reference to a page not currently resident triggers a page fault, which the OS services by fetching the page from backing store (disk), possibly first evicting a resident page to free a frame. Advantages: (1) a process can run with far less physical memory than its total logical address-space size, since only the pages actually touched are ever resident; (2) more processes can be kept in memory simultaneously (higher degree of multiprogramming), improving CPU utilization; (3) a process can start executing before all of it is loaded, reducing startup latency; (4) unused code paths (error handlers, rarely-taken branches) may never be loaded at all, saving both memory and the I/O time to fetch them.

(b) Demand paging works because real programs exhibit the principle of locality of reference: at any point in execution a program references only a small, slowly-changing subset of its total address space. Spatial locality (nearby addresses tend to be referenced close together in time — sequential instruction execution, array traversal) means that once a page is fetched, most of the memory accesses that follow will hit other bytes already on that same page, amortizing the fault's cost. Temporal locality (recently referenced addresses tend to be referenced again soon — loop bodies, frequently-called subroutines) means that once a page is resident it will likely be reused many times before it needs to be evicted, again amortizing the one-time fault cost over many cheap in-memory accesses. Together these give programs a small, stable working set of pages that captures the overwhelming majority of memory references at any given time, which is exactly why loading only that working set (demand paging) achieves near-full-memory performance at a fraction of the physical memory footprint.

(c) Given. Page-fault service time: 20 ms if an empty frame is available or the replaced page is unmodified; 50 ms if the replaced page is modified. Memory access time $m_a=100$ ns. 60% of page faults require replacing a modified page (cost 50 ms); by implication the remaining 40% cost 20 ms. Find. The maximum page fault rate $p$ such that the effective access time (EAT) does not exceed 200 ns. Approach. Compute the fault-rate-weighted average page-fault service time, substitute into the standard EAT formula $EAT=(1-p)m_a+p\cdot t_{fault}$, and solve the resulting inequality for $p$.

Check: reads "for 60% of the page faults a page replacement is necessary and the page to be replaced is modified" as meaning 60% of ALL page faults cost 50 ms and the other 40% cost 20 ms (empty frame or unmodified victim) — the natural partition given only two stated service times.

Weighted average page-fault service time. Converting both service times to nanoseconds: $20\ \text{ms}=20{,}000{,}000\ \text{ns}$, $50\ \text{ms}=50{,}000{,}000\ \text{ns}$. $$t_{fault}=0.6(50{,}000{,}000)+0.4(20{,}000{,}000)=30{,}000{,}000+8{,}000{,}000=38{,}000{,}000\ \text{ns}$$
Set up the EAT inequality and solve for p. $EAT=(1-p)(100)+p(38{,}000{,}000)\le 200$. $$100-100p+38{,}000{,}000p\le 200 \;\Rightarrow\; p(38{,}000{,}000-100)\le 100 \;\Rightarrow\; p\le\dfrac{100}{37{,}999{,}900}$$ $$\boxed{p_{\max}\approx 2.632\times10^{-6}}$$ (about one page fault allowed per 380,000 memory references.)

Final Results — Q2(c)
Quantity	Value
Weighted average page-fault service time	38,000,000 ns (38 ms)
Maximum acceptable page fault rate	≈ 2.632 × 10^-6 (≈ 1 in 380,000 references)

Topic: Demand paging, locality of reference, and effective access time.

Key relations: $EAT=(1-p)\,m_a+p\cdot t_{fault}$, where $p$ is the page fault rate and $t_{fault}$ is the (possibly weighted-average) page-fault service time; here $t_{fault}$ is itself a probability-weighted mix of the modified- and unmodified-victim costs.

Why this works: Because $t_{fault}\gg m_a$ by many orders of magnitude (milliseconds vs. nanoseconds), even a vanishingly small fault rate dominates the EAT — this is precisely why keeping the page fault rate low is the single most important lever for virtual-memory performance, far more important than shaving nanoseconds off the hit-path memory access itself.

Common pitfall: Forgetting to convert both service times to the same unit as the memory access time before combining them (a units mismatch of 10⁶ here), and forgetting to weight the two fault costs by their stated probabilities rather than using either one alone.

Source: Silberschatz, Galvin & Gagne, Operating System Concepts, ch. 9–10 (Memory Management, Virtual Memory), §9.1 (demand paging, EAT) and §10.1 (locality, working-set model).

← Question 1 Next: Question 3 →