Once you use atomic cmpxchg you've lost a great deal of scalability because it implies a retry loop (internal or by the user) The last thing you want is all of the threads failing to cmpxchg (spuriously or otherwise ) spinning on a shared cacheline Real world alternatives show atomic xchg only solutions scale to hundreds of threads.
Agreed. But you make it sound like the worst case is necessarily fatal. It depends on the use-case. The workable cmpxchg algorithms will make progress on at least one core each round. In a push or pop operation one of the cmpxchg must have succeeded for another to fail. The atomic xchg algorithms that I know of have other undesirable pathologies (e.g. a suspended producer can stall the consumer).
cmpxchg can fail spuriously on some platforms