3 ms·
What is a wait-free stack?
by programmer_dude 10y ago
What is a wait-free stack?
- krig 10y agoFrom the introduction: > In this paper, we describe an algorithm to create a wait-free stack. A concurrent data structure is said to be wait-free if each operation is guaranteed to complete within a finite number of steps. In comparison, the data structure is said to be lock-free if at any point of time, at least one operation is guaranteed to complete in a finite number of steps. Lock-free programs will not have deadlocks but can have starvation, whereas wait-free programs are starvation free.
- wcrichton 10y agoWait-freedom is described in the introduction. Quote: There are three levels of progress guarantees for non-blocking data structures. A concurrent object is: - obstruction-free if a thread can perform an arbitrary operation on the object in a finite number of steps when it executes in isolation, - lock-free if some thread performing an arbitrary operation on the object will complete in a finite number of steps, or - wait-free if every thread can perform an arbitrary operation on the object in a finite number of steps. Wait-freedom is the strongest progress guarantee; it rules out the possibility of starvation for all threads. Wait-free data structures are particularly desirable for mission critical applications that have real-time constraints, such as those used by cyber-physical systems.