The idea: main memory as a cache for the disk

A program sees a large, private virtual memory: 2 GB here, the same for every process. The machine has much less physical memory (128 MB here), shared by all processes. The rest lives on disk. The hardware translates every virtual address into a physical one, and the operating system moves pages between disk and memory.

The page follows one lw, sw or instruction fetch at a time: the address is split, the TLB is searched, on a miss the page table is read from memory, on a page fault the OS brings the page from disk, and finally the data is accessed. The counters at the top add up the cost in cycles.

A virtual address goes to the TLB; a hit goes straight to the data access (100 cycles); a miss reads the page table, and if V = 1 the PTE is copied into the TLB (200 cycles); if V = 0 a page fault makes the OS read the disk, about 10,000,000 cycles, and the instruction restarts
Most accesses hit in the TLB; a TLB miss costs one extra memory read, a page fault costs a disk read.

Virtual memory is the same idea as a CPU cache, one level lower. The words are different:

CacheVirtual memory
block (16–64 B)page (4 KB)
block offsetpage offset
tagvirtual page number
miss (10–100 cycles)page fault (~10,000,000 cycles)
handled by hardwarehandled by the OS
direct-mapped or set-associativefully associative: any page in any frame
write-back or write-throughalways write-back

Address translation

Memory is cut into pages of 4 KB = 212 bytes. A 31-bit virtual address is a 19-bit virtual page number (VPN) and a 12-bit page offset. A 27-bit physical address is a 15-bit physical page number (PPN) and the same offset. Only the page number is translated; the offset is copied unchanged.

Example (Demo 1): lw 0x10010004 has VPN 0x10010 and offset 0x004. Process A's page 0x10010 is in physical page 0x7FFB, so the physical address is 0x7FFB004.

Virtual address 0x10010004 split into VPN 0x10010 and offset 0x004; the page table maps 0x10010 to PPN 0x7FFB, the offset is copied, giving physical address 0x7FFB004
Only the page number is translated; the 12-bit offset passes through unchanged.

The page table

The page table has one entry (PTE) per virtual page and is indexed by the VPN. It lives in physical memory; the page table register holds its base address, so the entry for a page is at base + VPN × 4. Each PTE here holds:

  • V: valid. 1 = the page is in physical memory and the entry holds its PPN. 0 = it is on disk (the entry holds the disk location) or not part of the program at all.
  • W: writable. 0 for code pages.
  • U: use bit, set by the hardware on every access (for replacement).
  • D: dirty bit, set by the hardware on every store.

Two costs follow. Size: 219 entries × 4 B = 2 MB per process, even though process A uses 7 pages. And time: without help, every load or store needs two memory accesses, one for the PTE and one for the data.

The translation lookaside buffer (TLB)

The TLB is a small cache of recent translations, inside the MMU. It is fully associative: every entry compares its VPN with the address at the same time. A hit gives the PPN in the same cycle, so the access costs only the data access. A miss reads the PTE from memory and copies it into the TLB, replacing the least recently used entry.

Programs touch the same pages over and over (a page has 4096 bytes, and a loop stays on a few pages), so real TLBs of 16 to 512 entries hit more than 99 % of the time. A TLB that is too small for the working set thrashes:

Trace (data0, data0, text0, stack, data0, text0)TLB hitsTLB missesCycles
2-entry TLB (Demo 2)151,100
4-entry TLB (Demo 3)33900

Three pages are used in a loop and only two fit, so LRU always throws out the page that comes next.

Page faults

When the PTE has V = 0 and a disk location, the access causes a page fault: an exception that runs the OS's page-fault handler (Demo 4). The handler finds a free frame (or makes one, see below), reads the 4 KB page from disk, writes V = 1 and the new PPN into the PTE, and returns to the same instruction, which starts again. A disk access takes about 10 ms, ten million cycles at 1 GHz, so the OS runs another process while it waits.

CaseWhat happensCycles
TLB hitdata access100
TLB miss, V = 1PTE read + data200
page fault, free framePTE read, disk read, restart (PTE read again), data10,000,300
page fault, dirty victimas above + writing the victim to disk20,000,300

Memory protection

Each process has its own page table. A process can only produce virtual addresses, and its page table only points to its own frames, so it cannot even name another process's memory. In Demo 6, A and B both load 0x10010004: A gets 0x7FFB004, B gets its own copy at 0x7FFE004. The page table register can only be changed by the OS.

Sharing is just two page tables pointing at the same frame: both programs' code page 0x00400 maps to 0x7FFA. It is mapped with W = 0, so neither process can change it. A store to it, or a load from a page that does not exist (a null pointer), is a protection fault (Demo 5): the OS kills the process.

Process A and B page tables: both map code page 0x00400 to the shared frame 0x7FFA with W = 0; A maps 0x10010 to 0x7FFB and B maps 0x10010 to 0x7FFE
The same virtual address leads to different frames in different processes, except where the OS shares a frame on purpose.

On a context switch the OS loads the page table register with the new process's table. This TLB has no process ID, so it must be flushed, and the new process starts with TLB misses. Real TLBs tag entries with an address-space ID to avoid that (see the Context Switch page).

Replacement policies

When no frame is free, the OS must evict a page. Ideally the least recently used one, but keeping exact LRU order on every access is too expensive. Instead (Demo 7):

  • The hardware sets U = 1 in the PTE whenever the page is accessed.
  • Periodically the OS clears every U bit (the Clear Use Bits button).
  • On a page fault it evicts a page with U = 0: not used since the last clear. Here the OS checks the frames in order from a clock hand; if every page has U = 1, it clears them all and takes the frame under the hand.

Virtual memory is always write-back. A store only sets D = 1; the page goes to disk when it is evicted, and only if it is dirty. A clean victim (code, or data only read) is dropped, because its disk copy is still correct. In Demo 7 the victim is A's dirty data0, so it is written to disk first (1 disk write); the last access then faults again and reads it back.

Multilevel page tables

A 2 MB table per process is mostly empty entries. A two-level page table splits the VPN in two: the first part indexes a small page directory, whose entries point to second-level tables, and a second-level table only exists where the program has pages. A miss then costs one memory access per level. The Paging and Page Replacement page draws a two-level walk on 32-bit x86, and Linux Virtual Memory a four-level walk on x86-64.

What the page leaves out

  • Only 6 of the 32,768 page frames and only the page-table rows the programs use are drawn.
  • No cache between the CPU and memory: every access costs 100 cycles. In reality PTEs and data are usually in the cache.
  • The hardware updates U and D in the PTE directly on every access, also on a TLB hit. Real machines set them when the TLB entry is loaded (and on the first store) and keep a dirty bit in the TLB.
  • The real MIPS TLB is refilled by software: a TLB miss is an exception and an OS routine reads the page table. The page draws a hardware page table walk, as on x86 and ARM.
  • No read/execute permission bits, no kernel/user bit, no address-space IDs, no huge pages, no disk queueing: one fault at a time.
  • A protection fault does not kill the process here, so you can keep trying accesses.

Where these pages come from in the first place: Translating and Starting a MIPS Program lays out text at 0x00400000, data at 0x10000000 and the stack under 0x7FFFFFFC.