Examine the hardware and software architecture of virtual memory: address decomposition, Memory Management Unit (MMU) operation, Page Table Entry bitfields, and multi-level hierarchical paging structures.
The fundamental limitation of Base and Limit dynamic relocation (Module 01) is that each process must still occupy a strictly contiguous block of physical memory. If an application requires 16 MB of RAM, and available memory is fragmented into four separate 4 MB holes, the program cannot run without expensive compaction.
Pioneered in 1962 on the University of Manchester Atlas computer, Virtual Memory via Paging completely breaks the contiguous allocation constraint:
To the executing CPU core, the process appears to inhabit a massive, unbroken, contiguous array of linear addresses ($0 \dots 2^{64}-1$). In reality, the physical frames backing those pages are scattered arbitrarily throughout physical RAM. External fragmentation is completely eliminated.
When the CPU emits a virtual memory address $VA$, the hardware Memory Management Unit (MMU) automatically splits the binary address into two distinct components:
Let $S = 2^n$ be the page size in bytes. For an $m$-bit virtual address space:
Where $f = \text{PageTable}[p].\text{FrameNumber}$ is the physical frame retrieved from the Page Table.
Consider a 32-bit system with standard 4 KB ($2^{12}\text{ bytes}$) pages:
If the CPU references virtual address 0x0000840C:
Virtual Address: 0x0000840C
Binary: 0000 0000 0000 0000 1000 | 0100 0000 1100
\______________________/ \____________/
Page Number p = 8 (0x8) Offset d = 0x40C (1036)
The MMU looks up index $8$ in the Page Table. If entry $8$ contains Frame Number $f = 2$ (0x00002), the Physical Address is formed by concatenating $f$ and $d$:
$$ \text{PA} = (0\text{x}00002 \ll 12) \mid 0\text{x}40C = 0\text{x}0000240C $$
0x000021A4 for an operand read instruction.
The Page Table is not merely an array of frame numbers; each Page Table Entry (PTE) contains critical hardware status and protection bitfields:
| Bit Field | Name | Hardware Function & Purpose |
|---|---|---|
| Present (P / Valid) | Bit 0 | 1 if page is resident in physical RAM. 0 if page is unmapped or on disk; accessing triggers an immediate Page Fault. |
| Read/Write (R/W) | Bit 1 | 0 = Read-Only (attempting to write triggers a protection fault). 1 = Read-Write. Used for code segment protection. |
| User/Supervisor (U/S) | Bit 2 | 0 = Kernel mode only (Ring 0). 1 = User space accessible (Ring 3). Prevents user code from touching kernel memory. |
| Accessed (A / Ref) | Bit 5 | Set to 1 by the hardware MMU on any read or write. Inspected by page replacement algorithms (such as Clock or LRU aging). |
| Dirty (D / Modified) | Bit 6 | Set to 1 by the hardware MMU whenever a write occurs. When evicting the page, the OS knows it must write it back to disk. |
| Page Frame Number | Bits 31–12 | The upper physical address bits representing the physical RAM frame holding the page data. |
While simple single-level paging successfully eliminates external memory fragmentation, it introduces a severe secondary challenge: the scaling crisis of page table memory overhead.
In a flat (single-level) paging design, the operating system maintains a single monolithic array where every possible virtual page number corresponds to a contiguous slot in physical RAM.
If a system runs $100$ concurrent processes, $400\text{ MB}$ of physical RAM is consumed solely by page table metadata. Crucially, each 4 MB table must be stored in strictly contiguous physical memory so the MMU can perform simple array index lookups ($Base + p \times 4$), re-introducing the contiguous allocation problem.
Allocating a flat page table for a single 64-bit process would require millions of times more RAM than exists on entire enterprise servers.
The reason flat linear page tables are so catastrophically wasteful is that real-world programs exhibit extreme address space sparsity.
A typical user application does not populate 4 GB or 16 Exabytes of memory continuously. Instead, its virtual layout consists of three small, isolated clusters:
The vast chasm between the top of the heap and the bottom of the stack—often spanning hundreds of gigabytes or terabytes—is completely empty and unmapped. A flat page table wastes over $99.9\%$ of its entries storing invalid PTEs ($P = 0$) for memory addresses the program never touches.
To eliminate the storage overhead of unmapped address space, modern operating systems page the page table itself. In a two-level hierarchical paging scheme, the monolithic page table is broken into thousands of distinct 4 KB pages, coordinated by a top-level table called the Page Directory.
A 32-bit virtual address is partitioned into three discrete fields:
The architectural brilliance of multi-level paging lies in conditional allocation:
Consider a minimal 32-bit program requiring only $12\text{ KB}$ of memory (one 4 KB page for code, one for data, one for stack):
Total memory consumed for page tables: $4\text{ KB} + 4\text{ KB} + 4\text{ KB} = \mathbf{12\text{ KB}}$, compared to $4096\text{ KB}$ ($4\text{ MB}$) for a flat table—a $99.7\%$ memory savings!
On modern 64-bit x86-64 processors, the hierarchical paging model is extended to four discrete levels. While pointers in x86-64 are 64 bits wide, current processor hardware implements a 48-bit canonical virtual address space (capable of addressing 256 Terabytes).
In a 48-bit virtual address, bits 47 through 0 define the address space, while bits 63 through 48 must be an identical copy of bit 47 (sign-extension rule):
0x0000_0000_0000_0000 to 0x0000_7FFF_FFFF_FFFF (lower 128 TB).0xFFFF_8000_0000_0000 to 0xFFFF_FFFF_FFFF_FFFF (upper 128 TB).#GP).Because each Page Table Entry in 64-bit mode is 8 bytes wide, a single 4 KB page frame holds exactly $4096 / 8 = 512 = 2^9$ entries. Consequently, every level of the hierarchy indexes exactly 9 bits:
The CPU control register CR3 stores the physical base address of the active process's root PML4 table. When translating address $VA$, the hardware MMU executes the following sequential steps:
Traversing four levels of page tables adds significant overhead. For database engines, virtual machine hypervisors (KVM), and scientific simulations with massive memory footprints, standard 4 KB pages cause severe TLB cache thrashing.
Modern processors allow the MMU to terminate the tree walk early by setting the Page Size (PS) bit (bit 7) in intermediate table entries:
By setting the PS bit in a Page Directory (PD) entry, the PD entry points directly to a contiguous 2 MB physical frame, completely bypassing the fourth-level Page Table (PT).
A single TLB entry now maps 2 MB instead of 4 KB ($512\times$ greater cache coverage).
By setting the PS bit in a Page Directory Pointer Table (PDPT) entry, the entry points directly to a contiguous 1 GB physical frame, bypassing both the PD and PT levels.
Enables hypervisors to map hundreds of gigabytes of guest physical memory with negligible TLB misses.
With high-performance cloud servers deploying hundreds of terabytes of physical memory, the 48-bit canonical limit (256 TB virtual space) has become an architectural bottleneck.
Modern processors (Intel Ice Lake and newer, AMD Zen 4) introduce 5-Level Paging (Paging57):
Hierarchical paging brilliantly solves the memory storage scaling crisis, but it introduces a severe hardware performance bottleneck:
If a physical RAM access takes 50 nanoseconds, a simple memory read would take $250\text{ ns}$—a catastrophic $400\%$ hardware slowdown on every memory instruction.
Without specialized hardware caching, modern multi-level virtual memory would be unacceptably slow. In Module 04, we examine the critical hardware component that restores near-zero-latency translation: the Translation Lookaside Buffer (TLB).