Diff for "AdvancedPageReplacement"

Differences between revisions 42 and 43

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.

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.
PageReplacementRequirements

The replacement algorithms

ARC Adaptive Replacement Cache.
LIRS Low Inter-Reference Recency Set.
CLOCK-Pro an effective improvement of the CLOCK replacement, and the ClockProApproximation that Rik van Riel is planning to implement. Linux Weekly News has a nice article explaining CLOCK-Pro.
CAR Clock with Adaptive Replacement.

Linux implementations

Rahul Iyer's implementation of CART, RahulIyerCART
Rik van Riel's ClockProApproximation.
Rik van Riel's proposal for the tracking of NonResidentPages, which is used by both his ClockProApproximation and by Peter Zijlstra's CART and Clock-pro implementations.
Peter Zijlstra's CART PeterZCart
Peter Zijlstra's Clock-Pro PeterZClockPro2

NetBSD

NetBSD folks are also discussing better page replacement policies.

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 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 here.

More details about ARC removal from PostgreSQL.

It looks like ARC has finally been replaced by the 2Q algorithm, which is a cache replacement algorithm designed for databases.

Benchmarking

Testing is an essential part of implementing one of the above page replacement algorithms on Linux.

The PageReplacementTesting page points out problems with LRU worst cases and is used to collect benchmarks to demonstrate LRU deficiencies.

For other pages in this category, see CategoryAdvancedPageReplacement

-  ⇤ ← Revision 42 as of 2008-08-13 06:04:33 → 
  Size: 3710
  Editor: pdfwpr01
  Comment:
+   ← Revision 43 as of 2017-12-30 01:05:10 → ⇥
  Size: 3734
  Editor: localhost
  Comment: converted to 1.6 markup
-Deletions are marked like this.
+Additions are marked like this.
 Line 1:
-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 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 15:
- * [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.13.5210 ARC] Adaptive Replacement Cache. 
 * [http://www.cse.ohio-state.edu/hpcs/WWW/HTML/publications/abs02-6.html LIRS] Low Inter-Reference Recency Set.
 * [http://www.cse.ohio-state.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. Linux Weekly News has a nice article [http://lwn.net/Articles/147879/ explaining CLOCK-Pro].
 * [http://www.almaden.ibm.com/cs/people/dmodha/clockfast.pdf CAR] Clock with Adaptive Replacement.
+ * [[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.13.5210|ARC]] Adaptive Replacement Cache. 
 * [[http://www.cse.ohio-state.edu/hpcs/WWW/HTML/publications/abs02-6.html|LIRS]] Low Inter-Reference Recency Set.
 * [[http://www.cse.ohio-state.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. Linux Weekly News has a nice article [[http://lwn.net/Articles/147879/|explaining CLOCK-Pro]].
 * [[http://www.almaden.ibm.com/cs/people/dmodha/clockfast.pdf|CAR]] Clock with Adaptive Replacement.
 Line 20:
- * Rahul Iyer's implementation of CART, ["RahulIyerCART"]
+ * Rahul Iyer's implementation of CART, [[RahulIyerCART]]
 Line 22:
- * Rik van Riel's proposal for the tracking of NonResidentPages, which is used by both his ClockProApproximation and by Peter Zijlstra's [http://www.linux-mm.org/PeterZCart CART] and [http://linux-mm.org/PeterZClockPro2 Clock-pro] implementations.
 * Peter Zijlstra's CART ["PeterZCart"]
 * Peter Zijlstra's Clock-Pro ["PeterZClockPro2"]
+ * Rik van Riel's proposal for the tracking of NonResidentPages, which is used by both his ClockProApproximation and by Peter Zijlstra's [[http://www.linux-mm.org/PeterZCart|CART]] and [[http://linux-mm.org/PeterZClockPro2|Clock-pro]] implementations.
 * Peter Zijlstra's CART [[PeterZCart]]
 * Peter Zijlstra's Clock-Pro [[PeterZClockPro2]]
 Line 26:
-NetBSD folks are also discussing [http://marc.theaimsgroup.com/?l=netbsd-tech-kern&m=111806501516943&w=2 better] page replacement policies.
+NetBSD folks are also discussing [[http://marc.theaimsgroup.com/?l=netbsd-tech-kern&m=111806501516943&w=2|better]] page replacement policies.
 Line 31:
-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].
+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]].
 Line 33:
-More [http://www.varlena.com/varlena/GeneralBits/96.php details] about ARC removal from PostgreSQL.
+More [[http://www.varlena.com/varlena/GeneralBits/96.php|details]] about ARC removal from PostgreSQL.
 Line 35:
-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.
+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.