"Lock free" data structures are tied very closely to the data being locked, and depend heavily on certain CPU operations being atomic. This is more of an issue with ARM than with x86, because ARM needs more fence instructions. Really, "lock free" programming is just locking critical sections with lower level hardware primitives.
The opposite extreme is POSIX locks. Locks are the OS's problem, and nothing in the code says what's covered by the lock. That was once standard practice and is now recognized as being bad.
I have to disagree, as the more interesting lock free algorithms use atomic operations that can fail. Yes, a compare-and-swap is like having a critical section on modifying that particular address. But a compare-and-swap can fail if what is currently there is unexpected. The result of that failure generally means redoing a bunch of work, rather than just trying again. Interesting lock free algorithms tend to have the structure:
1. Read some data.
2. Perform computations on that data.
3. Trying to commit the result of that computation. If someone else committed data to the same location after you read it in step 1, go back to step 1.
That's less like a "critical section," and more like a transaction. For lock free algorithms that just rely on atomic operations that cannot fail (such as an atomic increment), then yes, those are just like having a lower-level critical section. (And, on some architectures, that's exactly what they are.)
(Also, not all architecture use hardware mechanisms to enforce actual mutual exclusion. For example, Power does not, as it uses load-linked, stored-conditional: https://en.wikipedia.org/wiki/Load-link/store-conditional. On Power, even things like atomic increments are implemented with LL/SC. Architectures basically have to decide: will they implement atomics through some kind of a lock mechanism, or some kind of LL/SC mechanism.)
What lock-free means in this case is that an OS level thread freezing doesn't prevent global progress. That's true on the abstraction level of typical programming, but grandparent is very much correct:
> Really, "lock free" programming is just locking critical sections with lower level hardware primitives.
Compare and swap is interesting. It's a tiny transaction. It can even operate across networks - FireWire had hardware compare and swap support. Compare and swap with retry may have to wait and retry, which is effectively waiting for someone else to stop using a resource you want. So it's a form of a critical section lock.
Can fence instructions really be seen as locking mechanism? While a lock generally is bound to some data, memory fences are bound to relationships between data or a piece of code. I don't know if Rust or any other language can help you with that.
Isn't the actual bad practice to expose locks at all? If the locking is done implicitly in API calls, one doesn't need to ask "What locks it".
See also, eg, the LOCK prefix on x86 instructions.
(disclaimer: I only have approximate knowledge of anything, I'm not an expert)
That is incorrect. Properly designed and implemented mutexes (like in the parking_lot crate [1]) are extremely fast in the uncontented case, and need just one byte of overhead (and no heap-allocated memory) per mutex. In the contented case, a lock-free algorithm still has to deal with arbitration between the different threads, so it's typically not faster than a lock-based approach. Lock-free algorithms do have certain advantages (like deadlock-freedom), but performance is typically not one of them.
> Locking is a [...] scalability destroying operation
Also incorrect. If you have N threads trying to append to a single queue, then you have a scalability problem whether you're using locked or lock-free data structures. The solution in such a case is fine-grained concurrency and a different approach, not lock-free algorithms.
A common train of thought seems to be "locks are slow, so lock free must be fast", while lock-free says nothing about performance -- only about forward progress.
The question is "What prevents me from making changes to this variable without breaking everything".
So the point is not "What locks guard this data" the point is, how do I determine whether I can currently modify (or even read) this data. This allows the compiler to check that, indeed, you never use the data in a way that would break things. Hence your compiler can then give guarantees about thread-safety.
Now it seems likely that, when compilers do this and you write wrong code, your conclusion might be "I need a mutex lock for this", or if performance matters, "I need to rewrite this to allow performant lockless code. But the main question remains "Can I currently modify this data without issues".
In big multi-core systems, I model the handful of locks by the worst-case access frequency for a core to understand contention. In practice, this is often on the order of 100ms, which means the locks are effectively contention-free and the fast path almost always wins.