ALLPCB
Background
Many students do not get a thorough introduction to microcomputer fundamentals, and as a result the basic concepts of the memory management unit (MMU) and page tables are unclear. That lack of understanding makes it difficult to learn operating systems such as Linux and leads to common questions about memory management. The following explains the core MMU mechanisms and page table behavior.
Single-level page table (assumption)
With an MMU enabled, the CPU always issues virtual addresses. The MMU translates those virtual addresses to physical addresses using a page table, then accesses the physical memory. The MMU contains a register that holds the base address of the page table.
Assume a page size of 4 KB and a single-level page table. Each page table entry is 32 bits. The mapping works as follows.
If the CPU accesses virtual address 0, the MMU checks page table entry 0. If that entry has no valid mapping, the MMU raises a page fault. The CPU will then run the fault handler.
If the CPU accesses virtual address 4 KB, the MMU checks page table entry 1 (4 KB / 4 KB = 1). If entry 1 is present and maps to physical address 6 MB with permissions RX, the MMU will translate the access to physical address 6 MB. A read or execute is allowed, while a write would cause a page fault because the entry does not grant write permission.
If the CPU accesses virtual address 8 KB + 16, the MMU checks entry 2 (8 KB / 4 KB = 2). If entry 2 maps to physical address 8 MB, the translated physical access is 8 MB + 16. Permission checks are applied as well.
If the CPU accesses virtual address 3 GB, the MMU checks the corresponding page table entry. Suppose that entry maps the virtual address 3 GB to physical address 0 and has kernel-only permissions. The resulting access depends on the CPU mode:
- If the CPU is running in user mode, the access will fault because the entry grants only kernel privilege.
- If the CPU is running in kernel mode, the access is permitted and proceeds normally.
With a single-level page table and 4 KB pages, each 4 KB region of virtual address space requires one 32-bit page table entry. To cover a 4 GB virtual address space, the page table size is 4 GB / 4 KB * 4 bytes = 4 MB.
The page table must provide coverage for the entire virtual address space: any unmapped virtual address will result in a page fault because the MMU has no entry to consult.
In this scheme, any virtual address can be translated by using the high 20 bits of the virtual address as the page table index (4 KB pages imply a 12-bit page offset), and the low 12 bits as the offset within the page.
Multi-level page tables
Allocating a 4 MB page table per process can waste memory. Multi-level page tables (two-level, three-level, etc.) address this by allocating second- and deeper-level tables only when needed.
For example, split a 32-bit virtual address into 10/10/12 bits: the top 10 bits index the first-level table, the next 10 bits index a second-level table, and the low 12 bits are the page offset. If the MMU looks up virtual address 16 (which decomposes into top=0, middle=0, offset=16), it first reads first-level entry 0. If that entry contains the physical address of a second-level table (for example, 2 MB), the MMU then uses the middle 10 bits to index that second-level table at physical address 2 MB. If the second-level entry maps the page to physical address 1 GB, the MMU translates the access to physical address 1 GB + 16.
In this example each first-level table contains 2^10 entries and occupies 2^10 * 4 bytes = 4 KB. Each second-level table also contains 2^10 entries and occupies 4 KB. The advantage is that a second-level table only needs to exist if its corresponding first-level entry is present. If a first-level entry is not present, the entire corresponding 4 KB second-level table can be omitted, saving memory. Page tables can be extended to three or more levels on larger address spaces.
When switching processes, the MMU only needs to be given the base address of the current process's top-level page table. Loading that base address activates the new process's virtual-to-physical mappings.
