Part 5 of 7 · 2 min read
Effective access time with faults
In plain words: Page 5 gave the effective access time (EAT) as an average over hits and misses. The same idea applies to page faults. Let p be the page-fault rate, the share of memory accesses that cause a fault (0 ≤ p ≤ 1). Then:
EAT = (1 − p) × (memory access time) + p × (page-fault service time)
The numbers below are made up to show the idea, and they follow the style of OSC's example. A memory access takes 100 ns. A fault that needs the disk takes 5 ms, which is 5,000,000 ns, to service. Then:
EAT = (1 − p) × 100 + p × 5,000,000 = 100 + p × 4,999,900 ns.
| Fault rate p | One fault in | EAT | Slowdown |
|---|---|---|---|
| 0 | never | 100 ns | 1.0 times |
| 0.000001 | 1,000,000 accesses | about 105 ns | 1.05 times |
| 0.00001 | 100,000 accesses | about 150 ns | 1.5 times |
| 0.0001 | 10,000 accesses | about 600 ns | 6 times |
| 0.001 | 1,000 accesses | about 5,100 ns | 51 times |
Check one row: for p = 0.0001, 0.0001 × 4,999,900 = 499.99, so the EAT is 100 + 499.99 = 599.99 ns, about 6 times a bare access. The disk is so much slower than memory that even one access in 10,000 ruins the speed.
To keep the slowdown at 10% or less, the EAT must be at most 110 ns, so p × 4,999,900 ≤ 10, and p ≤ 10 / 4,999,900, which is about 0.000002 (2.0 × 10⁻⁶). So fewer than one access in 500,000 may fault. This is a hard limit, and it explains the whole of the next two pages: the system must choose the pages to keep with great care, and it must give each process enough frames.
Page-fault rate
The page-fault rate is the share of a process's memory accesses that cause a page fault, and it enters the effective access time as the weight of the fault service time.
Example: a rate of 0.0001 means one fault in every 10,000 accesses, and with a 5 ms service time it makes the average access about 6 times slower.
Interview angle
"What is a page fault, and is it always bad?" A good answer says that a page fault is an exception, that most faults are minor and normal (the first touch of memory, a file mapped but not read yet), and that only major faults at a high rate hurt. It names the steps and the restart of the instruction.
Check yourself: 1. Find the EAT for p = 0.00002 with the made-up numbers. 2. Why is a small p still dangerous? 3. What is the largest p that keeps the slowdown at 20%?