4 ms·

"lock free" regards to being free from any process/thread/device holding a lock for an undetermined amount of time. The formal definition IIRC is "a system is

"lock free" regards to being free from any process/thread/device holding a lock for an undetermined amount of time. The formal definition IIRC is "a system is lock free, at least one concurrent process makes progress towards finishing in a unit of time" (There's a hard to achieve version called "wait free" which means "every process makes amortized progress towards finishing") The important property of a lock free system is that pausing any thread/process does not stop the others from progressing; whereas with classical locks (mutex, semaphore, spin, whatever), if you pause a lock-holding process you risk starving the entire system.

mehrdadn 7y ago
I love your last paragraph. It's extremely intuitive and yet I don't think I've ever seen it explained that way.
- DSingularity 7y ago
  If you like this kind of thing: http://courses.cs.vt.edu/~cs5204/fall07-kafura/Papers/TransactionalMemory/Linearizability.pdf http://courses.cs.vt.edu/~cs5204/fall07-kafura/Papers/Transa...
- vishnugupta 7y ago
  Not to take anything away from the parent's thoughtful comment. That important property is, in fact, the definition of lock-free. Lock-free and wait-free (which has a stronger guarantee) algorithms are sub-classifications of non-blocking algorithms. If I could recommend one book on this topic it'd be "The Art of Multiprocessor Programming". The authors have contributed to this subject through original research and make the topic quite approachable.
  - deleted 7y ago
    [deleted]
  - mehrdadn 7y ago
    > Not to take anything away from the parent's thoughtful comment. That important property is, in fact, the definition of lock-free. According to Wikipedia, it's the definition of non-blocking, not the definition of lock-free... which I guess is a correction for both the parent comment and yours. [1] As far as I recall ever seeing, people always talk about it in terms of guaranteed systemwide progress, which I don't find as enlightening as what happens when you pause a thread. [1] https://en.wikipedia.org/wiki/Non-blocking_algorithm https://en.wikipedia.org/wiki/Non-blocking_algorithm
  - MaxBarraclough 7y ago
    A good article on this hierarchy (if you can forgive the low-contrast style): http://concurrencyfreaks.blogspot.com/2013/05/lock-free-and-wait-free-definition-and.html http://concurrencyfreaks.blogspot.com/2013/05/lock-free-and-...
DSingularity 7y ago
Yeah, this is why -- for me -- lock free is more about blocking/reliability than performance.
dragontamer 7y ago
> The important property of a lock free system is that pausing any thread/process does not stop the others from progressing; whereas with classical locks (mutex, semaphore, spin, whatever), if you pause a lock-holding process you risk starving the entire system. With that being said, stopping any thread/process is rare in high-performance circumstances. In many cases, it is easier to avoid getting your thread stopped (as simple as spinning up one-thread per logical core), rather than to switch to a lock-free algorithm. Besides, your typical OS Mutex (CriticalSection in Windows) handles the pause situation just fine. The OS will keep track of which threads are waiting on which locks, and restart the threads as resources become available. Its the "known problem" and well studied by pretty much all programmers. Lock-free data structures are exponentially more difficult to write, especially when you are handling "out of memory" edge cases. The general recommendation is to write "mostly lock free", but use a lock for corner-cases. CAS-loop with pointer swapping gets you lock free in most cases, and is very easy to understand. The only problem is that it doesn't work in all cases or data-structures, so you inevitably end up using locks to finish your program. EDIT: And it should be noted that locks can be faster. So if you're going for absolute performance, you should write both implementations and measure.
- beagle3 7y ago
  > With that being said, stopping any thread/process is rare in high-performance circumstances. While that's true from a performance perspective, it is not true from a reliability perspective - it's always possible that the thread holding a lock has faulted, was swapped out, or otherwise had a bug (e.g. in a library you called beyond your control) that caused it to stall. Also, if more than one lock is involved, a deadlock is possible as well (not all of which can be detected by an OS, and most OSes suck at detecting deadlocks if they even try). > The OS will keep track of which threads are waiting on which locks, and restart the threads as resources become available. But causes for a pause are not necessarily under your control or the OSes privilege; You can take a critical section, write to a local file .... and wait 20 seconds because the drive has gone to sleep, someone competing for the disk, swapping in/out, a recoverable disk error, or the fact that it is not actually local but rather virtualized SAN across the internet. Also, someone might have paused a thread from the debug API for whatever reason (or kill -STOP on linux), which might be expected to only pause that thread -- but in a system that isn't lock free, that could pause anything and everything, in a non reproducible way. > Lock-free data structures are exponentially more difficult to write For sure. Personally, I find that they keep me on my toes "the right way", that is - they force me to consider what and where actually needs synchronization and can be contended (whereas a lock allows me to be lazy. which is sometimes good). > The only problem is that it doesn't work in all cases or data-structures, Yes. ABA problems are not solved by CAS, which is why I personally prefer LL/SC, but ... whatever, CAS is harder but still doable. > So if you're going for absolute performance, you should write both implementations and measure. Upon a quick review of history, my use of lock free structures and algorithms is dominated by reliability requirements ("nothing must unexpectedly pause the system" - mostly seqlocks), and only a few cases for performance - mostly shared lists and shared (often reference) counters.

mehrdadn 7y ago

I love your last paragraph. It's extremely intuitive and yet I don't think I've ever seen it explained that way.

DSingularity 7y ago
If you like this kind of thing: http://courses.cs.vt.edu/~cs5204/fall07-kafura/Papers/TransactionalMemory/Linearizability.pdf http://courses.cs.vt.edu/~cs5204/fall07-kafura/Papers/Transa...
vishnugupta 7y ago
Not to take anything away from the parent's thoughtful comment. That important property is, in fact, the definition of lock-free. Lock-free and wait-free (which has a stronger guarantee) algorithms are sub-classifications of non-blocking algorithms. If I could recommend one book on this topic it'd be "The Art of Multiprocessor Programming". The authors have contributed to this subject through original research and make the topic quite approachable.
- deleted 7y ago
  [deleted]
- mehrdadn 7y ago
  > Not to take anything away from the parent's thoughtful comment. That important property is, in fact, the definition of lock-free. According to Wikipedia, it's the definition of non-blocking, not the definition of lock-free... which I guess is a correction for both the parent comment and yours. [1] As far as I recall ever seeing, people always talk about it in terms of guaranteed systemwide progress, which I don't find as enlightening as what happens when you pause a thread. [1] https://en.wikipedia.org/wiki/Non-blocking_algorithm https://en.wikipedia.org/wiki/Non-blocking_algorithm
- MaxBarraclough 7y ago
  A good article on this hierarchy (if you can forgive the low-contrast style): http://concurrencyfreaks.blogspot.com/2013/05/lock-free-and-wait-free-definition-and.html http://concurrencyfreaks.blogspot.com/2013/05/lock-free-and-...

DSingularity 7y ago

Yeah, this is why -- for me -- lock free is more about blocking/reliability than performance.

dragontamer 7y ago

> The important property of a lock free system is that pausing any thread/process does not stop the others from progressing; whereas with classical locks (mutex, semaphore, spin, whatever), if you pause a lock-holding process you risk starving the entire system. With that being said, stopping any thread/process is rare in high-performance circumstances. In many cases, it is easier to avoid getting your thread stopped (as simple as spinning up one-thread per logical core), rather than to switch to a lock-free algorithm. Besides, your typical OS Mutex (CriticalSection in Windows) handles the pause situation just fine. The OS will keep track of which threads are waiting on which locks, and restart the threads as resources become available. Its the "known problem" and well studied by pretty much all programmers. Lock-free data structures are exponentially more difficult to write, especially when you are handling "out of memory" edge cases. The general recommendation is to write "mostly lock free", but use a lock for corner-cases. CAS-loop with pointer swapping gets you lock free in most cases, and is very easy to understand. The only problem is that it doesn't work in all cases or data-structures, so you inevitably end up using locks to finish your program. EDIT: And it should be noted that locks can be faster. So if you're going for absolute performance, you should write both implementations and measure.

beagle3 7y ago
> With that being said, stopping any thread/process is rare in high-performance circumstances. While that's true from a performance perspective, it is not true from a reliability perspective - it's always possible that the thread holding a lock has faulted, was swapped out, or otherwise had a bug (e.g. in a library you called beyond your control) that caused it to stall. Also, if more than one lock is involved, a deadlock is possible as well (not all of which can be detected by an OS, and most OSes suck at detecting deadlocks if they even try). > The OS will keep track of which threads are waiting on which locks, and restart the threads as resources become available. But causes for a pause are not necessarily under your control or the OSes privilege; You can take a critical section, write to a local file .... and wait 20 seconds because the drive has gone to sleep, someone competing for the disk, swapping in/out, a recoverable disk error, or the fact that it is not actually local but rather virtualized SAN across the internet. Also, someone might have paused a thread from the debug API for whatever reason (or kill -STOP on linux), which might be expected to only pause that thread -- but in a system that isn't lock free, that could pause anything and everything, in a non reproducible way. > Lock-free data structures are exponentially more difficult to write For sure. Personally, I find that they keep me on my toes "the right way", that is - they force me to consider what and where actually needs synchronization and can be contended (whereas a lock allows me to be lazy. which is sometimes good). > The only problem is that it doesn't work in all cases or data-structures, Yes. ABA problems are not solved by CAS, which is why I personally prefer LL/SC, but ... whatever, CAS is harder but still doable. > So if you're going for absolute performance, you should write both implementations and measure. Upon a quick review of history, my use of lock free structures and algorithms is dominated by reliability requirements ("nothing must unexpectedly pause the system" - mostly seqlocks), and only a few cases for performance - mostly shared lists and shared (often reference) counters.