[concurrency-interest] Lock-free mania

David Holmes dcholmes at optusnet.com.au
Sun Apr 15 19:18:43 EDT 2007


Szabolcs Ferenczi wrote:
> What is the advantage of the lock-free algorithm? Pros:
>
> 1: If there is no conflict in the actual interaction among threads,
>   the overhead is less than by a conventional mutual exclusion
>   algorithm.

Lock-free algorithms address the situation where there *is*
conflict/contention, and where lock-based techniques would require threads
to be blocked. Taking threads off processors and placing them back later
incurs a lot of overheads, cools caches etc and can greatly lower
concurrency. Lock-free algorithms address contention by retrying operations
rather than blocking the thread (though the algorithm may degrade to
blocking depending on what its being used for). It is far more
efficient/effective to repeat a sequence of instructions than to block the
thread.

Livelock is addressed via wait-free / obstruction-free techniques where some
thread is guaranteed to make progress. If a CAS-loop fails for one thread
that means it succeeded for another one.

The implementation of locks will often use "lock-free" techniques internally
to make them more efficient on multi-processor systems.

In the uncontended case, the path through a lock-free algorithm may be
longer than a lock-using algorithm.

> 1: It is more complicated, more difficult to prove its correctness or
>   to test it. It is a major drawback.

Yes which is why we leave it to the experts to define these things and then
use them.

> 2: When there are frequent conflicts between threads, i.e. under heavy
>   load conditions, it becomes a busy waiting loop and, consequently,
>   it becomes very inefficient just at the critical moment.

In the worst-case pathology some threads might continually retry, but that
means other threads made progress. If a CAS loop fails in one thread it is
because it succeeded in another.

> Why are people keen to invent so-called lock-free algorithms if they
> cannot prove the correctness nor can they test them?

I think there are more people keen to use them rather than invent them. And
yes inventing them is fraught with peril and is best left to the experts.

Like any performance tool you need to evaluate it in context. Any mechanism
has a "sweet spot" where it performs best for the given application and
load; and they all degrade under various conditions.

Use the best tool available for a given job.

Note there are also "local" versus "global" performance issues here. If your
server application is the only thing running and tries to utilize all CPU's
all the time, the wait-free/lock-free techniques can be a boon. However, if
there are half a dozen applications running on the system, all competing for
CPU resources, then the use of lock-free might improve the throughput of an
individual application, but at the expense of the other applications. In a
sense lock-free makes an application "greedy" for CPU and in a group
environment it may be better to have less-greedy applications.

Ultimately the best solution is to always remove contention - if you can do
it.

Cheers,
David Holmes



More information about the Concurrency-interest mailing list