Virtual Memory - Page Table Size

Formulae

$\begin{equation*} \text{Number of Page Table Entries} = \frac{2^{\text{Virtual Address Bits}}}{\text{Size of Page}} \end{equation*}$

$\begin{equation*} \text{Size of Page Table} = \text{Number of Page Table Entries} \times \text{Size per Page Table Entry} \end{equation*}$

Large Size?

The following arguments favor a larger page size.

The size of the page table is inversely proportional to the page size. memory (or other resources used for the memory map) can therefore be saved by making the pages bigger.

A larger page size can allow larger caches with fast cache hit times.

Transferring larger pages to or from secondary storage, possibly over a network, is more efficient than transferring smaller pages.

The number of TLB entries is restricted, so a larger page size means that more memory can be mapped efficiently, thereby reducing the number of TLB misses.

Small Size?

The main motivation for a smaller page size is conserving storage. A small page size will result in less wasted storage when a contiguous region of virtual memory is not equal in size to a multiple of the page size. The term for this unused memory in a page is called internal fragmentation.

Here are a few techniques to reduce the Page Table Size

Limit Register

Keep a limit register that restricts the size of the page table for a given process. If the virtual page number becomes larger than the contents of the limit register, entries must be added to the page table.

Dual Page Table

Divide the page table and let it grow from the highest address down, as well as from the lowest address up. This means that there will be two separate page tables and two separate limits. The use of two page tables breaks the address space into two segments. This scheme does not work well when the address space is used in a sparse fashion rather than as a contiguous set of virtual addresses.

Inverted Page Table

Apply a hashing function to the virtual address so that the page table need be only the size of the number of physical pages in main memory. Such a structure is called an inverted page table. The lookup process is slightly more complex. An inverted page table would require extra bytes per entry to save the next virtual address.

Multi-Level Page Table

This scheme consist of two or more levels of page tables in a hierarchical manner. The entries of the level 1 page table are pointers to a level 2 page table and entries of the level 2 page tables are pointers to a level 3 page table and so on. The entries of the last level page table are stores actual frame information. Level 1 contains a single page table and address of that table is stored in the PTBR (Page Table Base Register).

Reference to PTE in level 1 page table = PTBR value + Level 1 offset present in virtual address.
Reference to PTE in level 2 page table = Base address (present in Level 1 PTE) + Level 2 offset (present in VA).
Reference to PTE in level 3 page table= Base address (present in Level 2 PTE) + Level 3 offset (present in VA).
Actual page frame address = PTE (present in level 3).

Virtual Page Table

Allow the page tables to be paged by allowing the page tables to reside in the virtual address space. This scheme requires placing all the page tables in the address space of the operating system and placing at least some of the page tables for the operating system in a portion of main memory that is physically addressed and is always present and thus never on disk.

The Beard Sage

Virtual Memory – Page Table Size