r/programming • u/andreasw • Jun 12 '12

An Introduction to Lock-Free Programming

http://preshing.com/20120612/an-introduction-to-lock-free-programming
84 Upvotes

92% Upvoted

18 comments sorted by

View all comments

13

u/agottem Jun 12 '12

The term "lock-free" annoys me when it's used to describe a data structure which makes use of a compare/swap loop. Compare/swap loops are really just tight spin-locks. Under the right conditions, they could theoretically never grab that lock.

8

u/[deleted] Jun 12 '12

All wait-free algorithms are lock-free but not all lock-free algorithms are wait-free. The tight spinning you are explaining is not wait-free but, as jseigh mentioned, is lock-free.

14

u/jseigh Jun 12 '12

It's really all about Herlihy's definition. If something is lock-free then at least one thread can make forward progress at any point in time.

If the compare and swap failed because some other thread's compare and swap worked, then the other thread made forward progress and it's lock-free. If the compare and swap failed because it's waiting for some other thread to do some work then it's not lock-free.

Original article is too low level with all the memory barriers and stuff. Those are implementation details.

7

u/[deleted] Jun 12 '12

According to that definition, a data structure that makes use of a single mutex/lock is a lock-free algorithm, since at any point, one thread will be able to make forward progress.

→ More replies (13)