Aprelius logo
uptime: 00:00:00
Computer Science

Paging

Paging is a way to split memory into fixed size chunks: pages in virtual memory and frames in physical memory. The OS builds a page table that maps virtual pages to physical frames and the MMU using TLB cache translates virtual addresses into physical addresses on every memory access.

How translation works

A virtual address splits into a virtual page number and an offset. The page number names the virtual page; the offset picks the exact byte within it. Translation changes only the page number — via a physical frame number — leaving the offset unchanged. For a 4 KiB page (4096 = 2^12 bytes), the offset is the low 12 bits:

text
Virtual address:   [  virtual page number  | 12-bit offset ]
Physical address:  [ physical frame number | 12-bit offset ]

For example, with 4 KiB pages and virtual address 0x12345, the low 12 bits are the offset:

text
Virtual address:   0x12345
                   ├── virtual page:    0x12
                   └── offset:          0x345

After translation:

Physical address:  0xABC345
                   ├── physical frame:  0xABC
                   └── offset:          0x345

Multi-level page tables

If page table would be flat on 64-bit address space it would be huge, so the table is built as a tree of smaller arrays. There are 4 levels on x86-64, each table occupies one 4 KiB page and contains 512 entries of 8 bytes each:

  • CR3(Control Register 3) is a register that holds the physical address of the root page table, the PML4. The OS loads a new value during an address-space switch, such as a process context switch, which provides process memory isolation.
  • Each level indexes into the next array until the final entry gives the physical page frame; the offset is appended unchanged.
  • The walk is done by the MMU's hardware page-table walker — no software involved.

The tables themselves live in RAM, so a full walk is several real memory reads. Page table entries cache into the L1/L2 caches like any other data, which keeps the common case fast. Completed translations also cache in the MMU's TLB.

Page table entries

Each entry maps a virtual page to a physical frame and carries permission bits, so the MMU can enforce who can touch what:

  • Present — the page is actually mapped
  • R/W — writable or read-only
  • NX — not executable
  • User/Supervisor — accessible from user code or kernel only

Page faults

When a translation can't complete, the MMU raises a page fault and the OS handler decides what happened:

  • Not present → the mapping was never made. This is demand paging: the malloc that succeeds instantly in the virtual memory note faults the first time the page is touched, and the OS allocates physical RAM right then.
  • Protection violation → the mapping exists but the access isn't allowed (writing to read-only, executing non-executable). This is the classic segmentation fault, and how the OS gets told a program tried to do something it shouldn't.

References