translation lookaside buffer (TLB)

What is a translation lookaside buffer (TLB)?

A translation lookaside buffer (TLB) is a type of memory cache that stores recent translations of virtual memory to physical addresses to enable faster retrieval. This high-speed cache is set up to keep track of recently used page table entries (PTEs). Also known as an address-translation cache, a TLB is a part of the processor's memory management unit (MMU).

With a TLB, there's no need to place PTEs in registers, which is impractical, or keep the entire page table in the main memory, which requires two main memory references. Instead, the TLB checks if the page is already in the main memory. The processor examines the TLB for a PTE, retrieves the frame number and forms the real address. If the page is not in the main memory, a page fault is issued, and the TLB gets updated with the new PTE.

How a translation lookaside buffer works

The TLB is based on the idea of "locality of reference," which means it contains only the entries of those pages that the central processing unit (CPU) needs to access frequently. When a program references a virtual memory address, the search starts in the CPU. First, the instruction caches are checked. If the required memory is not in these very fast caches, the system has to look up the memory's physical address. At this point, the TLB is checked for a quick reference to the location in the physical memory.

When an address is searched in the TLB but not found, the physical memory must be searched with a memory page crawl operation. As virtual memory addresses are translated, the values referenced are added to the TLB. Most processors include TLBs to increase the speed of virtual memory operations through inherent latency-reducing proximity as well as the high-running frequencies of current CPUs.

Why translation lookaside buffers are necessary

In an operating system, a page table is created for each process. Moreover, each page table contains a PTE. A PTE provides information about where the actual page is residing in the main memory. It also includes bit information, such as the valid or invalid bits, dirty bits, and protection bits. The frame number, which is the address of the main memory being referenced, is also included in the PTE. The page table and its PTEs must be placed somewhere to reduce the overall access time as much as possible.

One option is to use registers -- a type of high-speed memory that can reduce access time. In this case, each request generated from a virtual address will be matched to the relevant page number of the page table, which will reveal where that page resides in the main memory. However, this is not a practical approach because registers are usually too small to hold all the PTEs of a page table, which can consist of millions of entries.

Another option is to keep the entire page table in the main memory. The challenge with this method is that two main memory references will be required: one to find the frame number, and the other to go to the address specified by that number.

A TLB can eliminate the problems associated with both these issues. This high-speed cache can keep track of recently used transactions through PTEs. This enables the processor to examine the TLB to confirm if a PTE is present, known as a TLB hit, and then retrieve the frame number and real address. If the PTE is not found in the TLB, the page number is used as an index, and the TLB gets updated with a new PTE.

Translation lookaside buffer hits vs. translation lookaside buffer misses

A TLB hit means a PTE is present in the TLB and the processor has found it, given a virtual address. When this happens, the CPU accesses the actual location in the main memory. It consists of these steps:

• The CPU generates a virtual address. This is a logical address.
• The address is checked in the TLB and is present.
• If the address is present, its frame number is retrieved.
• The CPU now knows where the page lies in the main memory.

A TLB miss means a PTE was not found in the TLB. In this case, the page number is used as the index while processing the page table. In other words, the processor accesses the page table in the main memory and then accesses the actual frame in the main memory. The steps in a TLB miss are as follows:

• The CPU generates a virtual address. Again, this is a logical address.
• The address is checked in the TLB and is not present.
• The page number is matched to a page table residing in the main memory.
• The corresponding frame number is retrieved.
• The CPU now knows where the page lies in the main memory.
• The TLB is updated with the new PTE.

Access times with translation lookaside hits and misses

Since a TLB miss requires additional steps for retrieval, it increases the access time compared with a TLB hit. The probability of a TLB hit can be represented as P% and the probability of a TLB miss as (1 - P)%.

Effective access time = P (t + m) + (1 - P) (t + km + m)

• t = time taken to access the TLB
• m = time taken to access the main memory
• k = 1 with single-level paging

The formula shows that effective access time can be decreased by increasing the TLB hit rate (P) or by avoiding multilevel paging.

Translation lookaside buffer advantages and disadvantages

The TLB is a memory type that is both cheaper and bigger than the register, and faster and smaller than the main memory. When a memory address is stored in the TLB and can be retrieved from there, the speed is enhanced. This is because the CPU doesn't have to access the main memory to access the page table multiple times. Instead, it can access the TLB, which is closer to the CPU, which speeds up access.

TLBs also provide the support required for multiuser computers to keep memory separate by having a user and a supervisor mode, and by using permissions on read/write bits to enable sharing.

One drawback of a TLB is that it can suffer performance issues from multitasking and code errors. This performance degradation, called a cache thrash, is caused by an ongoing computer activity that fails to progress due to excessive use of resources or conflicts in the caching system.

Translation lookaside residence and content-addressable memory

Most processors for desktops, laptops and servers include one or more TLBs in the MMU. TLBs are especially common in CPUs that use paged or segmented virtual memory. A TLB can reside between the CPU and its cache or between the CPU cache and the main memory. Some TLBs are also placed between the different levels of a multilevel cache. Others are implemented as content-addressable memory (CAM). The CAM search key is the virtual or logical address, while the search result is a physical address.

Learn memory management strategies to improve virtual machine performance, explore the differences between CPUs and microprocessors and see how to choose the best CPU for virtualization.