What is an Inverted Page Table?
Learn what an inverted page table is, why it is sized to physical RAM, and how hashed lookup makes it practical.
Expected Interview Answer
An inverted page table flips the usual mapping direction by keeping one entry per physical frame instead of one entry per virtual page, storing which process and virtual page currently occupies each frame, so the table's size scales with physical memory rather than with the number of processes and their virtual address spaces.
A conventional (forward) page table is per-process and indexed by virtual page number, so total page-table memory grows with the number of processes and the size of each one's virtual address space, which becomes wasteful as address spaces grow into the 64-bit range. An inverted page table instead has exactly one entry per physical frame, and each entry records which process ID and virtual page number currently owns that frame — a single table sized to physical RAM serves every process on the system. The obvious downside is lookup: given a virtual address, the OS can no longer directly index the table by virtual page number, since the table is organized by physical frame, so it must search for a matching process-ID-and-virtual-page pair, which a linear scan would make prohibitively slow; in practice this is solved by hashing the (process ID, virtual page number) pair into a hash table that points into the inverted table, giving near-constant-time lookup. This design is used in systems like PowerPC and some historical Unix implementations specifically because it bounds page-table memory by the amount of physical RAM installed, not by how many processes happen to be running or how sparse their address spaces are.
- Table size scales with physical RAM, not with number of processes
- Avoids the sparse, per-process table bloat of forward page tables
- Motivates hashed lookup as the practical implementation technique
- Contrasts directly with multilevel forward tables for deeper understanding
AI Mentor Explanation
An inverted page table is like a stadium keeping one entry per physical seat, recording which spectator and which ticket number currently occupies that seat, instead of each spectator carrying their own personal seating chart of the whole stadium. The seat-indexed list is only as large as the number of physical seats, no matter how many total ticket holders exist across all matches ever played. Finding a specific spectator now means searching seat records for a matching ticket number, which staff speed up with a hashed lookup by ticket number rather than checking every seat one by one.
Step-by-Step Explanation
Step 1
One entry per frame
The table has exactly one entry per physical frame of RAM, not per virtual page.
Step 2
Frame entry contents
Each entry stores the owning process ID and the virtual page number currently mapped to that frame.
Step 3
Lookup by hashing
To translate a virtual address, the OS hashes (process ID, virtual page number) into a hash table pointing at the matching frame entry.
Step 4
Bounded table size
Total table size is fixed by physical RAM size, regardless of how many processes or how sparse their address spaces are.
What Interviewer Expects
- Clear definition: one entry per physical frame, not per virtual page
- Understanding that table size scales with physical RAM, not process count
- Awareness that lookup requires a hash table, since indexing is no longer by VPN
- Ability to contrast it with forward (multilevel) page tables
Common Mistakes
- Confusing an inverted page table with a multilevel forward page table
- Thinking lookup is still a direct array index by virtual page number
- Not mentioning the hash-table trick needed to make lookup fast
- Forgetting that shared memory across processes is harder to represent with only one owner per frame
Best Answer (HR Friendly)
“An inverted page table flips the usual approach: instead of each program keeping its own lookup table of its entire virtual memory, the operating system keeps just one shared table sized to the actual physical memory installed, with each entry recording which program and which piece of virtual memory currently lives in that physical spot. This keeps the table's size predictable and bounded by real RAM rather than growing with however many programs happen to be running, at the cost of needing a smarter hashed lookup instead of a simple direct index.”
Code Example
struct ipt_entry {
int pid; /* owning process */
unsigned vpn; /* virtual page in that process */
int valid;
};
#define NUM_FRAMES 65536
struct ipt_entry ipt[NUM_FRAMES]; /* sized to physical RAM, not per-process */
#define HASH_SIZE 8192
int hash_table[HASH_SIZE]; /* maps hash(pid, vpn) -> frame index, -1 if empty */
int hash_key(int pid, unsigned vpn) {
return ((unsigned)pid * 2654435761u + vpn) % HASH_SIZE;
}
int translate_frame(int pid, unsigned vpn) {
int h = hash_key(pid, vpn);
int frame = hash_table[h];
if (frame == -1) return -1; /* not resident: page fault */
if (ipt[frame].pid == pid && ipt[frame].vpn == vpn && ipt[frame].valid)
return frame;
return -1; /* hash collision without a real match: page fault */
}Follow-up Questions
- Why is a hash table needed for lookup in an inverted page table?
- How does an inverted page table handle memory shared between two processes?
- Which real systems have used inverted page tables, and why?
- How does an inverted page table compare to a multilevel forward page table on memory usage?
MCQ Practice
1. What does an inverted page table have one entry per?
Unlike a forward page table indexed by virtual page, an inverted page table has exactly one entry per physical frame.
2. Why does an inverted page table need a hash table for lookups?
Since entries are indexed by frame, finding a given (process, virtual page) requires a search, made fast via hashing into the table.
3. What is the main memory advantage of an inverted page table?
Because there is one shared table sized to physical memory, it avoids the per-process table bloat that forward page tables can have.
Flash Cards
What is an inverted page table? — A page table with one entry per physical frame, recording which process and virtual page owns it.
What bounds its size? — The amount of physical RAM installed, not the number of processes.
Why is a hash table needed? — Because entries are indexed by frame, not virtual page, so lookup by VPN requires hashing to find a match quickly.
What is a downside of inverted page tables? — Shared memory across processes and lookup complexity are harder than with a simple forward table.