CSE Roadmap

Core tier · about 5 hours · 6 parts

Part 2 of 6 · 2 min read

The TLB

Think of it this way. A person who often phones the same ten numbers does not look them up in the big directory each time. They keep the ten on a note by the phone, and look in the directory only for a new number. The translation lookaside buffer (TLB) is that note. It is a small, very fast memory inside the processor. Each entry holds a virtual page number and the frame number it maps to, with the protection bits of the page. The analogy stops in one place: the person chooses what goes on the note, while the hardware fills the TLB by itself.

The use of the TLB on each memory access:

  1. The hardware takes the page number of the virtual address and looks in the TLB for it. All entries are searched at the same time.
  2. Hit: the entry is found. The frame number is used at once, with no read of the page table. The protection bits are checked too.
  3. Miss: no entry. The hardware walks the page table (page 4), finds the frame number, puts a new entry into the TLB (and removes an old one if the TLB is full), and then continues.

In plain words: On x86-64, the walk is done by the hardware. Some other processors leave it to the operating system: a miss causes a trap, and kernel code fills the entry. OSTEP describes both styles.

The TLB works because of locality: programs tend to use the same pages again and again, and nearby pages in a row. A loop that sums an array of 4-byte integers reads 1,024 integers from one 4 KiB page before it moves to the next. The first read of a page misses, and the next 1,023 reads hit. The miss ratio of that loop is 1 in 1,024, which is about 0.1%.

Translation lookaside buffer

The translation lookaside buffer (TLB) is a small, fast cache in the processor that holds recent translations from virtual page numbers to frame numbers, with the page's protection bits, so that most memory accesses need no page table read.

Example: a loop over an array of 4-byte integers takes one TLB miss for each 1,024 reads, and hits on the rest.

Check yourself: 1. What does a TLB entry hold? 2. What does the hardware do on a TLB miss? 3. Why does a loop over an array give a high hit ratio?