Explain Hashing in Operating System in detail?

Software Development
#1

When constructing the page table, hash tables are frequently used. Virtual page numbers are hashed into hash tables in hashed page tables, which use virtual addresses as their source of data. To manage address spaces larger than 32 bits, they are employed.

The linked list of items for each entry in the hash table is hashed to the same place (to avoid collisions – as we can get the same value of a hash function for different page numbers). The virtual page number is the hash value. All the components outside of the page offset make up the virtual page number.

Hash Table has the following elements:-

  • Virtual Page Number (VPN): p, q
  • Page Frame Number (PFN): r
  • Offset: d
  • Hash Function: h(x)
  • Hashed Page Table with schema (key, VPN, PFN, Pointer to next entry with key) for each entry in the table

It so happens that h(p) = same_key and h(q) = same_key. There is a hash collision. Both p and q are hashed to the same_key.

This is resolved by chaining the entry with VPN = q to the entry with VPN = p. Chaining means using the Pointer field in the entry with VPN = q to point to the entry with VPN = p.

Working of Hash Page Table

  • Operating system (OS) grabs p from the CPU and performs h(p) to get same_key.
  • OS looks up the first entry in the Hashed Page Table with key = same_key and checks p against the first entry’s VPN field. It checks p against q. This is incorrect.
  • OS uses the Pointer in the first entry to find the second entry. It knows that the second entry has the same key = same_key, because the Page Table is constructed this way. OS checks p against the second entry’s VPN field. It checks p against p. This is correct. Bam. Kill confirmed.
  • OS knows that this is the correct entry it is looking for. It grabs PFN from the second entry. It grabs r. r is the correct physical frame number that corresponds to virtual page number p.
  • OS uses r to look for the physical frame it wants in physical memory, and looks for the exact word wanted which is offset by d within frame r in physical memory