Re: queued spinlock code and results

[Nick Piggin <npiggin@suse.de>]

On Tue, Jul 10, 2007 at 01:52:47PM -0700, Christoph Lameter wrote:
> On Sun, 8 Jul 2007, Andi Kleen wrote:
> 
> > I would say the main drawback of switchable and queued locks 
> > would be also that they require a larger spinlock_t thus increasing
> > cache usage
> 
> Right. Zoran Radovic has shown that queued locks are inferior 
> to other approaches. The best approach that he found in his research were 
> the HBO locks that are somewhat more intelligent form of spinlocks.
> 
> http://user.it.uu.se/~zoranr/
> http://www.it.uu.se/research/group/uart/projects/nucasynch/
> 
> Paper on the issue with measurements:
> http://www.it.uu.se/research/publications/lic/2003-008/2003-008.pdf


OK, maybe I do have my terminology wrong -- we'll call them FIFO locks
or ticket locks. The point is not to improve performance of the contended
case (although they may have slightly better contended case characteristicds),
but to improve worst case latency and improve fairness.

BTW. some advanced congestion algorithms like HBO may find these ticket
locks useful because you can see immediately how many CPUs are contending
the lock, and spinners know how many CPUs are in front of them. That info
could be fed into the spin backoff scheme.