What is an inverted page table in operating systems?

An inverted page table is one of the techniques to structure a page table, where the table is indexed by the actual frame number in the physical memory. The entry in the table corresponds to the logical page number § and the process-id (pid) of the process that owns that page. The tuple (pid,p) is extracted whenever a memory reference happens and is forwarded to the memory subsystem that contains the inverted page table.

The memory subsystem searches through the inverted page table for a match. If a match is found at an entry, such as $i$, then the corresponding physical address consists of $i$ and the offset (d). If no match is found, this means an address was accessed illegally. The 64-bit UltraSPARC and PowerPC are common examples of systems that use inverted page tables.

Why use the inverted page table?

As you can observe, an inverted page table has exactly one entry for each physical frame in the real memory, and therefore only one inverted page table exists in an operating system. This is in contrast to the standard hierarchical page tables, which are indexed by logical address pages, and each process has its own separate page table.

Since a process references pages using logical addresses, hierarchical page tables seem to be the natural way to structure a page table. The translation of addresses is therefore a constant order of operation.

However, the drawback of this technique is that each page table corresponding to a process may contain millions of entries just to track how physical memory is being used. This consumes large amounts of physical memory, which may be undesirable. In such a scenario, the inverted page table solves this problem by only having entries corresponding to actual physical frames, and there is only a page table in the whole system.

Search problem in an inverted page table

While an inverted page table solves the problem of page tables consuming a lot of physical memory, it increases the amount of time to resolve a memory reference. Since an inverted page table is indexed by physical frame numbers, and lookups for memory reference are based on logical addresses, this scheme requires searching through the table to find the match.

Thus, the search operation may require searching the whole table, which takes far too long. This problem can be solved using a hash table, which requires two memory reads for each memory reference but will improve the performance of the system as a whole.

Paging

Paging is one of the widely used memory management schemes, in which the physical address space of a process is non-contiguous. This scheme avoids fragmentation of the disk. Processes are allocated physical memory whenever the latter is available. This scheme requires setting up a page table, which resolves logical addresses generated by CPU to physical addresses in the main memory.