Inverted Page Tables

Since traditional page tables are indexed by virtual page numbers, each virtual page requires a separate entry. With 4096 bytes per page and a 232 byte address space, more than 1 million page table entries are required. The page table will need to be at least 4 megabytes in size. This size is certainly manageable on larger computers.

However, when 64-bit systems proliferate, the scenario radically alters. We require a page table with 252 entries if the address space is now 264 bytes and has 4 KB pages. The table is over 30 million gigabytes in size if each entry is 8 bytes. It is impossible to tie up 30 million gigabytes merely for the page table, neither now nor for many years to come, if ever. As a result, 64-bit paged virtual address spaces require a different solution.

The inverted page table is one option for this problem. Instead of having one entry per page of virtual address space, this design has one entry per page frame in physical memory. 

An inverted page table, for instance, only needs 65,536 entries for 256 MB of RAM, a 4-KB page, and 64-bit virtual addresses. Which (process, virtual page) is present in the page frame is recorded in the entry.

Inverted page tables have a significant drawback that makes virtual-to-physical translation much more challenging, even if they save enormous amounts of space, at least when the virtual address space is significantly bigger than the physical memory. 

The hardware can no longer locate the physical page by utilizing p as an index into the page table when process n references virtual page p. The complete inverted page table must be searched instead for an entry (n, p). 

Additionally, all memory references must be searched for, not just page faults. Making your machine blindingly fast by searching a 64K table for every memory reference is not the way to do it.

The TLB can be used to solve this problem. 

Translation can proceed as quickly as with conventional page tables if the TLB has enough space to contain all of the frequently used pages. On a TLB miss, however, a software search of the inverted page table is required. A hash table hashed on the virtual address is one practical approach to carry out this search. 

As seen in Figure, all virtual pages that are currently in memory and have the same hash value are chained together. The mapping process will be significantly sped up if the hash table has the same number of slots as the machine's physical pages. Once the page frame number has been found, the new (virtual, physical) pair is entered into the TLB.

Inverted page tables are currently used on some IBM and Hewlett-Packard workstations and will become more common as 64-bit machines become widespread.

Happy Exploring!