8/4/2026 at 1:00:26 PM
A common approach to mitigating the described data race without using blocking locks is to utilize a sequence lock.A sequence lock is a blocking lock. If the writer dies between the two increment operations, then the readers will spin forever waiting for the counter to become even again.
by danbruc
8/4/2026 at 2:20:31 PM
This is why wait-free and lock-free are separate concepts. Author is not claiming wait-free.by rbranson
8/4/2026 at 2:56:27 PM
Obstruction-free, lock-free, and wait-free are increasingly strong guarantees for non-blocking synchronization mechanisms. A sequence lock is a blocking synchronization mechanism and therefore provides none of the aforementioned guarantees.by danbruc
8/4/2026 at 2:57:46 PM
No, it's neither wait-free nor lock-free. Wait-free guarantees all threads make progress, lock free guarantees at least one thread makes progress even if another thread is suspended or dead.by eqvinox
8/4/2026 at 1:58:07 PM
Also, there's no guarantee of progress. The writer can starve the reader forever.by jnwatson
8/4/2026 at 2:55:52 PM
That is always possible, even in any algorithm that claims to be wait-free, if some writer just keeps writing the shared data.All the claims about something being lock-free and/or wait-free depend on a rational behavior of the writers.
If any writer acts crazy, progress becomes impossible regardless of what all others do, unless someone kills the rogue thread or process.
In practice, the algorithm from TFA is much more likely to guarantee progress than any of the algorithms that are theoretically proven to guarantee progress, because it has an extremely small overhead, while the alternatives are much more complex and they waste a lot of time.
Moreover, most wait-free algorithms guarantee progress only for the whole system, in the sense that one random thread will progress, but they do not guarantee anything for a given thread, which may be blocked forever or stuck in an infinite loop, if unlucky.
by adrian_b
8/4/2026 at 3:02:27 PM
Not true, a wait-free algorithm guarantees that a read will complete in a bounded amount of time. And it guarantees that all threads make progress, it is lock-free that only guarantees progress for one thread.If the value changes frequently, it will get outdated quickly, but that has nothing to do with the synchronization mechanism used. And even if writes happen rarely, there is always a chance that the value you read will be outdated a nanosecond later.
by danbruc
8/4/2026 at 3:07:41 PM
Only the read of data small enough to be read atomically will complete in a bounded amount of time (i.e. not larger than 16 bytes on the current x86 or Arm CPUs).If you have a bigger shared data structure, in which some other thread writes continuously, there exists absolutely no way to stop it and no way for any other thread to progress.
by adrian_b
8/4/2026 at 3:16:34 PM
No, such algorithms exist and they use various mechanisms to achieve this. For larger data structures a common trick is to make a copy, update the copy, and then replace the original or parts of it with the copy. This provide readers with a stable view of the data structure that does not depend on small atomic reads. Another mechanism is that the different threads help each other to complete their interrupted work instead of making it invalid by modifying the data right away.by danbruc
8/4/2026 at 3:35:46 PM
Not true.If a writer writes continuously the shared data, it is impossible for the other thread to make the copy that must be edited.
If the copy succeeds, then you are right that an updated version could be substituted to the original using an atomic operation on pointers.
But there is no way to guarantee that the first copy succeeds.
Of course, in practice RCU is used very frequently, because all the other threads are well behaved and access the shared data for a minimum time, so the copy will succeed in most cases.
But absolute guarantees are impossible inside an algorithm expressible in an abstract programming language. Only using functions of the operating system to detect and stop a misbehaving thread can solve all cases.
by adrian_b
8/4/2026 at 3:42:06 PM
About what scenario are you actually talking? Are all threads using the read() and write() functions of the shared data structure? In that case it is absolutely possible for readers and writers to make progress even if a rogue writer is calling write() in a tight loop.Or are you talking about a scenario where a rogue writer essentially randomly modifies the shared data structure instead of using the designated write() function? Well, in that case all bets are obviously off.
by danbruc
8/4/2026 at 3:03:58 PM
I think you missed the point; seqlock based approaches will lock dead if you suspend/abort a thread in the wrong place. Other lock-free approaches don't have this issue. This isn't about a thread writing garbage, it's about guarantees applicable within the constraints.by eqvinox
8/4/2026 at 3:18:37 PM
No, you missed my point.I agree that there is the risk for a writer to be halted in the middle of its critical section, which would stop all the other writers and readers.
My point is that there exists no solution that is risk free, because if a writer enters an infinite loop while writing the shared data, that will stop progress in any other algorithm, regardless if it is claimed to be wait-free.
There exists no method to stop such a writer, except an external intervention from the operating system, which would have to use an IPI (inter-processor interrupt) to halt that CPU core and then kill the offending thread.
In my opinion a great number of lock-free or wait-free algorithms, all of which are proposed based on the fear of what happens if a writer is halted in a critical section, are completely impractical, because their overhead is many times higher in comparison with using a lock for writers and using the method from TFA for readers.
With those algorithms, a lot of CPU time is wasted continuously to guard against an event that should never happen in bug-free operating systems and applications.
It is much more efficient to try to detect the lack of progress and do something about that only in the unlikely case when this happens.
by adrian_b
8/4/2026 at 3:58:48 PM
> if a writer enters an infinite loop while writing the shared data, that will stop progress in any other algorithmNo, it won't, not in a wait-free algorithm. For lock-free algorithms, yes, it's a matter of scheduling and stochastics.
But this is not the case for seqlocks. You don't need an infinite loop, you don't need to keep writing. Just stop the thread after it set the seqlock value to odd ("being modified"). Because it's not lock-free.
(I do agree that a lot of this is overblown and ill-applied; "lock-free" just sounds good and it's sufficiently available that people reach for it and end up overusing it. However, there are cases where it matters and is absolutely appropriate, and it also matters that we are able to have a conversation about these situations and conditions and use the terminology in a consistent manner.)
> using a lock for writers and using the method from TFA for readers
Case in point, I'm confused what you mean there, what do you mean with "method from TFA"? I don't see how anything in the article combines with a lock for writers.
by eqvinox
8/4/2026 at 4:02:45 PM
I suspect adrian_b is talking about a scenario where a rouge thread essentially writes random garbage to random addresses in the address space.by danbruc
8/4/2026 at 4:07:25 PM
ACK. I hadn't read the other arc of this thread yet, I think we're having a failure of communication... along the lines of looking at things from the perspective of a different layer, or something like that.by eqvinox
8/4/2026 at 3:28:29 PM
[...] because if a writer enters an infinite loop while writing the shared data, that will stop progress in any other algorithm [...]Even if you have
while (true) { sharedData.writeWaitFree(randomData) }
If, on the other hand, you mean that some threads will enter an infinite loop inside of a read or write operation, then you have a bug in your wait-free algorithm and all bets are off. But we would generally assume that the implementation is good and the erroneous behavior is external.
by danbruc
8/4/2026 at 3:39:27 PM
Whatever is your writeWaitFree, nothing can stop another thread to do plain writes.In that case no other thread can make progress.
I agree that this is a very unlikely case, but the case when a thread is halted inside the critical region can also appear only as a consequence of some bug, and such unlikely occurrences cannot justify wasting time at every access of shared data by using a too complicated wait-free algorithm.
by adrian_b
8/4/2026 at 2:57:37 PM
[...] then the readers will spin forever waiting for the counter to become even again.by danbruc