COMP 3150Operating Systems

Module 3 · Unit 9 · Lesson 3 of 7

The Translation Lookaside Buffer

The small hardware cache that makes paging practical. Every memory access requires a translation, and a translation requires walking the page table — four memory accesses on x86-64. Without a way to skip that walk, every load and store would cost five times the raw memory latency. The translation lookaside buffer (TLB) caches recently used translations, so the vast majority of accesses bypass the walk entirely. This lesson presents the TLB in detail: its structure, its performance, its interaction with the caches, and the mechanisms that keep it correct across context switches and multiprocessors.

01 Introduction

Lesson 9.1 introduced paging and the two-memory-access problem: because the page table is stored in physical memory, every logical access requires one access to the page table (to get the frame number) and one access to the data (to read or write the actual byte). Lesson 9.2 presented the multi-level page table, the structure that solves the page table's size problem, and showed that the problem is worse than it first appears: on x86-64, the page-table walk requires four memory accesses, so a single load or store instruction would, in the worst case, require five memory accesses.

This is unacceptable. On a modern processor, a main-memory access takes about 80 nanoseconds — hundreds of CPU cycles. If every access required five memory accesses, the processor would spend the overwhelming majority of its time waiting on memory, and the effective performance would be a fifth of what the hardware could deliver. The whole point of the memory hierarchy (Lesson 8.1) is to hide latency, and paging threatens to add a new kind of latency that the hierarchy does not hide.

The solution is the translation lookaside buffer (TLB), a small, fast, hardware-managed cache of recently used translations. The TLB stores the final result of a page-table walk — the mapping from a page number to a frame number — so that a subsequent access to the same page bypasses the walk entirely. Because programs have locality of reference (Lesson 8.1), the number of distinct pages a program touches in a short time is small, and the TLB's hit rate is very high — typically 99 percent or better. The average cost of translation is therefore much closer to a single memory access than to five.

The TLB is a small structure, but it is one of the most important components of a modern memory system. It sits at the boundary between the hardware and the software, and its design has a profound effect on the performance of every program. This lesson presents it in detail. It describes the TLB's structure and the role of associativity, defines the TLB hit rate and computes the effective access time, and presents the role of address-space identifiers in avoiding TLB flushes on context switches. It presents the TLB's replacement policy, its interaction with the caches (the physically-indexed versus virtually-indexed distinction), the problem of TLB shootdown in multiprocessors, the multi-level TLB hierarchies of modern processors, and the effect of huge pages on TLB reach. It closes with a discussion of the practical consequences: how to measure the TLB's behaviour, and what programming practices improve or degrade it.

Prerequisites

This lesson builds directly on Lessons 9.1 and 9.2. The paging model, the two-memory-access problem, the multi-level page table, and the page-table entry fields are all assumed. The memory hierarchy from Lesson 8.1 — in particular the role of the L1, L2, and L3 caches and the concept of locality — is used throughout. No prior knowledge of the TLB, of address-space identifiers, or of TLB shootdown is assumed; all are introduced here. The discussion of cache indexing in section 4.6 assumes familiarity with the basic structure of a cache, but the treatment is self-contained.

02 Learning objectives

By the end of this lesson you will be able to

  • Describe the TLB, its structure, and the role of associativity in its design.
  • Define the TLB hit rate and compute the effective access time of a memory reference.
  • Explain how address-space identifiers avoid TLB flushes on context switches.
  • Describe the TLB's replacement policies and its interaction with the caches.
  • Explain TLB shootdown, multi-level TLBs, and the effect of huge pages on TLB reach.

This lesson contributes to U9.3 and U9.4, and to course learning outcomes CLO1, CLO4, and CLO6.

03 Required reading

  • Operating System Concepts — Chapter 9, Section 9.4, through the discussion of the TLB, and Chapter 10, Sections 10.1–10.3. The standard treatment of the TLB, its hit rate, and its role in the effective access time calculation.
  • OSTEP — Chapter 19, Paging: Faster Translations (TLBs). The clearest available treatment of the TLB, its structure, the effective access time calculation, and its interaction with the page table. OSTEP's worked examples are the basis for the worked example in this lesson.
  • Tanenbaum & Bos — Modern Operating Systems, Chapter 3, Section 3.3, through the subsection on the TLB. The treatment of the TLB's structure, the role of ASIDs, and the TLB's behaviour across context switches.
  • Silberschatz et al. — Chapter 9, Section 9.4. Read the discussion of the effective access time and the worked examples of the hit-ratio computation.
  • Bryant, R. E., & O'Hallaron, D. R. — Computer Systems: A Programmer's Perspective, 3rd ed., Chapter 9, Virtual Memory, sections 9.6–9.8. The TLB presented from the programmer's perspective, including the interaction between the TLB and the caches.
  • Jacob, B., & Mudge, T. — Virtual Memory: Issues of Implementation and Performance. IEEE Computer, 1998. A survey of virtual memory implementations that includes a detailed treatment of the TLB, its associativity, and its interaction with the caches.
  • Intel Corporation. — Intel 64 and IA-32 Architectures Software Developer's Manual, Volume 3: System Programming Guide, Chapter 4, Paging, including the sections on the TLB, the TLB's management by the operating system, and the TLB-related instructions (INVLPG, INVPCID).
  • Linux man pages: man 1 perf-stat (for the dTLB and iTLB counters), man 2 madvise (for the MADV_HUGEPAGE flag), man 2 mmap (for MAP_HUGETLB), man 5 proc (for /proc/<pid>/status and the VmPTE field).

Reading strategy

Read the OSTEP chapter first. Its staged presentation — introducing the TLB, then the hit-rate calculation, then ASIDs, then the interaction with the caches — is the clearest available account, and its worked examples are the basis for the worked example in this lesson. Then read the Silberschatz section for the formal definition of effective access time. The Jacob and Mudge paper is the definitive survey of the trade-offs involved in TLB design; read it if you want to understand why TLBs have the structure they do. The Intel manual's chapter on paging is the authoritative reference for the x86-64 TLB specifically; the sections on the TLB's management and the invalidation instructions are worth reading carefully, because TLB invalidation is a common source of subtle bugs in kernel code.

04 Core content

4.1 Why the TLB exists

The multi-level page table of Lesson 9.2 has a beautiful property: it allows a large address space to be mapped with a small amount of memory, by allocating tables only for the regions the process actually uses. Its cost is the page-table walk: on x86-64, four memory accesses to fetch the four levels of the page table, plus one more to fetch the actual data. A single load or store would, in the worst case, cost five memory accesses — a performance disaster.

The translation lookaside buffer (TLB) is the mechanism that hides the walk's cost. The TLB is a small, fast, hardware-managed cache that stores recently used translations. Each entry in the TLB contains:

  • A key — typically the page number of a virtual address, possibly combined with an address-space identifier (section 4.4).
  • A value — the frame number that the page maps to, together with the protection bits (read, write, execute) and the other control bits from the page-table entry.

When the MMU translates a logical address, it first checks the TLB. If an entry matches the page number (a TLB hit), the MMU obtains the frame number directly from the TLB, without any memory access to the page table. The physical address is computed by concatenating the frame number with the page offset, and the data access proceeds. If no entry matches (a TLB miss), the MMU performs the full page-table walk, and when the walk completes, it inserts the resulting translation into the TLB for future use.

The TLB is effective because programs have locality of reference. A program that is executing a loop, traversing an array, or following a linked list repeatedly accesses a small number of pages. Once those pages' translations are in the TLB, the loop's accesses hit the TLB and bypass the walk. The TLB's hit rate is therefore very high — typically 99 percent or better on typical workloads — and the average cost of a memory access is close to the cost of a single access to memory.

The TLB in the address-translation path A diagram showing the role of the TLB in address translation. The CPU produces a logical address. The MMU first checks the TLB: if there is a hit, the frame number is obtained directly from the TLB, and the data access proceeds. If there is a miss, the MMU performs the full page-table walk (four memory accesses on x86-64), inserts the result into the TLB, and then performs the data access. The diagram compares the number of memory accesses on a TLB hit (one — the data) versus a TLB miss (five — four page-table levels plus the data). THE TLB IN THE ADDRESS-TRANSLATION PATH CPU logical address: (page p, offset d) p TLB cache of recent translations typically 32 – 2048 entries key: page number (+ ASID) value: frame number + protection hit Data access physical address = frame f, offset d miss Page-table walk four memory accesses on x86-64 1. read PML4 entry 2. read PDPT entry 3. read PD entry 4. read PT entry → frame the walk yields the frame number insert translation frame f The cost of a memory reference On a TLB hit: one memory access (the data itself). The page-table walk is bypassed entirely. On a TLB miss: five memory accesses (four for the walk, one for the data). The walk dominates the cost.
Figure 9.3 — The TLB in the address-translation path. On a TLB hit, the frame number is obtained directly from the TLB, and only the data access is performed. On a TLB miss, the MMU performs the full page-table walk — four memory accesses on x86-64 — inserts the result into the TLB, and then performs the data access. The TLB's purpose is to make the hit case the common one, and because of locality of reference, it succeeds.

4.2 TLB structure and associativity

The TLB is a cache, and like any cache it can be organised in several ways. The choice of organisation determines its speed, its size, and its conflict behaviour.

Fully associative
Every entry in the TLB is searched in parallel. A translation is present if any entry matches its page number. This is the most flexible organisation, because there is no possibility of conflict misses — a translation is either present or it is not, and the choice of which entries to keep is entirely a matter of the replacement policy. Its cost is the comparators: a fully associative TLB with 64 entries requires 64 comparators, each comparing the page number of the incoming address with the corresponding entry's key, all in parallel. This is expensive in area and in energy, and it limits the size of a fully associative TLB to a few dozen entries.
Set associative
The TLB is divided into sets, and each set holds a small number of entries (typically 2, 4, or 8). The page number is hashed to select a set, and the entries within the selected set are searched in parallel. A 4-way set-associative TLB with 64 entries has 16 sets of 4 entries each, and requires only 4 comparators — one per way. This is much cheaper than a fully associative TLB of the same size, at the cost of conflict misses: two page numbers that hash to the same set will compete for the set's 4 ways, and one may be evicted even though other sets have free space.
Direct mapped
The TLB has one entry per set, so the page number selects a single slot. There is no choice about placement, and no search: the TLB is a simple array indexed by the page number. This is the cheapest organisation and the fastest, but it has the highest conflict-miss rate, because two page numbers that hash to the same slot will evict each other on every access. Direct-mapped TLBs are rare in modern processors; set-associative TLBs are the standard.

In practice, modern TLBs use a variety of organisations at different levels. The L1 TLB, which is the smallest and fastest, is typically fully associative or 4-way set associative with 32 to 64 entries. The L2 TLB, which is larger and slower, is typically 4-way or 8-way set associative with 512 to 2048 entries. The choice of associativity reflects the trade-off between speed and conflict-miss rate: the L1 TLB must be fast, so it is small and simple; the L2 TLB can afford more comparators and more complexity, so it is larger.

The TLB's entries are accessed by the MMU on every memory access, in parallel with the cache lookup (in some designs) or before it (in others). The TLB's speed is therefore critical: an access that hits in the L1 TLB adds no measurable latency to the memory access, whereas an access that misses in the TLB triggers the page-table walk, which costs tens of cycles even when the page-table entries are themselves cached in L1 or L2.

4.3 TLB hits, misses, and effective access time

The performance of the TLB is characterised by its hit rate — the fraction of memory accesses for which the required translation is present in the TLB. The hit rate depends on the workload's locality and on the TLB's size: a program whose working set (Lesson 8.1) fits in the TLB's reach will have a hit rate near 100 percent, while a program whose working set exceeds the TLB's reach will have a lower hit rate.

The cost of a TLB hit and the cost of a TLB miss differ substantially. On a hit, the translation is performed by the TLB in parallel with the rest of the address-generation pipeline, so the cost is essentially the cost of the data access itself. On a miss, the MMU must perform the page-table walk — four memory accesses on x86-64, though some of those may themselves be cached — and then perform the data access. The effective access time (EAT) of a memory reference is therefore: 

EAT = h × t_hit + (1 − h) × t_miss

where h is the hit rate, t_hit is the time for a TLB hit, and t_miss is the time for a TLB miss. Because the TLB lookup happens before the data access in both cases, the difference between t_hit and t_miss is the cost of the page-table walk.

A concrete example makes the trade-off clear. Suppose a TLB hit takes 1 ns (essentially the cost of the data access itself, plus a small overhead for the TLB lookup), and a TLB miss takes 21 ns (1 ns for the TLB lookup, plus 20 ns for the four-level page-table walk, plus the data access). With a 99 percent hit rate, the effective access time is: 

EAT = 0.99 × 1 + 0.01 × 21
    = 0.99 + 0.21
    = 1.20 ns

With a 95 percent hit rate, the effective access time is: 

EAT = 0.95 × 1 + 0.05 × 21
    = 0.95 + 1.05
    = 2.00 ns

The difference between a 99 percent and a 95 percent hit rate is a factor of nearly two in effective access time, even though the difference in hit rate is only four percentage points. This is the same sensitivity we saw in Lesson 8.1 for caches: because the miss cost is so much higher than the hit cost, the hit rate's effect on the average is disproportionate. A program that just fits in the TLB's reach and a program that just exceeds it can differ by a factor of two in performance, purely because of the TLB's behaviour.

Hit rates in practice

On typical workloads, L1 TLB hit rates are above 99 percent, and the L2 TLB captures most of the misses of the L1. The combined hit rate — the fraction of accesses that hit in either the L1 or L2 TLB — is often above 99.9 percent. On workloads with poor locality — pointer chasing through a large graph, hash table probes with many collisions, machine-learning training on tensors larger than the TLB's reach — the hit rate can fall to 90 percent or lower, and the TLB becomes the dominant performance bottleneck.

4.4 Address-space identifiers and context switches

The TLB's entries are keyed by page number, but the meaning of a page number depends on the process: page 5 of process A and page 5 of process B are different pages, mapped to different frames. When the operating system switches from process A to process B, the TLB's entries for A's pages are no longer valid — they refer to A's address space, not B's — and the TLB must be flushed, or its entries invalidated.

Flushing the TLB on every context switch is expensive. If the TLB holds 64 entries, and a context switch costs 64 invalidations, the cost is small in absolute terms — each invalidation is a handful of cycles — but the effect on performance is large: after a flush, the TLB is empty, and the new process's first accesses all miss, requiring the full page-table walk. The process must rebuild its TLB entries from scratch, and the initial phase of its execution runs at the miss cost until the TLB is warm.

The standard solution is the address-space identifier (ASID), also called the process-context identifier (PCID) on x86-64. An ASID is a small integer that identifies the current address space. Each TLB entry includes the ASID alongside the page number, and a TLB lookup matches only if both the ASID and the page number match. When the operating system switches to a new process, it assigns a new ASID (or reuses an old one), and the TLB's entries for the previous process remain in the TLB but are simply not matched. No flush is required.

The ASID mechanism has one subtlety: the supply of ASIDs is finite (typically 8 to 16 bits, so 256 to 65,536 values), and a system with more processes than ASIDs must eventually reuse them. When an ASID is reused, the TLB entries from the previous use of that ASID are stale and must be invalidated. The operating system therefore maintains a policy for ASID allocation and reuse — for example, keeping the ASIDs of recently used processes and evicting the ones that have been idle longest — and the cost of a TLB flush is paid only when an ASID is reused.

The ASID mechanism is one of the reasons a context switch is not as expensive as the raw TLB size might suggest. On a system without ASIDs, every context switch would flush the TLB, and the switch cost would include the cost of refilling the TLB. On a system with ASIDs, most context switches leave the TLB intact, and the switch cost is dominated by the register save and restore rather than by the TLB.

4.5 TLB replacement policy

When a TLB miss occurs and the TLB is full, an entry must be evicted to make room for the new translation. The choice of which entry to evict is the TLB replacement policy, and it affects the TLB's hit rate in the same way that the cache replacement policy affects the cache's hit rate.

The candidate policies are similar to the cache replacement policies, and the trade-offs are the same.

  • Least Recently Used (LRU). Evict the entry that has not been used for the longest time. LRU is the intuitive choice and performs well when the working set has temporal locality. Its cost is the bookkeeping: tracking the recency of every entry requires either a timestamp or a linked list, both of which are expensive in a hardware TLB.
  • Pseudo-LRU. An approximation of LRU that is cheap to implement: a single bit per set of entries records which half was accessed most recently, and the eviction picks from the other half. This is not exactly LRU, but it is close in practice and much cheaper in hardware. Many real TLBs use pseudo-LRU.
  • Random. Evict a random entry. This is trivial to implement and, surprisingly, performs almost as well as LRU on many workloads. Its advantage is simplicity and predictability: there is no state to maintain, and no pathological workloads that defeat it.
  • Round robin. Evict the next entry in a circular order. Simple and predictable, but with worse behaviour than LRU or random on workloads with temporal locality.
  • Not recently used. A single bit per entry records whether the entry has been used since the last scan. Entries with the bit clear are the candidates for eviction. This is cheaper than LRU because the bit is updated by the MMU on each access and cleared by the operating system periodically.

Most real TLBs use some form of pseudo-LRU or random replacement, because the cost of true LRU is not justified by the marginal improvement in hit rate. The choice of policy is largely hidden from the operating system — the TLB is a hardware structure, and the replacement decision is made by the hardware — but the operating system can influence it through its own policies, for example by choosing which pages to keep resident in memory (Lesson 9.6).

4.6 The TLB's interaction with the caches

The TLB does not operate in isolation; it is part of a memory system that includes the L1, L2, and L3 caches. The way the TLB and the caches interact has a significant effect on performance, and it raises a subtle design question: should the caches be indexed by physical addresses or by virtual addresses?

A physically-indexed cache uses the physical address (after translation) to select the cache set. This is the traditional design, and it has the advantage that the cache's contents are independent of the address space — two processes that share a physical page will find the same data in the cache, no matter what virtual addresses they use to access it. Its disadvantage is that the cache lookup must wait for the translation, which adds the TLB lookup's latency to every cache access.

A virtually-indexed cache uses the virtual address to select the cache set, so the lookup can begin in parallel with the translation. This hides the translation latency, and it is why virtually-indexed caches are common for L1. Its disadvantage is the synonym or aliasing problem: two virtual addresses that map to the same physical address may index into different cache sets, so the same physical data can be present in the cache twice. This is a correctness issue that must be handled by the operating system, typically by ensuring that no two virtual addresses with different cache indices map to the same physical page.

Modern processors use a hybrid design called VIPT (Virtually-Indexed, Physically-Tagged). The cache is indexed by the low bits of the virtual address — which are the same as the low bits of the physical address, because the page offset is unchanged by translation — and tagged by the high bits of the physical address (after translation). The indexing can therefore begin immediately, in parallel with the TLB lookup, while the tag comparison waits for the physical address to be available. This gives the speed of a virtually-indexed cache with the correctness of a physically-indexed one, and it is the standard design in modern L1 caches. The constraint is that the cache's index bits must come entirely from the page offset, so the cache's size and associativity are limited by the page size: a 4 KB page has a 12-bit offset, so a VIPT cache can use at most the low 12 bits of the address for indexing — which, for a 64-byte cache line, means at most 64 sets.

The VIPT design explains why the page size and the cache design are linked. A larger page size allows a larger VIPT cache, which is one reason systems with large pages often have larger caches. And it explains why huge pages (Lesson 9.2) are attractive for workloads with poor TLB behaviour: a 2 MB huge page has a 21-bit offset, which allows much larger VIPT caches and much better TLB coverage than the 4 KB base page size.

4.7 TLB shootdown

On a multiprocessor system, each core has its own TLB. When the operating system changes a page-table entry — for example, to unmap a page, to change its protection bits, or to free a frame — it must ensure that no core continues to use the stale translation. This is the TLB shootdown problem.

The problem is that the TLB is a coherent structure only with respect to its own core. When core A modifies a page-table entry, the modification is visible to core A's TLB (after an appropriate invalidation) but not to core B's TLB, which may still hold a stale entry from an earlier access to the same page. The operating system must therefore send an inter-processor interrupt (IPI) to every core that might have the stale entry, and each core must invalidate the entry from its TLB.

TLB shootdown is expensive. An IPI is a heavyweight operation — it interrupts the receiving core, which must handle the interrupt, invalidate the TLB entry, and acknowledge — and the sending core must wait for all the acknowledgements before it can proceed with the operation that depended on the invalidation. On a system with many cores, a single page-table change can cost hundreds of cycles. The cost is so significant that kernel developers try to avoid page-table changes on multiprocessor systems, and there are special mechanisms (like Linux's reverse mapping) to identify exactly which cores need to be notified, so that the shootdown is sent to the minimum necessary set.

TLB shootdown is one of the reasons modern kernels use mechanisms like lazy TLB invalidation and batched invalidation. Instead of sending an IPI for every page-table change, the kernel can accumulate changes and send a single IPI that invalidates a batch of entries. It can also avoid the IPI entirely for changes that affect only the current core's TLB, because the current core can invalidate its own entry directly. The details are beyond the scope of this course, but the principle is important: the TLB's coherence requirements are a significant constraint on kernel design on multiprocessors.

4.8 Multi-level TLBs and TLB reach

Like the caches, modern TLBs are organised in a hierarchy. A small, fast L1 TLB holds a few dozen entries and is accessed in parallel with the L1 cache. A larger, slower L2 TLB holds several hundred to a few thousand entries and is accessed when the L1 TLB misses. Some processors have a third level, or use a unified TLB that serves both instructions and data.

The TLB reach is the amount of memory that the TLB can cover. It is the number of entries multiplied by the page size. For example, an L1 TLB with 64 entries and 4 KB pages has a reach of 256 KB; an L2 TLB with 512 entries and 4 KB pages has a reach of 2 MB. If a process's working set fits within the reach, the TLB hit rate is high; if the working set exceeds the reach, the TLB misses become frequent.

TLB reach is a significant constraint on modern workloads. The working sets of many applications exceed the reach of a 4 KB-page TLB: a machine-learning model with hundreds of millions of parameters touches far more memory than a few megabytes, and a virtual machine's guest memory can be tens of gigabytes. The traditional response has been to increase the TLB's size, but the TLB is a precious resource — it must be fast and small, and its associativity limits its size — so the growth has been slow.

The more effective response is to increase the page size. A TLB with 64 entries covers 256 KB with 4 KB pages, but 128 MB with 2 MB huge pages — a factor of 512 improvement in reach. This is the primary motivation for huge pages, and it is why huge pages are increasingly used for workloads with large working sets: databases, virtual machines, machine-learning training, and scientific simulations. Lesson 9.2 introduced huge pages in the context of the page table; here we see their effect on the TLB. The two effects — a smaller page table and a larger TLB reach — combine to make huge pages a significant performance optimisation for the right workloads.

4.9 Common misconceptions

"The TLB is managed by the operating system."

The TLB is a hardware structure. The MMU fills it on a miss, and the hardware chooses which entry to evict. The operating system's role is limited to invalidating entries when the page tables change (and to invalidating the whole TLB on context switches, unless ASIDs are used).

"The TLB is a cache of pages."

The TLB caches translations, not pages. A TLB entry says "page P is at frame F, with these protection bits". It does not contain the page's data, and a TLB hit does not avoid the data access — it only avoids the page-table walk.

"A TLB miss is the same as a page fault."

They are different events. A TLB miss means the translation is not in the TLB, but it may be in the page table, and the MMU can fetch it in the walk. A page fault means the page itself is not in memory (Lesson 9.4), and the operating system must bring it from disk. A page fault is much more expensive.

"Every memory access requires a page-table walk."

Only a TLB miss requires a walk. On a TLB hit, which is the common case, the translation is obtained directly from the TLB with no memory access to the page table.

"The TLB is flushed on every context switch."

Only if the system does not have address-space identifiers. With ASIDs (or PCIDs on x86-64), the TLB's entries are tagged with the address space, so a context switch does not require a flush. The entries for the outgoing process remain in the TLB and are simply not matched.

"Huge pages always improve performance."

Huge pages improve TLB reach and reduce the page-table walk, but they increase internal fragmentation and can be slower for workloads that use small, scattered regions of memory. The benefit is workload-dependent.

"The TLB and the caches are the same kind of thing."

They are both caches, but they cache different things. The TLB caches address translations; the L1/L2/L3 caches cache memory data. They are accessed in sequence on every memory access, and their performance interacts.

"The TLB has no effect on a single-threaded program."

The TLB affects every program, single-threaded or not. A single-threaded program with a working set larger than the TLB's reach will suffer TLB misses on a significant fraction of its accesses, and its performance will be dominated by the page-table walk.

05 Worked example

The following example computes the effective access time for a range of TLB configurations, and then demonstrates the effect of page size on TLB reach and the resulting performance.

Effective access time with a TLB

A system has the following characteristics:

  • A memory access takes 80 ns from L1 (the cache is fast, but not always hit; we'll model the memory access as a flat cost for simplicity).
  • A TLB lookup takes 1 ns, performed in parallel with the cache lookup.
  • A TLB miss triggers a page-table walk that takes 80 ns — because the page-table entries may themselves be cached in L1 or L2, the walk is not five full memory accesses, but roughly one full memory access plus some overhead.
  • The data access takes an additional 80 ns in either case.

The effective access time is: 

EAT = h × (t_tlb + t_data)
    + (1 − h) × (t_tlb + t_walk + t_data)

where h is the TLB hit rate. Substituting the values: 

EAT = h × (1 + 80) + (1 − h) × (1 + 80 + 80)
    = 81h + 161(1 − h)
    = 161 − 80h

The table below computes the effective access time for a range of hit rates.

TLB hit rate EAT (ns) Slowdown vs. no TLB Slowdown vs. perfect TLB
1.0081.01.00×1.00×
0.99981.081.00×1.00×
0.9981.801.01×1.01×
0.9585.01.05×1.05×
0.9089.01.10×1.10×
0.8097.01.20×1.20×
0.50121.01.49×1.49×
0.00161.01.99×1.99×

The pattern is instructive. At a hit rate of 99 percent or better, the TLB adds almost nothing to the access time: the EAT is 81.8 ns versus 81 ns for a perfect TLB, a difference of one percent. At 95 percent, the EAT is 85 ns, a difference of five percent. At 90 percent, it is 89 ns, a difference of ten percent. At 80 percent, it is 97 ns, a difference of twenty percent. And at lower hit rates the slowdown grows without bound: at a 0 percent hit rate (every access misses), the EAT is 161 ns, nearly twice the perfect-TLB cost.

The lesson is that a high hit rate is essential, and that the difference between a "very high" hit rate (99 percent) and a "high" hit rate (95 percent) is larger than the numbers suggest. This is the same sensitivity we saw for the caches in Lesson 8.1: the miss cost dominates the average, so the hit rate's effect on the average is disproportionate to its absolute value.

Effect of page size on TLB reach

Consider a workload that touches 64 MB of memory with reasonable locality. The following table compares the TLB's reach and hit rate for three page sizes.

Page size TLB entries TLB reach Working set / reach Estimated hit rate
4 KB 64 256 KB 256× low (many misses)
64 KB 64 4 MB 16× moderate
2 MB 64 128 MB 0.5× high (working set fits)
1 GB 64 64 GB 0.001× very high (trivially fits)

With 4 KB pages, a 64-entry TLB covers only 256 KB, so a 64 MB working set is 256 times the TLB's reach. The TLB will miss frequently, and the effective access time will be dominated by the page-table walk. With 2 MB huge pages, the same TLB covers 128 MB, which is larger than the 64 MB working set, so the TLB will hit on essentially every access.

This is why huge pages matter for workloads with large working sets. The improvement in reach — a factor of 512 for 2 MB pages over 4 KB pages — is what turns a TLB-miss-dominated workload into a TLB-hit-dominated one.

ASIDs and context switches

Consider a system without ASIDs, running a workload in which a process's TLB is warm (all its working-set pages are in the TLB) and the process is switched out and back in every 10 milliseconds. Without ASIDs, every context switch flushes the TLB, so after every switch the process's first accesses miss until the TLB is warm again. If the TLB takes about 100 accesses to warm, and the process performs 106 accesses per quantum, the cost of the flushes is about 100/106 = 0.01 percent — negligible. But if the process performs only 1000 accesses per quantum, the cost is about 10 percent — significant. The cost of the TLB flush is therefore a function of the process's run quantum relative to the TLB's warm-up time.

With ASIDs, no flush is required on the context switch, and the process's TLB entries remain valid. When the process runs again, its TLB is already warm, and its first accesses hit. The ASID mechanism therefore eliminates the warm-up cost entirely, which is a substantial benefit on workloads with frequent context switches between processes with large working sets.

A pathological case: pointer chasing

Consider a program that traverses a large linked list or tree with 107 nodes, each node on a separate page. The accesses are unpredictable (pointer chasing has no spatial locality), and the working set is far larger than any TLB. Every access is a TLB miss, and the effective access time is 161 ns instead of 81 ns — nearly twice as slow.

The remedy is not to increase the TLB size — no realistic TLB could cover 107 pages — but to improve the program's locality. Restructuring the data so that related nodes are on the same page, using a B-tree instead of a linked list, or using an array-based data structure, all improve locality and reduce TLB misses. This is the same principle as the cache-friendly programming of Lesson 8.1: the program's memory access pattern determines the memory system's performance, and good locality is the key to good performance.

06 Interactive activity

Activity · measure TLB behaviour on a live system

The goal of this activity is to observe the TLB's behaviour on a real system, measure its hit rate, and see the effect of page size on TLB performance. Work through the steps in your course VM.

  1. Inspect the TLB configuration. Use lscpu and cpuid to see the TLB's size and associativity on your machine. 
    lscpu | grep -i tlb
# If cpuid is available:
cpuid -1 | grep -i tlb
    The output shows the L1 data TLB, the L1 instruction TLB, the L2 TLB (also called STLB or shared TLB), and the number of entries and associativity of each. Write down the configuration for future reference.
  2. Measure TLB misses with perf. Use perf stat to count the TLB misses for a small workload and for a large one. 
    # Small workload (working set fits in the TLB)
perf stat -e dTLB-loads,dTLB-load-misses ./small_workload

# Large workload (working set exceeds the TLB)
perf stat -e dTLB-loads,dTLB-load-misses ./large_workload
    The ratio of dTLB-load-misses to dTLB-loads is the TLB miss rate. Compare the two workloads. How does the miss rate change with the working set size?
  3. Write a workload that stresses the TLB. Write a C program that traverses an array with a stride that is a multiple of the page size. This forces a TLB miss on every access (because each access is in a different page). 
    #include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define PAGE_SIZE  4096

int main(int argc, char **argv) {
    size_t n = atol(argv[1]);           /* total bytes */
    long   stride = atol(argv[2]);      /* bytes between accesses */

    char *buf = malloc(n);
    if (!buf) { perror("malloc"); return 1; }

    for (size_t i = 0; i < n; i++) buf[i] = 1;

    struct timespec t0, t1;
    clock_gettime(CLOCK_MONOTONIC, &t0);

    volatile long sum = 0;
    for (long rep = 0; rep < 10; rep++)
        for (size_t i = 0; i < n; i += stride)
            sum += buf[i];

    clock_gettime(CLOCK_MONOTONIC, &t1);
    double elapsed = (t1.tv_sec - t0.tv_sec)
                   + (t1.tv_nsec - t0.tv_nsec) / 1e9;
    printf("stride %5ld: %.4f s  (sum = %ld)\n",
           stride, elapsed, sum);
    free(buf);
    return 0;
}
    Run it with strides of 1, 8, 64, 4096, 8192, and 65536 bytes over a 64 MB buffer. Measure the time for each. Which stride is fastest? Which is slowest? Run perf stat on the slowest case and observe the TLB miss count.
  4. Compare 4 KB pages with huge pages. Modify the program to allocate memory with mmap using MAP_HUGETLB (if your system supports it and has huge pages available), and compare the TLB miss rate. 
    #include <sys/mman.h>

/* try huge pages first */
void *buf = mmap(NULL, n,
                 PROT_READ | PROT_WRITE,
                 MAP_PRIVATE | MAP_ANONYMOUS | MAP_HUGETLB,
                 -1, 0);

if (buf == MAP_FAILED) {
    /* fall back to base pages */
    buf = mmap(NULL, n,
               PROT_READ | PROT_WRITE,
               MAP_PRIVATE | MAP_ANONYMOUS,
               -1, 0);
}

/* check the page size of the mapping */
size_t pagesize = 0;
FILE *f = fopen("/proc/self/smaps", "r");
/* ... parse the KernelPageSize field for the mapping ... */
    If huge pages are available, the version with MAP_HUGETLB should show far fewer TLB misses on the large working set. If not, use madvise(MADV_HUGEPAGE) with transparent huge pages enabled.
  5. Observe the effect of ASIDs. Run two memory-intensive processes concurrently on the same machine, and compare the TLB miss rate of each to when they run alone. 
    ./large_workload 67108864 4096 &
./large_workload 67108864 4096 &
wait

# versus
./large_workload 67108864 4096
    The context switches between the two processes force each to rebuild its TLB when it runs again. If ASIDs are in use, the TLB is not flushed, but the two processes still compete for the TLB's limited entries. Compare the miss rates in the two cases to see how much contention the shared TLB causes.
  6. Inspect the page-table entries for a process. Use /proc/<pid>/pagemap (with root privileges) to see the frame numbers for a process's pages. Correlate the pattern of present pages with the process's memory layout from /proc/<pid>/maps. 
    sudo cat /proc/self/pagemap | head -c 64 | xxd
    The format is documented in man 5 proc. Each entry is 8 bytes and contains the present bit, the swapped bit, and the frame number. What fraction of the process's pages are present?
  7. Read man 1 perf-stat. Read the man page and identify all the TLB-related events the tool exposes: dTLB-loads, dTLB-load-misses, dTLB-stores, dTLB-store-misses, iTLB-loads, iTLB-load-misses, dtlb_load_misses.walk_completed, dtlb_load_misses.walk_duration. For each, write a sentence describing what it measures. Then run a small program under perf stat with all the TLB events and interpret the results. 
    perf stat -e dTLB-loads,dTLB-load-misses,\
iTLB-loads,iTLB-load-misses \
./small_workload
  8. Read the OSTEP chapter. Read OSTEP Chapter 19, Paging: Faster Translations (TLBs). Compare its presentation of the TLB to this lesson. What additional considerations does OSTEP raise — for example, the software-managed TLB, the TLB's role in the demand-paging mechanism, and the interaction between the TLB and the page fault handler? Write a short paragraph summarising the differences.

Reflect: the TLB is a small structure — a few dozen to a few thousand entries — and it sits at the boundary between the hardware and the operating system. The hardware fills it automatically on a miss; the operating system invalidates entries when the page tables change; and the two must coordinate carefully to ensure that a stale translation is never used. On a uniprocessor, the coordination is simple: the operating system invalidates the TLB entry and the change takes effect immediately. On a multiprocessor, the coordination requires IPIs and careful ordering, and the cost of a page-table change grows with the number of cores. What does this suggest about the future of the TLB on machines with hundreds or thousands of cores? What alternatives to the TLB might be feasible, and what would they give up?

07 Knowledge check

Check your understanding

Question 1

What is the TLB, and why is it necessary? Describe its structure and explain the role of associativity in its design.

Show answer
The translation lookaside buffer (TLB) is a small, fast, hardware-managed cache of recently used address translations. It is necessary because paged address translation requires a page-table walk on every access — four memory accesses on x86-64 — which would make every load and store five times as expensive as a raw memory access. The TLB caches the final result of the walk — the mapping from a page number to a frame number, together with the protection bits and other control bits — so that a subsequent access to the same page bypasses the walk entirely. Because programs have locality of reference, the TLB's hit rate is very high (typically 99 percent or better), and the average cost of translation is much closer to a single memory access than to five. The TLB's structure is that of a cache: each entry holds a key (the page number, possibly combined with an address-space identifier) and a value (the frame number and the control bits). The TLB can be organised as fully associative, set associative, or direct mapped, and the choice of organisation determines its speed, its size, and its conflict behaviour. A fully associative TLB searches every entry in parallel, so there are no conflict misses, but the comparators are expensive and the size is limited to a few dozen entries. A set associative TLB divides the entries into sets and searches only the entries within the selected set, which is much cheaper but introduces conflict misses: two page numbers that hash to the same set compete for the set's ways. A direct mapped TLB has one entry per set, so the page number selects a single slot; this is the cheapest organisation but has the highest conflict-miss rate. Modern TLBs use a mix: the L1 TLB is typically fully associative or 4-way set associative with 32 to 64 entries, and the L2 TLB is typically 4-way or 8-way set associative with several hundred to a few thousand entries. The choice reflects the trade-off between speed and conflict-miss rate at each level.

Question 2

Define the TLB hit rate and the effective access time. Compute the EAT for a system with a hit rate of 98 percent, a TLB lookup time of 1 ns, a page-table walk time of 60 ns, and a data access time of 80 ns. What is the cost of the TLB miss compared to a perfect TLB?

Show answer
The TLB hit rate is the fraction of memory accesses for which the required translation is present in the TLB. It depends on the workload's locality and on the TLB's size. The effective access time (EAT) is the average cost of a memory reference, weighted by the hit rate:

EAT = h × t_hit + (1 − h) × t_miss

where t_hit = t_tlb + t_data and t_miss = t_tlb + t_walk + t_data. Substituting the given values:

t_hit = 1 + 80 = 81 ns
t_miss = 1 + 60 + 80 = 141 ns
EAT = 0.98 × 81 + 0.02 × 141
EAT = 79.38 + 2.82 = 82.20 ns

The cost of the TLB misses is the difference between the EAT and the perfect-TLB case (81 ns): 82.20 − 81 = 1.20 ns, which is about 1.5 percent of the perfect-TLB cost. The sensitivity to the hit rate is high: at a 95 percent hit rate, the EAT would be 0.95 × 81 + 0.05 × 141 = 76.95 + 7.05 = 84 ns, a 3.7 percent slowdown; at a 90 percent hit rate, the EAT would be 0.90 × 81 + 0.10 × 141 = 72.9 + 14.1 = 87 ns, a 7.4 percent slowdown. The EAT formula shows that the effect of the hit rate is disproportionate to its absolute value, because the miss cost dominates the average.

3

What is an address-space identifier (ASID)? What problem does it solve, and how does it affect the cost of a context switch? What is the trade-off in using ASIDs?

Show answer
An address-space identifier (ASID), also called a process-context identifier (PCID) on x86-64, is a small integer that identifies the current address space. It is stored alongside the page number in each TLB entry, and a TLB lookup matches only if both the ASID and the page number match. The problem it solves is the context switch flush. Without ASIDs, the TLB entries for the outgoing process are invalid after a context switch, because the meaning of a page number depends on the process's address space. The TLB must therefore be flushed on every context switch, which empties it and forces the incoming process to rebuild its translations from scratch. With ASIDs, the entries for the outgoing process remain in the TLB and are simply not matched while the incoming process runs, because its ASID is different. No flush is required, and the incoming process's own TLB entries (if it has run before) are still present. This eliminates the warm-up cost of the context switch. The trade-off is that the supply of ASIDs is finite — typically 8 to 16 bits, so 256 to 65,536 values — and a system with more processes than ASIDs must eventually reuse them. When an ASID is reused, the TLB entries from its previous use are stale and must be invalidated, so the cost of the flush is deferred, not eliminated. The operating system therefore maintains a policy for ASID allocation and reuse, and the benefit of ASIDs depends on the ratio of ASIDs to concurrently running processes.

Question 4

Describe the interaction between the TLB and the L1 cache. What is the difference between a physically-indexed and a virtually-indexed cache, and what is the VIPT design? What constraint does the page size impose on a VIPT cache?

Show answer
On every memory access, the processor must both translate the address (using the TLB or a page-table walk) and look up the data in the cache. The way these two operations are ordered depends on the cache's indexing and tagging. A physically-indexed cache uses the physical address (after translation) to select the cache set. This is the traditional design, and it has the advantage that the cache's contents are independent of the address space: two processes that share a physical page will find the same data in the cache, no matter what virtual addresses they use. Its disadvantage is that the cache lookup must wait for the translation, which adds the TLB lookup's latency to every cache access. A virtually-indexed cache uses the virtual address to select the cache set, so the lookup can begin in parallel with the translation. This hides the translation latency, and it is why virtually-indexed caches are common for L1. Its disadvantage is the synonym problem: two virtual addresses that map to the same physical address may index into different cache sets, so the same physical data can be present in the cache twice, which is a correctness issue. The VIPT (Virtually-Indexed, Physically-Tagged) design combines the two: the cache is indexed by the low bits of the virtual address — which are the same as the low bits of the physical address, because the page offset is unchanged by translation — and tagged by the high bits of the physical address (after translation). The indexing can therefore begin immediately, in parallel with the TLB lookup, while the tag comparison waits for the physical address. This gives the speed of a virtually-indexed cache with the correctness of a physically-indexed one. The constraint is that the cache's index bits must come entirely from the page offset, so the cache's size and associativity are limited by the page size: a 4 KB page has a 12-bit offset, so a VIPT cache can use at most the low 12 bits of the address for indexing — which, for a 64-byte cache line, means at most 64 sets. This is one reason systems with large pages often have larger caches, and one reason huge pages are attractive for memory-intensive workloads.

Question 5

What is TLB shootdown? Why is it necessary on a multiprocessor system, and what is its cost? What is the relationship between TLB shootdown and the trend toward machines with many cores?

Show answer
TLB shootdown is the process of invalidating a TLB entry on every core that might hold a stale copy of it, when the operating system changes a page-table entry. The problem is that each core has its own TLB, and the TLB is coherent only with respect to its own core. When core A modifies a page-table entry — for example, to unmap a page, change its protection bits, or free a frame — the modification is visible to core A's TLB (after an appropriate invalidation) but not to core B's TLB, which may still hold a stale entry from an earlier access to the same page. The operating system must therefore send an inter-processor interrupt (IPI) to every core that might have the stale entry, and each core must invalidate the entry from its TLB. TLB shootdown is necessary because the alternative — allowing different cores to see different translations for the same page — would be a correctness failure. A core that used a stale translation could read or write a frame that the operating system had reallocated to a different purpose, corrupting data or violating protection. The cost of TLB shootdown is significant. An IPI is a heavyweight operation: it interrupts the receiving core, which must handle the interrupt, invalidate the TLB entry, and acknowledge; the sending core must wait for all the acknowledgements before it can proceed. On a system with many cores, a single page-table change can cost hundreds or thousands of cycles. The cost is so significant that kernel developers try to avoid page-table changes on multiprocessor systems, use reverse mapping to identify exactly which cores need to be notified, and batch invalidations to amortise the IPI cost. The relationship to the trend toward many-core machines is direct: as the number of cores grows, the cost of a TLB shootdown grows, because the IPI must reach more cores and the acknowledgements take longer. On a machine with hundreds of cores, the shootdown cost can dominate the cost of the page-table change itself. This has led to research on alternative TLB designs, on mechanisms to avoid shootdowns (such as lazy invalidation or generation-based tagging), and on system designs that reduce the frequency of page-table changes on multi-core systems.

08 Unit discussion

Discussion prompt

The TLB is a small structure — a few dozen to a few thousand entries — but its performance has a disproportionate effect on the performance of a modern system. A program whose working set fits in the TLB's reach runs at nearly full speed; a program whose working set exceeds it runs at a fraction of the speed, even though the code is identical and the arithmetic is the same. The difference is entirely in the memory access pattern, and the pattern is the programmer's responsibility.

This is a familiar theme from Lesson 8.1, where we saw that the cache's behaviour is dominated by locality. The TLB extends the theme: the locality that matters is not only for individual bytes and cache lines, but also for pages. A program that touches many pages randomly, even if each page is touched only once, will miss in the TLB on every access and suffer the page-table walk. A program that touches few pages but accesses them intensely will hit in the TLB and run at full speed.

The trend in hardware design has been to increase the number of cores, and this trend has complex implications for the TLB. On the one hand, more cores mean more TLB shootdowns and more pressure on the shared L2 TLB; on the other hand, more cores mean more opportunities for parallelism, which can hide the TLB's latency if the workload has enough parallelism. The trend also favours huge pages, which improve TLB reach but increase internal fragmentation — a trade-off that does not resolve cleanly.

Consider the workloads you know — a web browser, a database, a machine-learning training run, a compiler, a graphics renderer. Which ones are TLB-friendly, and which are not? How would you design a program to be TLB-friendly without sacrificing other goals? What role should the operating system play in this — should it automatically promote pages to huge pages, or should the application control it? Post your response to the Unit 9 discussion forum and reply to at least two classmates. Supports CLO1, CLO4, and CLO6.

09 Practice exercise

This ungraded exercise consolidates the lesson and prepares you for Lesson 9.4. Aim to spend 60–90 minutes on it.

  1. Compute effective access times. For the following TLB configurations, compute the effective access time and the slowdown compared to a perfect TLB. The base parameters are: TLB lookup = 1 ns, page-table walk = 50 ns, data access = 80 ns.
    Hit rate EAT (ns) Slowdown vs. perfect
    1.00——
    0.999——
    0.99——
    0.95——
    0.90——
    0.80——
    0.50——
    0.00——
  2. Compute TLB reach. For the following TLB configurations and page sizes, compute the TLB reach. State whether a 64 MB working set would fit in the reach.
    • 64 entries, 4 KB pages
    • 512 entries, 4 KB pages
    • 2048 entries, 4 KB pages
    • 64 entries, 2 MB pages
    • 512 entries, 2 MB pages
    • 64 entries, 1 GB pages
  3. Design an experiment for TLB thrashing. Write a C program that allocates a large buffer and traverses it with different strides. Measure the execution time for strides of 1, 8, 64, 4096, 8192, and 65536 bytes on a 64 MB buffer. Then run each with perf stat -e dTLB-loads,dTLB-load-misses and record the TLB miss count. Plot or tabulate the relationship between stride and TLB miss rate. 
    for stride in 1 8 64 4096 8192 65536; do
    echo "stride = $stride"
    perf stat -e dTLB-loads,dTLB-load-misses \
        ./stride_test 67108864 $stride
done
    Explain your observations in terms of page size and TLB reach.
  4. Investigate ASIDs. On a Linux system, use /proc/cpuinfo or lscpu to check whether the processor supports PCIDs (the x86-64 equivalent of ASIDs). Then check whether the kernel is using them. 
    lscpu | grep -i pcid
cat /proc/cpuinfo | grep -i pcid

# Check whether the kernel is using PCIDs
dmesg | grep -i pcid
    If PCIDs are supported, they should appear in the CPU flags, and the kernel should use them by default. If not, the kernel flushes the TLB on every context switch.
  5. Measure the effect of context switches. Write two programs, each with a large working set. Run them alone and then concurrently, and measure the TLB miss rate of each in both cases. 
    # Run alone
perf stat -e dTLB-loads,dTLB-load-misses ./workload

# Run concurrently
perf stat -e dTLB-loads,dTLB-load-misses \
    ./workload &
perf stat -e dTLB-loads,dTLB-load-misses \
    ./workload &
wait
    How much does the TLB miss rate increase when two processes compete for the TLB? Explain the result in terms of TLB capacity and context switches.
  6. Compare 4 KB and huge pages. Write a program that allocates 64 MB with base pages and the same with huge pages (via MAP_HUGETLB or madvise(MADV_HUGEPAGE)). Traverse both with a stride of 4096 bytes and measure the time and TLB misses for each. 
    /* Allocate with base pages */
void *base = mmap(NULL, 64*1024*1024,
                  PROT_READ | PROT_WRITE,
                  MAP_PRIVATE | MAP_ANONYMOUS,
                  -1, 0);

/* Allocate with huge pages */
void *huge = mmap(NULL, 64*1024*1024,
                  PROT_READ | PROT_WRITE,
                  MAP_PRIVATE | MAP_ANONYMOUS | MAP_HUGETLB,
                  -1, 0);
    What is the difference in TLB misses? What is the difference in time? Is the improvement worth the increased internal fragmentation?
  7. Read the OSTEP chapter. Read OSTEP Chapter 19, Paging: Faster Translations (TLBs). Compare its presentation of the TLB to this lesson. What additional considerations does OSTEP raise — for example, the software-managed TLB, the role of the TLB in the demand-paging mechanism, and the interaction between the TLB and the page fault handler? Write a short paragraph summarising the differences.
  8. Reflect. In your own words, explain why the TLB is so important for a modern system, and what would happen without it. Then describe one situation in your own experience — a program you have written or a system you have used — where the TLB's behaviour could plausibly have affected performance. What was the memory access pattern, and what would you do differently now?

10 Summary

  • The translation lookaside buffer (TLB) is a small, fast, hardware-managed cache of recently used translations. Its purpose is to hide the cost of the page-table walk, which on x86-64 requires four memory accesses per translation.
  • On a TLB hit, the frame number is obtained directly from the TLB, and only the data access is performed. On a TLB miss, the MMU performs the full page-table walk, inserts the result into the TLB, and then performs the data access.
  • The TLB is effective because of locality of reference. A program's working set is typically small, so a modest TLB covers it, and the hit rate is very high — typically 99 percent or better on real workloads.
  • The TLB's organisation can be fully associative, set associative, or direct mapped. Fully associative has no conflict misses but is expensive; direct mapped is cheap but has the highest conflict-miss rate. Modern TLBs use a mix: small, fully associative L1 TLBs and larger, set-associative L2 TLBs.
  • The effective access time is EAT = h × t_hit + (1 − h) × t_miss, where h is the hit rate. Because the miss cost is much higher than the hit cost, the hit rate's effect on the average is disproportionate: a 99 percent hit rate gives a nearly perfect EAT, while a 90 percent hit rate gives a 10 percent slowdown.
  • An address-space identifier (ASID), called a process-context identifier (PCID) on x86-64, is a small integer stored alongside the page number in each TLB entry. It allows the TLB to hold entries for multiple processes simultaneously, so that a context switch does not require a TLB flush.
  • The TLB replacement policy decides which entry to evict when a miss occurs and the TLB is full. The candidates are LRU, pseudo-LRU, random, round robin, and not recently used. Most real TLBs use some form of pseudo-LRU or random, because true LRU is too expensive.
  • The TLB interacts with the caches. A physically-indexed cache waits for the translation; a virtually-indexed cache can begin the lookup in parallel but has the synonym problem. The VIPT design combines the two, at the cost of a constraint on cache size and associativity relative to the page size.
  • On a multiprocessor, TLB shootdown is required when the operating system changes a page-table entry: the change must be propagated to every core that might hold a stale entry, via inter-processor interrupts. The cost of shootdown grows with the number of cores, and it is a significant constraint on kernel design on many-core machines.
  • Modern processors have multi-level TLBs: a small, fast L1 TLB, and a larger, slower L2 TLB. The TLB reach is the number of entries multiplied by the page size, and it determines whether a workload's working set fits in the TLB.
  • Huge pages increase TLB reach dramatically — a factor of 512 for 2 MB pages over 4 KB pages, with the same TLB — at the cost of increased internal fragmentation. They are the primary remedy for workloads whose working sets exceed the TLB reach, and they are increasingly used in databases, virtual machines, and machine-learning training.
  • A TLB miss is not a page fault. A TLB miss means the translation is not in the TLB, but the page may still be in memory; a page fault means the page itself is not in memory, and the operating system must bring it from disk (Lesson 9.4). The page fault is much more expensive.

Looking ahead

This lesson presented the TLB, the small hardware cache that makes paging practical. The TLB's hit rate depends on the program's locality, and its behaviour is the primary determinant of memory-system performance on modern processors. Lesson 9.4 presents demand paging: the mechanism by which a page can be brought into memory from disk only when it is actually needed. This is the mechanism that allows a process's address space to exceed the physical memory, and it is the foundation of virtual memory in the classical sense. The lesson covers the page-fault mechanism, the handling of a page fault, the difference between a major and minor fault, and the practical consequences for program performance.

11 References

  • Arpaci-Dusseau, R. H., & Arpaci-Dusseau, A. C. Operating Systems: Three Easy Pieces, Chapter 19, Paging: Faster Translations (TLBs). Available online at ostep.org.
  • Silberschatz, A., Galvin, P. B., & Gagne, G. Operating System Concepts, 10th ed., Chapter 9, Section 9.4, and Chapter 10, Sections 10.1–10.3.
  • Tanenbaum, A. S., & Bos, H. Modern Operating Systems, 4th ed., Chapter 3, Section 3.3.
  • Bryant, R. E., & O'Hallaron, D. R. Computer Systems: A Programmer's Perspective, 3rd ed., Chapter 9, Virtual Memory, sections 9.6–9.8.
  • Jacob, B., & Mudge, T. Virtual Memory: Issues of Implementation and Performance. IEEE Computer, 1998.
  • Intel Corporation. Intel 64 and IA-32 Architectures Software Developer's Manual, Volume 3: System Programming Guide, Chapter 4, Paging.
  • Rosenblum, M., Bugnion, E., Herrod, S. A., Witchel, E., & Gupta, A. The Impact of Architectural Trends on Operating System Performance. Proceedings of the ACM Symposium on Operating Systems Principles, 1995. Includes a discussion of the TLB's role in operating-system performance.
  • Bhargava, R., Serebrin, B., Spadini, F., & Manne, S. Accelerating Two-Dimensional Page Walks for Virtualized Systems. Proceedings of the International Conference on Architectural Support for Programming Languages and Operating Systems, 2008. A paper on the interaction between the TLB and virtualization.
  • Love, R. Linux Kernel Development, 3rd ed., Chapter 12, Memory Management. The Linux kernel's handling of the TLB, including TLB shootdown and the reverse-mapping mechanism.
  • Linux man-pages: man 1 perf-stat, man 2 madvise, man 2 mmap, man 5 proc.
👤