On Thu, 21 Jun 2007 10:31:53 -0700 (PDT)
Linus Torvalds <torvalds@linux-foundation.org> wrote:
This reminds me Nick's proposal of 'queued spinlocks' 3 months ago
Maybe this should be re-considered ? (unlock is still a non atomic op,
so we dont pay the serializing cost twice)
http://lwn.net/Articles/227506/
extract :
Implement queued spinlocks for i386. This shouldn't increase the size of
the spinlock structure, while still able to handle 2^16 CPUs.
The queued spinlock has 2 fields, a head and a tail, which are indexes
into a FIFO of waiting CPUs. To take a spinlock, a CPU performs an
"atomic_inc_return" on the head index, and keeps the returned value as
a ticket. The CPU then spins until the tail index is equal to that
ticket.
To unlock a spinlock, the tail index is incremented (this can be non
atomic, because only the lock owner will modify tail).
Implementation inefficiencies aside, this change should have little
effect on performance for uncontended locks, but will have quite a
large cost for highly contended locks [O(N) cacheline transfers vs
O(1) per lock aquisition, where N is the number of CPUs contending].
The benefit is is that contended locks will not cause any starvation.
Just an idea. Big NUMA hardware seems to have fairness logic that
prevents starvation for the regular spinlock logic. But it might be
interesting for -rt kernel or systems with starvation issues.
-
