Re: [PATCHES] update i386 spinlock for hyperthreading

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