Editing Non-blocking algorithm (section)

== Lock-freedom ==
Lock-freedom allows individual threads to starve but guarantees system-wide throughput. An algorithm is lock-free if, when the program threads are run for a sufficiently long time, at least one of the threads makes
progress (for some sensible definition of progress).
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.

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.

The decision about when to assist, abort or wait when an obstruction is met is the responsibility of a ''contention manager''. This may be very simple (assist higher priority operations, abort lower priority ones), or may be more optimized to achieve better throughput, or lower the latency of prioritized operations.

Correct concurrent assistance is typically the most complex part of a lock-free algorithm, and often very costly to execute: not only does the assisting thread slow down, but thanks to the mechanics of shared memory, the thread being assisted will be slowed, too, if it is still running.