</>EmbeddedInterview

What is an inverted page table?

HardOperating System Concepts

Short answer: A normal page table has one entry per virtual page of each process. An inverted page table has one entry per physical frame, recording which process (address-space ID) and which virtual page currently occupy it. Its size depends only on physical memory, not on the number of processes or the size of their address spaces. The drawback is lookup: you have to search for the entry that matches (ASID, virtual page), so a hash table is used to make it fast.

Comparison

Per-process page tables Inverted page table
Entries one per virtual page (per process) one per physical frame (system-wide)
Size grows with address space × processes fixed: frames × entry size
Lookup direct indexing (fast) search by (ASID, VPN): needs hashing
Sharing pages between processes easy (two entries point to the same frame) hard (one frame has one owner entry)

Example: 4 GB of RAM with 4 KB frames has 1,048,576 frames. With 16-byte entries the inverted table is 16 MB in total, regardless of whether there are 10 or 10,000 processes.

Why software-only inverted tables are slow: a TLB is content-addressable hardware that compares all entries at once. In software, searching every entry on each TLB miss would be O(number of frames). The fix is a hashed inverted page table: hash (ASID, VPN) to a bucket and follow a short chain. This was used by IBM POWER and PowerPC (hashed page table) and Intel Itanium.

Where it is used today: mostly historical in general-purpose CPUs; ARM and x86 use multi-level per-process tables, which work well with sparse 64-bit address spaces and make sharing easy. The idea remains in TLBs, in some hypervisor and accelerator designs, and in exam questions.