Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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

4 Answers 4

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
6  
@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
4  
@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

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 is blocked for an arbitrary lock time, could that stall other threads or impair system operation for an arbitrarily long time [if so, it's not lock-free].
  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 non-blocking]
  4. If some threads are given lots of CPU time, could they force another 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. It's possible for a lock-free algorithm to use locks, but only if the algorithms can fully recover in the event a thread gets waylaid while holding a lock (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).

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

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

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.