INVERTED PAGE TABLE

• Inverted page table is a global page table maintained by the operating system for all the processes. 
• There is just one page table in the entire system, implying that additional information needs to be stored in the page table to identify page table entries corresponding to each process. 
• A technique that greatly reduces the amount of storage required for page tables in systems with large address spaces
• Each entry in the inverted page table contains the VPN of the virtual page mapped into that page frame.
• Entry consists of the virtual address of the page stored in that real memory location, with information about the process that owns that page.
• Decreases memory needed to store each page table, but increases time needed to search the table when a page reference occurs.
• Thus, the amount of storage required for the page table depends on the amount of main memory in the system,not the size of the virtual address space.
• It stores one entry per physical frame, and is a linear array where the contents at each location is <pid (process id), virtual page number> and the index of each location is the physical frame address. 
•  The formula will change now:

•  <pid (id), virtual page number (p)> = page-table[f]     
• This straightaway implies that look-ups can no more happen on the virtual page number. 
• The entire table has to be searched entry-by-entry to find a matching entry having the pid equal to "id" and virtual page number equal to "p". 
• The index location corresponding to the match is the physical frame address (f), which then combined with the offset(d) gives the physical address.
• We can easily infer that look-up time in an inverted page table may be significantly higher when compared to a simple page table. 
• However, because the table stores one entry per physical frame address and there is a single page table in the entire system, the amount of memory used by the inverted page table has reduced considerably.
• Performance of inverted page tables is usually addressed through hashed page tables. 
• But, there is one more disadvantage of using inverted page tables apart from performance. It is shared memory.
• Because there is one and only one entry in the page table per physical frame, and that contains exactly one virtual page number, we no longer can map the same physical frame to multiple virtual page numbers in different processes.

                                                                      search

                                                                          |

     CPU----->LOGICAL ADDRESS(pid,p,d)----->PAGE TABLE(pid,p)------>PHYSICAL ADDRESS(i,d)------>PHYSICAL MEMORY