6 ms·
> 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
by 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.
- dragontamer 7y ago> 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. If the write to the local file needs to be protected by a critical section (seems unlikely to me, but... I can imagine some situations like that), the alternative is performing the write inside of a CAS loop instead. When the CAS-loop fails (because its been 20-seconds and the compare-and-swap has a grossly different value you were waiting on) you have to perform a 2nd I/O operation and restart the entire computation. What is more performant? Locking your other threads? Or potentially doing extremely expensive work repeatedly? Locking your other threads (especially if there are some other threads that have work to do) could very much be the more performant answer. In fact, I would argue that the locking implementation is more likely to be work efficient. > 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. I think that is reasonable and typical. I think beginners think of "lock free" as a potential improvement to efficiency. But the advantages of lock free are entirely independent of performance, it has more to so with requirements as opposed to performance in most cases.