‘Lock-free’ means the application cannot ‘lock up’, rather than there are no locks. CAS does use a kind of hardware-level lock in the cache, but can never cause any application to lock up because there is no per-process state like in a software lock.