CSE Roadmap

Core tier · about 5 hours · 7 parts

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.