11–20 of 31 posts
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.
Also, there's no guarantee of progress. The writer can starve the reader forever.
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.
This is why wait-free and lock-free are separate concepts. Author is not claiming wait-free.
Earlier quoted context omitted.
Also, there's no guarantee of progress. The writer can starve the reader forever.
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 m…
Earlier quoted context omitted.
Also, there's no guarantee of progress. The writer can starve the reader forever.
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 m…
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.
Earlier quoted context omitted.
Also, there's no guarantee of progress. The writer can starve the reader forever.
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 m…
iceoryx2 provides zero-copy inter-process communication mechanisms based on shared memory and data structures that are modified concurrently by multiple processes. One of the key operations in these algorithms is a memory copy using core::ptr::copy. However, this results in undefined behavior if one process reads the data while another process writes to it concurrently. Even if our lock-free algorithm reliably detect…
You're fixing a theoretical problem (mismatch between CPU and compiler memory models, the CPU is perfectly fine doing these reads and writes, it's only the compiler declaring them "UB") by throwing away a shitton of performance, forcing everything into bytewise accesses. Considering this is Rust, I would at minimum expect this be written to be generic over access size to allow using 64-bit reads/writes. I'm also miss…
Earlier quoted context omitted.
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 m…
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 r…
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.
Earlier quoted context omitted.
You're fixing a theoretical problem (mismatch between CPU and compiler memory models, the CPU is perfectly fine doing these reads and writes, it's only the compiler declaring them "UB") by throwing away a shitton of performance, forcing everything into bytewise accesses. Considering this is Rust, I would at minimum expect this be written to be generic over access size to allow using 64-bit reads/writes. I'm also miss…
The compiler declares them UB because very useful transformations would change the semantics of races. Races are ok with specially marked variables!
Earlier quoted context omitted.
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 r…
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.
Earlier quoted context omitted.
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 m…
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.
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.