Paging Explained

The Moving Boxes Analogy

You are moving to a new apartment. You pack everything into numbered boxes. Box 1 has your books, box 2 has your kitchen gear, box 3 has your clothes. When the movers unload, box 1 ends up in the bedroom closet, box 2 goes in the kitchen cabinet, box 3 lands in the hallway. The boxes are not in sequence — they are scattered wherever space exists. But you have a list: "Box 1 → bedroom closet, Box 2 → kitchen, Box 3 → hallway." Whenever you need something, you consult that list.

This is exactly how paging works. Your program's memory is split into numbered pages (boxes). Physical RAM is split into same-sized frames (storage rooms). The OS keeps a page table (your list) that maps each page to whichever frame holds it. The pages can scatter across RAM in any order — and external fragmentation disappears.

Why Paging?

Recall from the previous lesson that contiguous allocation causes external fragmentation — free memory scattered in chunks too small to use. Compaction fixes it but is expensive.

Paging's insight: stop requiring that a process occupy contiguous physical memory. Break both the process and physical RAM into identical small chunks. Map them independently.

By making all chunks the same size, you always have a chunk of the right size available — you never have a "wrong-sized hole" problem.

Core Vocabulary

Pages and frames are always the same size. A typical modern system uses 4 KB pages. A process with 16 KB of data has exactly 4 pages. Those 4 pages can land in any 4 free frames in physical RAM.

Address Translation: Logical to Physical

A logical address has two parts: a page number (p) and an offset (d).

Translation:

1. Extract page number p from logical address
2. Look up page table entry for p --> get frame number f
3. Physical address = (f × page_size) + d

Example:

Page size = 4 KB (4096 bytes)
Logical address = 0x00005200

Page number  = 0x00005200 / 4096 = 5
Offset       = 0x00005200 % 4096 = 0x200

Page table says: page 5 --> frame 12

Physical address = 12 × 4096 + 0x200 = 0xC200

Address Translation Flow

Page Table Entry (PTE) Fields

Each entry in the page table stores more than just a frame number:

When the valid bit is 0 and a process accesses that page, the CPU raises a page fault — the OS must load the page from disk. (Covered in detail in the Virtual Memory lesson.)

The TLB: Solving the Speed Problem

Every memory access requires consulting the page table — but the page table itself lives in RAM. Without optimization, every logical memory access would require two physical RAM accesses (one for the page table, one for the data). This would halve memory performance.

The Translation Lookaside Buffer (TLB) solves this. It is a small, extremely fast cache (typically 64–1024 entries) built into the CPU that stores recent page-to-frame translations.

TLB Hit rate on a typical workload is 99%+. This means the average memory access is nearly as fast as a direct RAM access.

• TLB Hit: ~1–5 ns
• TLB Miss: ~50–100 ns (must read page table from RAM)

On a context switch, the TLB must be flushed (or tagged with an ASID — Address Space Identifier) so one process cannot use another process's translations.

Multi-Level Page Tables

A 64-bit address space with 4 KB pages would require a page table with 2^52 entries — about 18 petabytes per process. That is clearly impossible.

Multi-level page tables solve this by making the page table itself a tree, only allocating nodes for the address ranges actually used.

Only allocate PT nodes where the process actually uses memory. A process using 1 MB only needs a handful of nodes, not petabytes.

Linux uses a 4-level page table on x86-64 (PML4 → PDPT → PD → PT). Windows uses the same hardware structure.

Paging in Real Operating Systems

Linux: Uses 4-level page tables on x86-64. The top-level pointer lives in register CR3. The kernel uses huge pages (2 MB) for kernel memory to reduce TLB pressure.

Windows: Also uses 4-level page tables. Each process has a dedicated page directory stored in the Process Control Block.

macOS (Apple Silicon): ARM architecture uses a similar 4-level translation, with Apple's custom TLB management for performance-per-watt optimization.

Summary

Key Takeaways

• Paging eliminates external fragmentation entirely by making all units the same size
• Every memory access involves an address translation from logical to physical
• The TLB makes this translation almost free in the common case
• Multi-level page tables handle modern 64-bit address spaces efficiently
• The valid bit is the foundation for virtual memory and demand paging — covered next