1442
Comment:
|
2367
|
Deletions are marked like this. | Additions are marked like this. |
Line 7: | Line 7: |
----- The replacement algorithms: |
== The replacement algorithms == |
Line 13: | Line 11: |
* [http://www.cs.wm.edu/hpcs/WWW/HTML/publications/abs05-3.html CLOCK-Pro] an effective improvement of the CLOCK replacement. | * [http://www.cs.wm.edu/hpcs/WWW/HTML/publications/abs05-3.html CLOCK-Pro] an effective improvement of the CLOCK replacement, and the ClockProApproximation that Rik van Riel is planning to implement. |
Line 16: | Line 14: |
---- | == Proposals for dealing with non-resident pages == |
Line 18: | Line 16: |
Proposals for dealing with non-resident pages: | Rik's interface (for implementation, see NonResidentPages, code and patches on [http://surriel.com/patches/nonresident my home page]): |
Line 20: | Line 18: |
(TBD - Rik will add his idea shortly, but feel free to add yours too) | {{{ extern int recently_evicted(struct address_space * mapping, unsigned long offset); extern int remember_page(struct address_space * mapping, unsigned long offset); }}} The ''recently_evicted'' function is queried by the pagein or page cache allocation code, to determine whether the data at the offset ''offset'' from the page cache or process object ''mapping'' was recently evicted. The function returns 0 if the page was not found, 1 if the page 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 ''offset'' from ''mapping'' was just paged out. We use a hash of ''mapping->host->i_ino'' and ''mapping->host->i_sb'' (and/or possibly other fields) to keep things unique. |
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, and the ClockProApproximation that Rik van Riel is planning to implement.
[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, code and patches on [http://surriel.com/patches/nonresident my home page]):
extern int recently_evicted(struct address_space * mapping, unsigned long offset); extern int remember_page(struct address_space * mapping, unsigned long offset);
The recently_evicted function is queried by the pagein or page cache allocation code, to determine whether the data at the offset offset from the page cache or process object mapping was recently evicted. The function returns 0 if the page was not found, 1 if the page 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 offset from mapping was just paged out.
We use a hash of mapping->host->i_ino and mapping->host->i_sb (and/or possibly other fields) to keep things unique.