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

Question

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

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?

---

¹ 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".

Answer 1

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.

Answer 2

I've studied The Art of Multiprocessor Programming¹ 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.

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

Answer 3

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.

Answer 4

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.

Answer 5

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 ...

Answer 6

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.