Page in Operating System

Multi-level page table gets too big

- Multi-level page table works for 32 bit memory

- Doesn't work for 64 bit memory

- 264 bytes and 4 KB pages => 252 entries in page table

- If each entry is 8 bytes => 30 million GB or 30PB for page table

- Need a new solution

Inverted Page Table

- Keep one entry per (real) page frame in the "inverted" table

- Entries keep track of (process, virtual page) associated with page frame.

- Need to find frame associated with (n,p) for each memory reference process n, virtual page number p.

Need to search inverted table efficiently

- Search page frames on every memory reference 
- How to do this efficiently?

• Keep heavily used frames in TLB (Translation is very fact)
• If miss, then can used and associative search to find virtual page to frame mapping
• Use a hash table hashed on virtual address. Use linked list. (If hash table entries equal page frame number, average chain will just have just one entry)

- Inverted Page Table is common on 64 bit machines

Inverted Page Tables-the Picture