3 ms·

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

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

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.