[senderista]

Maybe you mean ticket locks? That’s kind of the practical version of the bakery algorithm. It’s not the same because ticket locks require fetch-and-add (or its emulation over another atomic RMW like CAS), while the bakery algorithm uses only reads and writes (which makes it impractical).

Using a futex to allow ticket locks to block in the kernel does have a thundering herd problem. Fortunately you can do “smart sleeps” by measuring the time elapsed since the last wakeup and the change in the turn counter since then, and using that to estimate the time until the current thread’s turn (we don’t want to block the queue by oversleeping, so sleep for half of that estimate, then redo the estimate again, etc). (The same logic can be applied to spinning during the waiter’s timeslice, to avoid unnecessary cache coherence traffic.)

I assume you’re referring to Guy Blelloch’s work on wait-free hazard pointers? That’s very cool although I doubt it’s solving a practical problem. The practical issue with hazard pointers is the StoreLoad barrier on the read side (which can be moved to the GC side via membarrier(2) etc).

[j_seigh]

https://groups.google.com/g/comp.programming.threads/c/XU6Bt... https://groups.google.com/g/linux.kernel/c/gk6AUkXR9As/m/-1W... Yes, I am aware of the asymmetric memory barriers trick and the atomic memory move trick also.

There's a couple of other ways to achieve wait freedom on hazard pointer loads (protect) but they haven't been published so they're kind of moot.