[MaxBarraclough]

That would open the door to thread-starvation, right? Unlikely in practice, but the point being that it does affect the formal correctness of the algorithm.

I imagine it also impacts real-world performance, but lock-free algorithms aren't assured to be faster anyway.

Annoyingly I recall reading a good article on exactly this question - the importance of hardware atomics vs locking - but can't recall what it was. These locks still aren't as bad as ad-hoc locking, in terms of deadlock risk, as you're guaranteed that they are 'leaf locks', with no order-of-acquisition hierarchies/orderings to worry about.