Structure of the Page Table

Structure of the Page Table

1. Hierarchical Paging

Most modern computer systems support logical address spaces of 2^32 to 2^64. With a 2^32 address space and 4K ( 2^12 ) page sizes, this leave 2^20 entries in the page table. At 4 bytes per entry, this amount to a 4 MB page table, this is too large to reasonably keep in contiguous memory.

One simple solution to this problem is to divide the page table into smaller pieces. One option is to use a two-level paging system in which page table itself is paged.

For example, a system with 32-bit logical address space and page size of 4kb. A logical address is divided into a page number consisting of 20 bits and a page offset consisting of 12 bits.

The first identifies an entry in the outer page table, which identifies where in memory to find one page of an inner page table. The second 10 bits finds a specific entry in that inner page table, which in turn identifies a particular frame in physical memory.

Because address translation works from the outer page table inward, this scheme is also known as a forward-mapped page table. With a 64-bit logical address space and 4K pages, there are 52 bits worth of page numbers, which is still too many even for two-level paging. One could increase the paging level, but with 10-bit page tables it would take 7 levels of indirection, which would be prohibitively slow memory access. So some other approach must be used.

2. Hashed Page Tables

A common approach for handling address spaces larger than 32-bits is to use a hashed page table, with the hash value being the virtual page number. Each entry in the hash table contains a linked list of elements that hash to the same location. Each element consists of three fields: 1. the virtual page number, 2. the value of the mapped page frame, and 3. a pointer to next element in the linked list.

The virtual page number in the virtual address is hashed into the hash table. The virtual page number is compared with field1 in the first element in the linked list. If there is a match, the corresponding page frame(field 2) is used to form the desired physical address. If there is no match, subsequent entries in the linked list are searched for matching virtual page number.

3. Inverted Page Tables

Another approach is to use an inverted page table. Instead of a table listing all of the pages for a particular process, an inverted page table lists all of the pages currently loaded in memory, for all processes. ( I.e. there is one entry per frame instead of one entry per page. )

Access to an inverted page table can be slow, as it may be necessary to search the entire table in order to find the desired page (or to discover that it is not there. ) Hashing the table can help speedup the search process.

Inverted page tables prohibit the normal method of implementing shared memory, which is to map multiple logical pages to a common physical frame. (Because each frame is now mapped to one and only one process.)