Course contentsShow
← Computer Science
Lesson 1359 of 2,87231. Memory ManagementFree lesson

Two-Level Page Tables

Understanding the structure and address translation process in a two-level paging scheme.

Two-Level Page Tables

What you'll learn: How two-level page tables split a single large page table into a hierarchy to save memory and improve efficiency.

The Problem with Single-Level Page Tables

Remember that flat page tables can become enormous. For a 32-bit address space with 4KB pages, you'd need over a million entries per process—most pointing to unused memory. That's wasteful!

How Two-Level Page Tables Work

A two-level page table breaks the page table into smaller chunks, organized hierarchically:

  1. Outer (first-level) page table: Points to second-level page tables
  2. Inner (second-level) page tables: Contain the actual page-to-frame mappings

Think of it like a book with chapters. Instead of one giant index listing every page in existence, you have a table of contents (outer table) pointing to chapter-specific indices (inner tables). If a chapter doesn't exist, you don't waste space indexing its pages!

Address Translation Process

The virtual address is now split into three parts:

  • Outer index: Selects which second-level page table to use
  • Inner index: Selects the specific page table entry within that table
  • Offset: Identifies the byte within the page (unchanged from single-level)

The MMU uses the outer index to find the second-level table, then uses the inner index to find the frame number, and finally adds the offset for the physical address.

Memory Savings

Only allocated regions need second-level tables. If a process uses only 10% of its address space, you only need ~10% of the second-level tables—a massive savings compared to maintaining one huge table with mostly invalid entries!

Key Takeaway: Two-level page tables reduce memory overhead by creating page tables on-demand, storing only mappings for memory regions actually in use rather than maintaining a massive flat table with mostly empty entries.