Working of Inverted Page Table

The operation of an inverted page table is shown below.

The virtual address generated by the CPU contains the fields and each page table entry contains the other relevant information required in paging related mechanism. When a memory reference takes place, this virtual address is matched by the Memory Management Unit(MMU), the Inverted Page table is searched and the corresponding frame number is obtained. If the match is found at the i^th entry then the physical address of the process is sent as the real address otherwise if no match is found then Segmentation Fault is generated. Note: Number of Entries in Inverted page table = Number of frames in Physical Address Space(PAS).

Examples: The Inverted Page table and its variations are implemented in various systems like PowerPC, UltraSPARC, and the IA-64 architecture. An implementation of the Mach operating system on the RT-PC also uses this technique. 

Most Operating Systems implement a separate page table for each process, i.e. for the ‘n’ number of processes running on a Multiprocessing/ Timesharing Operating System, there is an ‘n’ number of page tables stored in the memory. Sometimes when a process is very large and it occupies virtual memory then with the size of the process, its page table size also increases substantially.

Example: A process of size 2 GB with:
Page size = 512 Bytes
Size of page table entry = 4 Bytes, then
Number of pages in the process = 2 GB / 512 B = 222
Page Table Size = 222 * 22 = 224 bytes

Through this example, it can be concluded that for multiple processes running simultaneously in an OS, a considerable part of memory is occupied by page tables only. Operating Systems also incorporate multilevel paging schemes which further increase the space required for storing the page tables and a large amount of memory is invested in storing them. The amount of memory occupied by the page tables can turn out to be a huge overhead and is always unacceptable as main memory is always a scarce resource. Various efforts are made to utilize the memory efficiently and to maintain a good balance in the level of multiprogramming and efficient CPU utilization.