What does "lock free" mean on modern architecture?

[Elazar Leibovich]

I'm not sure if this is the correct forum, I think it's related, but let me know if I'm wrong.

The definition of a lock free object, is, an object, where at least one thread running a method on it, is bound to finish running it in a constant amount of time.

So why is a typical code that uses locks isn't lock free?

class Counter {

    ReentrantLock l = new ReentrantLock();

    private int n = 0; 

    void inc() {

         l.lock();

        try {

            n++;

        } finally {

            l.unlock();

        }

    }

} 

 

The code above doesn't look like it's lock free, since, err..., it uses a lock. However one thread will always finish in a constant amount of steps - the one that holds the lock.

The motivation for this definition originally, if I understand that correctly, is that without a CAS instruction one cannot implement a lock that is bound to finish in a finite amount of steps. So without CAS, the above code cannot guarantee any thread to run inc in a finite amount of threads.

Today, as you can see, the ReentrantLock is implemented with CAS (link) so my Counter class is indeed lock-free by definition...

Moreover, given CAS, every object can be turned into a wait free object, with a certain construction. There's a nice exposition for that in The Art Of Multiprocessor Programming.

It sounds to me that in practice, on modern architecture, saying "wait free" or "lock free" is more or less like saying "computable by a Turing machine".

I'm not trying to trigger a deep philosophical debate about "what is the real meaning of lock free".

I'm trying to understand whether I can gain any useful insight from knowing that a certain algorithm is lock-free, or can I just treat it like saying the algorithm is "compatible with cloud computing". 

[Martin Thompson]

One way to think about this not being lock-free is to consider an interrupt occurring to the thread inside the lock. At this point no threads are currently making progress, if others have been blocked and parked by the operating system. If the code had been replaced with a CAS instruction in a loop then at least one thread could be making progress and any point of time if more than one thread was concurrently trying to update the counter. If the algorithm had been replaced by LOCK XADD on x86 it would then be wait-free.

--
You received this message because you are subscribed to the Google Groups "mechanical-sympathy" group.
To unsubscribe from this group and stop receiving emails from it, send an email to mechanical-symp...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Henry Robinson]

Lock-freedom is meaningful only when you consider a scheduler which is making decisions about which thread to run next - and which can conspire against you to arbitrarily delay the thread that you really want to run. If you're using locks, and the scheduler decides to arbitrarily delay the thread that holds the lock, no other thread can make progress.

A lock-free algorithm guarantees that at least one of the threads that _are_ selected for execution will complete its operation in a finite period. This is a useful property: an adversarial scheduler (or other source of unexpected delay, e.g. IO) cannot hold up system-wide progress.

Also note that there's nothing magical about CAS that makes algorithms lock-free or otherwise - as you say, locks may be implemented using CAS. It's how the instructions are deployed that causes an algorithm to become lock-free or not. If one thread has to wait on another, distinguished thread, to make progress, it won't be executing a lock-free algorithm.

Henry

--

You received this message because you are subscribed to the Google Groups "mechanical-sympathy" group.
To unsubscribe from this group and stop receiving emails from it, send an email to mechanical-symp...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

--
Henry Robinson
Software Engineer
Cloudera
415-994-6679

[Elazar Leibovich]

I don't think this is the definition for lock-free.

If I understand you correctly, you essentially require any thread to finish its work in constant amount of steps. Why do I say any thread? Because the adversarial scheduler can choose to run any of the threads alone, and you still expect system wide progress.

To my understanding this is the definition of wait-free, not lock free.

There is something magical about CAS, at least according to The Art Of Multiprocessor Programming. This instruction have consensus number of infinity, and hence can be used to generate lock-free and wait-free objects from any object.

For example, have I used Peterson lock, and evil scheduler could make the lock itself wait forever. With CAS, this is simply impossible regardless of scheduler.

--
You received this message because you are subscribed to a topic in the Google Groups "mechanical-sympathy" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/mechanical-sympathy/Tm3xRcvpnzE/unsubscribe.
To unsubscribe from this group and all its topics, send an email to mechanical-symp...@googlegroups.com.

[Elazar Leibovich]

While I may agree that this should be the definition for lock-freedom, I don't think this currently is. In Wikipedia, as well as The Art Of Multiprocessor Programming the definition is that always at least one thread is making progress.

That said, I'm not sure I completely understand your definition.

How many thread am I allowed to freeze, and I can still expect the system to work? If I can freeze all threads except one, than the system is actually wait-free, since all threads will finish in constant time regardless of other threads.

--
You received this message because you are subscribed to a topic in the Google Groups "mechanical-sympathy" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/mechanical-sympathy/Tm3xRcvpnzE/unsubscribe.
To unsubscribe from this group and all its topics, send an email to mechanical-symp...@googlegroups.com.

[Georges Gomes]

The definition is weird

" always at least one thread is making progress."

That's always the case... Otherwise it's dead-lock :)

I would call a lock-free algo, an algo that never parks a thread.
Lock() does CAS and a few think then park to OS scheduler if fails.

Wait-free is even more interesting to define :)

My 2 cents

[Henry Robinson]

On 10 May 2014 14:07, Elazar Leibovich <ela...@gmail.com> wrote:

I don't think this is the definition for lock-free.

If I understand you correctly, you essentially require any thread to finish its work in constant amount of steps. Why do I say any thread? Because the adversarial scheduler can choose to run any of the threads alone, and you still expect system wide progress.

You're correct - but that simply confirms that 'any' is drawn from the set of threads executed by the scheduler. If the scheduler chooses only to execute one thread, a lock-free algorithm will guarantee that that thread will complete its operation. But if the scheduler chooses to interleave two or more threads, being lock-free only guarantees that one of those threads will complete its operation in finite time. 

 

To my understanding this is the definition of wait-free, not lock free.

Wait freedom says that _all_ threads that are executed for a sufficiently large - but finite - number of steps will complete their operation.

A counter using CAS is a good example:

// 'val' is some atomic integer type

while (true) {

  int old = val.old;

  if (val.CAS(old, old + 1) == old) break;

}

If you've got many threads running this code at once, some thread from that set will always make progress and successfully increment the counter. But you can't guarantee that any particular thread will make progress, since it could be getting starved by not executing line 3 quickly enough after line 2, 'old' becomes stale since another thread changed val and therefore the CAS will not succeed.

So this implementation is not wait-free, because some thread may be caused to wait. It is lock-free, because the scheduler cannot prevent some thread from successfully incrementing the counter.

 

There is something magical about CAS, at least according to The Art Of Multiprocessor Programming. This instruction have consensus number of infinity, and hence can be used to generate lock-free and wait-free objects from any object.

Well, yes, CAS has very nice properties, but don't interpret those to mean that all algorithms using CAS as a synchronization primitive are necessarily lock- or wait- free: it's very easy to construct counterexamples.

Henry

[Elazar Leibovich]

Not always makes a progress, always finish with a finite number of steps. With extreme bad luck, Peterson lock can never finish.

[Martin Thompson]

Given a set of threads that are ready to run and execute a concurrent algorithm, and given at least one processor is available, then at least one thread should always be able to make progress in the algorithm to be lock-free. This is my mental model.

If you take any algorithm with locks (think mutex) and within the lock a thread can block for any reason (IO, Interrupt, taking another lock, etc.) then the algorithm is not lock-free.

There are many multi-step CAS based algorithms that are not lock-free that can be a complete nightmare in the presence of interrupts and insufficient CPU resource. I put one of them in the original Disruptor and lived to regret it :-)

[Ross Bencina]

On 11/05/2014 7:10 AM, Elazar Leibovich wrote:
> While I may agree that this should be the definition for lock-freedom, I
> don't think this currently is. In Wikipedia, as well as The Art Of
> Multiprocessor Programming the definition is that always at least one
> thread is making progress.

Hello Elazar,

Keep in mind that "lock-free" is a property of of the ensemble of
threads executing the algorithm over a shared resource.

The lock-free property provides a global forward-progress guarantee: At
least one thread executing the algorithm will *always* make forward
progress. It says nothing about whether individual operations complete.

To be clear, the global forward-progress guarantee applies only to the
threads executing the algorithm, not to other unrelated threads that may
be scheduled. So, we are not talking about global forward progress of
the whole system, we are talking about global forward progress of the
threads that are executing the algorithm.

One example of something that is not lock-free is a live-lock condition,
where two threads executing an algorithm "fight" indefinitely, so no
global progress is made. Lock-free guarantees the absence of live-lock.

Another example, which has already been mentioned, is the blocking
condition, where the suspension of one thread mid-operation will halt
forward progress of all other threads executing the algorithm. (i.e. the
suspended thread may block other threads indefinitely). This is similar
to what happens if a thread is suspended inside a critical section
(other threads wanting to access the critical section are blocked from
doing so). One way to think about it is that lock-free algorithms are
immune to priority inversion.

Note that the global forward progress guarantee of "lock-free" does not
say anything about fairness. For example, the ensemble of threads can
make forward progress while an individual thread may be indefinitely
starved (fail to make progress) and this would still be called "lock
free" -- since globally, forward progress is being made. On the other
hand, a wait-free algorithm guarantees that every operation completes in
a bounded number of steps.

Ross.

[Rüdiger Möller]

My (very own) definition:

Completely lock free:

No thread is waiting for anything ever except for new input (true idle).