§20.3–20.6Multi-level Page Tables … Summary

Forget segments — attack the waste directly: why keep the invalid regions of the page table in memory at all?

20.3 Multi-level Page Tables

The multi-level page table multi-level page table A page table chopped into page-sized pieces with entirely-invalid pieces simply not allocated — a page directory tracks which pieces exist. Space grows with the USED address space, at the cost of an extra memory load per TLB miss (x86's design). defined in ch. 20 — open in glossary turns the linear array into a tree, and it is so effective that most modern systems use it (x86 included). Two moves: chop the page table into page-sized units; if an entire page of PTEs is invalid, don’t allocate that page at all. A new structure — the page directory page directory The top structure of a multi-level page table: one entry per page of the page table, saying whether that piece holds any valid PTEs and, if so, which frame it lives in (its base register: the PDBR — x86's CR3). defined in ch. 20 — open in glossary — records which pieces exist: each page-directory entry (PDE) page-directory entry One page-directory record (PDE): a valid bit plus a PFN; valid means at least one PTE on the pointed-to page of the page table is valid — invalid means that whole slice of address space costs nothing. defined in ch. 20 — open in glossary holds a valid bit and a PFN, where valid means “at least one PTE on the page I point to is valid.” Invalid PDE → that whole slice of the table simply isn’t there. The multi-level table makes parts of the linear page table disappear, freeing those frames for real work.

Two structural advantages: page-table space is allocated in proportion to the address space you actually use — sparse spaces, finally handled honestly; and each piece fits neatly in a page, so growing a table means grabbing any free frame — no hunt for 4MB of contiguous memory, because the directory’s indirection lets pieces live anywhere. The costs: on a TLB miss, two memory loads (PDE, then PTE) rather than one — a time-space trade-off — and undeniably more complexity in the lookup, wherever it runs.

A Detailed Multi-Level Example

A 16KB address space with tiny 64-byte pages: 14-bit addresses, 8-bit VPN, 6-bit offset. A linear table needs 256 entries (1KB = sixteen 64-byte pages of 16 PTEs each) — for this:

The VPN now splits in two: the top 4 bits index the directory (16 entries, one per page of the table), the bottom 4 index within the chosen page:

PDEAddr = PageDirBase + (PDIndex * sizeof(PDE))
// if PDE valid:
PTEAddr = (PDE.PFN << SHIFT) + (PTIndex * sizeof(PTE))

Only three pages exist where sixteen would have been: the directory, and the two pieces of the table with valid mappings. Walk any address through it:

More Than Two Levels

The goal is that every piece of the structure fits in a page — the directory included. Take a 30-bit space with 512-byte pages: 21-bit VPN, 9-bit offset; 128 PTEs fit per page, so the page-table index takes 7 bits… leaving 14 bits of directory index. A 2¹⁴-entry directory spans 128 pages — goal destroyed. The remedy is recursion: split the directory itself and add a level above it:

Each added level is another load on a miss — x86-64 walks four. Whew: a lot of work, all just to look something up in a tree.

The Translation Process: Remember The TLB

The full per-reference control flow, TLB first (Figure 20.6):

VPN = (VirtualAddress & VPN_MASK) >> SHIFT
(Success, TlbEntry) = TLB_Lookup(VPN)
if (Success == True)    // TLB Hit
    if (CanAccess(TlbEntry.ProtectBits) == True)
        Offset   = VirtualAddress & OFFSET_MASK
        PhysAddr = (TlbEntry.PFN << SHIFT) | Offset
        Register = AccessMemory(PhysAddr)
    else
        RaiseException(PROTECTION_FAULT)
else                    // TLB Miss
    PDIndex = (VPN & PD_MASK) >> PD_SHIFT
    PDEAddr = PDBR + (PDIndex * sizeof(PDE))
    PDE     = AccessMemory(PDEAddr)
    if (PDE.Valid == False)
        RaiseException(SEGMENTATION_FAULT)
    else
        PTIndex = (VPN & PT_MASK) >> PT_SHIFT
        PTEAddr = (PDE.PFN << SHIFT) + (PTIndex * sizeof(PTE))
        PTE     = AccessMemory(PTEAddr)
        if (PTE.Valid == False)
            RaiseException(SEGMENTATION_FAULT)
        else if (CanAccess(PTE.ProtectBits) == False)
            RaiseException(PROTECTION_FAULT)
        else
            TLB_Insert(VPN, PTE.PFN, PTE.ProtectBits)
            RetryInstruction()

On a hit, nothing changed. Only a miss pays the two extra AccessMemory calls — the smaller table’s whole price, collected only when the cache fails.

20.4 Inverted Page Tables

The extreme point in the design space: keep one table for the whole system, with an entry per physical frame recording which process uses it and which of that process’s virtual pages maps there. Finding a translation becomes a search — in practice a hash table built over the structure (the PowerPC’s approach). The inverted page table inverted page table One system-wide table with an entry per PHYSICAL frame (which process, which virtual page), found by search — in practice hashed (PowerPC). The extreme reminder that page tables are just data structures. defined in ch. 20 — open in glossary makes the chapter’s moral explicit: page tables are just data structures, and data structures can be made smaller, bigger, faster, slower — whatever the constraints reward.

20.5 Swapping The Page Tables To Disk

One last assumption quietly relaxed: even shrunken tables might not fit in physical memory. Some systems therefore place page tables in kernel virtual memory, letting the tables themselves be swapped to disk under pressure. How anything moves between memory and disk is the next chapters’ story — and the VAX/VMS case study will show this trick in production.

20.6 Summary

Real page tables are built as trees, hashes, and hybrids — not just arrays — each choice trading time against space: bigger tables serve misses faster; smaller tables give memory back. Memory-tight systems choose small structures; memory-rich systems running page-hungry workloads may prefer big flat ones. And with software-managed TLBs, the entire data-structure universe belongs to the OS innovator — that’s you. Dream the big dreams only operating-system developers can dream.