Inverted Page Table

An inverted page table is a technique used to structure a page table, where the table is indexed by the actual frame number in the physical memory. Each entry in the table corresponds to a logical page number and the process ID (PID) of the process that owns that page. This allows for faster lookups and improved performance in virtual memory management.

Need of Inverted Page table

Most operating systems use a separate page table for each process, as in normal paging. In normal paging, if there are 100 processes, then 100 will be the page tables in the main memory. Sometimes, when a process size is very large, its page table size also increases considerably. Through an inverted page table, the overhead of storing an individual page table for each process is removed. A global page table is used, which is used by all processes.

Example: If A process size is 2 GB with Page size = 512 Bytes and page table entry size is 4 Bytes, then

  • Number of pages in the process = 2 GB / 512 B = 222
  • Page Table Size = 222 * 22 = 224 bytes

If multiple processes run simultaneously in an OS with large sizes, then only a considerable amount of memory is occupied by page tables.

Various efforts are made to utilize the memory efficiently and to maintain a good balance between multi-programming and efficient CPU utilization.

Working

In an inverted page table, indexing is done with frame numbers instead of the logical page number. Each entry in the page table contains the following fields.

  • Frame No: It specifies the Frame where the page no is actually present in main memory
  • Page number: It specifies the page number which is required.
  • Process id: An inverted page table contains pages of all the processes in execution. So, page No may be the same for different processes, but the Process ID of each process is unique. Through Process ID, we get the desired page of that process.
  • Control bits –These bits are used to store paging table entry information. These include the valid/invalid bit, protection, dirty bit, reference bits, and other information bit.
  • Chained pointer: It is possible when two or more processes share some part of the main memory. In simple words, when two or more logical pages need to map to the same Page Table Entry, then a chaining pointer is used.

No of frames in main memory = No of entries in Inverted page table

Inverted-Page-table-(IPT)-in-OS

Example

Inverted-Page-table-(IPT)-in-OS-Example

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 and Disadvantages:

  • Reduced memory space
  • Longer Search time