- Pages and Segments
- Page Tables
So far, we’ve treated the MMU as a magical box that performs translation and protection. How these protections are defined depends on whether the architecture uses software or hardware page tables. The page table is the data structure that defines the mappings from virtual addresses to physical ones. On an architecture like x86, the layout of this data structure is defined by the CPU; every time there’s a memory access, the CPU consults the tables and finds out where the real destination should be. I say "every time," but this isn’t quite true. Rather, it maintains a cache (otherwise, memory accesses would be painfully slow), and the operating system must invalidate the relevant parts of this cache after modifying the page table.
Page tables on x86 aren’t actually tables, they’re a tree. Every 32-bit address is split into three parts, two of 10 bits and one of 12 bits. The first 10 bits (a value from zero to 1023) give an index within a 4KB page known as the page directory. This is a list of 32-bit addresses. The address found from this is the location of another (4KB) page called the page table, with a similar structure. This then gives an address of a 4KB page, and the remaining 12 bits of the original address give the location within this page.
Astute readers will have noticed that the page tables contain 32-bit entries, but only 20 bits are required to uniquely identify the address of a 4KB page. The remaining 12-bits are used for flags. The "not present" flag, for example, identifies the target page (or page table, if it’s in the page directory) as not currently being present in physical memory. If a process tries to access memory in one of these pages, the CPU will issue a page fault, which the operating system will catch and load the page. This is also used by operating systems like Linux that perform lazy allocation, so memory is allocated only when it’s used, rather than when it’s requested. Other flags are used for things like permissions.
On an architecture like SPARC, the situation is quite different. The SPARC has a cache of virtual to physical mappings, just as x86 does. This is called a translation look-aside buffer (TLB). In the case of the SPARC, each entry has a process ID associated with it, so the buffer doesn’t have to be flushed when a new process runs. Unlike x86, the SPARC is unaware of the structure of the page tables—they’re entirely the operating system’s responsibility. Whenever an address is accessed that isn’t in the cache, a page fault is issued, and the OS must provide the correct mapping.
You might imagine that this process is quite slow, and you would be right. In early SPARC systems, around 50% of the CPU time was spent in the operating system’s page-fault handler. To alleviate this situation, newer SPARCs take a hybrid approach. They reserve a region of memory that acts as an overflow for the TLB. If the entry isn’t in the TLB, it will first look in this region—a simple table—and will load the mapping from there, if possible. This approach dramatically improved the performance of the SPARC architecture.