From Wikipedia, the free encyclopedia

In computing, cache algorithms (also frequently called replacement algorithms or replacement policies) are optimizing instructions – algorithms – that a computer program or a hardware-maintained structure can follow to manage a cache of information stored on the computer. Cache size is usually limited, and if the cache is full, the algorithm must choose which items to discard to make room for the new ones.

The most efficient caching algorithm would be to always discard the information that will not be needed for the longest time in the future. This optimal result is referred to as Belady's minimum. Since it is impossible to predict how far in the future information will be needed, this is not implementable in practice. It can be calculated only after an experiment, compare the effectiveness of actually used cache algorithm with optimal one.

Examples of caching algorithms are:

• Least Recently Used (LRU): discards the least recently used items first. This algorithm requires keeping track of what was used when, which is expensive if one wants to make sure the algorithm always discards the least recently used item. General implementations of this technique require to keep "age bits" for cache-lines and track the "Least Recently Used" cache-line based on age-bits. In such implementation, every time a cache-line is used, the age of all other cache-lines changes.
• Most Recently Used (MRU): discards, in contrast to LRU, the most recently used items first. This caching mechanism is used when access is unpredictable, and determining the least most recently used section of the cache system is a high time complexity operation. A common example of this is database memory caches.
• Pseudo-LRU (PLRU): For caches with large associativity (generally >4 ways), the implementation cost of LRU becomes prohibitive. If a probabilistic scheme that almost always discards one of the least recently used items is sufficient, the PLRU algorithm can be used which only needs one bit per cache item to work.
• Least Frequently Used (LFU): LFU counts how often an item is needed. Those that are used least often are discarded first.
• Adaptive Replacement Cache (ARC): constantly balances between LRU and LFU, to improve combined result.

Other things to consider:

• Items with different cost: keep items that are expensive to obtain, e.g. those that take a long time to get.
• Items taking up more cache: If items have different sizes, the cache may want to discard a large item to store several smaller ones.
• Items that expire with time: Some caches keep information that expires (e.g. a news cache, a DNS cache, or a web browser cache). The computer may discard items because they are expired. Depending on the size of the cache no further caching algorithm to discard items may be necessary.

Various algorithms also exist to maintain cache coherency. This applies only to situation where multiple independent caches are used for the same data (for example multiple database servers updating the single shared data file).

• Page replacement algorithm

• fully associative cache
• set associative cache
• direct mapped cache