Inverted Page Table in Operating System

Introduction

Most operating systems implement a separate page table for each process, i.e., there are n page tables kept in memory for the 'n' number of processes running on a Multiprocessing/ Time-Sharing operating system.

When a process is vast in size and takes up a lot of virtual memory, the page table size grows dramatically. 

Also see, Introduction to Paging

Example: 

A process of size 4 GB with:
Page size = 512 Bytes
Size of page table entry = 8 Bytes, then
Number of pages in the process = 4 GB / 512 B = 223
PageTable Size = 223 * 23 = 226 bytes

This example shows that when numerous processes are operating in an OS simultaneously, page tables take up a significant amount of memory. 

Multilevel paging strategies are also included in operating systems, which increase the amount of space necessary for storing page tables and demand a lot of memory.

The amount of memory occupied by page tables can be a significant overhead, which is always undesirable because main memory is always a limited resource.

Various attempts are made to optimize memory and maintain a healthy balance between multiprogramming and efficient CPU use. 

Inverted Page Table

Another option is the Inverted Page Table structure, which consists of a one-page table entry for every main memory frame.

As a result, the number of page table entries in the Inverted Page Table is reduced to the number of frames available in physical memory. A single-page table represents all processes' paging information. 

The overhead of holding a separate page table for each process is reduced with the inverted page table. A fixed area of memory is required to store the paging information of all processes together.

Because the indexing is done with respect to the frame number rather than the logical page number, this technique is known as inverted paging.

The fields listed below are found in each page table entry. 

• Page number - It specifies the logical address's page number range. 
• Process Id - All of the processes under execution have their address space information stored in an inverted page table. Because two processes can have a similar set of virtual addresses, the Inverted Page Table must maintain a process Id for each process to uniquely identify its address space. This is accomplished by combining the PId and the Page Number. As a result, this Process Id serves as an address space identifier, ensuring that a virtual page for a specific process is accurately mapped to the physical frame. 
• Control Bits - Extra paging-related information is stored in these bits. The valid bit, dirty bit, reference bits, protection, and locking information bits are among them. 
• Chained Pointer - It's feasible that two or more processes will share a section of main memory at some point. In this situation, two or more logical pages map to the same Page Table Entry, and the details of these logical pages are mapped to the root page table via a chaining pointer. 

The working and operation of the inverted page table are shown below

The fields and other essential information necessary in paging-related mechanisms are contained in the virtual address created by the CPU and each page table entry.

When a memory reference occurs, the memory-mapping unit matches the virtual address, searches the Inverted Page table for a match, and obtains the matching frame number.

If a match is discovered at the ith entry, the process's physical address is provided as the real address; a Segmentation Fault is triggered if no match is found. 

Note: The number of entries in the inverted page table is equal to the number of frames in the physical address space (PAS) 

Examples

The Inverted Page table and its variants are used in various systems, including the PowerPC, UltraSPARC, and IA-64 architectures.

This approach is also used in an RT-PC implementation of the Mach operating system.                                                                       

You can also read about the interleave memory.