Ü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 <[EMAIL PROTECTED]> 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 <[EMAIL PROTECTED]> ---------------------------(end of broadcast)--------------------------- TIP 7: don't forget to increase your free space map settings
