Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

A common definition of lock-free is that at least one process makes progress. 1

If I have a simple data structure such as a queue, protected by a lock, then one process can always make progress, as one process can acquire the lock, do what it wants, and release it.

So does it meet the definition of lock-free?


1 See eg M. Herlihy, V. Luchangco, and M. Moir. Obstruction-free synchronization: Double-ended queues as an example. In Distributed Computing, 2003. "It is lock-free if it ensures only that some thread always makes progress".

share|improve this question
3  
I've always understood "lock free" to describe a data structure and set of algorithms that don't use locks, just a small defined set of atomic memory operations. E.g. drdobbs.com/parallel/writing-lock-free-code-a-corrected-queue/… – Paul Johnson Jan 21 at 16:39

That's no definition for lock-free.

If you can guarantee progress then you have deadlock-free, and if you have the eventual completion of every request, then you have starvation-free, but not lock-free.

I question whether your simple example actually provides this anyway. You need lock hierarchies and so on to actually make progress guarantees when multiple locks are involved.

share|improve this answer
1  
I'm using the definition from M. Herlihy. A methodology for implementing highly concurrent data objects. Transactions on Program- ming Languages and Systems, 1993. "The lock-free condition guarantees that some process will always make progress despite arbitrary halting failures or delays by other processes" – Joe Pension Mar 23 '12 at 22:12
12  
@Joe: That isn't a definition, it describes an implication. Beware the logic fallacy of the inverse. – Ben Voigt Mar 23 '12 at 22:15
2  
Could also quote M. Herlihy, V. Luchangco, and M. Moir. Obstruction-free synchronization: Double-ended queues as an example. In Distributed Computing, 2003. "It is lock-free if it ensures only that some thread always makes progress". – Joe Pension Mar 23 '12 at 22:25
1  
there is also starvation free which is more specific than deadlock free (every process gets to go no matter what other processes do) note that CaS loops (based on atomic primitives) aren't – ratchet freak Mar 23 '12 at 22:37
5  
@Joe: If the rest of the world calls that property deadlock-free, then I'm going to use that term. No, your simple example is not deadlock-free. In order to guarantee that something is deadlock-free, you not only need synchronization, but a guarantee that no thread performs any blocking operation while holding the lock. "do what it wants" is extremely vague and doesn't appear to provide this guarantee. – Ben Voigt Mar 23 '12 at 23:22

I've studied The Art of Multiprocessor Programming1 and their text is lacking in clarity, just like the book you refer to. Here are some quotes from TAMPP:

Quote 1 (Definition of lock-free)

A method is lock-free if it guarantees that infinitely often some method call finishes in a finite number of steps.

Quote 2 (Definition of nonblocking)

a pending invocation of a total method is never required to wait for another pending invocation to complete.

Quote 3 (claim that lock-free is nonblocking)

The wait-free and lock-free nonblocking progress conditions guarantee that the computation as a whole makes progress, independently of how the system schedules threads.

The problem is that the claim in Quote 3 does not obviously follow from the definition in Quote 1. As already mentioned, a synchronized queue seems to satisfy Quote 1: infinitely often some method will successfully acquire the lock and complete.

Note specifically the quite vague phrase in Quote 3: "independently of how the system schedules threads". This is not preceded by any kind of a formal description of the "thread-scheduling system", so we are left to reconstruct its properties based on our preconceptions on what the definitions should mean:

  1. the system always executes instructions of some thread;
  2. it may never execute instructions of any given thread;
  3. all the threads are invoking the method under consideration.

On such a system, a blocking method cannot be lock-free: if the thread holding the lock is never again scheduled for execution, there will be no other thread which can complete its method invocation in a finite number of steps, yet there will be some threads that are executing steps of the method. For a more realistic system, one which does guarantee to give CPU time to each thread eventually, the definition must explicitly include the nonblocking property:

Corrected definition of lock-free

A method is lock-free if it is non-blocking and, additionally, guarantees that infinitely often some method call finishes in a finite number of steps.

1 Maurice Herlihy, Nir Shavit, The Art of Multiprocessor Programming, Elsevier 2008, pp. 58-60

share|improve this answer
1  
The wording of quote 1 is really strange. What do they mean by "infinitely often"? Obviously something different than "always", so it is ok that the method does never return in "some" cases? – Hulk Jan 22 at 9:23
    
Yes, imprecise language abounds. What's "often" anyway? I think they mean "in an infinite execution history, this particular event occurs infinitely many times". – Marko Topolnik Jan 22 at 9:25

Terminology isn't always consistent, but I think what's important is to ask the following questions about a proposed algorithm or system:

  1. Is there any sequence of events where threads could become stuck waiting for each other even if all threads were allowed all CPU time they could use [if so, it's not deadlock free]
  2. If one thread were blocked for an arbitrary long time, could that stall other threads or impair system operation for an arbitrarily long time [if so, it's not non-blocking].
  3. Is there some at-least-theoretically possible combination of thread scheduling which could cause all threads to repeatedly retry the same operations while invalidating each others' work, without anyone making progress [if so, it's not lock-free]
  4. If some threads are given sufficiently CPU time relative to another, could they force the latter thread to keep retrying its operations indefinitely [if so, it's not wait-free].

Much of the significance of lock-free algorithms isn't that they're faster than non-lock-free algorithms, but rather the fact that they aren't prone to dying if a thread gets waylaid [note that such a guarantee merely requires that algorithms be non-blocking, but all lock-free algorithms are]. It's possible for a lock-free algorithm to use locks, but only if lock-acquisition attempts include timeouts along with algorithms to ensure that it will always be possible for someone to make progress (for example, an algorithm could use a CompareExchange loop as its primary arbitration method, but use locks to arbitrate access when contention seems high; if a lock seems to be held for excessively long, other threads could decide to abandon efforts to use that lock and instead create a new one. Note that because consistency is ensured via CompareExchange, having customers abandon the lock wouldn't jeopardize system consistency, though it may mean that code which had been holding the old lock won't get any work done until it too abandons the old lock and gets in line for the new one.

share|improve this answer
    
This is different from standard terminology: your 2. refers to the standard meaning of non-blocking whereas 3. refers to lock freedom. – Marko Topolnik Jan 23 at 14:04
    
I've seen inconsistent terminology usages, and I don't know of an "official" standard. What's most important is that there are different guarantees an algorithm may be able to offer, and it's important to use an algorithm which offers guarantees sufficient to meet application requirements. Many papers only cover some of the guarantees above, but there are cases where each may be be able to satisfy application requirements more easily than any other guarantees which would meet requirements. – supercat Jan 23 at 19:33
    
I think there's a consensus that the terminology presented in The Art of Multiprocessor Programming is "standard". – Marko Topolnik Jan 24 at 14:56
    
@MarkoTopolnik: I'll edit the post to fit that then. Do you like the new version?. – supercat Jan 24 at 22:05
    
Cool, very nice. – Marko Topolnik Jan 27 at 6:20

You have to look at the "definition" you quote in context:

The traditional way to implement shared data structures is to use mutual exclusion (locks) to ensure that concurrent operations do not interfere with one another. Locking has a number of disadvantages with respect to software engineering,fault-tolerance, and scalability (see [8]). In response,researchers have investigated a variety of alternative synchronization techniques that do not employ mutual exclusion. A synchronization technique is wait-free if it ensures that every thread will continue to make progress in the face of arbitrary delay (or even failure) of other threads. It is lock-free if it ensures only that some thread always makes progress.

You're using locks for mutual exclusion, thus it's not a lock-free technique they are talking about.

share|improve this answer

If I use locks, can my algorithm still be lock-free?

It could be, but it depends on the algorithm.

If I have a simple data structure such as a queue, protected by a lock, then one process can always make progress, as one process can acquire the lock, do what it wants, and release it.

So does it meet the definition of lock-free?

Note per se.

If the "do what it wants" step does not involve acquiring any other locks, and it is guaranteed to complete in a finite time, then this particular part of your algorithm will be deadlock free.

However, if those preconditions are not satisfied, there is at least the potential for deadlocks ...

share|improve this answer
    
After some study of the text in The Art of Multiprocessor Programming I've come to the conclusion that mutexes definitely invalidate the definition of lock-free, when the definition is correctly spelled out. I've added an answer to this page to clarify this. – Marko Topolnik Jan 21 at 10:11

The example you give is not lock-free for the following reason.

Support one thread acquires the lock, and the OS scheduler suspended the thread for a infinite lone period, then all of the thread cannot make progress because no can can acquire the lock that is acquired by the suspended thread.

Generally speaking, algorithms that use locks are not lock-free.

Note that deadlock-free and lock-free are two different concepts. deadlock-free means there is no possibility for deadlock, but there could be livelock which can prevent the whole system from making progress. Lock-freedom is stronger than that because it means some threads in the system always makes progress with finite number of steps.

share|improve this answer
    
Look at a more careful definition on Wikipedia: "An algorithm is lock-free if it satisfies that when the program threads are run sufficiently long at least one of the threads makes progress." This excludes the case of halting threads. Also progress under halting is covered by obstruction freedom, not lock freedom. – Marko Topolnik Jan 21 at 7:51
    
@MarkoTopolnik Your comment does not make sense at all. Lock-freedom covers obstruction-freedom. Anything that is lock-free must be obstruction-free. And the definition you gave does not exclude halting threads. – Chaoran Jan 26 at 17:59
    
Please take care to distinguish "making sense" from "being correct". My comment is incorrect, as can be seen from my subsequent answer. But the Wikipedia definition is also wrong or at least ambiguous. – Marko Topolnik Jan 26 at 20:23
    
@MarkoTopolnik Since you admit that your comment is not correct, you should remove it to avoid confusing other readers. Wikipedia is often incorrect or ambiguous. You should find subtle definitions like "lock-freedom" in academic papers such as cs.rochester.edu/~scott/papers/2006_PPoPP_synch_queues.pdf (the definition of lock-free is in section 2.1) – Chaoran Jan 26 at 22:37
    
Yes, including the nonblocking property as a part of the definition of lock-freedom is one way to do it. That was stated in an earlier revision of my answer. – Marko Topolnik Jan 27 at 6:13

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.