Hashed Page Table
1. Can you tell the complexity of searching a virtual address in a Hashed Page Table?
Answer:
The complexity of searching a virtual address in a Hashed Page Table is considered to be O(1) in the assumption that a good hash function and a distributed hash table.
2. Which structuring of the page table is the most memory efficient?
Answer:
Hashed Page Table is more memory efficient than any other page table structuring because it only allocates the portions that are used in the virtual address space which ultimately saves memory space.
Hashed Page Tables in Operating System
There are several common techniques for structuring page tables like Hierarchical Paging, Hashed Page Tables, and Inverted Page Tables. In this article, we will discuss the Hashed Page Table.
Hashed Page Tables are a type of data structure used by operating systems to efficiently manage memory mappings between virtual and physical memory addresses.
In Hashed Page Tables, the virtual page number in the virtual address is hashed into the hash table. They are used to handle address spaces higher than 32 bits. Each entry in the hash table has a linked list of elements hashing to the same location (to avoid collisions – as we can get the same value of a hash function for different page numbers). The hash value is the virtual page number. The Virtual Page Number is all the bits not part of the page offset.
For each element in the hash table, there are three fields
- Virtual Page Number (which is the hash value).
- Value of the mapped page frame.
- A pointer to the next element in the linked list.