Re: Improve caching

[Eduardo Horvath <eeh%NetBSD.org@localhost>]

On Wed, 25 Nov 2009, Matthias Kretschmer wrote:

> Hi,
> 
> > There was some discussion about this [1]. And I have found this page  
> > [2] which describes optional page cache replacement algorithms in Linux.
> > 
> > [1] http://marc.info/?l=netbsd-tech-kern&m=111806501516943&w=2
> > [2] http://linux-mm.org/AdvancedPageReplacement
> 
> maybe it would be nice to exchange something like LRU/CLOCK by a
> randomized paging algorithm.  Deterministic online algorithm are at best
> k competitive (where k is the size of the fast memory in number of
> pages).  There are known randomized online algorithms which are 2H_k
> competitive against oblivious adversaries (where H_k is the k-th
> harmonic number).

Another option that might be worth investigating is to move pages 
immediately to the head of the active list when they take a protection 
(reference/write) fault.  This might result in a closer approximation to 
true LRU.  But it may also result in increased overhead.

Another thing to consider is moving buffer cache pages that are otherwise 
unreferenced to the inactive list immediately after each copy operation 
completes.  That should give preference to replacing those pages over 
replacing pages that are mapped into process address spaces.

Be prepared to make detailed performance measurements or, knowing the 
history of these mailing lists, you are likely to be flamed.

Eduardo