Side table
A page table ( English page table ) is the data structure that is used for converting between virtual and physical addresses. Virtual addresses are used by processes and are an abstraction from physical memory. The process can only write and read to its own virtual memory. The conversion of the virtual address of a process is now usually done by the MMU and cannot be viewed by the process. The side tables contain the mapping between the virtual and the physical address.
Single-level page table
The address conversion with the aid of a single-level page table is carried out by interpreting the n more significant bits of a virtual address as the page number of the requested memory page and using the m less significant bits as an offset . Based on the base address of the page table, which is held in a register of the memory management unit , the page number determines that entry in the page table from which the base address of the required real memory page can be read. In addition, the page table contains status information about the memory page on the higher-order bits, which for example provide information on whether the memory page is in the RAM or whether it has been changed since the last access. The base address of the real memory page read from the page table together with the unchanged offset result in the real address.
Since the number of entries in a single-level page table depends on the size of the virtual address space and the selected page size, a problem arises if the virtual address space is too large and / or the selected page size is too small. For example, if you choose a page size of 4 kiB, the associated page table has only 16 entries with a 16-bit address space, i.e. a virtual memory of 64 kiB. For a 32-bit address space, i.e. a virtual memory of 4 GiB in size, and the same page size, an associated page table already requires over a million entries, all of which would have to be kept in memory. In order to keep the memory requirements of the page tables acceptable even for large address spaces, the concepts of the multi-level page table and the inverted page table were developed.
Multi-level page table
The address conversion with the aid of a k -step page table is done by dividing a virtual address into k * n more significant bits as page table references and m less significant bits as offset . With the k th reference in the virtual address, the base address of the page table of level k + 1 is read from the k th page table . The last stage then contains the actual reference to the real base address. The base address of the real memory page read from the last level of the page table together with the unchanged offset result in the real address.
The advantage of this approach over the single-level page table is that not all parts of the page table always have to be kept in memory.
Inverted page table
In particular, single-level, but also multi-level page tables require a lot of storage space just to store the page table in memory. The inverted page table approach eliminates this problem. An entry per virtual page is no longer created in the page table, but only one entry per real memory page. However, access to this table now requires a search process in order to find the virtual address in the entire page table and to read out the associated real address. The search in the inverted page table is often accelerated by adding a hash table .
Since there is no information about swapped out pages in the inverted page table, a "normal" page table must be used in the event of a page error.
Page fault
With every method it can of course happen that the requested virtual address is located in a memory page that is not in the main memory , but must first be loaded from the background memory into the main memory by paging ( demand paging ). The memory management unit signals this as soon as these in the status bits in the so-called Valid bit of a page table Invalid (a 0 i. D. R.) finds entry by a so-called page fault triggers (Page Fault).
Individual evidence
- ↑ a b Andrew S. Tanenbaum Modern Operating Systems . Translated by Uwe Baumgarten. 2nd, revised edition. Pearson Studium / Prentice Hall, Munich 2003, ISBN 3-8273-7019-1 .