page table structures
Summary
Page table structures
| Method | Core Idea | Lookup Steps | Advantages | Disadvantages |
|---|---|---|---|---|
| direct paging | single-level page table indexed by virtual page number | 1 lookup | - fast lookup | - wastes memory for large address spaces |
| 2-level paging | page table split into smaller sub tables | 2 lookups (outer → inner → frame) | - saves memory, less overhead when not all pages are used | - slower without TLB, more complex |
| inverted page table | one entry per physical frame | search (or hash) over entries | -1 table for all processes - huge memory savings, good for very large virtual spaces | - slower lookup, needs hashing, harder to implement |
Concept
- modern logical memory space is massive -> huge number of pages
- each page must have an entry in the page table -> hueg page table
- high overhead
- page table might itself be fragmented
Direct paging
- per process
- keep all entries in a single table
2-level paging
- per process
- page table is broken up into smaller sub-tables
- generally, the sub-tables are the size of a page
Inverted page table
- consolidated over all processes
- entries are indexed by frame number instead
- search for the
PIDand page number in the inverted page table
Application
Multi-level paging