Re:A lock-free ring-buffer with contiguous reservations (2019)
by SergeAx on Thursday February 29, 2024 @11:13PM
(#39558468)
Please excuse me if my question is dumb, I have little understanding of Rust. You declaring your implementation "lock-free", but are using Atomic* Rust primitives at the same time. Those are using CPU atomic instructions, if I googled correctly. Those, in their turn, are using CPU locking mechanism. Turns out that you just shifted locking from language to CPU, right?
[ Parent
| on HN ]
Re:A lock-free ring-buffer with contiguous reservations (2019)
by DannyBee on Friday March 01, 2024 @12:09AM
(#39558720)
It's a reasonable question, because lock-free is a confusing term.
Lock-free here does not mean "without any form of synchronization primitive". That is impossible. Some synchronization must occur.
Instead, it is a term of art that means:
1. Thread failure can't cause other threads to get blocked. 2. Forward progress in the algorithm is guaranteed.
Basically: threads can't block each other and death of threads does not screw things up.
https://en.wikipedia.org/wiki/Non-blocking_algorithm
CPU atomics often work by blocking (they have to) but they are non-interruptible instructions and there is a fixed maximum execution time.
(So you can still guarantee forward progress if you use them).
Re:A lock-free ring-buffer with contiguous reservations (2019)
by mrcode007 on Thursday February 29, 2024 @11:20PM
(#39558502)
Yes, this is correct and the most overlooked aspect and reason for the misnomer. Atomics imply locking at the cpu. Depending on the CPU the lock happens either for the entire memory bus (pre Intel P6 on x86) or as part of snoop disable bits on relevant cache lines in the snooping protocol
Re:A lock-free ring-buffer with contiguous reservations (2019)
by DannyBee on Friday March 01, 2024 @12:10AM
(#39558728)
It's not a misnomer, it's just a bad term of art. When it was coined folks were well aware that atomics locked at the CPU level.
Re:A lock-free ring-buffer with contiguous reservations (2019)
by mrcode007 on Friday March 01, 2024 @01:00AM
(#39558989)
“In discussing the question, he used to liken the case to that of the boy who, when asked how many legs his calf would have if he called its tail a leg, replied, ” Five,” to which the prompt response was made that calling the tail a leg would not make it a leg.”
Re:A lock-free ring-buffer with contiguous reservations (2019)
by gpderetta on Friday March 01, 2024 @06:25AM
(#39560767)
The "locking" happening on the CPU level is very different from the software level locking, as it is guaranteed by the hardware to be bounded (technically bus arbiters are not guaranteed to complete in finite time, but they are astronomically unlikely to do so).