Translation lookaside buffer

A translation lookaside buffer is a physical cache buffer used to speed-up accesses for page table entries. This reduces the blocking time required to decode multilevel page tables. Like with regular caches, we have hits and misses.

• For hits, they exist in the TLB already and we can jump straight to the correct physical page.
• For misses, we need to translate the virtual address using the page table and add it to the TLB.
  • The hardware locates the page table in memory using the page table base register.
  • It looks up the page table entry (PTE) for the page using the VPN as an index.
  • If the page is valid and present in physical memory, the hardware will extract the page frame number (PFN) from the PTE, install it into the TLB, and retries the instruction.

Quantitatively

Quantitatively:

$${\text{TLB}}_{\text{hit time}}={\text{TLB}}_{\text{search}}+\text{Mem}$$ $${\text{TLB}}_{\text{miss time}}={\text{TLB}}_{\text{search}}+(\#\text{levels}+1)\times \text{Mem}$$

Then, the average (or effective) access time (EAT) is given by:

$$\text{EAT}=\alpha \times {\text{TLB}}_{\text{hit time}}+(1-\alpha )\times {\text{TLB}}_{\text{miss time}}$$

Note that any context switches require handling the TLB, so the kernel will have to either flush the cache or attach a process ID to the TLB. Most implementations will just flush the TLB (including x86-64 automatically).