Re: Page replacement algorithm in buffer cache

Sent from my iPad

On 22-Mar-2013, at 11:28, Amit Kapila <amit.kapila@huawei.com> wrote:

> On Friday, March 22, 2013 10:22 AM Atri Sharma wrote:
>> Hello all,
>>
>> Sorry if this is a naive question.
>>
>> I was going through Greg Smith's slides on buffer
>> cache(http://www.westnet.com/~gsmith/content/postgresql/InsideBufferCac
>> he.pdf).
>> When going through the page replacement algorithm that we use i.e.
>> clocksweep algorithm, I felt a potential problem in our current
>> system.
>>
>> Specifically, when a new entry is allocated in the buffer, it's
>> USAGE_COUNT is set to 1. On each sweep of the algorithm, the
>> USAGE_COUNT is decremented and an entry whose  USAGE_COUNT becomes
>> zero is replaced.
>
> Yes, it is replaced but in the next clock sweep pass, not immediately after
> making 0.
> So till the time of next pass if nobody accesses the buffer and all other
> buffers have higher count, it can be replaced.
> Also the buffer, it has returned for which the usage count becomes 1, it
> will come to reduce the usage count only in next pass.
> So in whole, I think it needs 2 passes for a freshly returned buffer to be
> re-used incase no one uses it again.
>
> With Regards,
> Amit Kapila.
>

Hmm,so in the second pass,it gets replaced,right?

I think that if the initialization of USAGE_COUNT starts at the maximum allowed value instead of one, we can have a
bettersolution to this problem. 

Another,more complex solution could be to introduce an ageing factor as well.

Regards,

Atri