Part 5 of 6 · 4 min read
Keeping the TLB right
Context switches, address-space tags and shootdowns
In plain words: A TLB entry is valid only for the address space that created it. Virtual page 5 of process A and virtual page 5 of process B are different pages. When the kernel switches from A to B (Level 1), the entries of A must not be used for B. There are two ways to deal with it.
- Flush. The kernel empties the TLB at every context switch. This is simple, and costly: the new process starts with an empty TLB and takes a burst of misses.
- Tags. Each entry carries an address-space identifier (ASID), a small number that names the process whose table made the entry. The processor compares the current ASID with the tag of each entry, so entries of several processes can stay in the TLB together. On x86-64 the feature is called a process-context identifier (PCID). With tags, a context switch needs no flush, and a process that returns finds some of its entries still there.
A second problem arises when a mapping changes. If the kernel changes a page table entry, for example to take a page away or to change its protection, the old translation may still be cached. The kernel must remove it with a special instruction. On a machine with several processors, other processors may also hold the old entry in their own TLBs. The kernel must then ask them to remove it: it sends an interrupt to each of the other processors, and each runs a short routine that clears the entry. This is a TLB shootdown. It is costly, because the processors must stop what they are doing for a moment, so the kernel batches changes and avoids shootdowns where it can. A program with many threads that maps and unmaps memory often (Level 2) pays this cost.
Another consequence is that the first access to a page after a change is slow, since the entry has to be loaded again. The TLB is not part of the programmer's model, but its behaviour can be seen in the timing of the program.
Address-space identifier
An address-space identifier (ASID) is a small number stored in each TLB entry that names the address space the entry belongs to, so that entries of different processes can coexist and the TLB need not be emptied at a context switch.
Example: entries tagged ASID 7 are used only while the process with ASID 7 is running.
Common mistake
A page that is in memory can still be slow to reach. "In memory" and "in the TLB" are different: a page can be present in a frame and absent from the TLB, and then the access pays for a page walk. Do not mix a TLB miss (cheap, no kernel) with a page fault (expensive, page 7).
Check yourself: 1. Why must the TLB entries of process A not be used by process B? 2. What does an ASID let the kernel avoid at a context switch? 3. What is a TLB shootdown, and why is it costly?
Words you will meet
| Word | Meaning |
|---|---|
| TLB | A small cache of recent page translations |
| Hit | The translation is in the TLB |
| Miss | The translation is not in the TLB, so the table is walked |
| Hit ratio | The share of accesses that hit |
| Effective access time | The average time of one memory access |
| TLB reach | Entries times page size |
| Locality | The tendency to reuse the same and nearby pages |
| ASID / PCID | A tag that names the address space of a TLB entry |
| TLB shootdown | Asking other processors to drop a stale entry |
Quick notes
- 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.
- The effective access time is the average time of one memory access, found by adding the time of each case multiplied by the share of accesses that fall into it.
- The TLB reach is the amount of memory whose translations the TLB can hold at one time, equal to the number of entries times the page size.
- An address-space identifier (ASID) is a small number stored in each TLB entry that names the address space the entry belongs to, so that entries of different processes can coexist.