Re: ARC patent

On Fri, Jan 21, 2005 at 03:42:38PM +0100, Manfred Koizar wrote:
> On Fri, 21 Jan 2005 02:31:40 +0200, Hannu Krosing <hannu@tm.ee> wrote:
> >2) Another simple, but nondeterministic, hack would be using randomness,
> >i.e. 
> >
> >  2.1) select a random buffer in LR side half (or 30% or 60%) of 
> >       for replacement. 
> >
> >  2.2) dont last accessed pages to top of LRU list immediately, 
> >       just push them uphill some amount, either random, or 
> >       perhaps 1/2 the way to top at each access.
> 
> Sounds good, but how do find the middle of a linked list?  Or the other
> way round:  Given a list element, how do you find out its position in a
> linked list?  So the only approach that is easily implementable is
> 
> 2.3) If a sequential scan hint flag is set, put the buffer into the
>      free list at a random position.
> 

If we use the clock algorithm as an approximation to LRU, we can avoid
a lot of the MRU/LRU churn. Then the seq. scan hint could just be another
type of clock bit.

Ken