Editing Page table (section)

== Page table types ==
There are several types of page tables, which are optimized for different requirements. Essentially, a bare-bones page table must store the virtual address, the physical address that is "under" this virtual address, and possibly some address space information.

=== {{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>

=== {{Anchor|MULTILEVEL}}Multilevel page tables ===
[[File:X86 Paging 4K.svg|thumb|right|upright=2|Two-level page table structure in [[x86]] architecture (without [[Physical Address Extension|PAE]] or [[Page Size Extension|PSE]]).]]
[[File:X86 Paging PAE 4K.svg|thumb|right|upright=2|Three-level page table structure in x86 architecture (with [[Physical Address Extension|PAE]], without [[Page Size Extension|PSE]]).]]

The inverted page table keeps a listing of mappings installed for all frames in physical memory. However, this could be quite wasteful. Instead of doing so, we could create a page table structure that contains mappings for virtual pages. It is done by keeping several page tables that cover a certain block of virtual memory. For example, we can create smaller 1024-entry 4&nbsp;KB pages that cover 4&nbsp;MB of virtual memory.

This is useful since often the top-most parts and bottom-most parts of virtual memory are used in running a process - the top is often used for text and data segments while the bottom for stack, with free memory in between. The multilevel page table may keep a few of the smaller page tables to cover just the top and bottom parts of memory and create new ones only when strictly necessary.

Now, each of these smaller page tables are linked together by a master page table, effectively creating a [[Tree (data structure)|tree]] data structure. There need not be only two levels, but possibly multiple ones. For example, a virtual address in this schema could be split into three parts: the index in the root page table, the index in the sub-page table, and the offset in that page.

Multilevel page tables are also referred to as "hierarchical page tables".

=== Virtualized page tables ===
It was mentioned that creating a page table structure that contained mappings for every virtual page in the virtual address space could end up being wasteful. But, we can get around the excessive space concerns by putting the page table in virtual memory, and letting the virtual memory system manage the memory for the page table.

However, part of this linear page table structure must always stay resident in physical memory in order to prevent circular [[page fault]]s and look for a key part of the page table that is not present in the page table.

=== Nested page tables ===
:{{see also|Second Level Address Translation}}
Nested page tables can be implemented to increase the performance of [[hardware virtualization]]. By providing hardware support for [[page-table virtualization]], the need to emulate is greatly reduced. For [[x86 virtualization]] the current choices are [[Intel]]'s [[Extended Page Table]] feature and [[AMD]]'s [[Rapid Virtualization Indexing]] feature.