1. Introduction

In a traditional paging system, each process maintains its own page table. As virtual address spaces become larger—especially in modern 64-bit systems—the size of page tables grows dramatically.

To reduce this memory overhead, operating systems can use an Inverted Page Table (IPT).

An inverted page table stores information based on physical memory frames rather than logical pages, significantly reducing the amount of memory required for page tables.

2. Problem with Traditional Page Tables

In a conventional paging system:

Each Process
        ↓
Own Page Table
        ↓
One Entry Per Virtual Page

As virtual address spaces increase:

• More pages exist

• More page table entries are required

• Memory consumption increases significantly

Key Observation

Traditional page table size depends on:

Virtual Address Space Size

rather than:

Physical Memory Size

This becomes inefficient in large systems.

3. What is an Inverted Page Table?

An Inverted Page Table (IPT) is a single global page table maintained for the entire system.

Instead of having:

One Entry Per Virtual Page

it stores:

One Entry Per Physical Frame

Key Idea

Traditional Paging
        ↓
One Entry Per Page

Inverted Paging
        ↓
One Entry Per Frame

Since the number of physical frames is much smaller than the number of virtual pages, memory usage is greatly reduced.

4. Basic Concept

Suppose a system has:

Physical Memory = 1024 Frames

The inverted page table contains:

1024 Entries

regardless of:

• Number of processes

• Size of virtual address spaces

This is the major advantage of IPT.

5. Structure of an Inverted Page Table

Each entry corresponds to one physical frame.

Typical fields include:

Process ID (PID)

Identifies the process that owns the page.

Page Number

Specifies which virtual page is stored in the frame.

Control Information

Contains management bits such as:

• Valid bit

• Protection bit

• Reference bit

• Dirty bit

6. Example Structure

This means:

Frame 1
contains

Process 2
Page 3

7. How Address Translation Works

The CPU generates:

(PID, Page Number, Offset)

The operating system must determine:

Which frame contains
(PID, Page Number)?

Once found:

Physical Address
=
Frame Number + Offset

8. Translation Steps

Step 1

CPU generates:

(PID, Page Number, Offset)

Example:

PID = 2
Page = 3
Offset = 100

Step 2

Search the inverted page table.

Find:

(PID = 2, Page = 3)

Suppose it is located at:

Frame 1

Step 3

Construct physical address:

(Frame 1, Offset 100)

This becomes the final physical address.

9. Major Challenge

Unlike traditional page tables:

Page Number
        ↓
Direct Index
        ↓
Frame Number

there is no direct indexing in IPT.

Instead:

PID + Page Number
        ↓
Search Table
        ↓
Frame Number

Searching can be expensive.

10. Need for Hashing

To avoid linear searching, most systems use:

Hash Tables

Basic Idea

Hash(PID, Page Number)
        ↓
Locate Entry
        ↓
Get Frame Number

Hashing makes lookups much faster.

11. Hash-Based Lookup Example

Suppose:

PID = 2
Page = 3

Compute:

Hash(2,3)

The hash function points to a location in the inverted page table.

The matching entry is then retrieved quickly.

12. Why Inverted Page Tables Save Memory

Consider:

Virtual Pages
=
1,000,000

Traditional paging requires:

1,000,000 Entries

If physical memory contains:

10,000 Frames

then IPT requires only:

10,000 Entries

This is a massive reduction.

13. Advantages of Inverted Page Table

Reduced Memory Consumption

Only one entry per physical frame.

Single Global Structure

No separate page table for each process.

Better Scalability

Works efficiently for large address spaces.

Suitable for 64-bit Systems

Large virtual spaces become manageable.

Reduced Page Table Overhead

Significantly smaller memory footprint.

14. Disadvantages of Inverted Page Table

Slower Lookup

Direct indexing is not possible.

Search Overhead

Requires searching or hashing.

More Complex Design

Implementation is more complicated.

Additional Hardware Support

Efficient performance often requires special support mechanisms.

15. Traditional vs Inverted Page Table

16. Example Comparison

Suppose:

Virtual Pages = 1,000,000
Physical Frames = 10,000

Traditional Page Table

Entries Required
=
1,000,000

Inverted Page Table

Entries Required
=
10,000

Memory reduction:

100× smaller

17. Relationship with Paging

Normal Paging:

Page Number
        ↓
Page Table
        ↓
Frame Number

Inverted Paging:

(PID, Page Number)
        ↓
Inverted Page Table
        ↓
Frame Number

The fundamental paging concept remains the same.

Only the organization of the page table changes.

18. Real-World Analogy

Imagine a library.

Traditional Page Table

A list of every book and the shelf where it is stored.

Book → Shelf

Large libraries require huge lists.

Inverted Page Table

A list of shelves and the book currently stored on each shelf.

Shelf → Book

Since shelves are limited, the list remains small.

19. Practical Usage

Inverted page tables are particularly useful in:

• Large memory systems

• 64-bit operating systems

• Enterprise servers

• Systems with huge virtual address spaces

Some operating systems combine:

Inverted Page Tables
+
Hashing
+
TLBs

to achieve efficient address translation.

Most Important Point

Inverted page tables reduce page table memory overhead by storing one entry per physical frame instead of one entry per virtual page, making them highly suitable for large address-space systems.