4
$\begingroup$

I understand that we might need hierarchical paging to handle page tables with sizes greater than the size of one frame, but what is the use of Hashed Page tables then? I would understand if we were storing page-numbers and mapped frame numbers as $key-value$ pairs, because then hashing would make the process of accessing a particular $key-value$ pair much faster but can't we just store the base of the page table and add the virtual page number, go to that index of Page Table, and get the frame number anyway?

$\endgroup$
2
$\begingroup$

There are several advantages of hashed page tables over the standard flat/hierarchal page tables. One of these being size, a hashed page table will use less space in memory than using a flat or hierarchal page table. It will at most have one entry for every physical frame (worst case scenario; unlikely as many page numbers will end up having same hash value) instead of having an entry for every page (many of which will be left unused; although this problem is alleviated with the use of hierarchal page tables). Inverted page tables also have this advantage, however hashed page tables have a performance advantage over inverted tables, as the lookup is much faster in hashed page table. So a hashed page table combines the space advantage of an inverted table with the lookup advantage of a standard page table.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.