Cache Algorithms

Cache algorithms are optimizing instructions – Algorithm s – that a Computer Program can follow to manage a Cache of information stored on the Computer . Cache size is usually limited, and if the cache is full, the computer (that is, the Programmer ) must decide which items to keep and which to discard to make room for new items.

Examples of caching algorithms are:

Least Recently Used discards the least recently used items first. Obviously, this 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. If a probabilistic scheme that almost always discards one of the least recently used items is sufficient, the Pseudo-LRU algorithm can be used which only needs one bit per cache item to work.

Least Frequently Used (least frequently used) counts how often an item is needed. Those that are used least often are discarded first.

Belady's Min – The ''most'' efficient caching algorithm would be to always discard the information that will not be needed for the longest time in the future. Since it is impossible to predict how far in the future information will be needed, this is not implementable in hardware, however (with pre-defined simulations) it can be used as a gauge as to the effectiveness of other algorithms.

Other things to consider:

Cost: keep those items that are expensive to obtain, e.g. those that take a long time to get.

Size: If items have different sizes, you may want to discard a large one to store several smaller ones.

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.

EXTERNAL LINKS

fully associative cache

set associative cache

direct mapped cache

Information About

Cache Algorithms