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

**To**:**Adam Hamsik <haaaad%gmail.com@localhost>****Subject**:**Re: Improve caching****From**:**Matthias Kretschmer <kretschm%cs.uni-bonn.de@localhost>**- Date: Wed, 25 Nov 2009 16:28:55 +0100

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.

**Follow-Ups**:**Re: Improve caching***From:*Thor Lancelot Simon

**Re: Improve caching***From:*Eduardo Horvath

**References**:**Improve caching***From:*Davide Italiano

**Re: Improve caching***From:*Adam Hamsik

- Prev by Date:
**Intel I55 chipset supported?** - Next by Date:
**Re: Intel I55 chipset supported?** - Previous by Thread:
**Re: Improve caching** - Next by Thread:
**Re: Improve caching** - Indexes: