CREATE OWN LIBRARY

Hashed Page Table with example 

We use another concept when the address space is larger than 32 bits, which is the hash page table. This page table has a hash value being the virtual page number. 

And each entry in the hash table contains a linked list of elements that hash to the same location (to handle collisions). 

Each element consists of three fields: 

(1) The virtual page number, 

(2) The value of the mapped page frame, and 

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

Address translation process for hash table:

1. Page number in Logical Address (generated by CPU) is hashed into the hash table. 

2. The page number of the logical address is compared with the first element (field 1: virtual page number) in the linked list. 

If both page numbers are matched then retrieve the corresponding frame number (field 2 in the linked list) to from the physical address. 

If both page numbers do not match then subsequent entries in the linked list searched for a matching virtual page number.

                            Fig: Hash Page Table                               

Clustered Page Tables

A variation of the hash page table is the cluster page table. This concept is useful when 64 bit address space has been proposed.

The cluster page table is similar to hashed pages except that each entry in the cluster page table refers to several pages rather than a single page like the hash page table.

Therefore, a single page-table entry can store the mappings for multiple physical-page frames. 

Clustered page tables are particularly useful for sparse address spaces, where memory references are noncontiguous and scattered throughout the address space.

Question 1: 

A paging system where the linked list is used to maintain the frame number and each element consist of three fields: (1) the virtual page number, (2) the value of the mapped page frame, and (3) a pointer to the next element in the linked list.

This concept of page table is called

(A) Single page table   (B) Multi-level page table  (C) Hash page table  (D) Listed list page table.

Solution:

Option (C) is correct because this is the concept of the hash page table.

Question 2: 

A computer system, using a paging system where memory references are non-contiguous and scattered throughout the address space which is called sparse address space, and a single page table entry can store the mapping for multiple physical page frames.

This concept of paging is called

(A) Single level paging     

(B) Hash page table  

(C) Multi-level paging  

(D) Cluster page table 

Solution:

Option (D) is correct because this is the concept of the Cluster page table.