OS Study 12. Memory: TLB, Using a Cache to Speed Up Address Translation

As explained in the previous section, when we use paging, the size of the page table and the cost of accessing it can slow the system down.

To speed up the OS’s address translation, we need help from hardware.

More specifically, we use a piece of hardware called the TLB.

The TLB (Translation Lookaside Buffer) is part of the MMU (Memory Management Unit). Because it stores frequently used virtual-to-physical address mappings in hardware, you can think of it as an “address translation cache.”

1. Basic TLB algorithm

Conceptually, the TLB works very similarly to a regular cache.

• If it is, the hardware can translate the address quickly without consulting the page table.
• If it is not, the hardware must look up the page table in memory, perform the translation, and then (typically) insert that translation into the TLB.

In other words, the TLB reduces the number of page-table accesses, which improves performance.

More concretely:

1. The hardware extracts the VPN (Virtual Page Number) from the virtual address.
2. It checks whether there is an entry for that VPN in the TLB.

• If the VPN is found in the TLB, we call this a TLB hit, and the hardware reads the corresponding PFN (Page Frame Number) from that TLB entry.
• If the VPN is not in the TLB, we call this a TLB miss. The hardware then accesses the page table in memory to find the VPN→PFN mapping.

3. If the page-table lookup succeeds (the virtual address is valid and accessible), the hardware loads that translation into the TLB.

4. After updating the TLB, the hardware restarts the address translation from the beginning — this time, it will find the mapping in the TLB.

Because the TLB is located very close to the CPU core and implemented as extremely fast hardware, it can significantly accelerate address translation.

To summarize:

• Memory accesses are much slower than most CPU operations.
• Page tables usually live in main memory.
• Therefore, frequent TLB misses cause many extra memory accesses. To avoid this, we want to design the system and programs so that TLB misses are minimized.

2. A Closer Look: Locality and TLB Performance

The TLB is especially effective when a program (or process) exhibits spatial and temporal locality. In those cases, the TLB and the program’s access patterns reinforce each other, and performance gains are larger.

• Spatial locality: If a program accesses memory address x, it is highly likely to access addresses near x in the near future.
• Temporal locality: If a program accesses a certain memory location once, it is likely to access the same location again within a short time.

A classic example that shows both types of locality is an array.

Let’s walk through a concrete example.

Imagine that all the metadata and data for an array a are laid out in memory as shown in the (following) figure.

Now imagine we run the following code:

int sum = 0;

for (i = 0; i < 10; i++) {
    sum += a[i];
}

Let’s walk through what happens with the TLB when the program accesses each element of a.

1. Accessing a[0]

• The hardware checks the TLB for the page that contains a[0] (VPN 6).
• There is no entry for this page yet, so we get a TLB miss.
• The hardware goes to the page table, finds the VPN 6 → PFN mapping, updates the TLB with this entry, and then retries the translation.
• Now the TLB contains: VPN 6 → PFN X.

2. Accessing a[1], a[2], a[3]

• Each time, the hardware checks the TLB.
• VPN 6 is already in the TLB, so these accesses result in TLB hits.
• The TLB still contains: VPN 6 → PFN X.

3. Accessing a[4], a[5], a[6]

• These elements reside on the next virtual page, say VPN 7.
• On the first access to a[4], there is no entry for VPN 7, so we get a TLB miss.
• The hardware looks up VPN 7 in the page table, inserts VPN 7 → PFN Y into the TLB, and then retries the translation.
• Subsequent accesses to a[5] and a[6] are TLB hits.
• Now the TLB contains (at least): VPN 6 and VPN 7.

4. Accessing a[7]

• Suppose a[7] happens to be mapped to a different page, VPN 8.
• Again, the hardware checks the TLB, finds no entry for VPN 8, and we get a TLB miss.
• The hardware consults the page table, loads VPN 8 → PFN Z into the TLB, and then completes the translation.
• The TLB now contains an entry for VPN 8.

5. Accessing a[8], a[9]

• These accesses hit the TLB entry for VPN 8, so both are TLB hits.

From this example, you can clearly see spatial locality at work:

• Because the elements of the array are stored contiguously within a page, the program pays the cost of a TLB miss only when it first touches each new page (e.g., a[0], a[4], a[7] or a[8], depending on layout).
• Once that page’s translation is in the TLB, all nearby elements on the same page produce TLB hits.

If the TLB is large enough to hold the translations for all the pages that the array spans, and the program continues to use this array later (e.g., in another loop), temporal locality also kicks in: previously cached translations are reused, which further increases the TLB hit rate.