Paging: Translating Virtual to Physical Addresses

The Basic Mechanism: Paging and Address Translation

As we touched upon previously, the fundamental idea behind paging is to divide memory into fixed-size blocks. The virtual address space is chopped into pages, and the physical memory (RAM) is divided into same-sized blocks called page frames. The OS is then responsible for mapping virtual pages to physical frames.

A key insight is that a contiguous block of virtual pages does not need to map to a contiguous block of physical frames. This flexibility is what allows the OS to overcome the problem of physical memory fragmentation.

To see how this works, let's start with a simple example.

The crucial next step is to understand how a virtual address itself is structured. The hardware doesn't treat it as a single monolithic number. Instead, it splits it into two parts:

1. Virtual Page Number (VPN): The upper bits of the address, which identify the virtual page.
2. Page Offset: The lower bits of the address, which specify the byte's location within that page.

The size of the page determines how many bits are used for the offset. For example, with 4 KiB pages ($2^{12}$ bytes), the lower 12 bits of the virtual address form the page offset. The remaining upper bits form the VPN.

The translation process then becomes:

• The VPN is translated to a Physical Frame Number (PFN) using the page table.
• The offset remains unchanged. It is simply combined with the PFN to form the final physical address.

This short video provides an excellent visual walkthrough of this fundamental process.

The Page Table and its Entries

As you've now seen, the page table is the central data structure for address translation. It's essentially a lookup table, indexed by the VPN, that provides the corresponding PFN. For each process, the OS maintains a separate page table.

Let's formalize the translation with the simple example from the OSTEP text.

However, a Page Table Entry (PTE) contains much more than just the physical frame number. It also holds several crucial control bits that the MMU uses to enforce memory protection and manage pages.

These bits are what enable the OS to implement the features we discussed in the last lesson. For example:

• If a process tries to write to a page marked Read-Only, the MMU triggers a protection fault.
• If a process tries to access a page where the Present bit is 0, the MMU triggers a page fault, signaling the OS to load the page from disk.

The Size Problem: Multi-Level Page Tables

So far, we've considered a simple, linear page table (an array). This works for tiny address spaces, but it fails spectacularly with modern 64-bit systems. A 64-bit address space is enormous (16 exabytes). A single page table to map this entire space, even with 4 KiB pages, would require trillions of entries and consume a petabyte-scale amount of memory itself. This is obviously impractical.

The solution is to add a level of indirection, creating a tree-like structure known as a multi-level page table. Instead of one giant table, we have a hierarchy of smaller tables.

• A top-level table's entries don't point to physical frames. Instead, they point to the physical address of a next-level page table.
• This continues for several levels until the final-level table, whose entries point to the actual physical frames.

This hierarchical approach saves an immense amount of space because page tables for unused regions of the virtual address space simply don't need to be allocated. Modern architectures like x86-64 use a four-level page table scheme.

A Full Translation Walkthrough

Now we can put all the pieces together to see how a virtual address is translated in a modern x86-64 system. The CPU's CR3 register holds the physical address of the top-level page table (the Page Map Level 4 Table, or PML4). The hardware then "walks" the page table hierarchy.

The following diagram illustrates this entire process.

Let's walk through this step-by-step with a concrete example.

This entire process—splitting the address, indexing into tables, and checking protection bits—is performed automatically in hardware by the Memory Management Unit (MMU) on every single memory access. It's a remarkable piece of engineering that is completely transparent to the running application.

The obvious performance question is: doesn't this slow things down? Accessing one memory location now requires up to four additional memory reads just to walk the page tables. This would be prohibitively slow. The hardware solves this with a specialized cache called the Translation Lookaside Buffer (TLB), which stores recently used virtual-to-physical address translations. If a translation is in the TLB (a "TLB hit"), the lengthy page table walk can be skipped entirely.

Conclusion

In this lesson, we have dissected the core mechanism that powers virtual memory. We've moved from the high-level concept to the low-level hardware implementation details.

Here are the key takeaways:

• Address Splitting: A virtual address is composed of a Virtual Page Number (VPN) and a Page Offset. The offset is never translated.
• Page Tables: These are per-process data structures, managed by the OS, that map VPNs to Physical Frame Numbers (PFNs).
• Page Table Entries (PTEs): A PTE contains the PFN plus crucial control bits for protection (read/write/execute) and memory management (present, dirty, accessed).
• Multi-Level Structure: To handle vast 64-bit address spaces efficiently, modern systems use a hierarchy of page tables (e.g., 4 levels on x86-64).
• Translation Process: The MMU uses a special register (CR3) to find the top-level page table and "walks" the hierarchy using parts of the virtual address as indices to find the final PFN.

We've seen that the present bit in a PTE indicates whether a page is actually in physical RAM. When a program tries to access a page that isn't present, the MMU triggers a page fault. In our next lesson, we will explore how the OS handles this. Since physical memory is limited, the OS must decide which page to evict to make room for the new one. This leads us directly to the topic of page replacement algorithms.