Paging — The Freedom Won by Translating Addresses

In a nutshell

If you map virtual addresses to physical frames in fixed-size pages, external fragmentation disappears, and each process can be given its own independent address space.

Why this was needed

The early approach was to give each process one contiguous chunk of memory. This approach soon ran into external fragmentation: a situation where the total free space is sufficient but there is no contiguous piece, so a new process cannot be loaded. You can push everything together by compaction, but the system stops while you do so.

The insight of paging is simple: remove the requirement that memory be contiguous. Cut the address space into fixed-size pages (usually 4KB) and cut physical memory into frames of the same size. Put a page into any frame, and just write down in a table where you put it.

How it works

A virtual address is split into two parts. The upper bits are the page number and the lower bits are the offset. If the page size is 4KB, the offset is 12 bits. Address translation looks up the page number in the page table, replaces it with a frame number, and attaches the offset unchanged. Because the offset is not touched, the relative position within a page is preserved.

A performance problem immediately arises here. The page table is in memory, so one memory access turns into two memory reads. The cache that removes this problem is the TLB (Translation Lookaside Buffer). It holds recent translation results, and on a hit it gets the physical address directly with no extra memory access.

The effective access time is calculated as follows. If a TLB access takes 20ns, a memory access takes 100ns, and the TLB hit ratio is 80 percent:

• Hit: 20 + 100 = 120ns
• Miss: 20 + 100 (page table) + 100 (actual data) = 220ns
• Effective access time = 0.8 × 120 + 0.2 × 220 = 140ns

Raising the hit ratio to 98 percent makes it 122ns. This shows that a few percentage points of hit ratio decide the overall performance.

In a 64-bit address space the page table itself becomes enormous, so a multilevel page table is used. The address is split into several pieces, the table is layered like a tree, and only the branches that are actually used are created. x86-64 usually has four levels. The more levels there are, the higher the cost of a TLB miss, so for workloads that use a lot of memory, huge pages, which increase the page size, are effective. With 2MB pages, the same memory is covered by 1/512 as many TLB entries.

What it looks like in the field

The reason huge pages are often mentioned for programs that scan a large heap at random, such as databases and the JVM, is the TLB. However, there are many reports that Linux transparent huge pages (THP) actually create tail latency in databases because of defragmentation delays, so the PostgreSQL and Redis documentation sometimes recommends against always and suggests madvise or disabling it. It is a good example of how even a good feature can lead to different conclusions depending on the workload's access pattern.

What to check in the quiz that follows

Check whether you can work out how an address is split and how the TLB hit ratio changes the effective access time.