LRU has been obsoleted by large address spaces, streaming media and garbage collection, but until 2002 there weren't many replacements available that are suitable to be implemented in a general purpose OS. However, with the advent of LIRS, ARC, Clock-pro and CAR/CART algorithms, it looks like there could be a benefit to Linux in implementing something better than LRU or the unbalanced use-once that is in use currently.
The only problem is, the advanced page replacement algorithms need to keep a history of recently evicted pages, and we don't want to spend too much memory or cpu on that. This page is a template for brainstorming on how we can implement such a framework, and on which of the advanced page replacement algorithms we should experiment with.
Please feel free to edit this page, after having created an account.
The replacement algorithms:
[http://www.almaden.ibm.com/StorageSystems/autonomic_storage/ARC/index.shtml ARC] Adaptive Replacement Cache.
[http://www.cs.wm.edu/~sjiang/lirs.htm LIRS] Low Inter-Reference Recency Set.
[http://www.cs.wm.edu/hpcs/WWW/HTML/publications/abs05-3.html CLOCK-Pro] an effective improvement of the CLOCK replacement.
[http://www.almaden.ibm.com/cs/people/dmodha/clockfast.pdf CAR] Clock with Adaptive Replacement.
Proposals for dealing with non-resident pages:
(TBD - Rik will add his idea shortly, but feel free to add yours too)