Linux implements an LRU based page replacement algorithm. Although simple, it is suboptimal for a wide range of important workloads.

At the present moment there are a few experimental implementations of advanced replacement algorithms being developed and discussed.

This page attempts to detail known LRU deficiencies, along with benchmarks to highlight them.

Frequency

The most significant issue with LRU is that it uses too little information to base the replacement decision: recency alone.

It does not take frequency of page accesses into account.

A good example from "The LRU-K Page-Replacement Algorithm for Database Disk Buffering" <http://www.cs.umb.edu/~poneil/publist.html>:

Consider a multi-user database application, which references randomly chosen customer records through a clustered B-tree indexed key, CUST-ID, to retrieve desired information (cf.-A]). Assume simplistically that 20,000 customers exist, that a customer reeord is 2000 bytes in length, and that space needed for the B-tree index at the leaf level, free space included, is 20 bytes for each key entry. Then if disk pages contain 4000 bytes of usable space and ean be packed full, we require 100 pages to hold the leaf level nodes of the B-tree index (there is a sin- gle B-tree root node), and 10,000 pages to hold the reeords. The pattern of reference to these pages (ignoring the B-tree root node) is clearly: 11, Rl, 12, R2, 13, R3, . . .. alternate references to random index leaf pages and record pages. If we can only afford to buffer 101 pages in memory for this application, the B-tree root node is automatic; we should buffer all the B-tree leaf pages, since each of them is referenced with a probability of .005 (once in each 200 general *page* references), while it is clearly wasteful to displace one of these leaf pages with a data *page*, since data pages have only .00005 probability y of referenee (once in each 20,000 general *page* references). Using the LRU *algorithm*, however, the pages held in memory buffers will be the hundred most recently referenced ones. To a first approximation, this means 50 B-tree leaf pages and 50 record pages. Given that a *page* gets no extra credit for being referenced twice in the recent past and that this is more likely to happen with B-tree leaf pages, there will even be slightly more data pages present in memory than leaf pages. This is clearly inappropriate behavior for a very common paradigm of disk accesses.