Cache replacement policies

Computers keep things they use a lot.

Sometimes the fast spot gets full. The computer must pick something to toss. It needs room for new things.

One way is to pick the newest thing. This is like a stack of books. You take the top one first.

Another way is to pick the oldest thing. This is like a line at a store. The first person in line leaves first.

Some ways pick what was used a long time ago. This helps keep the most useful things. It is a smart way to stay organized.

Computers use a fast storage area called a cache. It keeps data that the computer uses often. This helps the computer work much faster. But the cache has a small size. When it is full, the computer must pick something to toss. This set of steps is called a replacement policy.

One way is called First In, First Out. This works like a line at a store. The oldest item is the first to leave. Another way is Last In, First Out. This works like a stack of books. The newest item is tossed first.

Many computers use a way called Least Recently Used, or LRU. This method looks at when things were used. It tosses the item that has not been used for the longest time.

Some systems use Most Recently Used, or MRU. This tosses the item used most recently. This can be helpful if a computer scans files in a loop.

Other ways are simpler. Random replacement picks an item by chance. It does not need to track history. This is very simple to do.

Computers use a fast storage area called a cache to work quickly. This cache keeps data that is used often or very recently. Using a cache makes a computer faster because it is cheaper to access. However, a cache has a limited size. When the cache is full, the computer must choose something to discard. This choice is made by a cache replacement policy. These policies are sets of instructions that manage the information in the cache.

There are many ways these policies work. One way is called First In, First Out, or FIFO. This method removes items in the exact order they were added. Another way is Last In, First Out, or LIFO. This works like a stack where the newest item is removed first. Some systems use Random Replacement, which picks an item to toss by chance. This is a simple method used in ARM processors.

Many computers use a policy called Least Recently Used, or LRU. This method tracks when items are used. It discards the item that has not been used for the longest time. It can be hard to do because the computer must keep track of usage. Because of this, many designers use Pseudo-LRU instead. This is a simpler version that uses just one bit per item. It uses a binary tree of pointers to find what to replace.

Researchers have studied many different strategies over the years. In 1985, Chou and DeWitt spoke at the 11th VLDB conference. They said Most Recently Used, or MRU, is best for certain patterns. MRU discards the item used most recently. This is helpful when a computer scans files in a loop. Other experts like Paul V. Bolotoff wrote about cache principles in 2007. They noted that streaming video can sometimes fill a cache with data that is only used once.

Understanding these policies helps us see how computers handle hard jobs. A perfect policy is called Bélády's algorithm. It would discard the item that is not needed for the longest time. This is called the clairvoyant algorithm because it knows the future. However, computers cannot actually predict the future, so this is not possible in real life. We can only compare our real policies to this ideal version. This helps us find the best balance between speed and accuracy.

Cache replacement policies are essential algorithms used to manage a computer's cache memory. A cache is a small, high-speed storage area that keeps recent or frequently used data. Accessing a cache is much faster and computationally cheaper than accessing main memory. However, because a cache has limited space, it eventually becomes full. When new data must be stored, the system must use a replacement policy to decide which existing item to discard.

To understand how well a cache works, engineers look at two main figures of merit: latency and hit ratio. The hit ratio describes how often the system finds the requested item in the cache. A higher hit ratio means the cache is working effectively. Latency is the time it takes for the cache to return an item after it is requested. There is a constant trade-off between these two factors. More efficient strategies track more usage information to improve the hit ratio. However, tracking this extra information can increase latency, making the system slower.

Computer scientists have developed several different types of policies to handle these decisions. One theoretical ideal is Bélády's algorithm, also called the optimal replacement policy or the clairvoyant algorithm. This policy would always discard the item that will not be needed for the longest time in the future. Because a computer cannot actually predict the future, this algorithm is unfeasible for real-world use. Instead, it serves as a benchmark. Engineers use it to calculate the practical minimum for error and compare it to real algorithms.

Simple queue-based policies are another common category. First In, First Out (FIFO) treats the cache like a queue. It evicts blocks in the exact order they were added, regardless of how often they are used. Conversely, Last In, First Out (LIFO) behaves like a stack. In LIFO, the most recently added block is the first one to be evicted. Some systems use Random Replacement (RR), which simply selects an item to discard by chance. This method requires no access history and is used in ARM processors due to its simplicity.

Recency-based policies are more complex but often more effective. The Least Recently Used (LRU) algorithm discards items that have not been accessed for the longest time. This requires tracking "age bits" for cache lines to monitor usage. Because full LRU can be expensive to implement in hardware, many designers use Pseudo-LRU (PLRU). PLRU uses a binary tree of one-bit pointers to approximate the LRU decision. This reduces hardware costs and power usage while maintaining a similar hit ratio.

Other specialized policies address specific data patterns. Most Recently Used (MRU) discards the item that was used most recently. While this sounds counterintuitive, researchers like Chou and DeWitt noted in 1985 that MRU is best for repeated scans of large datasets. In these cyclic patterns, MRU often achieves more hits than LRU. Another variant is Segmented LRU (SLRU), which divides the cache into probationary and protected segments. This helps ensure that only data accessed at least twice reaches the protected area.

Modern networking and web caching also require unique approaches. The SIEVE algorithm was designed for web caches like Content Delivery Networks. It uses a single FIFO queue with a moving hand to select objects for eviction. It employs "lazy promotion" to avoid updating the data structure during every cache hit. For network applications, Time-Aware, Least Recently Used (TLRU) is used. TLRU uses a timestamp called Time to Use (TTU) to regulate content based on its lifetime. This ensures that short-lived or unpopular content is replaced quickly to make room for new data.