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

Inverted Page Tables

Exploring inverted page tables that have one entry per physical frame rather than per virtual page.

Inverted Page Tables

What you'll learn: How inverted page tables flip the traditional paging structure by indexing physical frames instead of virtual pages.


The Traditional Problem

Traditional page tables have one entry for every virtual page in a process's address space. On 64-bit systems with huge virtual address spaces, these tables can become enormous—even if the process only uses a tiny fraction of that space. You're paying memory overhead for potential pages, not just actual ones.

The Inverted Approach

An inverted page table flips the model: it contains one entry per physical frame of memory, not per virtual page. Each entry stores which <process-id, virtual-page-number> pair currently occupies that physical frame.

Think of it like a hotel registry: instead of giving every potential guest in the world a mailbox slot (traditional), you have one slot per room and write down who's staying there.

How Translation Works

When the CPU needs to translate a virtual address:

  1. Extract the virtual page number and process ID
  2. Search the inverted page table for a matching <pid, vpn> entry
  3. The index where you find it is the physical frame number
  4. Combine with the page offset to get the physical address

The catch: You must search the entire table (or use a hash table) instead of direct indexing. This makes lookups slower unless assisted by a TLB.

Why Use It?

  • Space efficiency: Table size depends on physical memory size, not virtual address space size
  • Shared physical memory: One table for the entire system, not per-process
  • Great for systems with massive virtual spaces but limited physical RAM

Key Takeaway: Inverted page tables save space by having one entry per physical frame rather than per virtual page, trading direct lookup speed for dramatically reduced memory overhead.