Non-Blocking Algorithm
Jump to navigation
Jump to search
A Non-Blocking Algorithm is an Algorithm that is associated with the possible suspension of a computing thread or operations.
- Example(s):
- Counter-Example(s):
- See: Nonblocking Minimal Spanning Switch, Computer Science, Algorithm, Scheduling (Computing), Thread (Computing), Lock (Computer Science), Resource Starvation, International Conference on Distributed Computing Systems, Telecommunications Network, Clos Network.
References
2021
- (Wikipedia, 2021) ⇒ https://en.wikipedia.org/wiki/Non-blocking_algorithm Retrieved:2021-9-21.
- In computer science, an algorithm is called non-blocking if failure or suspension of any thread cannot cause failure or suspension of another thread; for some operations, these algorithms provide a useful alternative to traditional blocking implementations. A non-blocking algorithm is lock-free if there is guaranteed system-wide progress, and wait-free if there is also guaranteed per-thread progress. "Non-blocking" was used as a synonym for "lock-free" in the literature until the introduction of obstruction-freedom in 2003.[1]
The word "non-blocking" was traditionally used to describe telecommunications networks that could route a connection through a set of relays "without having to re-arrange existing calls" (see Clos network). Also, if the telephone exchange "is not defective, it can always make the connection" (see nonblocking minimal spanning switch).
- In computer science, an algorithm is called non-blocking if failure or suspension of any thread cannot cause failure or suspension of another thread; for some operations, these algorithms provide a useful alternative to traditional blocking implementations. A non-blocking algorithm is lock-free if there is guaranteed system-wide progress, and wait-free if there is also guaranteed per-thread progress. "Non-blocking" was used as a synonym for "lock-free" in the literature until the introduction of obstruction-freedom in 2003.[1]
- ↑ Herlihy, M.; Luchangco, V.; Moir, M. (2003). Obstruction-Free Synchronization: Double-Ended Queues as an Example (PDF). 23rd International Conference on Distributed Computing Systems. p. 522.
2003
- (Herlihy et al., 2003) ⇒ Maurice Herlihy, Victor Luchangco and Mark Moir (2003). "Obstruction-Free Synchronization: Double-Ended Queues as an Example". In: Proceedings of the 23rd International Conference on Distributed Computing Systems.
- QUOTE: We introduce obstruction-freedom, a new nonblocking property for shared data structure implementations. This property is strong enough to avoid the problems associated with locks, but it is weaker than previous nonblocking properties — specifically lock-freedom and wait-freedom — allowing greater flexibility in the design of efficient implementations. Obstruction-freedom admits substantially simpler implementations, and we believe that in practice it provides the benefits of wait-free and lock-free implementations.