Chapter 18's linear page table has one entry for every page in the address space, whether or not it's used. This tool follows Chapter 20, Paging: Smaller Tables, through ways to shrink it: bigger pages, combining paging with segmentation, multi-level page tables, and inverted page tables.
We usually have one linear page table for every process in the system. Assume a 32-bit address space with 4KB pages and a 4-byte page-table entry.
One entry per page in the whole address space, no matter how much of it the process is using.
Page tables are too big and thus consume too much memory.
Page tables are too big and consume too much memory — so try 16KB pages instead of 4KB.
Bigger pages mean fewer virtual pages, so the page table has fewer rows.
Big pages lead to internal fragmentation: a page holding a little bit of data still burns a whole page's worth of physical memory.
However many bits it has, a flat page table still needs one entry for every page in the address space — including the huge gap between the heap and the stack that a process never touches. Full of invalid entries, most of the table is wasted whether pages are 4KB or 16KB.
| Page | PFN | valid | prot | present | dirty |
|---|
Each process has three page tables, one for each segment. While the process runs, the base register for each segment holds the physical address of a linear page table for just that segment — so an entirely unused segment needs no table at all.
| SN value | Content |
|---|---|
| 00 | unused segment |
| 01 | code |
| 10 | heap |
| 11 | stack |
flat table (Chapter 18) = 2^32 / 2^12 × 4 B = 4 MB each segment's own table = 2^18 × 4 B = 1 MB, at most segment 00 (unused) = 0 B — nothing to allocate
A used segment's table is still sized to that whole segment, so a small heap still reserves a full 1MB table. Paged segmentation only pays off when several segments genuinely go unused — it doesn't fix sparseness inside one big segment. Multi-level page tables fix that, later in this chapter.
To see the idea work end to end, scale everything down: a 10-bit virtual address (1024 bytes), split into a 2-bit segment number, a 4-bit VPN and a 4-bit offset — 16-byte pages, up to 16 pages per segment.
Paged segmentation already skips the table for a whole unused segment. A multi-level table goes further: it adds one more layer of indirection — a page directory — so that if just a range of VPNs within a region is unused, the OS never has to allocate the page of PTEs that would have covered it. The trade-off is one extra memory reference on every translation, even a successful one.
| Parameter | Detail |
|---|---|
| Address space | 16 KB |
| Page size | 64 bytes |
| Virtual address | 14 bits |
| VPN | 8 bits |
| Offset | 6 bits |
| # of PTEs | 28 (256) |
| VPN range | Region |
|---|---|
| 0000 0000 – 0000 0001 | code |
| 0000 0010 – 0000 0011 | (free) |
| 0000 0100 – 0000 0101 | heap |
| 0000 0110 – 1111 1101 | (free) |
| 1111 1110 – 1111 1111 | stack |
14-bit Virtual address
The top 4 bits of the VPN (13–10) pick one of 16 page-directory entries; the next 4 bits (9–6) then pick one of 16 entries inside whichever page of PTEs that entry points to. The low 6 bits (5–0) are the offset within the 64-byte page and never get translated.
Only 2 of the 16 page-directory entries are valid, so only 2 pages of PTEs exist at all — one at PFN 100 covering VPNs 0000 xxxx (code and heap), the other at PFN 101 covering VPNs 1111 xxxx (the stack). Every other 4-bit prefix needs nothing.
Decimal or hex (0x…), from 0 to 16383.
Every table so far has one entry per virtual page, so its size grows with the address space — and every process gets its own copy. An inverted page table flips this around: there's a single table, shared by all processes, with exactly one entry per physical frame. Since physical memory is normally far smaller than the sum of every process's virtual address space, the table stays small no matter how many processes are running or how big their address spaces are.
The trade-off: each entry must now record which process and which virtual page currently live in that frame, and the hardware can no longer index the table directly by VPN — it has to search for the entry whose (PID, VPN) matches. A real implementation doesn't scan the table one frame at a time like the demo below; it hashes (PID, VPN) into a hash table so a lookup still costs about one comparison, not one per physical frame.
Two processes, P0 and P1, each with a 1KB virtual address space of their own, share these same 8 physical frames. The table has one row per frame — regardless of which process, or how many processes, are using it.
| Parameter | Detail |
|---|---|
| Physical memory | 512 B |
| Frame / page size | 64 B |
| # of physical frames | 23 (8) |
| Per-process virtual address | 10 bits (1 KB) |
| VPN | 4 bits |
| Offset | 6 bits |
| Frame (PFN) | PID | VPN | Prot |
|---|
Pick a process and an address in its address space (decimal or hex, 0–1023). The table is searched frame by frame for a matching (PID, VPN) — the frame it's found in is the physical frame number.