Re: Improve caching

[Matthias Kretschmer <kretschm%cs.uni-bonn.de@localhost>]

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

A quick search using Google if there is some OS implementing a
randomized algorithm like randomized marking, but I haven't found any
hints.  So I cannot point out to any pratical experiments.

The theoretical description of the randomized marking algorithm can be
found in textbooks like [3].

Regards
Matthias.

P.S.: Using a PRNG would of course make the whole algorithm
deterministic in theory, but for pratical purposes it might yield a nice
performing algorithm anyway.  One may do not need to use any fancy PRNG
and a reasonable fast should be ok.

[3] A. Borodin, R. El-Yaniv, "Online Computation and Competitive
    Analysis", Cambridge University Press, 1998.