Inverted Page Table

An Inverted Page Table is a memory-management structure used in virtual memory systems to translate virtual addresses into physical addresses more space-efficiently than a traditional per-process page table.2 Instead of keeping a separate page table for every process, the system maintains one global table with exactly one entry for each physical frame in RAM.2 This design is especially valuable when address spaces are large, because conventional page tables may consume substantial memory even for pages that are not currently resident in main memory.2

In short-note form, the key idea is simple: a normal page table maps virtual page $\rightarrow$ physical frame, whereas an inverted page table stores entries indexed by physical frame, and each entry records which process and which virtual page currently occupy that frame.2 Because multiple processes may use the same virtual page number, entries usually include a PID or address-space identifier, together with control bits such as valid, dirty, reference, and protection bits.2

A conceptual view is shown below.2

The structure reduces page-table memory overhead because the number of entries is proportional to the number of physical frames, not to the size of each process's virtual address space.2 However, lookup is less direct: the virtual page number cannot be used as a simple array index, so systems often rely on hashing and the TLB to make translation practical.3

Footnotes

1. Page table - Wikipedia - Overview of page tables, including inverted page tables, structure, and lookup trade-offs. ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶

2. Inverted Page Table - GeeksforGeeks - Notes on definition, fields, advantages, disadvantages, and example architectures. ↩ ↩² ↩³ ↩⁴ ↩⁵

3. Operating Systems Lecture Notes Lecture 10 Issues in Paging and Virtual Memory - Lecture notes explaining inverted page tables as mappings only for resident physical pages. ↩ ↩²

4. Appendix L: Advanced Concepts on Address Translation - Discussion of address-translation structures, including inverted and hashed page tables, and their design trade-offs. ↩ ↩²

5. Faster Translations (TLBs) - OSTEP - Explains TLBs, translation caching, and fields such as ASID and protection bits relevant to paging. ↩ ↩²

Structure and fields of an inverted page table

Each entry in an inverted page table corresponds to one frame in main memory and typically stores the following information:2

Because the table is organized by physical frames, the number of entries is:

$$\text{Number of IPT entries} = \frac{\text{Physical Memory Size}}{\text{Page Size}}$$

For example, if physical memory is $4\ \text{GB}$ and page size is $4\ \text{KB}$, then the number of entries is:

$$\frac{4 \times 2^{30}}{4 \times 2^{10}} = 2^{20} = 1{,}048{,}576$$

Thus, the table grows with RAM size rather than with the potentially enormous virtual address spaces of all running processes.2 This is why the design is attractive on systems with large address spaces, including some architectures such as PowerPC, UltraSPARC, and IA-64.

Footnotes

1. Page table - Wikipedia - Overview of page tables, including inverted page tables, structure, and lookup trade-offs. ↩ ↩² ↩³ ↩⁴ ↩⁵

2. Inverted Page Table - GeeksforGeeks - Notes on definition, fields, advantages, disadvantages, and example architectures. ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶

3. Faster Translations (TLBs) - OSTEP - Explains TLBs, translation caching, and fields such as ASID and protection bits relevant to paging. ↩ ↩²

4. Operating Systems Lecture Notes Lecture 10 Issues in Paging and Virtual Memory - Lecture notes explaining inverted page tables as mappings only for resident physical pages. ↩

Why inverted page tables are used

The primary motivation is memory efficiency.2 In a traditional single-level page-table design, every process needs its own table, and the size of that table depends on the virtual address space, even if many pages are unused.2 In contrast, the inverted approach stores only mappings for pages that are actually resident in physical memory.2

This difference becomes significant for large address spaces. If a machine supports many processes with large virtual memories, maintaining per-process linear page tables can waste a considerable amount of memory just for bookkeeping. An inverted page table avoids that by replacing many large tables with one compact, global structure.2

Another useful perspective is:

• Traditional page table: indexed by VPN, easy lookup, but potentially very large.2
• Inverted page table: indexed conceptually by physical frame, compact in memory, but lookup is more complex.2

This makes the IPT a classic design trade-off between space and lookup simplicity.2

Footnotes

1. Page table - Wikipedia - Overview of page tables, including inverted page tables, structure, and lookup trade-offs. ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶

2. Inverted Page Table - GeeksforGeeks - Notes on definition, fields, advantages, disadvantages, and example architectures. ↩ ↩² ↩³

3. Operating Systems Lecture Notes Lecture 10 Issues in Paging and Virtual Memory - Lecture notes explaining inverted page tables as mappings only for resident physical pages. ↩ ↩² ↩³ ↩⁴

4. Appendix L: Advanced Concepts on Address Translation - Discussion of address-translation structures, including inverted and hashed page tables, and their design trade-offs. ↩ ↩²

Short note for exam writing

An Inverted Page Table is a system-wide paging structure used in operating systems with virtual memory.2 Unlike a conventional page table, which keeps one entry for each virtual page of each process, an inverted page table keeps one entry for each physical frame in memory. Each entry usually stores the virtual page number, the corresponding process identifier, and control bits such as valid, dirty, and protection bits.2

Its chief advantage is that it greatly reduces the memory required for page tables, especially in systems with large virtual address spaces.2 However, the main drawback is slower lookup, because translation requires searching the table using PID and VPN rather than direct indexing; therefore hashing and TLBs are commonly used to improve performance.3 Inverted page tables have been used in architectures such as PowerPC, UltraSPARC, and IA-64.

A compact memory relation is:

$$\text{IPT size} \propto \text{Number of physical frames}$$

whereas for conventional paging:

$$\text{Page-table size} \propto \text{Number of virtual pages across processes}$$

Hence, an inverted page table is best described as a space-saving paging technique with more complex address translation.2

Footnotes

1. Page table - Wikipedia - Overview of page tables, including inverted page tables, structure, and lookup trade-offs. ↩ ↩² ↩³ ↩⁴ ↩⁵

2. Inverted Page Table - GeeksforGeeks - Notes on definition, fields, advantages, disadvantages, and example architectures. ↩ ↩² ↩³ ↩⁴

3. Faster Translations (TLBs) - OSTEP - Explains TLBs, translation caching, and fields such as ASID and protection bits relevant to paging. ↩ ↩²

4. Operating Systems Lecture Notes Lecture 10 Issues in Paging and Virtual Memory - Lecture notes explaining inverted page tables as mappings only for resident physical pages. ↩ ↩²