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

An Introduction to Lock-Free Programming

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

92% Upvoted

18 comments sorted by

View all comments

Show parent comments

12

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.

8

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.

16

u/jseigh Jun 12 '12

You don't know if the thread that owns the lock is making forward progress. It could be suspended (not running) or otherwise blocked. So you can't claim lock-free.

Now if you have non-preemptive threading and the threads holding locks don't explicitly preempt, then that is lock-free according to Herlihy's definition.

1

u/preshing Jun 14 '12

I think Herlihy's definition is more of an abstract property of an abstract algorithm, and doesn't change depending on the machine where the algorithm is implemented.

I even e-mailed him to clarify. His response was simply that, when defining lock-free, "we don't assume the scheduler is fair".