Paging: The Basics

The paging model

Paging divides physical memory into fixed-size blocks called frames and logical memory into same-sized blocks called pages. A page of logical address space maps to a frame of physical memory. The page size is a hardware-defined constant, typically 4 KB (4096 bytes).

Because all pages and frames are the same size, the OS never faces the “find a large enough contiguous hole” problem. Any free frame can hold any page. The only trade-off is that no two pages can share a frame — but pages from different processes can (shared memory, copy-on-write).

Address translation

A logical address on a paged system is split into two parts:

• Page number (p): the high-order bits, used to index the page table.
• Offset (d): the low-order bits, passed through unchanged to form the physical address within the frame.

If logical addresses are $m$ bits and the page size is $2^n$, then the offset is the $n$ least significant bits, and the page number is the $(m-n)$ most significant bits.

Translation: PTBR + p × PTE_size → Page-Table Entry → Frame Number f. Physical address = f × 2^n + d.

Example

32-bit logical address, 4 KB pages ($2^{12}$ bytes):

• Offset = 12 bits (bits 0–11)
• Page number = 20 bits (bits 12–31)
• Number of pages per process = $2^{20} = 1\text{,}048\text{,}576$ pages
• The page table has 1M entries

Page-table entry (PTE) structure

A typical PTE (32-bit or 64-bit) contains:

Bits	Field	Meaning
12–51	Frame number	Physical frame address (top bits; page-aligned, so lower bits are implicitly zero)
0	Present (P)	1 if the page is in physical memory; 0 triggers a page fault
1	Read/Write (R/W)	0 = read-only; 1 = read-write
2	User/Supervisor (U/S)	0 = kernel only; 1 = user accessible
3	Page-Level Write-Through (PWT)	Caching policy
4	Page-Level Cache Disable (PCD)	Caching policy
5	Accessed (A)	Set by the MMU on any access; used by page-replacement algorithms
6	Dirty (D)	Set by the MMU on write; indicates the page must be written back to disk on eviction

Additional bits (NX/XD) mark pages as non-executable, an important security feature for preventing code execution from data pages (buffer-overflow mitigation).

Memory overhead of the page table

A single-level page table for a 32-bit process with 4 KB pages requires $2^{20}$ entries. If each PTE is 4 bytes, the table is 4 MB per process. With 100 processes, that’s 400 MB of page tables — absurd.

Multi-level page tables (next notes) solve this by structuring the page table as a sparse tree, only allocating memory for the parts that are actually used.

Page-table base register (PTBR)

The PTBR (CR3 on x86) holds the physical address of the top-level page table for the currently running process. On a context switch, the kernel saves the old process’s PTBR and loads the new process’s PTBR. This is one of the most performance-critical operations in the kernel.

Loading CR3 also flushes (or partially flushes, with PCIDs) the TLB, since old translations belong to the old process’s address space.

Summary

• Paging divides memory into fixed-size pages (logical) and frames (physical).
• The page table maps page numbers to frame numbers; the offset passes through unchanged.
• A single-level page table wastes memory for sparse address spaces; multi-level page tables solve this.
• The PTBR points to the current process’s page table; it is reloaded on every context switch.