Comment by adrian_b | Hacker News Reader

Comment by adrian_b | Hacker News Reader

Parent Full thread

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.

> if a writer enters an infinite loop while writing the shared data, that will stop progress in any other algorithm

No, 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.

I suspect adrian_b is talking about a scenario where a rouge thread essentially writes random garbage to random addresses in the address space.

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.

[...] 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) }

all other threads will be able to continue. Whether the result will be of any value will depend on the use case.

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.

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.

Reply on news.ycombinator.com