25-Comp-A5 Operating Systems · December 2014

Question 6 of 7: Virtual Memory, Effective Access Time, and Locality

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

Notes on this paper

98-COMP A-5 Operating Systems — National Examinations, December 2014. 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 6: Virtual Memory, Effective Access Time, and Locality (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. Page table held entirely in associative (fully-associative, effectively instantaneous) registers, so there is no separate lookup penalty beyond the memory access itself; page-fault service time is $S1$ ms (empty frame available, or replaced page unmodified) or $S2$ ms (replaced page modified, needing a write-back); memory access time $A$ ns; $F\%$ of all page faults fall into the $S2$ case (replacement needed and the victim is modified), so the remaining $(100-F)\%$ of faults cost $S1$. Find. The maximum page-fault rate $p$ (probability a reference faults) such that effective memory access time $\text{EMAT}\le 1.3A$ ns.

Approach. Write EMAT as a weighted average of the no-fault and fault cases, substitute the blended average fault-service time, then solve the inequality for $p$.

Average page-fault service time. Since $F\%$ of faults cost $S2$ ms and $(100-F)\%$ cost $S1$ ms, $$S_{avg}=\left[\left(1-\tfrac{F}{100}\right)S1+\tfrac{F}{100}S2\right]\ \text{ms} = \left[\left(1-\tfrac{F}{100}\right)S1+\tfrac{F}{100}S2\right]\times10^{6}\ \text{ns.}$$
Effective memory access time. A reference either hits (probability $1-p$, cost $A$) or faults (probability $p$, cost $S_{avg}+A$: pay the full fault-service time, then still perform the memory access once the page is resident): $$\text{EMAT}=(1-p)A+p(S_{avg}+A)=A+p\,S_{avg}.$$
Impose the bound and solve for $p$. $$A+p\,S_{avg}\le1.3A \implies p\,S_{avg}\le0.3A$$ $$\boxed{p_{max}=\dfrac{0.3A}{S_{avg}}=\dfrac{0.3A}{10^{6}\left[\left(1-\tfrac{F}{100}\right)S1+\tfrac{F}{100}S2\right]}}$$

Sanity check with representative numbers $A=100$ ns, $S1=10$ ms, $S2=20$ ms, $F=30\%$: $S_{avg}=(0.7\times10+0.3\times20)\times10^{6}=13\times10^{6}$ ns, giving $p_{max}=0.3(100)/13\times10^{6}\approx2.31\times10^{-6}$, and substituting back, $\text{EMAT}=A+p_{max}S_{avg}=100+2.31\times10^{-6}(13\times10^6)=100+30=130=1.3A$ ns exactly, confirming the algebra.

(b) Virtual memory is a memory-management technique that separates the addresses a program uses (its logical/virtual address space) from the physical memory actually installed, using demand paging (or segmentation) to keep only the currently-needed portions of a process resident in RAM while the rest sits on disk (the backing store), transparently to the program. Two advantages:

Programs can run larger than physical memory. Since only active pages need to be resident, a program's total logical address space (and the sum of all concurrently loaded programs') can exceed installed RAM — the programmer is freed from manually overlaying code/data to fit a fixed physical budget.
Higher degree of multiprogramming and memory protection. Because each process only needs its working set resident rather than its entire footprint, more processes can be kept partially loaded simultaneously, improving CPU utilization; each process's page table also gives natural isolation (one process cannot address another's physical frames), improving protection as a side effect of the indirection virtual memory already requires.

(c) Locality of reference is the empirical observation that, over any short interval, a running program tends to access a small, slowly-changing subset of its total address space — temporal locality (recently accessed items are likely to be accessed again soon: loop bodies, hot variables) and spatial locality (items near a recently accessed address are likely to be accessed soon too: sequential instruction fetch, array traversal). This is precisely what makes demand paging practical at all: if references were uniformly scattered across the whole address space, keeping only a handful of frames resident would cause a page fault almost every reference.

Two virtual-memory techniques that directly exploit locality:

The working-set model. The OS tracks, for each process, the set of pages referenced within the last $\Delta$ references (its working set) and keeps exactly that set resident. Because of temporal/spatial locality this set is small and stable over short windows, so working-set-based allocation keeps the fault rate low while still bounding how much memory each process ties up — directly enabling degree-of-multiprogramming decisions (admit a new process only if enough free frames remain after every resident process's working set is satisfied).
LRU (or LRU-approximating, e.g. clock/second-chance) page replacement. By evicting the page not touched for the longest time, LRU is explicitly betting that a page's *recency* of access predicts its *near-future* access — a bet that is correct precisely because of temporal locality. Performance is enhanced because the pages actually still "hot" (inside the working set) are exactly the ones LRU protects from eviction, keeping the fault rate close to what an offline-optimal algorithm would achieve without needing to know the future.

Topic: Effective memory access time under demand paging, and the locality principle that makes virtual memory workable.

Key relations: $\text{EMAT}=(1-p)\cdot(\text{hit cost})+p\cdot(\text{fault cost})$, generally; here simplifying to $\text{EMAT}=A+pS_{avg}$ because both branches include one memory access $A$. Working-set size $|WS(t,\Delta)|$ tracks locality directly; LRU approximates "will be used soon" with "was used recently."

Why this works: The associative (fully-associative, effectively free) page table lookup is what allows collapsing EMAT to a simple two-term expression — a system with an actual TLB-miss-then-page-table-walk penalty would need a third term. Locality is not a logical guarantee but an empirical regularity of real programs (loops, stacks, sequential code/data access) strong enough that replacement policies exploiting it consistently outperform policies that ignore access history (e.g. random replacement).

Common pitfall: Forgetting to convert $S1$/$S2$ from milliseconds to nanoseconds before combining with $A$ (a 6-order-of-magnitude unit mismatch that silently makes $p_{max}$ wrong by a factor of $10^6$), and double-counting the memory access $A$ (adding it to $S_{avg}$ AND separately in the hit term without collapsing the $(1-p)A+pA$ terms first).

Source: Silberschatz, Galvin & Gagne, Operating System Concepts, ch. 10 (Virtual Memory, §10.1 demand paging & effective access time, §10.6 the working-set model, §10.4 LRU approximations).

← Question 5 Next: Question 7 →