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
Rik's interface (for implementation, see NonResidentPages):
* Keeps track of whether a non-resident page was recently evicted * and should be immediately promoted to the active/frequency list. * * The pageout code stores a recently evicted page in this cache * by calling remember_page(mapping/mm, offset/vaddr, generation) * and can look it up in the cache by calling recently_evicted() * with the same arguments. */ extern int recently_evicted(void * mapping, unsigned long index, short objgen); extern void remember_page(void * mapping, unsigned long index, short objgen, short flag);