Comparison of MFU and LRU page replacement algorithms
When does MFU (Most Frequently Used) page replacement algorithm have better performance than LRU (Least Frequently Used)? When is it worse than LRU? Where can I find information beyond the basic definition of the MFU page replacement algorithm?
Answer
Typically, I've seen an MFU cache used as the primary, backed by a secondary cache that uses an LRU replacement algorithm (an MRU cache). The idea is that the most recently used things will remain in the primary cache, giving very quick access. This reduces the "churn" that you see in an MRU cache when a small number of items are used very frequently. It also prevents those commonly used items from being evicted from the cache just because they haven't been used for a while.
MFU works well if you have a small number of items that are referenced very frequently, and a large number of items that are referenced infrequently. A typical desktop user, for example, might have three or four programs that he uses many times a day, and hundreds of programs that he uses very infrequently. If you wanted to improve his experience by caching in memory programs so that they will start quickly, you're better off caching those things that he uses very frequently.
On the other hand, if you have a large number of items that are referenced essentially randomly, or some items are accessed slightly more often than, or items are typically referenced in batches (i.e. item A is accessed many times over a short period, and then not at all), then an LRU cache eviction scheme will likely be better.