Inverted Page Table in OS

Inverted Page Table is an advanced memory management technique used in modern operating systems to reduce memory overhead. It stores page table entries for all processes in a single global table, improving efficiency in large systems.
In this section, we will explore the concept, need, structure, and working of inverted page tables in detail, list of key topics are given below.

1. What is an Inverted Page Table?

An Inverted Page Table (IPT) is a single global page table indexed by physical frame numbers instead of logical page numbers.
Each entry corresponds to a frame and stores the page number and Process ID (PID) of the process that owns that page.

• Frame-Based Indexing: Table is indexed using physical frame numbers
• Global Table: One table is shared by all processes
• Process Identification: Uses PID to identify process ownership
• Efficient Mapping: Maps physical frames to logical pages
• Improved Memory Usage: Reduces page table size significantly

Need of Inverted Page Table

In traditional paging, each process maintains its own page table, which increases memory usage significantly.
Inverted page tables solve this issue by introducing a single global table for all processes, list of reasons are given below.

1. Problem with Traditional Page Tables

Traditional page tables consume large memory, especially when many processes are running simultaneously.
This creates overhead and reduces system efficiency.

• Multiple Page Tables: Each process requires its own table
• High Memory Consumption: Large processes create large page tables
• Scalability Issues: Not suitable for large systems

2. Memory Overhead Reduction

Inverted page tables remove the need for separate page tables, reducing overall memory usage.
This helps in efficient memory utilization in multi-programming systems.

• Single Global Table: Eliminates redundant tables
• Compact Storage: One entry per frame only
• Better Efficiency: Saves significant memory

3. Numerical Example of Memory Saving

Understanding with an example helps clarify why IPT is needed in large systems.
Let’s analyze memory usage in traditional paging.

• Given:
  • Process Size = 2 GB
  • Page Size = 512 Bytes
  • Page Table Entry Size = 4 Bytes
• Calculation:
  • Number of Pages = 2 GB / 512 B = 2²² pages
  • Page Table Size = 2²² × 4 Bytes = 2²⁴ Bytes (≈ 16 MB)
• Conclusion:
  • For multiple processes, page tables alone consume huge memory
  • IPT reduces this overhead significantly

Structure of Inverted Page Table

The structure of an inverted page table is organized based on physical memory frames.
Each entry stores essential information required for address translation, list of structural components are given below.

1. Frame Number

Each entry corresponds to a physical frame in main memory.
The index of the table itself represents the frame number.

• Direct Mapping: Index = Frame number
• Unique Entry: One entry per frame
• Efficient Storage: No duplication

2. Page Number

The page number identifies the logical page stored in the frame.
It is used along with PID for mapping.

• Virtual Page Identification: Links virtual page to frame
• Essential for Translation: Required for lookup
• Combined Key: Used with PID

3. Process ID (PID)

PID identifies which process owns the page stored in a frame.
This is necessary because a single table is shared by all processes.

• Unique Identification: Differentiates processes
• Supports Multi-Processing: Handles multiple processes
• Accurate Mapping: Ensures correct lookup

4. Control Bits

Control bits store additional information about the page status and access permissions.
They are essential for protection and memory management.

• Valid/Invalid Bit: Indicates if entry is valid
• Protection Bits: Control access permissions
• Dirty Bit: Indicates modification
• Reference Bit: Tracks usage

5. Chained Pointer

Chained pointers are used when multiple logical pages map to the same frame.
This is useful in memory sharing scenarios.

• Collision Handling: Manages multiple mappings
• Shared Memory Support: Enables sharing between processes
• Efficient Linking: Uses linked structure

Working of Inverted Page Table

The working of IPT involves searching for matching entries using process ID and page number.
Since it is indexed by frames, searching is required, list of working steps are given below.

1. Address Translation Process

When a CPU generates a logical address, it must be translated into a physical address.
This process involves matching entries in the inverted page table.

• Step 1: Logical address contains PID, Page Number, and Offset
• Step 2: Search IPT using PID and Page Number
• Step 3: If match found, obtain corresponding frame number
• Step 4: Combine frame number with offset to get physical address

2. Linear Search and Lookup

In basic implementation, IPT uses linear search to find the required entry.
This can increase lookup time.

• Full Table Scan: Search entire table
• Comparison: Match PID and page number
• Performance Issue: Slower than direct indexing

3. Use of Hashing for Optimization

To improve performance, hashing techniques are used instead of linear search.
Hashing reduces lookup time significantly.

• Hash Function: Maps page number to index
• Fast Lookup: Reduces search complexity
• Collision Handling: Uses chaining

4. Handling Page Faults

If no matching entry is found in IPT, a page fault occurs.
The operating system loads the required page from disk.

• Page Fault Detection: Entry not found
• Demand Paging: Load page into memory
• Update IPT: Insert new entry
• Resume Execution: Continue process

5. Important Note

Understanding this key concept is important for exams and practical knowledge.

• Number of Entries in IPT = Number of Frames in Physical Memory

Example of Inverted Page Table

Examples help in understanding how IPT works in real systems.
Let’s analyze a simple lookup scenario.

Example: Searching a Page

Consider that we need to find Page 2 of Process 3.
The system performs a search operation in the IPT.

We have to do a linear search as we want to find page 2 of process 3, then

The logical address generated by the CPU contains Process ID, Page No, and Page Offset.

Through searching in the Inverted Page Table, Process ID and Page No of the logical address are compared with Process ID and Page No.

If a match is found, then its corresponding frame number is obtained from the page table entry; otherwise, a page fault occurs, and Demand paging comes into the picture.

Note: No. of Entries in Inverted page table = No. of frames in Physical Address Space

Advantages of Inverted Page Table

IPT offers several advantages in modern operating systems.
These benefits make it suitable for large-scale systems, list of advantages are given below.

1. Reduced Memory Space

IPT significantly reduces memory usage by maintaining a single table.
This is its biggest advantage.

• Compact Structure: One entry per frame
• Memory Efficient: Saves large memory
• Scalable: Suitable for large systems

2. Efficient for Large Systems

IPT works well in systems with large virtual address spaces.
It supports multi-user environments effectively.

• Multi-Process Support: Handles many processes
• Large Memory Systems: Ideal for 64-bit systems
• Better Resource Utilization: Optimized usage

3. No Redundant Entries

Traditional page tables may have many unused entries.
IPT eliminates this redundancy.

• No Duplication: Single global mapping
• Optimized Storage: Efficient design
• Simplified Management: Easy to maintain

Disadvantages of Inverted Page Table

Despite its benefits, IPT has certain limitations.
These drawbacks must be understood for complete knowledge, list of disadvantages are given below.

1. Longer Search Time

Searching for entries can take more time compared to traditional paging.
This is due to the need for lookup operations.

• Linear Search Overhead: Slow in basic implementation
• Complex Lookup: Requires hashing
• Performance Impact: May increase access time

2. Complex Implementation

IPT is more complex compared to traditional page tables.
It requires additional structures like hash tables.

• Advanced Techniques Required: Hashing and chaining
• Collision Handling: Adds complexity
• Higher Overhead: Complex design

3. Difficult Page Sharing

Sharing pages between processes is not straightforward in IPT.
Extra mechanisms are required.

• Complex Sharing: Hard to map multiple processes
• Additional Management: Requires tracking
• Limited Flexibility: Compared to traditional paging

Comparison: Traditional vs Inverted Page Table

Understanding differences helps students choose the right approach in different scenarios.
The table below highlights key differences.

Conclusion

Inverted Page Table is a powerful memory management technique that reduces memory overhead by using a single global page table.
Although it introduces complexity and longer search time, it is highly efficient for systems with large memory and multiple processes.