|
Size: 3090
Comment: update interface to reflect the CLOCK-Pro one
|
Size: 4072
Comment: move Rahul Iyer's CART stuff to its own page
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 1: | Line 1: |
| 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 basic assumptions behind LRU have been invalidated by streaming media, garbage collection and other things possible in large address spaces, 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. |
| Line 6: | Line 6: |
== Goals == * More robust in corner cases where LRU / use-once fail. * Able to deal with long inter-reference distances, as a second level cache. Eg. caching for a database or being a file server. * Clean implementation. * SMP scalable. * Still good performance as a generic VM. |
|
| Line 19: | Line 27: |
| extern int recently_evicted(void * mapping, unsigned long index, short objgen); extern int remember_page(void * mapping, unsigned long index, short objgen); |
extern int recently_evicted(struct address_space * mapping, unsigned long offset); extern int remember_page(struct address_space * mapping, unsigned long offset); |
| Line 23: | Line 31: |
| 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 ''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. |
| Line 25: | Line 33: |
| 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 ''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. |
| Line 27: | Line 35: |
| 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. | We use a hash of ''mapping->host->i_ino'' and ''mapping->host->i_sb'' (and/or possibly other fields) to keep things unique. === Status of Linux CART implementation by Rahul Iyer === Please see RahulIyerCART. == Advanced Replacement in other systems == Operating systems are not the only place where advanced cache replacement algorithms have been studied and implemented. Databases and web proxies also tend to have fancy replacement algorithms. Recently ARC was implemented in the [http://www.postgresql.org postgresql DB]. However, after it was discovered that ARC is patented (by IBM) it was removed again. You can see a patch that was sent to the ''pgsql-patches'' mail-list proposing that ARC be reverted back to LRU [http://archives.postgresql.org/pgsql-patches/2005-01/msg00253.php here]. More [http://www.varlena.com/varlena/GeneralBits/96.php details] about ARC removal from PostgreSQL. It looks like ARC has finally been [http://archives.postgresql.org/pgsql-patches/2005-02/msg00015.php replaced by the 2Q algorithm], which is a cache replacement algorithm designed for databases. == Benchmarking == Testing is an essencial part of implementing one of the above page replacement algorithms on Linux. This [http://www.linux-mm.org/PageReplacementTesting page] focuses on describing LRU worst cases and collecting benchmarks to exploit LRU deficiencies. For other pages in this category, see CategoryAdvancedPageReplacement |
The basic assumptions behind LRU have been invalidated by streaming media, garbage collection and other things possible in large address spaces, 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.
Goals
- More robust in corner cases where LRU / use-once fail.
- Able to deal with long inter-reference distances, as a second level cache. Eg. caching for a database or being a file server.
- Clean implementation.
- SMP scalable.
- Still good performance as a generic VM.
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.
Status of Linux CART implementation by Rahul Iyer
Please see RahulIyerCART.
Advanced Replacement in other systems
Operating systems are not the only place where advanced cache replacement algorithms have been studied and implemented. Databases and web proxies also tend to have fancy replacement algorithms.
Recently ARC was implemented in the [http://www.postgresql.org postgresql DB]. However, after it was discovered that ARC is patented (by IBM) it was removed again. You can see a patch that was sent to the pgsql-patches mail-list proposing that ARC be reverted back to LRU [http://archives.postgresql.org/pgsql-patches/2005-01/msg00253.php here].
More [http://www.varlena.com/varlena/GeneralBits/96.php details] about ARC removal from PostgreSQL.
It looks like ARC has finally been [http://archives.postgresql.org/pgsql-patches/2005-02/msg00015.php replaced by the 2Q algorithm], which is a cache replacement algorithm designed for databases.
Benchmarking
Testing is an essencial part of implementing one of the above page replacement algorithms on Linux.
This [http://www.linux-mm.org/PageReplacementTesting page] focuses on describing LRU worst cases and collecting benchmarks to exploit LRU deficiencies.
For other pages in this category, see CategoryAdvancedPageReplacement