(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.
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.)