CSE Roadmap

Core tier · about 5 hours · 7 parts

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%?