One of the most consequential decisions in paging system design is choosing the page size. This single parameter ripples through every aspect of the memory system: from how much space is wasted in partially-filled pages to how large page tables grow, from how efficiently disk I/O operates to how effectively the TLB caches translations.

Modern systems typically use page sizes ranging from 4KB to 1GB, with 4KB being the most common default. But why 4KB? Why not 1KB or 16KB? Why do some systems support multiple page sizes simultaneously? Understanding the tradeoffs behind page size selection is essential for anyone designing or tuning memory systems.

Page size selection is not a simple optimization problem with a clear optimal answer. Instead, it involves balancing multiple competing concerns:

Small pages (e.g., 512 bytes, 1KB, 2KB):

• ✓ Less internal fragmentation (smaller waste in last page)
• ✓ Finer granularity of memory protection
• ✓ More precise working set management
• ✗ Larger page tables (more entries needed)
• ✗ More TLB misses (TLB covers less memory)
• ✗ Less efficient disk I/O (small transfers)

Large pages (e.g., 2MB, 1GB):

• ✓ Smaller page tables (fewer entries needed)
• ✓ Better TLB coverage (each entry covers more memory)
• ✓ More efficient disk I/O (larger sequential transfers)
• ✗ More internal fragmentation (larger waste in last page)
• ✗ Coarser granularity of protection
• ✗ Wasted memory for small allocations

Understanding page size requires grasping the mathematical relationships between page size, address space size, and page table structures.

Address Decomposition:

For a system with:

• Logical address space: 2^m bytes (m-bit addresses)
• Page size: 2^n bytes

The logical address divides as:

• Offset bits: n bits (to address bytes within a page)
• Page number bits: m - n bits (to identify which page)
• Number of pages: 2^(m-n) pages possible

Example Calculations:

Page Table Size Calculation:

The page table must have one entry for each possible page. If each page table entry (PTE) is e bytes:

Page Table Size = (Address Space Size / Page Size) × PTE Size
                = (2^m / 2^n) × e
                = 2^(m-n) × e

Concrete Example:

For a 32-bit address space with 4KB pages and 4-byte PTEs:

• Number of pages = 2^32 / 2^12 = 2^20 = 1,048,576
• Page table size = 1,048,576 × 4 bytes = 4 MB

For a 64-bit address space with 4KB pages:

• Number of pages = 2^64 / 2^12 = 2^52 ≈ 4.5 × 10^15
• Page table size = 2^52 × 8 bytes = 32 PB (petabytes!)

This last calculation reveals why 64-bit systems cannot use simple linear page tables and must use hierarchical or other compact representations.

Internal fragmentation occurs because processes rarely require exact multiples of the page size. The last page of every memory allocation is typically only partially filled, wasting the remaining space within that page.

Statistical Analysis:

For a randomly-sized allocation:

• Best case: The allocation exactly fills all its pages (0 bytes wasted)
• Worst case: The allocation is 1 byte larger than a page multiple (page_size - 1 bytes wasted)
• Average case: Half a page wasted (page_size / 2 bytes)

For a system with many processes, the total wasted space averages:

Total Internal Fragmentation ≈ (Number of Processes) × (Page Size / 2)

Implications for System Design:

1. Small Programs Suffer Most: A program using 100KB with 2MB pages wastes 1.9MB per segment. Small utilities, startup processes, and shell scripts become memory hogs.

2. Sparsely-Used Address Spaces: Languages/runtimes that allocate large virtual address spaces (for flexibility) but use memory sparsely face severe fragmentation with large pages.

3. The Mixed Workload Problem: Systems with both large (databases, VMs) and small (utilities, scripts) processes face a dilemma: small pages hurt big processes, large pages hurt small processes.

4. Solution: Multiple Page Sizes: Modern systems support multiple page sizes, using large pages for memory-intensive applications and small pages for general use.

Page tables consume memory too—and this overhead scales inversely with page size. Smaller pages mean more pages, which means more page table entries.

Page Table Memory as a Fraction of Address Space:

For a linear page table with entry size E:

Overhead Ratio = Page Table Size / Address Space Size
               = (Address Space / Page Size) × E / Address Space
               = E / Page Size

Example:

• 4-byte PTEs with 4KB pages: 4/4096 = 0.1% overhead
• 4-byte PTEs with 512-byte pages: 4/512 = 0.8% overhead
• 8-byte PTEs with 4KB pages: 8/4096 = 0.2% overhead

*64-bit systems use hierarchical page tables, so 'page table size' depends on address space utilization, not total possible addresses.

The Per-Process Cost:

Every process needs its own page table. On a system with 1000 processes and 4KB pages:

• 32-bit: 1000 × 4MB = 4GB just for page tables (!)
• With hierarchical page tables: Much less, since unused regions don't need entries

Why Hierarchical Page Tables Help:

With linear page tables, you need entries for the entire possible address space. With hierarchical tables, you only need entries for regions actually in use. A process using 100MB of a 4GB address space might have:

• Linear table: 1 million entries (4MB)
• Hierarchical table: ~25 thousand entries (~100KB)

This is why real systems use multi-level page tables—especially critical for 64-bit systems where linear tables are completely impractical.

The Translation Lookaside Buffer (TLB) is a small, fast cache within the CPU that stores recently-used page table entries. Because accessing the page table in main memory is slow (100+ CPU cycles), the TLB is essential for good performance. The TLB's effectiveness is critically influenced by page size.

TLB Coverage:

The amount of memory addressable through the TLB without causing a miss:

TLB Coverage = Number of TLB entries × Page Size

Example:

• 64-entry TLB with 4KB pages: 64 × 4KB = 256KB coverage
• 64-entry TLB with 2MB pages: 64 × 2MB = 128MB coverage
• 64-entry TLB with 1GB pages: 64 × 1GB = 64GB coverage

The Working Set Problem:

If a program's working set (actively used memory) exceeds TLB coverage, it will experience frequent TLB misses. Each miss requires:

1. Access to the page table in memory (100+ cycles)
2. (Potentially) Page table walks through multiple levels
3. Loading the new translation into the TLB
4. Retrying the original memory access

For memory-intensive workloads like databases or scientific computing, the working set can be gigabytes. With 4KB pages:

• 256KB TLB coverage is trivially exceeded
• Every access outside cached pages causes a TLB miss
• Performance can degrade by 10-30% or more

With 2MB huge pages:

• 128MB TLB coverage per set of entries
• Large working sets remain cacheable
• TLB miss rate drops dramatically

Page size significantly affects disk I/O performance when pages must be loaded from or written to secondary storage (swap space, memory-mapped files).

Disk I/O Characteristics:

Traditional hard drives (HDDs) have:

• High seek time: 5-15 milliseconds to position the head
• High rotational latency: 2-4 milliseconds waiting for data to rotate under head
• High transfer rate once positioned: 100-200 MB/s

SSDs have:

• Low seek time: ~0.1 milliseconds
• No rotational latency
• High transfer rates: 500 MB/s to 7000+ MB/s (NVMe)

But even on SSDs, each I/O operation has fixed overhead (command processing, queue handling). Larger transfers amortize this overhead better.

Efficiency Analysis:

For HDDs, the time to read a page:

Time = Seek Time + Rotational Latency + Transfer Time
     ≈ 10ms + 4ms + (Page Size / Transfer Rate)
     ≈ 14ms + (Page Size / 150 MB/s)

For 4KB page:  14ms + 0.026ms ≈ 14.03ms
For 64KB page: 14ms + 0.43ms ≈ 14.43ms
For 1MB page:  14ms + 6.7ms ≈ 20.7ms

The key insight: seek time and rotational latency dominate. Reading 16× more data (64KB vs 4KB) takes essentially the same time! This is why larger pages are more efficient for disk I/O—you get more data per 'penalty' of positioning.

Effective Bandwidth:

Effective Bandwidth = Page Size / Total Time

For 4KB page:  4KB / 14ms = 285 KB/s
For 64KB page: 64KB / 14.4ms = 4.4 MB/s (15× better!)

Different architectures and operating systems have made different page size choices based on their design priorities and historical constraints.

Standard Page Sizes by Architecture:

Why 4KB Became the Standard:

1. Historical Hardware Constraints: Early page table implementations had limited space. 4KB balanced internal fragmentation against page table size for 32-bit systems.

2. Disk Sector Alignment: Traditional hard drives used 512-byte sectors. 4KB = 8 sectors provided good alignment and minimal internal fragmentation for file-backed pages.

3. Memory Technology: DRAM chips were organized in ways that made 4KB a natural access unit.

4. Software Compatibility: Once 4KB became widespread, enormous amounts of software implicitly assumed it, creating inertia.

5. Power-of-Two Convenience: 4KB = 2^12 bytes makes address decomposition trivial in hardware (just look at bit positions).

Modern Trends:

• Larger base pages: Some ARM implementations now default to 16KB or 64KB pages, improving TLB coverage for memory-intensive mobile applications.
• Transparent Huge Pages (THP): Linux can automatically promote regular pages to huge pages when beneficial, without application changes.
• Application-specific choices: Databases and VMs routinely configure huge pages explicitly.

Given the tradeoffs we've discussed, it's clear that no single page size is optimal for all situations. Modern systems therefore support multiple page sizes, allowing the operating system and applications to choose the best fit for each particular use case.

How Multiple Page Sizes Work:

1. MMU Support: The hardware page table format includes a 'page size' indicator for each entry, or uses separate page table structures for different sizes.

2. TLB Partitioning: Some TLBs have separate sections for different page sizes; others handle all sizes in a unified structure with varying coverage.

3. OS Allocation: The kernel maintains separate free lists for different page sizes and allocates appropriately.

4. Application Requests: Applications can request large pages via special APIs (e.g., mmap with MAP_HUGETLB on Linux, VirtualAlloc with MEM_LARGE_PAGES on Windows).

Transparent Huge Page (THP) Challenges:

Linux's Transparent Huge Pages feature attempts to automatically use huge pages when beneficial. However, THP has known issues:

• Allocation Latency: Finding/creating a contiguous 2MB region can stall memory allocation.
• Memory Fragmentation: Over time, memory becomes fragmented, making huge page allocation difficult.
• khugepaged Overhead: The kernel daemon that promotes/demotes pages consumes CPU.
• Tail Latency: THP operations can cause unpredictable latency spikes.

Many high-performance applications disable THP and manually allocate huge pages at startup to avoid these issues.

Page size is one of the most consequential parameters in memory system design. Let's consolidate the key insights:

What's Next:

Now that we understand pages, frames, and page size trade-offs, we'll explore one of paging's most important benefits: non-contiguous allocation. We'll see how paging fundamentally changes memory allocation by allowing a process's pages to be placed in any available frames, anywhere in physical memory.