5.4Page table size, multilevel and inverted tables
The idea
A single page table can be huge. Multilevel tables page the page table, and inverted tables have one entry per physical frame.
Think of it like this: A phone book split into volumes and a master index of volumes, so you only keep the volumes you use.
Why it exists
With 32-bit addresses and 4 KB pages the flat table is 4 MB per process; 64-bit addresses would make it impossible.
How it works
- Page-table size = (number of pages) × (entry size).
- Make each table one page long: entries per page = page size / entry size.
- Each level takes log₂(entries per page) bits of the page number; count levels to cover all bits.
- Inverted table: size = (number of frames) × (entry size), searched by hash.
Worked example: 32-bit address, 4 KB page, 4-byte entry
2²⁰ pages, flat table 4 MB. A page holds 1024 entries (10 bits), so 2 levels of 10 bits cover the 20 page-number bits.
Now play with it
- →Change the virtual bits to 48 and see how many levels are needed.
- →Compare with the inverted table size from physical bits.
Defaults: 32-bit addresses, 4 KB pages, 4-byte entries → 2²⁰ pages, a 4 MB table, and 1024 entries per page so 2 levels of 10 bits each.
Check yourself
Entries per page = 512 and the page number has 27 bits. The minimum number of levels is
Exam notes (the dense version)
Page table size = number of pages × entry size = (virtual size ÷ page size) × entry size. A single table can be huge, so a multilevel table pages the page table itself: the page number is split into fields, one per level, and each table is ideally one page long (entries per page = page size ÷ entry size). Only the levels that are used need to exist. An inverted page table has one entry per physical frame (size = frames × entry size) and is searched by hashing (pid, page).
Previous year questions: Memory Management (11)
PYQs are grouped by topic, so this is the full set for Memory Management; try the ones that match this subtopic. Open all 11 on the topic page.