Translation Look-Aside Buffer

A cache that contains page table entries. Given a virtual address a processor will examine the TLB, and if the desired page table entry is present (a TLB hit) then the frame number is retrieved and the real address is formed. If the desired page table entry is not found (a TLB miss), the processor uses the page number to index the process page table and examine the corresponding page table entry to form the real address. if the page is present in main memory then the processor can retreive the frame number from the page table entry to form the real address. The processor then updates the TLB to include this new page table entry. If the desired page is not in main memory, a page fault is issued. At this point, the operating system is invoked to load the page and update the page table.

The Translation Look-aside Buffer (TLB) is a part of most Memory Management Units (MMUs), used to increase address translation speed. It caches recently used portions of the page table, used to map virtual page numbers to physical memory locations.

Purpose

Because the page table is stored in main memory, an un-cached paged RAM system will take twice as long for each access: one clock for the page table entry, and one for the actual data. This would become a major performance hit, especially when modern CPUs outpace their main memory by an order of magnitude.

As with most such problems, the solution is to cache the information required most often: the page table entry. Since the page table is being cached, certain elements of its metadata also need to be duplicated in the TLB. These include the dirty bit, which is set when the page is modified, and the reference bit, used to track page usage for the page replacement algorithm.

Operation

On every memory access, the memory controller looks for the virtual page number in the TLB. If it is found (a TLB hit), the reference bit is set (as is the dirty bit, if the access is a write), and the physical page number is used to determine the physical address; then, the actual memory access is made.

However, if the virtual page number is not in the TLB (a TLB miss), the situation becomes slightly more complicated. The memory controller cannot assume that this is only a TLB miss, and the page accessed is in physical memory somewhere, because there is the possibility that a page fault has occurred.

Therefore, the page table is checked for the accessed page. If the page is in physical memory, the entry is loaded into the TLB, and the access is retried as if a hit ocurred. If the page is not in memory, a page fault exception must be generated, as normal.

Interestingly, handling a TLB miss can be done equally well in software or hardware. In fact, in superscalar processors, handling misses in software can even be an advantage, allowing instructions unaffected by the memory access to continue executing, instead of waiting for the TLB hardware to finish. However, due to the relatively small size of the buffer, TLB misses are far more likely to occur than page faults, and so the software algorithm cannot afford to be as inefficient as the one used for page replacement can.

Performance Implications

In a protected memory system, a context switch implies the use of a new page table. Clearly then, the old page table must have the dirty and reference bits synchronised with the TLB, which must then be flushed of all entries. The TLB must then be slowly filled as pages are accessed, according to the operation outlined above. This can be a fairly expensive operation, and when rapid context switching occurs it can severely impact performance.

Implementation

Typical parameters for a Translation Look-aside Buffer are:

• Size: 32 to 8192 page table entries (each around 4 to 8 bytes in size)
• Access time: less than one clock cycle
• Miss penalty: 10 to 30 cycles
• Miss rate: 0.01% to 1%
• Associativity: 2-way to fully associative

References:

Computer Organization & Design, Patterson and Hennessy, Morgan Kaufman

Virtual memory systems typically have a page table with a list of virtual memory pages and their corresponding physical memory locations. However, the page table resides in memory itself. The result is that to access a virtual memory address requires two memory accesses: one to the page table to find the physical memory address, and then a second to access the actual address. This is incredibly inefficient.

A translation lookaside buffer (sometimes abbreviated TLB) is found in most processors with virtual memory support. It makes use of the fact that most programs typically only work on a small area of memory at once. When a memory address is accessed, its mapping is stored in a fully-associative cache inside the processor. The next time the same page is accessed, its physical mapping can be found quickly.

The translation lookaside buffer is the reason context switches can have big performance penalties. Every time the OS switches context, the entire buffer is flushed. When the process resumes, it must be rebuilt from scratch. Too many context switches will therefore cause an increase in cache misses and degrade performance. The buffer cannot be saved and restored as there is no guarantee in a virtual memory system that all virtual memory pages will exist in the same physical memory locations as they did before the process was suspended.