Generally, when you protect a data structure with a lock, that means that the thread which has the lock has mutually exclusive access to it. Other threads which want access must wait. When you have many threads which want access, you will tend to have serialized that part of your program. That will tend to hurt performance, if you gain performance from parallelism.
Lock-free approaches tend to allow multiple threads to access and modify a structure without having to get mutually exclusive access. Yes, if two threads are trying to touch the exact same part of the structure, they will interfere: one will succeed and move on, and the other will fail and have to retry. That's not much of a win over locks (generally). But, if it's common for the threads to touch different places of your structure, then they can do so without interfering with each other. That tends to allow better performance through parallelism.
I'm using a lot of weasel words ("tends to", "generally") because there are tradeoffs. If you have a shared structure which is accessed by multiple threads very rarely, then it may actually be better to use locks. Lock-free data structures tend to be more complicated (and hence, take a bit longer in the unconteded case) than simply protecting a data structure with a lock. So if you're almost always going to have uncontended access, it may actually yield better performance to use a lock.
But, locks can also be problematic when they're held too long or indefinitely. What if a thread dies while holding a lock? Or does I/O? Or is rescheduled? Other threads which want the lock must wait. Lock-free approaches tend to be free of such issues.
You can use mutexes to do fine-grained locking and still get into a dead-lock. Your algorithm can use only CASs and still not be deadlock-free.
The general idea of lock free is to holistically design a data structure that guarantees that when you I invoke its operations in any concurrent scenario, the overall system will make progress and won't get stuck.
The point of lock-free algos, though, is that you could usually do something different from just retrying. There is this concept/general approach in lock-free where if a CAS fails at a certain place, you could invoke helpers that would help some other part of the algorithm make progress. E.g. you may be inserting an element in some structure and your CAS fails at some level (usually because another thread is doing a delete). In that case, you would help the delete operation proceed by invoking some idempotent 'post_delete_cleanup' operation on the same node.
The idea of lock-free isn't that one particular thread won't block, but rather that the whole system would be making progress (i.e. no deadlock). It doesn't necessarily mean there will be no locks either.
Isn't it more like "mutex minimization" since you are trying to limit the critical section to a single a single atomic instruction(as opposed to more than one)?
FYI, this hasn't been the case in at least 20 years, on any of the major architectures. Cache coherency guarantees a single writer for any cache line aligned chunk of memory without any sort of bus lock.
I probably could have articulated my original question better, sorry.
By contention, I imply -- contention or conflicts on the same portions/pieces of structure.
If the data structure is subject to high concurrent access but in fairly disjoint regions of the data structure, we should try to implement fine grained locking scheme to increase the degree of parallelism and thus the scalability of data structure.
This is where CAS comes into picture. The article doesn't compare CAS to another locking primitive. Instead, CAS is just used as a mechanism to implement fine grained locking scheme where the methods operating on the data structure don't take global or coarse locks.
If the contention on the entire data structure is unreasonably high for some reason, then CAS based approaches or any flavors of it don't buy us much.
Though from what I've read, on Linux, pthreads implements its mutexes in user-space (futex) as well and are fairly cheap to use.
Goes without saying, spinlocks are not useful on uniprocessor machines or single core machines.