I think "lock free" is a misnomer because in many cases these atomic operations still perform locks at the hardware level.
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.
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.
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.
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.
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.
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.
http://concurrencyfreaks.blogspot.com/2013/05/lock-free-and-...
http://courses.cs.vt.edu/~cs5204/fall07-kafura/Papers/Transa...
If you think context switches are expensive, then this is also expensive, but in a different way. Nothing is ever locked, but certainly the computer slows down from its maximum performance potential. (But there are many similar effects that happen even without atomic operations, like mis-predicting a branch.)
My experience in using both is that sometimes profiling dictates that a lock is too expensive. I used to maintain a program that incremented a counter from hundreds of threads. Using an OS-level mutex to achieve this resulted in way too many context-switches, to the point where we were only using about 30% of the CPU to run our program and the rest of the CPU time was spent on OS-level housekeeping. Using atomic load/store was much faster. Enqueuing all the writes in a thread-local counter and flushing them to the global structure in an OS lock was the fastest, but only provided eventual consistency.
Atomic operations execute atop the cache consistency protocol, which typically looks like: https://en.wikipedia.org/wiki/MOESI_protocol
It is indeed true that atomic operations will execute in a bounded time, and processors generally provide fairness guarantees as well.
Right now you're asserting things about all this, while not being familiar with relatively basic aspects of how it works.
Back in the day, I wanted to implement a cache in our software product that used reference counting to update objects and when the object went to 0, free it from the cache. Pretty straightforward, no rocket science, but this was also cross-platform including Solaris, HP-UX, etc.
This was easy to do on Windows/Intel because they implemented a native CAS at the time (almost 20 years ago now), but the other systems didn't. The only way would be to add a mutex per object, which was a non-starter because it used real kernel memory and resources, so I had to abandon the feature entirely.
The above is truly lock-free because it doesn't require any additional resources that have to be tracked or freed.