Jan Wieck wrote:
>Moving the Cache Directory Block (cdb) on a hit to the MRU position of
>the appropriate queue "is the bookkeeping" of this strategy. The whole
>algorithm is based on it, and I don't see yet how to avoid that without
>opening a huge can of worms that look like deadlocks. But I'll think
>about it for a while.
>
I feared that.
Are there strategies that do not rely on a global lock? The Linux kernel
uses a lazy LRU with referenced bits: on access, the referenced bit is
set. The freespace logic takes pages from the end of a linked list, and
checks that bit: if it's set, then the page is moved back to the top of
the list. Otherwise it's a candidate for replacement. Pages start at the
head of that pseudo-lru list, with the reference bit clear: that way a
page that is accessed only once has a lower priority than a frequently
accessed page. At least that's how I understand the algorithm.
-- Manfred