Cache replacement policies
Algorithms that decide what to remove from a full cache.
Cache replacement policies are algorithms used by computer programs or hardware-maintained structures to manage a cache of information. They optimize performance by deciding which items to discard when the cache is full, balancing hit rate and latency.
- field
- Computing
- known_for
- Managing cache memory by selecting which items to evict when full
- key_metrics
- Hit ratio and latency
- example_algorithms
- Bélády's optimal, LRU, MRU, FIFO, LIFO, Random, SIEVE, TLRU, SLRU
Lore & Background
Cache replacement policies are optimizing instructions that manage a cache of information, improving performance by keeping recent or often-used data in faster memory. When the cache is full, the algorithm must choose which items to discard to make room for new data. The average memory reference time is calculated as T = m × Tm + Th + E, where m is the miss ratio, Tm is main-memory access time on a miss, Th is cache latency, and E includes secondary effects like queuing in multiprocessor systems. Two primary figures of merit are latency and hit ratio; faster replacement strategies typically track less usage information, while more efficient ones track more to improve hit rate.
Reader's Guide
Cache replacement policies are fundamental to computer performance, as they directly affect the hit ratio and latency of a cache. The most efficient theoretical algorithm is Bélády's optimal algorithm, which discards information not needed for the longest time, but it is unfeasible in practice because future access patterns cannot be predicted. Practical algorithms include LRU, which discards least recently used items; MRU, which discards most recently used items; FIFO, which evicts in order of addition; and Random replacement, which requires no access history. Each represents a compromise between hit rate and latency. For example, LRU is a family of algorithms including 2Q and LRU/K, while MRU is best for looping sequential reference patterns. SIEVE is designed for web caches, using lazy promotion and quick demotion to handle high one-hit-wonder ratios. TLRU adds time-awareness for content with valid lifetimes. The choice of policy depends on the application: video and audio streaming often have near-zero hit ratios, and some algorithms like LRU can suffer from cache pollution by streaming data. Ultimately, no single policy is universally best, and effectiveness is measured against benchmark applications.
Did You Know?
- Bélády's optimal algorithm is also called the clairvoyant algorithm, but it is unfeasible in practice because future information needs cannot be predicted.
- Random replacement does not require keeping any access history and has been used in ARM processors due to its simplicity.
- SIEVE uses a single FIFO queue and a moving hand to evict objects, quickly removing newly inserted objects that are often one-hit wonders.
- MRU cache algorithms have more hits than LRU for random access patterns and repeated scans over large datasets.
Frequently Asked Questions
What is Cache replacement policies?
Cache replacement policies are decision-making algorithms that determine which data items to kick out of a full cache so that new ones can be stored. They operate in both software and hardware contexts to keep frequently needed information readily accessible.
What role does Cache replacement policies play?
Its core job is to select the least valuable cached entry for eviction whenever space runs out, ensuring the cache holds the most useful data. By making smart discard choices, it directly influences how quickly a system can serve repeated requests.
Which well-known algorithms are part of the Cache replacement policies cast?
The lineup includes classic entries like LRU, FIFO, and Random, as well as more sophisticated ones such as SIEVE, TLRU, and SLRU. Bélády's optimal algorithm serves as the theoretical benchmark no real policy can actually achieve.
How do fans measure whether Cache replacement policies is doing a good job?
Two key metrics define its performance: hit ratio (how often a requested item is already in the cache) and latency (how long it takes to retrieve or replace data). A good policy keeps the hit ratio high while keeping latency low.
Why is Cache replacement policies important in computing?
Without a smart eviction strategy, caches would fill up with stale or rarely used data, forcing the system to repeatedly fetch information from slower storage. Effective replacement policies are a foundational layer that keeps modern processors, databases, and web servers running at acceptable speeds.
More in Algorithms And Data Structures 1-24
Elsewhere in the Algorithms And Data Structures universe
Spotted an error? Know more?
This is a living reference — every entry is fact-audited, and reader corrections feed straight into our audit queue. Suggest an edit · See this site's audit record