Editing Page table (section)

=== {{Anchor|FRAME-TABLE}}Inverted page tables ===
An ''inverted page table'' (IPT) is best thought of as an off-chip extension of the [[Translation lookaside buffer|TLB]] which uses normal system RAM. Unlike a true page table, it is not necessarily able to hold all current mappings. The operating system must be prepared to handle misses, just as it would with a MIPS-style software-filled TLB.

The IPT combines a page table and a ''frame table'' into one data structure. At its core is a fixed-size table with the number of rows equal to the number of frames in memory. If there are 4,000 frames, the inverted page table has 4,000 rows. For each row there is an entry for the virtual page number (VPN), the physical page number (not the physical address), some other data and a means for creating a [[hash collision|collision]] chain, as we will see later.

Searching through all entries of the core IPT structure is inefficient, and a [[hash table]] may be used to map virtual addresses (and address space/PID information if need be) to an index in the IPT - this is where the collision chain is used. This hash table is known as a ''hash anchor table''. The hashing function is not generally optimized for coverage - raw speed is more desirable. Of course, hash tables experience collisions. Due to this chosen hashing function, we may experience a lot of collisions in usage, so for each entry in the table the VPN is provided to check if it is the searched entry or a collision.

In searching for a mapping, the hash anchor table is used. If no entry exists, a page fault occurs. Otherwise, the entry is found. Depending on the architecture, the entry may be placed in the TLB again and the memory reference is restarted, or the collision chain may be followed until it has been exhausted and a page fault occurs.

A virtual address in this schema could be split into two, the first half being a virtual page number and the second half being the offset in that page.

A major problem with this design is poor [[cache locality]] caused by the [[hash function]]. Tree-based designs avoid this by placing the page table entries for adjacent pages in adjacent locations, but an inverted page table destroys spatial [[locality of reference]] by scattering entries all over. An operating system may minimize the size of the hash table to reduce this problem, with the trade-off being an increased miss rate.

There is normally one hash table, contiguous in physical memory, shared by all processes. A per-process identifier is used to disambiguate the pages of different processes from each other. It is somewhat slow to remove the page table entries of a given process; the OS may avoid reusing per-process identifier values to delay facing this. Alternatively, per-process hash tables may be used, but they are impractical because of [[Fragmentation (computing)|memory fragmentation]], which requires the tables to be pre-allocated.

Inverted page tables are used for example on the [[PowerPC]], the [[UltraSPARC]] and the [[IA-64]] architecture.<ref>William Stallings, ''Operating Systems Internals and Design Principles'', p. 353.</ref>