§18.2–18.6Where Are Page Tables Stored? … Summary

Page tables promise everything — sparse spaces, no external fragmentation, per-page protection — and then present two bills.

18.2 Where Are Page Tables Stored?

Do the arithmetic for a real address space — 32 bits, 4KB pages. The offset takes 12 bits, leaving a 20-bit VPN:

Far too much for on-chip MMU storage — so, unlike base/bounds pairs or segment registers, the page table lives in plain memory. (For now, in physical memory the OS manages; later even page tables get virtualized and swapped, which is too confusing right now, so we ignore it.) Here’s our tiny table, at home in the OS’s frame:

18.3 What’s Actually In The Page Table?

The simplest organization is the linear page table linear page table The simplest page table: a flat array indexed by VPN, one PTE per virtual page — the structure whose 4MB-per-process cost motivates smarter tables. defined in ch. 18 — open in glossary : an array, indexed by VPN, yielding a page-table entry (PTE) page-table entry One page table record (PTE): the physical frame number plus bits — valid, protection, present, dirty, reference — that the hardware checks and the OS exploits. defined in ch. 18 — open in glossary — the PFN plus a set of bits worth knowing:

The valid bit valid bit PTE bit marking a translation as usable; unused address-space pages are marked invalid and get NO physical frames — the trick that makes sparse address spaces cheap (access → trap, likely termination). defined in ch. 18 — open in glossary deserves the spotlight: it’s what makes paging handle sparse address spaces gracefully — every unused page between heap and stack is marked invalid and consumes no physical frame at all. The present bit present bit PTE bit saying whether the page is in physical memory or swapped to disk; the hinge on which chapter 21's swapping turns (x86 fuses it with validity into a single P bit). defined in ch. 18 — open in glossary , dirty bit dirty bit PTE bit set when a page has been modified since it was brought into memory — a clean page can be evicted without writing it back. defined in ch. 18 — open in glossary , and reference bit reference bit PTE bit (a.k.a. accessed bit) recording that a page was touched — the raw signal replacement policies use to guess which pages are popular. defined in ch. 18 — open in glossary are down-payments on the swapping and replacement chapters ahead.

The real thing, from x86 — find each flag:

18.4 Paging: Also Too Slow

The second bill. To translate VA 21, the hardware must first fetch the PTE — and it finds the table via the page-table base register page-table base register Hardware register (PTBR) holding the physical address where the running process's page table starts; the hardware computes PTEAddr = PTBR + VPN × sizeof(PTE) on every reference. defined in ch. 18 — open in glossary (PTBR), which holds the table’s starting physical address. Figure 18.6’s full per-reference protocol:

// Extract the VPN from the virtual address
VPN = (VirtualAddress & VPN_MASK) >> SHIFT

// Form the address of the page-table entry (PTE)
PTEAddr = PTBR + (VPN * sizeof(PTE))

// Fetch the PTE
PTE = AccessMemory(PTEAddr)

// Check if process can access the page
if (PTE.Valid == False)
    RaiseException(SEGMENTATION_FAULT)
else if (CanAccess(PTE.ProtectBits) == False)
    RaiseException(PROTECTION_FAULT)
else
    // Access is OK: form physical address and fetch it
    offset   = VirtualAddress & OFFSET_MASK
    PhysAddr = (PTE.PFN << PFN_SHIFT) | offset
    Register = AccessMemory(PhysAddr)

Count the AccessMemory calls: two. Every load, store, or fetch now costs an extra memory reference to the page table first — likely a 2× slowdown or more. Two real problems, then: without careful design, paging makes the machine too slow and fills memory with tables that are too big.

18.5 A Memory Trace

Watch the tax collected, reference by reference. The program couldn’t be humbler:

int array[1000];
...
for (i = 0; i < 1000; i++)
    array[i] = 0;

Disassembled (gcc -O), the loop is four instructions at virtual addresses 1024–1036:

1024 movl $0x0,(%edi,%eax,4)   ; array[i] = 0  (edi = base, eax = i)
1028 incl %eax                 ; i++
1032 cmpl $0x03e8,%eax         ; i == 1000?
1036 jne  0x1024               ; not yet — loop

Setup: 64KB address space, 1KB pages, linear page table at physical 1024. Code sits on VPN 1 → PFN 4; the 4000-byte array spans virtual 40000–44000, VPN 39–42 → PFN 7–10. Try the exact translations the hardware will make:

Each iteration: four instruction fetches, one store — and five page-table reads, one before each. Ten memory accesses to zero a single array element:

The patterns beg for exploitation: PT[1] is read four times per iteration with the same answer every time; the array marches predictably through VPN 39, then (around i=250) crosses into VPN 40, 41, 42. What kind of hardware would notice such repetition — and short-circuit it? That’s the next chapter.

18.6 Summary

Paging solves memory virtualization without external fragmentation and with genuine support for sparse address spaces. But done naively it’s too slow (an extra memory reference per access) and too big (megabytes of table per process). The next two chapters fix each in turn: a translation cache, then smarter table structures.