Content deleted Content added
B2u9vm1ea8g (talk | contribs) m grammar |
Hackranger87 (talk | contribs) The earlier definition was wrong: "An algorithm is lock free if every operation has a bound on the number of steps before one of the threads operating on a data structure completes its operation.[12]" . because this is same as wait free. |
||
Line 78:
progress (for some sensible definition of progress). All wait-free algorithms are lock-free.
An algorithm is lock free if infinitely often operation from some processors will succeed in finite number of step. For instance, if there N number of processors are trying to make an operation, some processes in N number of processes will succeed to finish the operation in finite number of steps and other might fail and retry on failure. The difference between wait-free and lock-free is, wait-free operations by every process is guaranteed to succeeds in finite number of steps regardless of other processor.
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.
| |||