Idriss Rami — Notes

Virtual memory

3 min read

Virtual memory gives each program the illusion of a large, contiguous private address space, while the OS and hardware translate those virtual addresses into physical addresses in actual RAM (or disk storage when RAM is full).

It buys three things at once:

  1. Extends apparent memory beyond physical RAM using disk space (swapping/paging).
  2. Isolates programs from each other. One program’s virtual address maps to different physical memory than another’s.
  3. Decouples programs from physical layout, so a program doesn’t need to know what physical address it lives at.

The basic idea

Programs use virtual addresses. The hardware memory management unit (MMU) translates each one into a physical address before sending it to the actual memory.

Program: ldw r2, 0x1000     →   MMU translates 0x1000 → 0x4823000   →   Memory access at 0x4823000

The translation is done via a Page table, a data structure (in main memory) that maps virtual pages to physical frames. A page is a fixed-size chunk (typically 4 KB); a frame is a chunk of physical memory the same size.

To translate virtual address :

  1. Take the high-order bits of to identify the virtual page number.
  2. Look that up in the Page table to get the physical frame number.
  3. Concatenate frame number with the low-order “offset” bits of to get the physical address.

For a 32-bit address space the page table needs entries; for 64-bit, a naive layout is impossibly large, so multi-level (hierarchical) and inverted page tables are used. See Page table for entry format, multi-level layouts, inverted/hashed variants, and the page-walk procedure.

What about memory not in RAM

If a program references a virtual page that isn’t currently in physical memory:

  1. The page table entry’s “present” bit is 0.
  2. The MMU raises a page fault exception.
  3. The OS handler runs: finds the page on disk (in the swap file), evicts some other page from RAM if needed, reads the requested page into the freed frame, updates the page table, returns from the exception.
  4. The program retries the access; this time the page is present and it succeeds.

The whole sequence is invisible to the program, which just notices a slight pause. From its perspective all of memory is always available; it never has to manage what’s “in RAM” vs “on disk.” That’s what makes virtual memory larger than physical RAM possible: pages get paged in and out on demand.

Benefits

  1. More memory than physically present. A 32-bit machine with 1 GB of RAM can run programs that use 4 GB of address space, with the OS swapping pages to disk as needed.

  2. Isolation between programs. Each program’s virtual addresses map through its own page table. Program A’s virtual is independent of Program B’s virtual . They can’t accidentally read or write each other’s memory.

  3. Memory protection. Page table entries include read/write/execute permission bits. Writing to a read-only page or executing a non-executable page raises an exception.

Costs

  • Translation overhead. Every memory access has to go through the page table. Without help that means two memory accesses per access (one to read the page table, one to read the actual data).
  • Page fault penalty. A miss that needs a disk read costs millions of CPU cycles.
  • Page table memory. The table itself takes up RAM.

Translation overhead is mitigated by the TLB, a small fast cache of recent translations. Most accesses hit the TLB and translate in zero extra time.

Graph View

Backlinks