On Wed, Feb 16, 2005 at 12:33:38PM -0500, Tom Lane wrote:
> "Jim C. Nasby" <decibel@decibel.org> writes:
> > The advantage of using a counter instead of a simple active
> > bit is that buffers that are (or have been) used heavily will be able to
> > go through several sweeps of the clock before being freed. Infrequently
> > used buffers (such as those from a vacuum or seq. scan), would get
> > marked as inactive the first time they were hit by the clock hand.
>
> Hmm. It would certainly be nearly as easy to adjust a counter as to
> manipulate the RECENTLY_USED flag bit that's in the patch now. (You
> could imagine the RECENTLY_USED flag bit as a counter with max value 1.)
>
> What I'm envisioning is that pinning (actually unpinning) a buffer
> increments the counter (up to some limit), and the clock sweep
> decrements it (down to zero), and only buffers with count zero are taken
> by the sweep for recycling. That could work well, but I think the limit
> needs to be relatively small, else we could have the clock sweep having
> to go around many times before it finally frees a buffer. Any thoughts
> about that? Anyone seen any papers about this sort of algorithm?
>
I have seen this algorithm described as a more generalized clock type
algorithm. As the size of the counter increases, up to the number of
buffers, the clock algorithm becomes LRU. One bit is the lightest
weight approximation. Increasing the number of bits or a count makes
the clock algorithm more closely approximate LRU. You need to balance
how long it takes to find a free buffer. That time increases as the
count size increases.
Ken