3 ms·

I don't think exchange is enough to implement all (or even most) lock-free/wait-free algorithms. CAS (i.e. lock cmpxchg), or an equivalent primitive in power, i

I don't think exchange is enough to implement all (or even most) lock-free/wait-free algorithms. CAS (i.e. lock cmpxchg), or an equivalent primitive in power, is needed. XCHG is enough to implement a mutex though, which is what most applications need.

adrian_b 3y ago
Lock-free and wait-free algorithms are not necessary for any computing task. They are only a performance enhancement and they indeed require either compare-and-swap (simple and double) from the IBM System/370 (1973) (later used by Motorola MC68020, then simple compare-and-swap was added to 486 and double compare-and-swap to Pentium) or load-locked + store-conditional from the S-1 Advanced Architecture Processor (LLNL, 1987) (later used by MIPS, then by POWER, ARM and others). Moreover, even for improving the performance the lock-free and wait-free algorithms must be used with care, because they are based on optimistic assumptions that may fail to be true in many scenarios with heavily contended shared resources, when the performance of the algorithms based on mutual exclusion is actually higher and more predictable (with mutual exclusion it is easy to guarantee FIFO access to a shared resource, which ensures that the wait times are bounded and that at any moment there is at least one thread that does useful work instead of retrying failed accesses to the shared resource).
- gpderetta 3y ago
  Well you mention that you can implement all programs, I just wanted to clarify that there are indeed some algorithms that cannot be implemented. In any case this has nothing to do with performance, you might need lock-free algorithms for correctness when implementing some real-time systems or when you need code to be reentrant.
  - adrian_b 3y ago
    I am curious to hear an example where a lock-free algorithm is needed for correctness, because I have never encountered any such case and this does not seem possible. Access to any kind of shared resource is always correct when only a single thread can access it. With mutual exclusion it is very easy to guarantee correctness due to serialized accesses. With lock-free algorithms concurrent accesses are possible and the algorithms must be carefully analyzed to demonstrate their correctness. Moreover, exactly in real-time systems is where lock-free algorithms are undesirable. Any pure lock-free algorithm must detect a transaction failure and retry it. There is no guarantee of success and no limit for the number of retries, so any hard real-time deadlines can be missed. Lock-free algorithms can be used in real-time systems only if they detect too many retries and then they fall back to lock-based algorithms before it is too late. The lock-free algorithms improve only the execution time of the typical case, but they increase the execution time for the worst case. For non-real-time applications the typical performance is more important, so lock-free algorithms are good, but for real-time applications the worst-case performance is the most important, which makes lock-free a.k.a. optimistic algorithms bad. Also neither mutual exclusion nor lock-free/wait-free algorithms have any problem with reentrancy when implemented correctly. Problems with reentrancy appear only in programs where there are mutable variables that are shared between threads and which should not have been shared (like when using some of the old standard C library functions). It is very common to have a very large number of threads that use reentrantly the same code that implements mutual exclusion for accessing some shared resource that is guarded by a lock.
    - gpderetta 3y ago
      Again, nothing to do with performance. For example an interrupt handler (or a signal handler) that needs to modify some shared resource. It can't take a mutex or even a spin lock because it might be owned by the thread it just interrupted. There are ways around that of course, for example by having threads disable interrupts inside critical sections, but that's not always appropriate. Similarly, for realtime systems, if you have threads with different priorities accessing the same data, to avoid deadlocks you either need mutexes with priority inversion (which has its own share of issues) or you use lock free code. edit: in any case the point isn't that there are better ways to write a program. The point is that if you have a program that uses a CAS-based lock-free algorithm, porting it to 386 it is not just a matter of paying a performance penality, you might need to rewrite it to preserve correctness. edit2: > There is no guarantee of success and no limit for the number of retries, so any hard real-time deadlines can be missed. Lock-free algorithms can be used in real-time systems only if they detect too many retries and then they fall back to lock-based algorithms before it is too late wait-free algos have guaranteed bounds.
      - adrian_b 3y ago
        An interrupt handler may use neither lock-based methods nor lock-free methods, because it may not remain stuck in a wait loop as required by the former and it may not use a CAS instrution as required by the latter, because any CAS instruction must be retried when it fails. Therefore an interrupt handler must always own whatever data structures it writes into, so it may write them at any time. Lock-free methods are not used inside interrupt handlers, but they are used by the code that reads what the interrupt handlers write. However this is the special case of single writer with one or more readers and this special case of lock-free access does not need compare-and-swap instructions or equivalents. For some particular cases, like counters that are updated by interrupt handlers, the readers can detect corrupt values and retry the reading, while for other cases, when the interrupt handler updates a more complex data structure, that can be guarded, for example, by a counter that is incremented both before and after the updating, so that the readers may be able to detect when they have to retry the reading. This special case of lock-free access does not need compare-and-swap, but, depending on the CPU memory access model, it may need store barriers a.k.a. store fences and load barriers a.k.a. load fences. Such lock-free access was trivial to implement on Intel 8086 or even earlier CPUs, because it does not even need atomic read-modify-write instructions. Normally, when lock-free algorithms are discussed, it is assumed that there are multiple writers, when different algorithms are needed than for the single-writer case, and when CAS instructions or equivalents are needed. There is no need for lock-free algorithms for avoiding deadlocks. The obvious solution to avoid deadlocks is to use a single lock protecting all shared data. Lock-free algorithms may provide a much better performance, but they are not necessary. Moreover, even without lock-free methods, deadlocks may be avoided in most cases by reorganizing the shared data. Any program where it is necessary at any point to hold multiple locks, is suspect of having a bad data organization, because this should not normally happen. You are right that wait-free algorithms by definition have guaranteed bounds, but unfortunately they are seldom applicable, otherwise concurrent programming would have been much easier.

adrian_b 3y ago

Lock-free and wait-free algorithms are not necessary for any computing task. They are only a performance enhancement and they indeed require either compare-and-swap (simple and double) from the IBM System/370 (1973) (later used by Motorola MC68020, then simple compare-and-swap was added to 486 and double compare-and-swap to Pentium) or load-locked + store-conditional from the S-1 Advanced Architecture Processor (LLNL, 1987) (later used by MIPS, then by POWER, ARM and others). Moreover, even for improving the performance the lock-free and wait-free algorithms must be used with care, because they are based on optimistic assumptions that may fail to be true in many scenarios with heavily contended shared resources, when the performance of the algorithms based on mutual exclusion is actually higher and more predictable (with mutual exclusion it is easy to guarantee FIFO access to a shared resource, which ensures that the wait times are bounded and that at any moment there is at least one thread that does useful work instead of retrying failed accesses to the shared resource).

gpderetta 3y ago
Well you mention that you can implement all programs, I just wanted to clarify that there are indeed some algorithms that cannot be implemented. In any case this has nothing to do with performance, you might need lock-free algorithms for correctness when implementing some real-time systems or when you need code to be reentrant.
- adrian_b 3y ago
  I am curious to hear an example where a lock-free algorithm is needed for correctness, because I have never encountered any such case and this does not seem possible. Access to any kind of shared resource is always correct when only a single thread can access it. With mutual exclusion it is very easy to guarantee correctness due to serialized accesses. With lock-free algorithms concurrent accesses are possible and the algorithms must be carefully analyzed to demonstrate their correctness. Moreover, exactly in real-time systems is where lock-free algorithms are undesirable. Any pure lock-free algorithm must detect a transaction failure and retry it. There is no guarantee of success and no limit for the number of retries, so any hard real-time deadlines can be missed. Lock-free algorithms can be used in real-time systems only if they detect too many retries and then they fall back to lock-based algorithms before it is too late. The lock-free algorithms improve only the execution time of the typical case, but they increase the execution time for the worst case. For non-real-time applications the typical performance is more important, so lock-free algorithms are good, but for real-time applications the worst-case performance is the most important, which makes lock-free a.k.a. optimistic algorithms bad. Also neither mutual exclusion nor lock-free/wait-free algorithms have any problem with reentrancy when implemented correctly. Problems with reentrancy appear only in programs where there are mutable variables that are shared between threads and which should not have been shared (like when using some of the old standard C library functions). It is very common to have a very large number of threads that use reentrantly the same code that implements mutual exclusion for accessing some shared resource that is guarded by a lock.
  - gpderetta 3y ago
    Again, nothing to do with performance. For example an interrupt handler (or a signal handler) that needs to modify some shared resource. It can't take a mutex or even a spin lock because it might be owned by the thread it just interrupted. There are ways around that of course, for example by having threads disable interrupts inside critical sections, but that's not always appropriate. Similarly, for realtime systems, if you have threads with different priorities accessing the same data, to avoid deadlocks you either need mutexes with priority inversion (which has its own share of issues) or you use lock free code. edit: in any case the point isn't that there are better ways to write a program. The point is that if you have a program that uses a CAS-based lock-free algorithm, porting it to 386 it is not just a matter of paying a performance penality, you might need to rewrite it to preserve correctness. edit2: > There is no guarantee of success and no limit for the number of retries, so any hard real-time deadlines can be missed. Lock-free algorithms can be used in real-time systems only if they detect too many retries and then they fall back to lock-based algorithms before it is too late wait-free algos have guaranteed bounds.
    - adrian_b 3y ago
      An interrupt handler may use neither lock-based methods nor lock-free methods, because it may not remain stuck in a wait loop as required by the former and it may not use a CAS instrution as required by the latter, because any CAS instruction must be retried when it fails. Therefore an interrupt handler must always own whatever data structures it writes into, so it may write them at any time. Lock-free methods are not used inside interrupt handlers, but they are used by the code that reads what the interrupt handlers write. However this is the special case of single writer with one or more readers and this special case of lock-free access does not need compare-and-swap instructions or equivalents. For some particular cases, like counters that are updated by interrupt handlers, the readers can detect corrupt values and retry the reading, while for other cases, when the interrupt handler updates a more complex data structure, that can be guarded, for example, by a counter that is incremented both before and after the updating, so that the readers may be able to detect when they have to retry the reading. This special case of lock-free access does not need compare-and-swap, but, depending on the CPU memory access model, it may need store barriers a.k.a. store fences and load barriers a.k.a. load fences. Such lock-free access was trivial to implement on Intel 8086 or even earlier CPUs, because it does not even need atomic read-modify-write instructions. Normally, when lock-free algorithms are discussed, it is assumed that there are multiple writers, when different algorithms are needed than for the single-writer case, and when CAS instructions or equivalents are needed. There is no need for lock-free algorithms for avoiding deadlocks. The obvious solution to avoid deadlocks is to use a single lock protecting all shared data. Lock-free algorithms may provide a much better performance, but they are not necessary. Moreover, even without lock-free methods, deadlocks may be avoided in most cases by reorganizing the shared data. Any program where it is necessary at any point to hold multiple locks, is suspect of having a bad data organization, because this should not normally happen. You are right that wait-free algorithms by definition have guaranteed bounds, but unfortunately they are seldom applicable, otherwise concurrent programming would have been much easier.