Translation Lookaside Buffer in Paging

Introduction

Paging gives a process a flexible virtual address space by mapping virtual pages to physical frames. But every memory access still needs address translation before the actual data can be reached.

The Translation Lookaside Buffer, or TLB, makes this translation faster. It caches recently used page-table translations so the MMU does not need to walk the page table for every memory reference.

What Is a TLB?

TLB stands for Translation Lookaside Buffer. It is a small, fast hardware cache located inside or near the Memory Management Unit, or MMU.

The TLB stores recent virtual-page-to-physical-frame translations. Instead of checking the page table in memory every time, the MMU first checks whether the needed translation is already present in the TLB.

It does not store the actual program data. It stores mapping information used to find that data.

What a TLB Entry Contains

A typical TLB entry stores the information needed to translate a virtual page quickly.

• VPN: Virtual Page Number.

• PFN: Physical Frame Number.

• Permission Bits: Specify read, write, and execute permissions.

• Valid/Status Bits: Indicate whether the entry can be used.

• ASID/PCID: Identifies the address space, if supported.

The page offset is not translated. It remains the same and is combined with the physical frame number to form the final physical address.

Why the TLB Is Needed

Without a TLB, a memory access may require extra memory operations just for translation. In a simple paging system, the CPU generates a virtual address. The system may first need to read the page-table entry from memory, and only then access the actual data.

With multilevel paging, the cost can be higher because the system may need to walk through multiple page-table levels before reaching the final PTE. The TLB reduces this cost by keeping recent translations close to the MMU.

TLB Hit

A TLB hit means the required translation is already present in the TLB. The flow for TLB Hit is:

• Virtual address: Check the TLB using the virtual page number.

• TLB hit: Get the corresponding physical frame number.

• Physical address: Combine the frame number with the same offset and access memory.

This is fast because the system does not need to walk the page table. The MMU directly obtains the physical frame number from the TLB.

TLB Miss

A TLB miss means the required translation is not present in the TLB. The flow for TLB Miss is:

• Virtual address: Check the TLB using the virtual page number.

• TLB miss: Search the page table to find the corresponding PTE and frame number.

• Update TLB: Store the mapping in the TLB and continue with memory access.

A TLB miss does not automatically mean the page is absent from memory. It only means the translation was not found in the TLB. The page table may still contain a valid present mapping.

TLB Miss vs Page Fault

A TLB miss and a page fault are different events.

A TLB miss can be resolved by a valid page-table entry. A page fault requires operating-system handling and is much more expensive.

Why a Small TLB Works Well

A TLB can be small and still useful because programs show locality.

• Temporal locality: If a page was used recently, it may be used again soon. Loops, repeated function calls, and reused variables often create this pattern.

• Spatial locality: If one address is accessed, nearby addresses may be accessed soon. Arrays and sequential instruction execution often create this pattern.

Because programs often reuse the same or nearby pages, many translations can be served from a small TLB.

Small TLB Trace Example

Suppose a TLB can hold 3 page translations and starts empty. The page access sequence is: 1, 2, 1, 3, 1

Here, Hits = 2 and Misses = 3, therefore, Hit ratio = 2 / 5 = 40%.

This is a cold-start trace because the TLB begins empty. Longer real workloads can have much higher hit ratios after frequently used translations are cached.

TLB and Context Switching

A TLB entry is valid only for the correct address space. The same virtual page number can map to different physical frames in different processes. For example, Process P1 maps VPN 10 to PFN 100, while Process P2 maps the same VPN 10 to PFN 170.

If the CPU switches from P1 to P2 and accidentally reuses P1’s stale TLB entry, P2 could access the wrong physical memory. There are two common solutions:

• Flush the TLB: Remove old entries during a context switch. This is simple and safe, but causes more misses after the switch.

• Use ASID/PCID-style tags: Store an address-space identifier with each TLB entry, so entries from different processes can coexist safely.

The key rule is that a TLB translation must always be interpreted in the correct address space.

Summary

The TLB is a small, fast cache for page-table translations. It stores recent VPN-to-PFN mappings so the MMU can translate virtual addresses without repeatedly walking the page table.

A TLB hit gives the translation quickly, while a TLB miss requires a page-table lookup. A page fault is different from a TLB miss because it means the page-table check found an invalid, not-present, or permission-related condition that needs OS handling.