Page table

Page tables are parts of processes which are used for transformation of virtual to physical page frames. The optimal page size is a compromise between frequency of page turns and size of the table. In practice, a size between 2 and 32 kbytes is common.

Single-level page table

The address conversion by means of a single-stage is done by interpretation of the page table of the n high order bits of a virtual address page number as the requested page of memory, and using the m least significant bits as an offset. The page number determines starting from the base address of the page table, which is held in a register of the memory management unit, those entry in the page table from which the base address of the required real memory page is read. In addition, the page includes tables on high-order bits status information about the memory page, for example, indicate whether the memory page is in RAM or whether it has been modified since the last access. Read out from the page table base address in real memory page, together with the unchanged offset give the real address.

Since the number of entries in a single-stage page table depends on the size of the virtual address space and the chosen page size, a problem arises when the virtual address space is too large and / or the selected page size is too small. If one chooses, for example, a page size of 4KB, then has the corresponding page table for a 16 - bit address space, ie, a virtual memory of 64KB, only 16 entries. For a 32- bit address space, ie, a virtual memory of 4GB size, and the same page size, a corresponding page table requires more than a million entries, all of which would have to be kept in memory. Thus, in order to keep the memory requirements of the page tables for large address spaces acceptable, the concepts of the multi-level page table and the inverted page table have been developed.

Multi-level page table

The address conversion by means of a k- level page table is achieved by dividing a virtual address to k * n higher-order bits as the page table, and references m lower-order bits as an offset. With the k-th reference in the virtual address, the base address of the page table of the level k 1 is read from the k-th page table. The final stage then contains the actual reference to the real base address. The read-out from the last stage of the page table base address in real memory page, together with the unchanged offset give the real address.

The advantage of this approach over the single-level page table is that not all parts of the page table must always be kept in memory.

Inverted page table

In particular, single-stage, but also multi-level page tables require a lot of memory to store only the page table in memory. With the approach of the inverted page table to eliminate this problem. It is no longer an entry for each virtual page created in the page table, but only one entry per each real page of memory. However, access to this table now requires a search process to find the virtual address to the entire page table and read the corresponding real address. Often searching the inverted page table is sped up by Upstream a hash table.

Since there are no information on pages swapped in the inverted page table, with a page fault recourse to a "normal" side table is necessary.

Page fault

In each method, it can happen, of course, that the requested virtual address is in a memory page is not in-memory, but only needs to be loaded into memory by paging from the background storage (English: demand paging ). The memory management unit signals this as soon as it finds a invalid entry in the status of a page table by triggering a so-called page fault ( page fault ).