Part 1 of 7 · 1 min read
Why this page comes fourth
In this module you will
- Explain why a flat page table is too large for a process, and compute its size.
- Split an address for a two-level and a four-level table, and count the memory reads of a lookup.
- Compute the memory a sparse process needs under a multi-level table.
- Describe hashed and inverted page tables, and say when each helps.
- Explain what a huge page saves.
Page 3 translated addresses through one table with one entry for each page. For a 32-bit space this table holds a million entries, and for a 48-bit space the table would be absurdly large. Yet most processes use only a small part of their address space. This page shows the layouts that exploit this fact: tables that exist only for the parts of the address space that are used. The sources are OSTEP chapter 20, OSC chapter 9 and MOS chapter 3. The code was compiled with gcc -O0 -Wall -Wextra and run on a two-processor Linux machine.
About this example About this example
Real: The facts, definitions and algorithms on this page come from the books named in the text. No program on this page was timed.
Scripted: The worked traces use small numbers chosen so they can be followed by hand.
Not real: The page simplifies real systems. Actual kernels add more cases, limits and tuning than a short page can show.