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.)
No comments:
Post a Comment