an inverted page table

An ordinary page table asks 'for this virtual page, which frame holds it?' and so its size grows with the (possibly enormous) virtual address space, multiplied by every process. An inverted page table flips the question to 'for this physical frame, which virtual page currently sits here?' — so it has just one entry per real frame. Picture a single building-wide ledger with one row per actual cupboard, naming who is using it, instead of a separate giant directory per tenant.

Concretely, the inverted page table has exactly as many entries as there are physical frames, regardless of how big or how many virtual address spaces exist. Each entry records which process and which virtual page currently occupies that frame. To translate, the hardware can no longer index directly by virtual page (the table is not organized that way), so it hashes the (process id, virtual page number) pair to find a candidate entry, then checks it — using a hash table with chaining to handle collisions. A match yields the frame number (which is just the entry's index).

Why it matters: an inverted page table bounds the page-table size by physical memory rather than by virtual memory, which is attractive when address spaces are vast and physical memory is comparatively small. The honest trade-offs are real: translation needs a hash lookup (more complex, with collision chains) instead of a direct index; sharing a frame between processes is awkward since each frame has only one entry; and it is harder to represent a page that is on disk. Because of these complications, most mainstream systems use multilevel forward page tables instead, and inverted tables appear in particular architectures — it is a real design point, not the default.