Ühel kenal päeval (reede, 21. jaanuar 2005, 15:42+0100), kirjutas
Manfred Koizar:
> 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?
Ok, we are back to using 2 lists - one for 1st and one for 2nd half and
spill the tail of 1st list over to 2nd when it growns.
But the fundamental fact of using two lists seems to be the first claim
in IBM's patent ;(
Not that I think that using 2 lists to know where the midpoint of linked
list is is patentable, but if we deside start acting scared of all
things in patent applications then we should be aware of it.
> Or the other
> way round: Given a list element, how do you find out its position in a
> linked list?
To know an *approximate* position, we could
1) have an independent periodic process that just scans the list and
records the position
2) each node inserted at head or tail is recorded true position
3) each node inserted in middle is given the same position as its
predecessor.
This would not be too expensive, but OTOH I can't think of a way to use
this onfo right now. An additional array of node pointers in list order
populated in step 1) could have more use.
> 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.
--
Hannu Krosing <hannu@tm.ee>
