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)