Explain Hashed page tables in operating system I have a difficult time understanding hashed page tables used in virtual memory management. Here is picture of the slide that I am referring to:





I understand that p is hashed and then the hash is checked in the page table for a match. What is elements referring to here? Is it the page table entry? What does chain mean and where is virtual page number located?

Can someobody help me understand the flow chart? Thanks
Definitions (What's with the symbols?)

In the diagram, we have these guys:


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 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 to use the Pointer field in the entry with VPN = q to point to the entry with VPN = p.

Workflow (How the system works)

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 seond 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. OS grabs the contents of the word and we're done. 

Source: Dave Johnson's COMP 421 (Rice University CS Dept)