Skip to main content

Paging: The Modern Answer

What This Concept Is​

Paging chops the virtual address space and physical memory into fixed-size blocks called pages (virtual) and page frames (physical). The common size is 4 KiB, with optional larger sizes (2 MiB, 1 GiB on x86-64).

A virtual address splits into two fields:

  • the high bits are the virtual page number (VPN)
  • the low bits are the offset inside the page

Translation consults a page table indexed by VPN. Each page-table entry (PTE) stores the page-frame number (PFN) and some status bits (valid, present, read/write, user/kernel, dirty, accessed, and so on). The physical address is (PFN << offset_bits) | offset.

Because pages are fixed-size, any page can go into any frame. External fragmentation at the frame level disappears.

Why It Matters Here​

Paging is the scheme every mainstream general-purpose OS uses today. It is also the foundation of:

  • TLBs (you must cache translations because every access traverses at least a table lookup)
  • page faults (the "valid" bit in a PTE gives you a hook to bring pages in on demand)
  • copy-on-write, shared memory, mmap, memory-mapped I/O (you flip PTE bits to change behavior)
  • NUMA and huge pages (you change which frame backs which page, or the page size, without changing the program)

Once you can split an address into VPN and offset and walk a page table, every later concept is a variation.

Concrete Example​

Small model. 16-bit virtual addresses, 1 KiB pages. Offset is 10 bits, VPN is 6 bits, so there are 64 virtual pages. With physical memory of 32 KiB, the PFN is 5 bits.

Virtual address 0x1A3C = 0001 1010 0011 1100:

  • VPN = 000110 = 6
  • offset = 10 0011 1100 = 0x23C = 572

If PTE[6] = (valid, PFN=11), the physical address is (11 << 10) | 572 = 0x2E3C.

Realistic model. 48-bit virtual addresses, 4 KiB pages on x86-64.

  • offset = 12 bits (4 KiB = 2^12)
  • VPN = 36 bits
  • a flat table of PTEs would hold 2^36 entries of 8 bytes each = 512 GiB per process, which is absurd, so real systems use multi-level tables (Cluster 2).

Virtual address 0x00007FFD_1234_5ABC:

  • offset = 0xABC (low 12 bits)
  • VPN = 0x7FFD1_2345 (next 36 bits)
  • translation produces some PFN P; physical address = (P << 12) | 0xABC.

Common Confusion / Misconception​

"Page size is a software choice." Page size is a hardware contract with the MMU. Linux picks 4 KiB on x86-64 because that is what the MMU supports as its small page size; it can also use 2 MiB or 1 GiB pages, but only at those specific hardware-supported sizes.

"Every memory access costs two memory accesses then, because the page table is in memory." In principle yes. In practice the TLB hides almost all of that cost. If you are bypassing the TLB you will see that cost directly.

"Offset bits are always 12." Only on 4 KiB pages. On 2 MiB huge pages the offset is 21 bits, and the VPN is correspondingly smaller.

How To Use It​

Given a page size P bytes and a virtual address va:

  1. offset = va mod P (low log2 P bits)
  2. VPN = va div P (the remaining high bits)
  3. Look up PTE[VPN] (or walk a multi-level table)
  4. If PTE is valid, pa = (PFN << log2 P) | offset; if not, page fault

Practice writing this down on paper a few times with 4 KiB, 2 MiB, and 1 GiB pages until the bit-field split is automatic.

Check Yourself​

  1. For 48-bit virtual addresses and 4 KiB pages, how many bits is the VPN? How many PTEs would a single flat page table need per process?
  2. For 2 MiB pages, how many bits is the offset? How does that change the per-PTE coverage?
  3. What bit(s) in a PTE let the kernel implement demand paging, and which let it implement read-only-on-write for CoW?

Mini Drill or Application​

Work these page-table math problems on paper:

  1. 32-bit virtual addresses, 4 KiB pages, 4 GiB of physical memory. VPN width? Offset width? PFN width? Flat page table size (with 4-byte PTEs)?
  2. 48-bit virtual addresses, 4 KiB pages. How many PTEs per level if the table is 4-level and each level indexes with 9 bits?
  3. A process reads virtual address 0x0000_0000_4020_10C8 on an x86-64 system with 4 KiB pages. Give the offset and the VPN.
  4. Same process, same system, but using 2 MiB huge pages. New offset and VPN for the same address?
  5. What goes wrong if two virtual pages point to the same page frame and both are marked writable?

Read This Only If Stuck​