[arielby]

lock-free data structures should have identical semantics (and uncontended performance) to lockful data structures with per-operation locks (up to performance), except for the temptation to hold the data structure lock for a long time.

The problem with locks is that people don't want one thread per object, and instead use one lock per object. This has the effect of making all object operations synchronous, which turns some potential race-conditions into deadlocks.

[bsder]

Lock-free data structures generally use check-and-retry (compare and swap) rather than a lock.

Now, in the face of contention, they don't scale as well as a lock. However, this falls under "optimize when you have data".