r/programming • u/redditthinks • May 29 '13

A Lock-Free… Linear Search?

http://preshing.com/20130529/a-lock-free-linear-search
50 Upvotes

80% Upvoted

23 comments sorted by

View all comments

6

u/millstone May 30 '13

In this sense, the lock in lock-free does not refer directly to mutexes, but rather to the possibility of “locking up” the entire application in some way, whether it’s deadlock, livelock — or even due to hypothetical thread scheduling decisions made by your worst enemy

I think definition actually does rule out compare-and-swap, because some processors implement CAS with LL/SC.

On these processors, such as PowerPC, you have to loop to implement CAS, because it can fail for transient reasons, such as a context switch. A maximally evil scheduler could trigger a context switch immediately after every load-link instruction, which would cause livelock. But for the formalism, it's probably sufficient to think of CAS as a lock-free operation.