Address Translation Mechanisms in Operating Systems: Page Tables, TLB, and Multi-Level Page Tables

Address Translation Mechanisms in Operating Systems: Page Tables, TLB, and Multi-Level Page Tables

1. Knowledge Description
Modern operating systems provide each process with an independent address space through virtual memory. The addresses accessed by processes are virtual addresses, while the actual data is stored at physical addresses in physical memory. Address translation is responsible for mapping virtual addresses to physical addresses. The core mechanisms include:

  • Page Table: Stores the mapping relationships between virtual pages and physical page frames.
  • TLB: A hardware cache that accelerates address translation.
  • Multi-Level Page Table: Solves the problem of page tables occupying excessive memory.

2. Basic Steps of Address Translation
Assuming the system uses paging for memory management, both virtual and physical addresses are divided into fixed-size pages (e.g., 4KB).

Step 1: Virtual Address Structure
A virtual address is divided into two parts:

  • Virtual Page Number (VPN): The high-order bits, used to index the page table.
  • Page Offset: The low-order bits, indicating the position within the page.
Example: 32-bit virtual address, page size 4KB (offset occupies 12 bits)  
Number of VPN bits = 32 - 12 = 20 bits, capable of representing 2^20 pages.

Step 2: Querying the Page Table
Each Page Table Entry (PTE) contains:

  • Valid Bit: Indicates whether the page is in physical memory.
  • Physical Frame Number (PFN): The page frame number in physical memory.
    Translation process:
Physical Address = (PFN × Page Size) + Offset

If the valid bit is 0, a page fault exception is triggered, and the operating system loads the missing page.

3. Problems with Page Tables and the Introduction of TLB
Problem 1: Large Page Table Capacity

  • In a 32-bit system, a single process's page table requires 2^20 PTEs (each PTE occupies 4B), totaling 4MB of memory.
  • The total capacity of page tables for all processes may exceed physical memory.

Problem 2: Slow Access Speed
Each memory read/write requires two memory accesses:

  1. Access the page table to obtain the PFN.
  2. Access the actual physical address.
    Access efficiency is halved!

TLB (Translation Lookaside Buffer)

  • A hardware cache that stores recently translated 〈VPN, PFN〉 pairs.
  • Workflow:
    1. The CPU issues a virtual address; the hardware first checks the TLB.
    2. If it hits (TLB hit), the PFN is directly obtained to form the physical address.
    3. If it misses (TLB miss), the page table is queried, and the TLB is updated.
  • TLB hit rates are typically >98%, significantly reducing additional memory accesses.

4. Solving Space Problems with Multi-Level Page Tables
Core Idea:

  • Store only the mappings for virtual pages that are actually used, avoiding allocating PTEs for unused contiguous virtual pages.
  • Divide the page table into a multi-level tree structure.

Example with a Two-Level Page Table (32-bit system):
The virtual address is divided into:

  • 10 bits (first-level page number) - 10 bits (second-level page number) - 12 bits (offset)

Translation Process:

  1. Use the first-level page number to index the Page Directory Table (unique per process).
  2. The Page Directory Entry (PDE) points to the starting address of the second-level page table.
  3. Use the second-level page number to index the second-level page table to obtain the PFN.

Advantages:

  • If a region of virtual pages is unused, only the PDE needs to be marked invalid, without allocating a second-level page table.
  • Saves space: 4KB page directory table + scattered second-level page tables.

Cost:

  • Multi-level queries may increase the number of memory accesses (requires TLB optimization).

5. Example Demonstration
Assume virtual address 0x00403004 (binary high 20 bits = 0000 0000 01|00 0000 0011), page size 4KB.

  • First-level page number = 1, second-level page number = 3, offset = 4.
  1. Obtain the physical address of the page directory table from the CR3 register.
  2. Access the first entry of the page directory table to get the second-level page table address.
  3. Access the third entry of the second-level page table to get the PFN.
  4. Combine the PFN with the offset to get the physical address.

If the TLB caches this mapping, only 1 memory access is required (actual data access).

6. Summary and Interview Key Points

  • The Page Table is the core of virtual memory but requires solutions for space overhead (multi-level page tables) and speed bottlenecks (TLB).
  • Multi-Level Page Tables trade time for space and are suitable for 64-bit systems (e.g., four-level page tables).
  • The TLB is key to hardware optimization; it needs to be flushed during process context switches (ASID can avoid complete flushing).
  • Real systems (e.g., x86-64) combine multi-level page tables (4 levels), TLB, and page fault handling to achieve efficient address translation.