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.

▲

adrian_b an hour ago | parent [-]

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.

▲

danbruc an hour ago | parent [-]

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.

▲

adrian_b 41 minutes ago | parent [-]

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.

	▲	danbruc 35 minutes ago \| parent [-]
		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.