HASHED PAGE TABLE

·        Common approach for handling address spaces larger than 32 bits.

·        Hash page table with hash value being the virtual page number is used.

·        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

3.     A pointer to the next element in the linked list

Working:

·        The virtual page number in the virtual address is hashed into the hash table.

·        The virtual page number is compared to field (a) in the first element in the linked list.

·        If there is a match, the corresponding page frame (field (b)) is used to form the desired physical address.

·        If there is no match, subsequent entries in the linked list are searched for a matching virtual page number.

Clustered page table:

·        Similar to hashed page tables except that each entry in the hash table refers to several pages rather than a single page.

·        A single page table entry can store the mappings for multiple physical page frames.

·        These tables are particularly useful for sparse address spaces where memory references are non-contiguous and scattered throughout the address space.