Implementation of Page Table :
Page table is kept in main memory. Page-table base register (PTBR) points to the page table. Page-table length register (PRLR) indicates size of the page table. In this scheme every data/instruction access requires two memory accesses. One for the page table and one for the data/instruction. The two memory access problem can be solved by the use of a special fast-lookup hardware cache called associative memory or translation look-aside buffers (TLBs) . Some TLBs store address-space identifiers (ASIDs) in each TLB entry – uniquely identifies each process to provide address-space protection for that process .
- Associative memory – parallel search
- Address translation (p, d)
- If p is in associative register, get frame out
- Otherwise get frame # from page table in memory
1.Hierarchical Page Tables
Break up the logical address space into multiple page tables .A simple technique is a two-level page table . A logical address (on 32-bit machine with 1K page size) is divided into: a page number consisting of 22 bits and a page offset consisting of 10 bits. Since the page table is paged, the page number is further divided into: a 12-bit page number and a 10-bit page offset. Thus, a logical address is as follows:
2.Hashed Page Tables :
Common in address spaces > 32 bits . The virtual page number is hashed into a page table. This page table contains a chain of elements hashing to the same location. Virtual page numbers are compared in this chain searching for a match . If a match is found, the corresponding physical frame is extracted .
3. Inverted Page Table:
One entry for each real page of memory . Entry consists of the virtual address of the page stored in that real memory location, with information about the process that owns that page. Decreases memory needed to store each page table, but increases time needed to search the table when a page reference occurs . Use hash table to limit the search to one — or at most a few — page-table entries .