= Page table
{wiki}
A <page table> is the <data structure> describing an <address space>'s mappings from virtual page numbers to <page frames>, together with access and status information. A <page table entry> can describe a resident <memory page> and its permissions. Nonresident or unmapped <memory pages> require a representation that lets the <operating system> distinguish them; a hardware not-present flag alone need not make that distinction. On <x86>, additional <operating system> information determines whether a not-present mapping is legitimate. https://pages.cs.wisc.edu/~remzi/OSTEP/vm-paging.pdf[Arpaci-Dusseau and Arpaci-Dusseau, OSTEP chapter 18, section 18.3: page-table contents and the x86 present bit]{ref}
The four rows drawn under <paging> are an illustrative model, combining <page table> and <operating system> information: virtual page `0x12` is resident in physical frame `0x07` with read-only permission; `0x13` is resident in `0x02` with read/write permission; `0x14` is mapped read/write but nonresident; `0x15` is unmapped. The labels deliberately separate mapping policy, residency and permission. They are not a literal <x86> entry layout. A <translation lookaside buffer> valid flag is a fourth, independent notion: it says that a cached translation can be considered, not that every resident <memory page> has a cached translation.
A flat <array> with one <page table entry> per virtual page would have $2^{16}/256=256$ entries in this example. At an assumed four <bytes> per entry, it occupies $256\cdot4=1024$ <bytes>, whether one <memory page> or all 256 <memory pages> are mapped. A <multi-level page table> saves space in sparse <address spaces> by allocating lower-level tables only for the regions that need them. The tradeoff is extra dependent lookups during a <page table walk>; a <translation lookaside buffer> avoids repeating those lookups on a hit. https://pages.cs.wisc.edu/~remzi/OSTEP/vm-smalltables.pdf[Arpaci-Dusseau and Arpaci-Dusseau, OSTEP chapter 20: Paging, Smaller Tables, section 20.3]{ref}
Back to article page
