3 ms·

Could someone please explain for the uninitiated what lock-free actually means and why it matters. After reading http://www.drdobbs.com/lock-free-data-structur

Could someone please explain for the uninitiated what lock-free actually means and why it matters. After reading http://www.drdobbs.com/lock-free-data-structures/184401865 http://www.drdobbs.com/lock-free-data-structures/184401865 i got this: * Normal locking means that the process which holds the lock can hold it arbitrarily long thereby locking out all other processes. Also a live-lock and dead-lock can occur if there is a conflict between processes which try to acquire the same set of resources but cannot acquire all of them at once. * Wait-free means that no algorithm working with the data structure will be delayed arbitrarily. This is pretty strong. A simple example would be a ring-buffer with a single reader and writer. * Lock-free means that no process can block the resource for longer than it takes to read/write it. There will always be at least one process that can make progress while the others may have to wait (weaker than wait-free, but stronger than ordinary locked). Normal processes on most operating systems can be interrupted at any instruction. This would make it impossible to carry out a multiple-instruction sequence to lock-modify-unlock the data structure because it could leave the data structure locked. Does this in turn mean that there must be a "commit" instruction that is uninterruptible?

gpderetta 10y ago
> Does this in turn mean that there must be a "commit" instruction that is uninterruptible? Yes, in a way. Some CPUs provide atomic instructions that perform multiple operations in a bounded time. These instructions cannot be interrupted (by other threads, the OS, interrupts) and appear all-or-nothing (i.e. the intermediate effects are not visible. The most common of such instructions is Compare And Exchange (aka CAS); CAS is often used as the 'commit' action in lock-free algorithms. Some other architectures have instead a more general 'transactional' feature (known as Load Linked/Store Conditional or LS/SC) which provides for very limited transactions of a single cacheline. A naive implementation could live-lock, but in practice server class architectures provide stronger guarantees. It can be proven that LL/SC and CAS are equally powerful (i.e. the same set of lock-free/wait-free algorithms can be implemented with both). LL/SC is more natural for RISC machines, while CAS is common in CISC, but there are plenty of counterexamples.
RossBencina 10y ago
Lock-freedom and wait-freedom are formal terms in concurrent algorithm theory. Best to check out Herlihy and Shavit, "The Art of Multiprocessor Programming," which I have unfortunately temporarily misplaced. Informally: "Lock-free" means that at each time step, at least one thread that is interacting with a shared object makes progress towards completing the operation (e.g. an enqueue or dequeue operation). Neither deadlock nor livelock (where no thread makes progress) can happen (hence "lock free"). This does not guarantee fairness or starvation-freedom (a fast thread could in-theory DoS a slow thread). "Wait-free" means that at each time step, every thread will make progress. This might e.g. involve an algorithm where fast threads help slow threads complete their operations. Wait-freedom is indeed a stronger condition, but it's usually more expensive to implement (although not always). > Does this in turn mean that there must be a "commit" instruction that is uninterruptible? Yes, lock-free algorithms make use of atomic instructions such as CAS (compare-and-swap). Sometimes it's used as a "commit" but there might be multiple atomic operations depending on the algorithm and the data structure (so I guess, a kind-of multi-phase commit sequence). This is a nice intro paper by one of the giants of the field: Maged M. Michael, "The Balancing Act of Choosing Nonblocking Features" ACM Queue vol. 11, no. 7 http://queue.acm.org/detail.cfm?id=2513575 http://queue.acm.org/detail.cfm?id=2513575 Update: I should add that "lock free" hasn't always been a formally defined technical term, and some people use it informally to mean "doesn't use mutexes," or even "only uses atomic operations." Under such a relaxed definition a hand-coded spin-lock might be considered "lock free," but it really isn't -- if a thread holding the spinlock crashes, the spinlock would never be unlocked; such a situation could not arise with a formally lock-free algorithm.
- pzh 10y ago
  It's interesting that many people consider lock-free algorithms to be appropriate for real-time programming, but by the formal definitions, lock-free doesn't guarantee that a particular thread won't be starved or that an operation would finish by a certain amount of time. Maybe in these cases, wait-free would be more appropriate...
  - RossBencina 10y ago
    > Maybe in these cases, wait-free would be more appropriate... In some cases wait-free algorithms are used (e.g. real-time Java queues). There's ongoing research into whether lock-free queues are wait-free in practice.[0] For example, under some reasonable scheduling assumptions, lock-free operations have been shown to have bounded time execution.[1] That's a result for uniprocessors. I'm not aware of a corresponding result for multiprocessors, but I haven't gone looking for a couple of years. There are some leads in the first citation. [0] "Are Lock-Free Algorithms Practically Wait-Free?" http://tce.technion.ac.il/wp-content/uploads/sites/8/2015/06/SC-2.1-K-Censor-Hillel.pdf http://tce.technion.ac.il/wp-content/uploads/sites/8/2015/06... [1] Anderson, J. H. et al. 1997. “Real-Time Computing with LockFree Shared Objects.” ACM Transactions on Computer Systems. 15(2):134–165 https://cs.unc.edu/~anderson/papers/tocs97.pdf https://cs.unc.edu/~anderson/papers/tocs97.pdf

gpderetta 10y ago

> Does this in turn mean that there must be a "commit" instruction that is uninterruptible? Yes, in a way. Some CPUs provide atomic instructions that perform multiple operations in a bounded time. These instructions cannot be interrupted (by other threads, the OS, interrupts) and appear all-or-nothing (i.e. the intermediate effects are not visible. The most common of such instructions is Compare And Exchange (aka CAS); CAS is often used as the 'commit' action in lock-free algorithms. Some other architectures have instead a more general 'transactional' feature (known as Load Linked/Store Conditional or LS/SC) which provides for very limited transactions of a single cacheline. A naive implementation could live-lock, but in practice server class architectures provide stronger guarantees. It can be proven that LL/SC and CAS are equally powerful (i.e. the same set of lock-free/wait-free algorithms can be implemented with both). LL/SC is more natural for RISC machines, while CAS is common in CISC, but there are plenty of counterexamples.

RossBencina 10y ago

Lock-freedom and wait-freedom are formal terms in concurrent algorithm theory. Best to check out Herlihy and Shavit, "The Art of Multiprocessor Programming," which I have unfortunately temporarily misplaced. Informally: "Lock-free" means that at each time step, at least one thread that is interacting with a shared object makes progress towards completing the operation (e.g. an enqueue or dequeue operation). Neither deadlock nor livelock (where no thread makes progress) can happen (hence "lock free"). This does not guarantee fairness or starvation-freedom (a fast thread could in-theory DoS a slow thread). "Wait-free" means that at each time step, every thread will make progress. This might e.g. involve an algorithm where fast threads help slow threads complete their operations. Wait-freedom is indeed a stronger condition, but it's usually more expensive to implement (although not always). > Does this in turn mean that there must be a "commit" instruction that is uninterruptible? Yes, lock-free algorithms make use of atomic instructions such as CAS (compare-and-swap). Sometimes it's used as a "commit" but there might be multiple atomic operations depending on the algorithm and the data structure (so I guess, a kind-of multi-phase commit sequence). This is a nice intro paper by one of the giants of the field: Maged M. Michael, "The Balancing Act of Choosing Nonblocking Features" ACM Queue vol. 11, no. 7 http://queue.acm.org/detail.cfm?id=2513575 http://queue.acm.org/detail.cfm?id=2513575 Update: I should add that "lock free" hasn't always been a formally defined technical term, and some people use it informally to mean "doesn't use mutexes," or even "only uses atomic operations." Under such a relaxed definition a hand-coded spin-lock might be considered "lock free," but it really isn't -- if a thread holding the spinlock crashes, the spinlock would never be unlocked; such a situation could not arise with a formally lock-free algorithm.

pzh 10y ago
It's interesting that many people consider lock-free algorithms to be appropriate for real-time programming, but by the formal definitions, lock-free doesn't guarantee that a particular thread won't be starved or that an operation would finish by a certain amount of time. Maybe in these cases, wait-free would be more appropriate...
- RossBencina 10y ago
  > Maybe in these cases, wait-free would be more appropriate... In some cases wait-free algorithms are used (e.g. real-time Java queues). There's ongoing research into whether lock-free queues are wait-free in practice.[0] For example, under some reasonable scheduling assumptions, lock-free operations have been shown to have bounded time execution.[1] That's a result for uniprocessors. I'm not aware of a corresponding result for multiprocessors, but I haven't gone looking for a couple of years. There are some leads in the first citation. [0] "Are Lock-Free Algorithms Practically Wait-Free?" http://tce.technion.ac.il/wp-content/uploads/sites/8/2015/06/SC-2.1-K-Censor-Hillel.pdf http://tce.technion.ac.il/wp-content/uploads/sites/8/2015/06... [1] Anderson, J. H. et al. 1997. “Real-Time Computing with LockFree Shared Objects.” ACM Transactions on Computer Systems. 15(2):134–165 https://cs.unc.edu/~anderson/papers/tocs97.pdf https://cs.unc.edu/~anderson/papers/tocs97.pdf