MCS locks and qspinlocks

Posted Mar 12, 2014 11:42 UTC (Wed) by corbet (editor, #1)
In reply to: MCS locks and qspinlocks by martinfick
Parent article: MCS locks and qspinlocks

They cannot be preempted by the scheduler, only by interrupts. So they have to be protected against nested calls in interrupt handlers, but that is already true of spinlocks.

MCS locks and qspinlocks

Posted Mar 12, 2014 13:05 UTC (Wed) by martinfick (subscriber, #4455) [Link] (8 responses)

OK, but a spinlock can only block other CPUs once held, this kind of lock can block other CPUs before acquiring the lock simply by being next inline for the lock.

MCS locks and qspinlocks

Posted Mar 12, 2014 13:59 UTC (Wed) by rriggs (guest, #11598) [Link] (7 responses)

I'm not sure I understand your point. Isn't the case for both that the current lock holder is blocking CPU cores, and the next lock holder will block CPU cores? The only distinction here is that the next lock holder is known rather than random.

MCS locks and qspinlocks

Posted Mar 12, 2014 23:04 UTC (Wed) by james (subscriber, #1325) [Link] (5 responses)

If I'm reading this correctly (and it's quite possible I'm not), the scenario would be something like:

CPU1 obtains a lock;
CPU2 tries to get the same lock, fails, and becomes next in line;
CPU3 tries to get the same lock, fails, and becomes second in line;
CPU2 is pre-empted by an interrupt;
CPU1 releases the lock;

Then CPU3 is still waiting for CPU2 to release the lock, which it won't do until it has returned from its interrupt handling and done whatever needed to be protected by the lock. With conventional spinlocks, CPU3 would have obtained the lock and could be doing something productive while CPU2 was still handling the interrupt.

What I'm not sure about is how often this situation will arise in practice. Obviously, you have to have a lock with at least two CPUs waiting for the situation to arise, and an interrupt being handled on the wrong CPU at just the wrong time. It looks like this is sufficiently infrequent that the performance hit when this happens is dwarfed by the performance benefits of the technique, but it would probably be a good idea to retry the benchmark on a machine subject to a network storm.

MCS locks and qspinlocks

Posted Mar 13, 2014 3:15 UTC (Thu) by martinfick (subscriber, #4455) [Link] (1 responses)

> It looks like this is sufficiently infrequent

I wonder about that since these locks are meant for highly contentious locks!

MCS locks and qspinlocks

Posted Mar 13, 2014 14:30 UTC (Thu) by raven667 (subscriber, #5198) [Link]

And a corollary that on a computer, a one in a million chance race is going to happen all the time, frequent and infrequent have different meanings than colloquial use.

MCS locks and qspinlocks

Posted Mar 13, 2014 11:23 UTC (Thu) by dvrabel (subscriber, #9500) [Link]

I think ticket locks have the same behavior as you describe.

MCS locks and qspinlocks

Posted Mar 13, 2014 15:55 UTC (Thu) by andresfreund (subscriber, #69562) [Link] (1 responses)

> CPU1 obtains a lock;
> CPU2 tries to get the same lock, fails, and becomes next in line;
> CPU3 tries to get the same lock, fails, and becomes second in line;
> CPU2 is pre-empted by an interrupt;
> CPU1 releases the lock;

Preemtion is disabled appropriately during spinlock acquiration IIRC.

MCS locks and qspinlocks

Posted Aug 23, 2024 12:53 UTC (Fri) by 301043030 (guest, #172920) [Link]

only process preemption is disabled, interruption is also valid.

MCS locks and qspinlocks

Posted Mar 13, 2014 9:58 UTC (Thu) by dgm (subscriber, #49227) [Link]

I'm feeling too lazy to find it out for myself: is it safe to give up waiting for the lock?