| (Commenting here since the other thread is going nowhere) To clarify, the main property of a non-blocking algorithm is that it's exclusively composed of simpler, smaller ("atomic") operations that demonstrate time-bound/progress-making guarantees, in turn making the bigger algorithm generally easier to reason about (Note "generally"). The consequence of this argument is twofold: 1. It's entirely possible to make a blocking algorithm provide the same guarantees as a non-blocking algorithm, as long as the underlying operations (blocking or otherwise) are proven to be correct. Blocking algorithm tend to throw other complex systems into the mix (e.g. the scheduler), and all of the dependencies and their usages have to be correct (w.r.t. whatever property we desire) to show that the final blocking algorithm is also correct. For instance, it can be argued that the priority inversion problem stems from the lack of scheduler's correctness, or alternatively, the incorrect use of the scheduler. However, in the absense of such problems, there are effectively no disadvantages on blocking algorithms on this respect. 2. If it turns out any atomic operations below the non-blocking algorithm do not meet the expected guarantees, then the non-blocking algorithm itself also becomes unsafe. I think the OP clearly demonstrates this problem--the CPU atomic instructions are but some kind of hardware "locks" (either a LOCK# pin on older processors or some complex cache coherency protocol, but this is an implementation detail) on their own that can sometimes fail to meet the programmer's expectations, leading to surprising results. In short, the fine line between blocking algorithms and nonblocking algorithms can be drawn by whichever smaller operations or components we assume to be correct. |