Content deleted Content added
→See also: link to related articles. |
CortexFiend (talk | contribs) Link suggestions feature: 3 links added. |
||
Line 15:
Other problems are less obvious. For example, certain interactions between locks can lead to error conditions such as [[Deadlock (computer science)|deadlock]], [[livelock]], and [[priority inversion]]. Using locks also involves a trade-off between coarse-grained locking, which can significantly reduce opportunities for [[parallel computing|parallelism]], and fine-grained locking, which requires more careful design, increases locking overhead and is more prone to bugs.
Unlike blocking algorithms, non-blocking algorithms do not suffer from these downsides, and in addition are safe for use in [[interrupt handler]]s: even though the [[Pre-emptive multitasking|preempted]] thread cannot be resumed, progress is still possible without it. In contrast, global data structures protected by mutual exclusion cannot safely be accessed in an interrupt handler, as the preempted thread may be the one holding the lock. While this can be rectified by masking interrupt requests during the critical section, this requires the code in the critical section to have bounded (and preferably short) running time, or excessive [[interrupt latency]] may be observed.<ref name="monit">{{cite journal | doi = 10.1145/358818.358824 | url = http://research.microsoft.com/lampson/23-ProcessesInMesa/Abstract.html | title = Experience with Processes and Monitors in Mesa | author = Butler W. Lampson | author-link = Butler W. Lampson |author2=David D. Redell |author2-link=David D. Redell | journal = Communications of the ACM | volume = 23 | issue = 2 | pages = 105–117 |date=February 1980| citeseerx = 10.1.1.142.5765 | s2cid = 1594544 }}</ref>
A lock-free data structure can be used to improve performance.
Line 55:
[[C++11]] programmers can use <code>std::atomic</code> in <code><atomic></code>,
and [[C11 (C standard revision)|C11]] programmers can use <code><stdatomic.h></code>,
both of which supply types and functions that tell the [[compiler]] not to re-arrange such instructions, and to insert the appropriate memory barriers.<ref>
Bruce Dawson.
[https://randomascii.wordpress.com/2020/11/29/arm-and-lock-free-programming/ "ARM and Lock-Free Programming"].
Line 84:
All wait-free algorithms are lock-free.
In particular, if one thread is suspended, then a lock-free algorithm guarantees that the remaining threads can still make progress. Hence, if two threads can contend for the same mutex lock or [[spinlock]], then the algorithm is ''not'' lock-free. (If we suspend one thread that holds the lock, then the second thread will block.)
An algorithm is lock-free if infinitely often operation by some processors will succeed in a finite number of steps. For instance, if {{var|N}} processors are trying to execute an operation, some of the {{var|N}} processes will succeed in finishing the operation in a finite number of steps and others might fail and retry on failure. The difference between wait-free and lock-free is that wait-free operation by each process is guaranteed to succeed in a finite number of steps, regardless of the other processors.
| |||