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?
- Inverted Page Table is common on 64 bit machines- 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 Tables-the Picture
No comments