Operating System - Hierarchical Structure of Page Table

Definition:

When a process has a large virtual address space, storing all page table entries in one large page table becomes inefficient. To solve this, we use a hierarchical (multi-level) page table structure.

This breaks the page table into multiple levels, reducing memory overhead and supporting sparse address spaces.

Basic Idea:

Instead of one big table:

  • The page table is divided into multiple levels.

  • Each level indexes the next, like directories in a file system.

  • Only the necessary parts of the table are kept in memory.

Address Breakdown (for 2-Level Page Table):

Suppose we have a 32-bit virtual address.

[ 10 bits | 10 bits | 12 bits ]
  Level 1   Level 2   Offset

  • Level 1 Index: Points to a page table of Level 2 tables.

  • Level 2 Index: Points to the actual page table entries (PTEs).

  • Offset: Offset inside the physical frame.

How It Works (2-Level Example):

  1. CPU generates virtual address:

    • Break it into Level 1 index, Level 2 index, and offset.

  2. Use Level 1 index to access Level 1 page table.

  3. Level 1 entry points to Level 2 page table.

  4. Use Level 2 index to find physical page number.

  5. Combine physical page and offset to get physical address.

Diagram: Hierarchical Page Table (2-Level)

          Virtual Address (32-bit)
       ------------------------------
       | L1 Index | L2 Index | Offset |
       ------------------------------
           ↓
   +--------------------+
   | Level 1 Page Table |
   +--------------------+
           ↓
   +--------------------+
   | Level 2 Page Table |
   +--------------------+
           ↓
   +----------------+
   | Frame in Memory|
   +----------------+
           ↓
   +----------------------+
   | Physical Address Data|
   +----------------------+

Advantages:

  • Saves memory by only creating page tables as needed.

  • Supports sparse address spaces.

  • Scales better for large address spaces (e.g., 64-bit systems).

Disadvantages:

  • More memory accesses to translate one address (one for each level).

  • Slower than single-level page table unless TLB (Translation Lookaside Buffer) is used.