Ticket spinlocks

Posted Feb 11, 2008 15:27 UTC (Mon) by PaulMcKenney (✭ supporter ✭, #9624)
In reply to: Ticket spinlocks by Nick
Parent article: Ticket spinlocks

Indeed, you do have to have two tasks spinning on the lock before the NMI/IRQ delay could
possibly cause a problem.  So I also hope that this effect is not a problem in practice, but
as you say, testing and experience will be required.

And ticket locks do have nice real-time properties, as they get rid of the possibility of
starvation!

Ticket spinlocks

Posted Feb 12, 2008 17:45 UTC (Tue) by bgamsa (guest, #33057) [Link] (3 responses)

Has anyone looked at MCS locks recently in the context of Linux and modern hardware. I believe it has more requirements in terms of hardware primitives, but it does provide queueing and local spinning.

Ticket spinlocks

Posted Feb 12, 2008 18:08 UTC (Tue) by PaulMcKenney (✭ supporter ✭, #9624) [Link] (2 responses)

We did take a look a few years ago.  Of course, pure MCS locks have an incompatible API, but
the K42 folks at IBM Research came up with a variant of MCS locks that matched the
Linux-kernel spin_lock() primitives.  If I remember correctly, MCS locks outperformed the
various NUMA-aware locking primitives, but were outperformed by simple spinlocks.

I would expect that ticket locks would out-perform MCS locks at low contention levels (the
common case in modern Linux kernels).  I am not sure how MCS locks and ticket locks would
compare at high levels of contention -- the ticket locks avoid the "thundering herd" problem,
so might do quite well.

Any benchmark results out there?

Ticket spinlocks

Posted Jul 28, 2008 22:35 UTC (Mon) by okeydoke (guest, #46751) [Link] (1 responses)

Ticket spinlocks perform terribly for uncontested and highly contested cases. Test cases on
LKML do not show any of this (a very trivial test case was done that does not show lock *and*
unlock cost).

Here are relevant numbers on 16-core (8x2) AMD64 machine:
Highly contested, MCS has 30724 a/s (average) and ticket locks have 6315 a/s (average). In the
uncontested case, MCS has 836744 a/s (average) and ticket locks have 688817 a/s (average).
Both implement FIFO fairness, anyways, so I do not expect relevance WRT "thundering herd"
problem.

MCS will perform better than the Anderson locks implemented under the name of "Fairlocks" and
"J-Locks" for Linux, also (I assume these are the NUMA-aware locking primitives you are
talking about?).

There are other implementations that perform better than both of these. Ticket lock with
proportional back-off helps alleviate performance issues in the highly contested case.

Ticket spinlocks

Posted Jul 28, 2008 22:37 UTC (Mon) by okeydoke (guest, #46751) [Link]

This is my MCS implementation and an optimized (for pipeline) Linux ticket lock
implementation. The results are not for the K42-variant MCS locks originally provided to
Linux.

Ticket spinlocks

Posted Dec 12, 2009 9:44 UTC (Sat) by bankkus (guest, #62476) [Link]

>> And ticket locks do have nice real-time properties, as they get rid of
>> the possibility of starvation!

Is that a correct statement? Not an x86 guru but whatever instruction is used to atomically increment the 16bit number is that guaranteed to complete in hw? In other words consider a 16 way processor if all threads incremented simulataneously is there a guarantee all 16 threads increment (in whatever order) or is it possible that on some of them the thread can context switch out before execution. If such is true then it does not guarantee no starvation.