CSE Roadmap

Core tier · about 5 hours · 6 parts

Part 1 of 6 · 1 min read

Why this page comes fifth

In this module you will

  • Explain what a TLB holds, and what happens on a hit and on a miss.
  • Compute the effective access time for a given hit ratio, with one or several table levels.
  • Compute the reach of a TLB, and explain why locality gives high hit ratios.
  • Read a measured curve of access time against the number of pages touched.
  • Explain what a context switch and a change of mapping do to the TLB.

Pages 3 and 4 made translation exact, and showed its cost: one extra memory read per table level on every access. At four levels, that would make a program about five times slower. Real programs do not run five times slower, because a small, fast cache keeps recent translations. This page explains the cache, gives the formula that tells how well it works, and measures it on a real machine. The sources are OSTEP chapter 19, OSC chapter 9 and MOS chapter 3. The test program was compiled with gcc -O2 -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: Numbers marked "made up to show the idea" were chosen for the examples.

Not real: The page simplifies real systems. Actual kernels add more cases, limits and tuning than a short page can show.