The idea: the same pages, three table shapes

A page table maps each virtual page of a process to a physical frame. With 32-bit addresses and 4 KiB pages, a virtual address is a 20-bit VPN (virtual page number) and a 12-bit offset, so a process has 220 = 1,048,576 possible pages. Real programs use very few of them, in a few far-apart places: code near the bottom, a heap, and a stack near the top. Such an address space is sparse.

Bar chart on a log scale of table memory. For processes A and B together: linear 8,388,608 bytes, two-level 28,672 bytes, inverted 49,152 bytes. For 100 processes like A: linear 419,430,400 bytes, two-level 1,638,400 bytes, inverted still 49,152 bytes.
Linear pays for every possible page; two-level pays for used regions; inverted pays for the RAM, once.

The page puts two processes into three separate designs. A (PID 1) has 7 pages and B (PID 2) has 3; the machine has 16 MiB of RAM, which is 4096 frames. There is no TLB here, so every translation walks the table. Each panel counts the memory reads one translation costs and the bytes its table takes. For the TLB and the four-level x86-64 walk, see The TLB and the x86-64 Page Walk.

Linear page table

The simplest table is an array with one 4-byte entry per virtual page. A register (PTBR, the page-table base register) holds its start, and the entry for a page is at PTBR + VPN × 4. One read gives the frame or says P = 0 (not present). The catch is size: 1,048,576 × 4 B = 4,194,304 bytes per process, even for a process with 7 pages. Two such processes fill half of this machine's RAM (Demo: memory used by each design).

Two-level page table

A two-level table splits the VPN: the top 10 bits pick an entry in a 4 KiB page directory, and the bottom 10 bits pick an entry in a 4 KiB second-level table. Each second-level table covers 1024 pages, a 4 MiB region. The trick: a region with no pages gets no table at all, only a directory entry with P = 0. This is the 32-bit x86 design (CR3 points to the directory).

Process A's 4 GiB address space with three used regions: code at directory index 1, heap at 64, stack at 767. The directory has 1024 entries, three of them present, each pointing to one 4 KiB table. Total 4 tables of 4 KiB, 16,384 bytes.
A's 7 pages sit in 3 regions, so A needs the directory and 3 tables: 16,384 bytes instead of 4 MiB.

A translation now costs two reads: the directory entry, then the table entry (Demo: one address, three tables). If the directory entry is empty, the walk stops after one read with a page fault (Demo: empty 4 MiB region). If the table exists but the entry is P = 0, it stops after two (Demo: missing page next to code).

The table grows only when a page lands in a new region: mapping 0x70000010 adds one 4 KiB table for directory entry 448, and A goes from 16,384 to 20,480 bytes (Demo: map a new page, who grows). In the worst case, a process that uses all 1024 regions needs the directory plus 1024 tables, 4 MiB + 4 KiB, slightly more than linear. x86-64 takes the same idea to four levels.

Inverted page table, with hashing

An inverted page table (IPT) turns the map around: one entry per physical frame, saying which process and which page live there: {PID, VPN, next}. The machine has one such table for all processes. Its size follows the RAM: 4096 frames × 8 B = 32,768 bytes, plus the hash table below, 49,152 bytes in all, whether there are 2 processes or 200.

The price is the search. The table is indexed by frame, but the MMU knows a page. Searching 4096 entries on every access is far too slow, so a hash anchor table (HAT) points into it: the slot is h = (VPN xor PID) mod 4096, the slot holds the first frame of a chain, and each IPT entry's next field links to the next one with the same hash. The MMU reads the slot, then each chain entry, until PID and VPN both match. The frame number is the entry's own index.

Key PID 2, VPN 0x00401 hashes to slot 0x403. HAT slot 0x403 points to IPT entry 0x7c5, which holds PID 1, VPN 0x00402: no match. Its next field points to entry 0x5b1, which holds PID 2, VPN 0x00401: match, so the frame is 0x5b1. Three reads.
A collision: B's page and one of A's share slot 0x403, so B's lookup reads the slot and two chain entries.

A lookup costs 1 + the chain length reads. For A 0x00401234 the chain has one entry, 2 reads. For B 0x00401234 the slot is shared with A's page 0x00402, so it takes 3 (Demo: process B, same address). The PID in each entry matters: A's 0x00403000 hashes to a slot whose only entry is B's page 0x00400, and only the PID check stops A from reading B's frame (Demo: missing page next to code).

Side by side

lineartwo-levelinverted (hashed)
one entry pervirtual pagevirtual page, in used regionsphysical frame
tablesone per processone tree per processone for the machine
A + B on this page8,388,608 B28,672 B49,152 B
100 processes like A419,430,400 B1,638,400 B49,152 B
reads per translation12 (1 if the region is empty)1 + chain length
grows whennever (all paid up front)a page lands in a new 4 MiB regionnever (fixed by RAM)
context switchload PTBRload CR3nothing: the PID is in the key
shared pageseasy: two entries, one frameeasyhard: one entry holds one PID

Two numbers to remember: a linear table costs address space size / page size × entry size, and an inverted table costs RAM size / page size × entry size. With 64-bit address spaces the first one is impossible, which is why real systems use either several levels or an inverted, hashed table.

Where each one is used

  • Linear: textbooks, small embedded MMUs, and the MIPS teaching design on Virtual Memory in Hardware. VAX put its linear user tables in virtual memory so they could be paged.
  • Multi-level: 32-bit x86 (two levels), x86-64 (four or five), ARMv8 and RISC-V Sv39/Sv48. Linux uses this shape everywhere.
  • Hashed / inverted: IBM System/38 and AS/400, the PowerPC and POWER hashed page table (HPT), and the IA-64 VHPT option. The hashed table works as a big cache of translations; the OS keeps its own per-process tables beside it.

See also Paging vs Segmentation for why pages replaced segments, Linux Virtual Memory for what the kernel does on a page fault, and Paging and Page Replacement for what happens when no frame is free.

What the page leaves out

There is no TLB, so every access walks the table; real CPUs cache translations and a walk is rare. Entries have no permission, accessed or dirty bits. The directory and tables are drawn as separate frames but their own IPT entries are not shown. Real hashed page tables (PowerPC) store several entries per bucket (a PTE group) instead of a chain, and fall back to a second hash; shared memory in an inverted table needs extra tricks, such as a global segment ID instead of the PID. The page also leaves out page tables that are themselves paged out, large pages in the directory (PSE), and five-level and nested (virtual machine) tables.

On the mind map

Open the Operating Systems mind mapOperatingSystemsBoot and program start: from power on to main()Boot and program startProcesses and the kernel: how user code talks to the kernelProcesses and the kernelInterrupts and devices: hardware interrupts the CPUInterrupts and devicesScheduling and deadlock: who runs next, who gets whatScheduling and deadlockVirtual memory: every address is translatedVirtual memoryPhysical memory: who gets which bytes of RAMPhysical memoryFiles and storage: from open() down to the diskFiles and storageDisks and RAID: blocks down to platter or flashDisks and RAIDIsolation and security: limit what a process can doIsolation and securityVirtual memoryVirtual memorypage table, TLB, page faultsTLB and page walkTLB and page walkTLB miss walks 4 levels from CR3Page table typesLinear 4 MiB, two-level 16 KiB, inverted RAMPage replacementPage replacementFIFO, Clock, LRU choose a victim pagePaging vs segmentationPaging vs segmentationfixed pages: no external fragmentationCopy-on-write forkCopy-on-write forkshare pages, copy one on its first writeThrashing and working setThrashing and working setToo little RAM: all faults, no workOpen the Operating Systems mind mapOperating Systemsevery address is translatedVirtual memoryVirtual memoryVirtual memorypage table, TLB, page faultsTLB and page walkTLB and page walkTLB miss walks 4 levels from CR3Page table typesLinear 4 MiB, two-level 16 KiB, inverted RAMPage replacementPage replacementFIFO, Clock, LRU choose a victim pagePaging vs segmentationPaging vs segmentationfixed pages: no external fragmentationCopy-on-write forkCopy-on-write forkshare pages, copy one on its first writeThrashing and working setThrashing and working setToo little RAM: all faults, no work
This page on the Operating Systems mind map · 64 pages in 9 branches · open it to see the whole map and test yourself in recall mode.