A spin-lock would be more like a CAS loop (and the CAS IS a primitive CPU instruction), where you retry until the CAS succeeds. The point of lock-free algos, t

A spin-lock would be more like a CAS loop (and the CAS IS a primitive CPU instruction), where you retry until the CAS succeeds. 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.