Handling a page fault, and effective access time

The compile job executes one instruction that reads a variable. The page is not in RAM.

The instruction stops mid-way. Nothing is finished, nothing is written.

Roughly 100 microseconds later — a thousand times a normal memory access — the same instruction runs again from the beginning, and this time it works.

The compile job never learns any of this happened.

Why & what

The steps. A page fault is a trap into the kernel, so everything from Topic 1.3 applies. What the kernel does next is a fixed sequence.

1. The MMU sees an invalid entry and traps. The faulting address is handed to the kernel.
2. The kernel checks the address is legitimate. Was this ever a legal address for PID 2317? If not, the process is killed — that is a segmentation fault. If yes, continue.
3. Find a free frame. If none is free, one has to be taken from somebody else. Choosing the victim is Topic 7.3.
4. Read the page from swap space. About 100 µs. The process goes to Waiting, and the scheduler runs somebody else in the meantime — the compile job's fault becomes the browser's turn on the CPU.
5. Update the page table and restart the instruction. Write in the frame number, set the valid bit, and re-execute.

Restart, not resume. This is the detail that gets asked about. The instruction never completed, so there is nothing to resume. The CPU runs it again from the beginning.

This is only safe because the hardware is designed for it. An instruction that had already modified something before faulting would be re-run and could apply the change twice, so CPU designers make faulting instructions leave no trace.

Effective access time. Let p be the page fault rate.

EAT = (1 − p) × 100 ns — + — p × 100,000 ns Because a fault costs a thousand times a memory access, p has to be astonishingly small:

• p = 0.01 (one fault per 100 accesses) → EAT 1,099 ns. Eleven times slower. The machine is unusable.
• p = 0.001 → EAT 199.9 ns. Twice as slow. Still bad.
• p = 0.0001 → EAT 110 ns. 10% slower. Acceptable.
• p = 0.00001 → EAT 101 ns. Barely measurable.

To keep the slowdown under 10% you need fewer than about one fault per 10,000 memory accesses. That is the number that makes everything else in this module necessary.

How it works

1. Compute the cost of a hit. Usually just the memory access time.
2. Compute the cost of a fault. The service time, which dwarfs everything else.
3. Weight them by probability. (1 − p) × hit + p × fault.
4. Compare against the no-fault case to get the slowdown factor.
5. Solve backwards if asked. "What fault rate keeps us under X?" is the same equation rearranged, and it is a common exam variant.

Common confusion

"A page fault wastes 100 µs of CPU time." It wastes 100 µs of that process's time. The CPU is handed to another process during the wait — the faulting process is in Waiting, exactly as in Topic 2.2. On a busy machine almost no CPU time is lost. On an idle one, most of it is.

"Page fault and segmentation fault are the same." They are opposites in outcome. A page fault means "this is your page, it just is not loaded yet" and is resolved silently. A segmentation fault means "this was never your address" and kills the process. Both are traps; only one is normal.

"The instruction is resumed from where it stopped." It is restarted from the beginning. Saying "resumed" in an interview invites the follow-up about partially completed instructions, which you then have to talk your way out of.

Interview angle

"Walk me through what happens on a page fault." Give the five steps in order. The two details that mark out a good answer: the process goes to Waiting so the CPU is not idle, and the instruction is restarted rather than resumed.

"Compute the effective access time." This is a guaranteed numerical question. Write the formula before substituting anything. The classic mistake is using the fault rate as a percentage where a fraction is required — p for "1%" is 0.01, not 1.