wait-free combiner lock

79 views
Skip to first unread message

Dmitry Vyukov

unread,
Nov 9, 2018, 7:13:13 PM11/9/18
to lock...@googlegroups.com
Hi,

An interesting wait-free combiner lock with 2 XCHG to enqueue work:
https://github.com/romkatv/action-chain/blob/master/src/action_chain.h

This is somewhat similar to the XCHG-based enqueue here:
http://www.1024cores.net/home/lock-free-algorithms/queues/non-intrusive-mpsc-node-based-queue

But the algorithm does not have that nasty inconsistency window
between XCHG and store when the queue links are broken. The novel part
is that it uses another XCHG to restore the next link and figure out
if it managed to do so before anybody observed the broken link or not.

This is more expensive than 1 CAS to enqueue for uncontended case, but
I guess should sustain high contention much better.

Chris M. Thomasson

unread,
Dec 2, 2018, 5:28:05 PM12/2/18
to Scalable Synchronization Algorithms
Need to check this out. Thanks for the heads up.
Reply all
Reply to author
Forward
0 new messages