Introduction to Wait-free Algorithms in C++ Programming [video]

https://www.youtube.com/watch?v=kPh8pod0-gk

by twoodfin • 2 years ago

53 5 2 years ago

youtube.com

yazzku• 2 years ago

For the memory order not covered in this talk, see Fedor Pikus: https://www.youtube.com/watch?v=ZQFzMfHIxng

And this whole blog series: https://preshing.com/20120612/an-introduction-to-lock-free-p...

kevmo3142• 2 years ago

Instead of dedicating two bits to flags, could the specific task in the video be accomplished by leveraging the sign bit? Define 0xFFFF to be zero, 0x0000 to be one, 0x0001 to be two, etc. Then for decrement, do an atomic `fetch_uint_sub(1)` and for increment, do an atomic `fetch_sint_add(1)`.

This could simplify read by making the sign flag a one-way gate enforced by the CPU semantics instead of the application?

NobodyNada2• 2 years ago

You'd need that fetch_sub operation to saturate at zero instead of wrapping to 0xFFFF, and I'm not aware of a processor that provides saturating atomic arithmetic operations.

kevmo3142• 2 years ago

Why? If we define zero as 0xFFFF it will saturate by rolling over the first bit, which increment will not change?

Introduction to Wait-free Algorithms in C++ Programming [video]

Related Stories