the effective access time of demand paging

Imagine most of your phone calls connect instantly, but one call in a thousand drops you into a long hold queue. Your average wait per call is not the instant time — it is the instant time most of the time plus a sliver of the dreadful hold time. If the hold is enormously long, even one-in-a-thousand can wreck your average. The effective access time of demand paging is this same weighted average, applied to memory: the time a memory reference takes on average, blending the fast common case (the page is in RAM) with the rare, slow case (a page fault).

Concretely, let ma be the normal memory-access time and let p be the page-fault rate. The effective access time is a weighted average: EAT = (1 - p) x ma + p x (page-fault service time). The first term covers the common case where the page is resident and the access just costs ma. The second term covers a fault, whose service time is dominated by a disk read and is therefore far larger than ma — often by a factor around a hundred thousand. Because that fault cost is so big, the whole formula is extremely sensitive to p: a small increase in the fault rate produces a large increase in EAT. (More refined versions split the fault cost into a fast case with a free frame and a slower case that must first write out a dirty victim.)

Why it matters: this formula turns the vague worry 'paging is slow' into a precise, predictable number, and it shows exactly why the page-fault rate must be kept astonishingly low. It is the quantitative backbone of every design decision in virtual memory: how many frames to give a process, which page-replacement policy to use, whether to prepage. It also delivers the central honest message of the whole topic: virtual memory is cheap only when faults are rare; let p creep up and the average memory access can slow by orders of magnitude, which is precisely what happens when a system begins to thrash.