Paging: Page Tables, Inverted Page Table, Multi-level Paging

Paging is a fundamental memory management strategy that allows a program’s data to be stored non-contiguously in physical memory. To enable this flexibility while keeping track of memory locations, the operating system uses data structures called page tables. As systems scale, more efficient variants like inverted page tables and multi-level paging are introduced to optimize memory usage and access speed.

What is Paging?

Paging divides both the logical address space (used by a process) and physical memory into fixed-size blocks:

• Logical address space → Pages
• Physical memory → Frames

Each logical page is mapped to any available physical frame. This mapping is done using a page table.

1. Page Table

A page table is a data structure maintained by the operating system that keeps the mapping between page numbers and frame numbers.

Key Concepts:

• Every process has its own page table.
• The logical address is split into:

  • Page number (p): Index into the page table.

  • Page offset (d): Location within the page.

• The page table returns the frame number, which is combined with the offset to form the physical address.

Challenges:

• Page tables can become very large, especially for systems with large address spaces (like 64-bit OS).
• Managing and storing them efficiently becomes essential.

2. Inverted Page Table

To reduce memory overhead, modern systems may use an inverted page table. Instead of having a separate page table for each process, an inverted page table maintains one global table for the entire system.

How It Works:

• The table has one entry per physical frame, not per virtual page.
• Each entry stores:

• • Process ID

  • Virtual page number

  • Information about the frame

Benefits:

• Dramatically reduces memory consumption for page tables.
• Especially effective when many processes are running.

Trade-Off:

• Slower lookup times since it may need to search through the entire table unless aided by hashing techniques.
• More complex management of page access and context switching.

3. Multi-level Paging

To avoid the huge memory cost of large single-level page tables, many systems use multi-level paging.

How It Works:

• The page table is broken into multiple levels, forming a hierarchical structure.
• The logical address is split into:

• • Top-level index (points to the page directory)

  • Second-level index (points to the page table)

  • Offset (within the page)

This process continues depending on the number of levels used (two-level, three-level, etc.).

Advantages:

• Saves memory by loading only the required portions of the page tables into memory.
• Helps manage sparse address spaces (when only a small part of the process uses memory).

Drawback:

• Increases the number of memory accesses per address translation, which can slow down performance unless supported by hardware like Translation Lookaside Buffer (TLB).