[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]
Re: Improve caching
> There was some discussion about this . And I have found this page
>  which describes optional page cache replacement algorithms in Linux.
>  http://marc.info/?l=netbsd-tech-kern&m=111806501516943&w=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
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 .
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.
 A. Borodin, R. El-Yaniv, "Online Computation and Competitive
Analysis", Cambridge University Press, 1998.
Main Index |
Thread Index |