tech-kern archive

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]

Re: Improve caching


> There was some discussion about this [1]. And I have found this page  
> [2] which describes optional page cache replacement algorithms in Linux.
> [1]
> [2]

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


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.

Home | Main Index | Thread Index | Old Index