Speeding Up Address Translation

Swapping pages in and out of main memory can be expensive. Every access to main memory means one memory access to obtain the physical address and a second access to get the data. To reduce this overhead, a Translation Lookaside Buffer (TLB) has been created. The TLB acts as a cache for page table entries that map to physical pages only. A TLB works on the principle of locality of reference, both temporal and spatial locality.

Given a virtual page number the memory management unit looks up the TLB to see if it exists. If the translation exists, we get a “TLB hit” and the physical page number is used to form the address. If the translation does not exist, a “TLB miss” is registered. This page might be there in memory, just not in the TLB. In this case, the translation is missing and the CPU loads the translation from the page table to the TLB. But if the translation is not in the page table, then a page fault has occurred. In this case, an exception is invoked. Therefore a page fault is an interrupt triggered by the MMU.

A page fault can be generated due to the following:

• Page is not resident,
• Page is invalid,
• Permission is not enough for operation.

The page that generates the page fault will have to be made available – another page will have to be replaced in the page table. Below are a few page replacement policies that might be implemented.

1. FIFO — First in/First Out A page that was in physical memory the longest is replaced.
2. LRU — Least Recently Used A page that has not been accessed for the longest time is replaced. Here the principle of locality is exploited. A page that is referenced will most likely be referenced again.