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):

extern int recently_evicted(void * mapping, unsigned long index, short objgen);
extern void remember_page(void * mapping, unsigned long index, short objgen, short state);

The recently_evicted function is queried by the pagein or page cache allocation code, to determine whether the data at the offset index from the page cache or process object mapping generation objgen was recently evicted. The function returns -1 if the page was not found, or a number matching the state argument if it was found.

The remember_page function is called by the pageout code, telling the non-resident page management code to remember that a page at offset index from mapping (generation objgen) was just paged out, and the page was on the state pageout list. Since we want to keep the non-resident page structure as small as possible, we'll only be using a few bits from objgen and state; quite possibly as few as 3 or 4 bits from objgen and 1 bit from state!

The objgen or object generation number is used to prevent false positives when a mapping_struct or mm_struct gets freed and reallocated. Then the mapping pointer will point to a different object, and we need a way to tell that the non-resident entries do not refer to the new user of the structure. The alternative to using an object generation number would be invalidating all entries when the object behind the mapping pointer is freed, which would mean a much larger data structure.