Content deleted Content added
→Lock-freedom: Light polishing of the second paragraph |
→Lock-freedom: Added new second paragraph distinguishing lock-free from mutex/spinlock. |
||
Line 75:
== Lock-freedom ==
Lock-freedom allows individual threads to starve but guarantees system-wide throughput. An algorithm is lock-free if it satisfies that when the program threads are run sufficiently long 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 N processors are trying to execute an operation, some of the 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.
| |||