Non-blocking algorithm: Difference between revisions

Content deleted Content added
multiple ref columns
Gene (talk | contribs)
Lock-freedom: Light polishing of the second paragraph
Line 77:
progress (for some sensible definition of progress). All wait-free algorithms are lock-free.
 
An algorithm is lock -free if infinitely often operation fromby some processors will succeed in a finite number of steps. For instance, if N number of processors are trying to makeexecute an operation, some processesof inthe N number of processes will succeed toin finishfinishing the operation in a finite number of steps and otherothers might fail and retry on failure. The difference between wait-free and lock-free is, that wait-free operationsoperation by everyeach process is guaranteed to succeedssucceed in a finite number of steps, regardless of the other processors.
 
In general, a lock-free algorithm can run in four phases: completing one's own operation, assisting an obstructing operation, aborting an obstructing operation, and waiting. Completing one's own operation is complicated by the possibility of concurrent assistance and abortion, but is invariably the fastest path to completion.