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 flag);
extern void remember_page(void * mapping, unsigned long index, short flag);