Three Frames, One Benchmark: Replacement Policy and Where the Latency Really Goes
A team is profiling a 32-bit process on a machine deliberately restricted to three physical page frames, an artificial limit the kernel honours so that replacement behaviour can be studied in isolation. Page size is 4 KB, all pages start out non-resident, and the captured reference string is 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5. In parallel the team measures the production configuration: TLB probe 10 ns, main-memory access 100 ns, TLB hit ratio 90%, page-fault service time 8 ms, and roughly one fault per 1,000 memory accesses. The process's true working set, measured separately with a hardware reference-bit sampler, is 40 pages. Engineering time is limited and can be spent on exactly one of three things: a larger, faster TLB, a rewritten page-fault handler, or extra page frames. The review meeting needs numbers, not intuition, before the budget is committed.
1. Compute the number of page faults for the 12-reference trace under FIFO, LRU and OPT with three frames, then repeat FIFO with four frames. Which policy exhibits Belady's anomaly here, and what property of a policy makes the anomaly impossible?
Read the worked answer
Walk the trace and count faults only when the referenced page is absent.
| Policy | Faults | Why |
|---|---|---|
| FIFO, 3 frames | 9 | insertion order evicts 1, 2, 3, 4, 1, 3, 4 in turn |
| LRU, 3 frames | 10 | at the tail, pages 5, 1, 2 are each still more recent than the incoming page, so 3, 4, 5 all miss |
| OPT, 3 frames | 8 | evicts 3 at the first reference to 4 (next use position 10), then 1 at position 7, then 1 again at position 10 |
| FIFO, 4 frames | 10 | the larger frame set removes the early conflicts but creates new ones at the tail |
FIFO faults rise from 9 to 10 when frames go from three to four: that is Belady's anomaly. LRU and OPT are stack algorithms: the set of pages resident in m frames is always a subset of the set resident in m+1 frames under the same reference string, so a fault under m+1 frames implies a fault under m frames and fault counts are monotonically non-increasing. FIFO has no such inclusion property, which is exactly why it can regress.
Two practical readings follow. First, OPT is the lower bound (8 here) and no implementable policy beats it. Second, LRU losing to FIFO on a 12-reference trace is not an argument for FIFO - short traces are noisy; the stack property is what protects against added memory making things worse.
2. Using the production measurements, compute the effective access time. Quantify separately the benefit of eliminating all TLB misses and of halving the page-fault service time, and state which investment the numbers support.
Read the worked answer
Break the access into three paths (p = 0.001 is the fault probability):
- TLB hit: 10 ns probe + 100 ns data = 110 ns
- TLB miss, page resident: 10 ns probe + 100 ns page-table access + 100 ns data = 210 ns
- any access that faults: add 8 ms = 8,000,000 ns
EAT = 0.9(110) + 0.1(210) + 0.001(8,000,000) = 99 + 21 + 8000 = 8120 ns
Note how lopsided the terms are: the TLB terms together contribute 120 ns, the fault term contributes 8000 ns - 98.5% of the total.
Scenario 1, perfect TLB (100% hit): EAT = 110 + 8000 = 8110 ns, a saving of 10 ns, about 0.12%.
Scenario 2, fault service halved to 4 ms: EAT = 120 + 4000 = 4120 ns, a saving of 4000 ns, about 49%.
Add frames as the third option: at 0.001 faults the fault term is already 8 microseconds; the marginal return on each additional frame is large compared with anything done to the TLB. The quantitative conclusion is to fund the fault handler (and frames), and to leave the TLB alone - optimising a 120 ns component inside an 8120 ns access is Amdahl's law ignored.
3. In production the same workload's fault rate is 0.001 at 512 frames but 0.05 at 128 frames. What is the process doing at 128 frames, how should the OS detect that condition online, and what are the available responses?
Read the worked answer
At 128 frames the effective access time becomes 0.05 x 8 ms = 400 microseconds of fault service per access, roughly 49 times the 8.12 microsecond figure measured with adequate memory. The CPU is spending nearly all its time in the fault handler rather than executing user code: this is thrashing. Its cause is structural, not a policy bug - the working set is 40 pages for the sampled phase but the measured fault-rate curve implies the true demand across the whole phase set far exceeds 128 frames, so every process is stealing frames from the others and each eviction is soon re-requested.
Detection is done with a page-fault frequency (PFF) monitor: the OS samples each process's fault rate over a window and compares it with an upper and lower bound. Rate above the upper bound means the process needs more frames; below the lower bound it can give frames back. The working-set model is the alternative: at each timer tick, pages with the reference bit set are marked in-window, and the OS allocates max(WS size) frames, suspending or swapping out a process when the sum of working-set sizes exceeds available frames.
Responses, in order of preference: allocate more frames from the free pool; reduce the degree of multiprogramming by suspending a process; switch from global to local replacement so one process cannot destroy another's working set. Simply changing the replacement algorithm will not help - no policy can keep a 40-page-plus working set resident in 128 frames.