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. 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).