3 ms·

Maybe you'd like Anthony Williams's _C++ Concurrency in Action_, which doesn't cover futexes (or how to write your own synchronization primitives in general), b

Maybe you'd like Anthony Williams's _C++ Concurrency in Action_, which doesn't cover futexes (or how to write your own synchronization primitives in general), but does cover real-world details like memory orderings and SMR for lock-free data structures. If that's still too high-level, then maybe check out Paul McKenney's excellent free monograph "Is Parallel Programming Hard, And, If So, What Can You Do About It?" for a more hardware-focused perspective (which doesn't cover futexes in detail either but does direct you to the canonical reference for implementing futex-based primitives, namely Ulrich Drepper's "Futexes Are Tricky"). I think TAOMPP is fine for what it is (teaching high-level concurrency concepts) and discussing OS-level implementation details would be out of place. The important thing it teaches is how to think about concurrency, not how to write your own synchronization primitives. E.g., the Peterson or bakery locks are useless in the real world (as the book admits), but understanding their proofs of correctness will help you reason about the concurrent algorithms you have to write yourself.

j_seigh 1y ago
Bakery locks are good for spin locks. They're more cache friendly. Plus you can do reader/writer spin locks. They're going to be strictly FIFO though. I guess you could tack on a futex wait for the spin wait in user space but it's going to be really inefficient. You are going to get a lot of spurious wake ups. Not one of the things futex's are designed for. Lock-free with hazard pointers or RCU* is still kind of tricky. It's going to be data structure specific and you really have to know what you are doing. Fun fact. You can make hazard pointers wait-free, actual wait free, not the dubious bounded retry loop hack. * Doing copy on write with RCU is fairly straight forward but probably expensive if updates are frequent.
- senderista 1y ago
  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 1y ago
    https://groups.google.com/g/comp.programming.threads/c/XU6BtGNSkF0/m/AmWXvkGn3DAJ https://groups.google.com/g/comp.programming.threads/c/XU6Bt... https://groups.google.com/g/linux.kernel/c/gk6AUkXR9As/m/-1Ws1gPsXocJ 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.

j_seigh 1y ago

Bakery locks are good for spin locks. They're more cache friendly. Plus you can do reader/writer spin locks. They're going to be strictly FIFO though. I guess you could tack on a futex wait for the spin wait in user space but it's going to be really inefficient. You are going to get a lot of spurious wake ups. Not one of the things futex's are designed for. Lock-free with hazard pointers or RCU* is still kind of tricky. It's going to be data structure specific and you really have to know what you are doing. Fun fact. You can make hazard pointers wait-free, actual wait free, not the dubious bounded retry loop hack. * Doing copy on write with RCU is fairly straight forward but probably expensive if updates are frequent.

senderista 1y ago
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 1y ago
  https://groups.google.com/g/comp.programming.threads/c/XU6BtGNSkF0/m/AmWXvkGn3DAJ https://groups.google.com/g/comp.programming.threads/c/XU6Bt... https://groups.google.com/g/linux.kernel/c/gk6AUkXR9As/m/-1Ws1gPsXocJ 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.