Operating System - Hashed Page Table in Operating Systems

Definition:

A Hashed Page Table is a page table structure used primarily in systems with large address spaces (like 64-bit architectures). It uses a hash function to map virtual page numbers to page table entries, offering a space-efficient solution for sparse address spaces.

Key Idea:

Instead of storing page table entries in a large linear array, hashed page tables use a hash table to directly look up the page table entry using a hash of the virtual page number.

Structure:

Each entry in the hash table is a bucket (often a linked list or chain) that contains:

  • Virtual Page Number (VPN)

  • Frame Number (Physical Page Number)

  • Pointer to Next Entry (for handling collisions)

How It Works (Step-by-Step):

  1. CPU generates a virtual address.

  2. The virtual page number (VPN) is extracted.

  3. A hash function is applied to the VPN to find the index in the hash table.

  4. In the bucket at that index, entries are searched linearly to find a matching VPN.

  5. If found, the corresponding frame number is used to construct the physical address.

Hash Table Data Structure - GeeksforGeeks

Example:

Assume:

  • VPN = 0x1A2

  • Hash(VPN) = 5 → Go to bucket 5

  • Bucket 5 contains:
    [VPN: 0x1A2 → PFN: 0x0B4]

So:

  • Physical Frame Number = 0x0B4

  • Final physical address = 0x0B4 + offset

Advantages:

  • Efficient for sparse address spaces (e.g., in 64-bit systems).

  • Requires less memory than multi-level page tables in some cases.

  • Simple structure using standard hash techniques.

Disadvantages:

  • Collisions in hash table require chaining or linear search in buckets.

  • Slightly slower than indexed page tables due to hashing and searching.

  • Requires a good hash function to reduce collisions.