[concurrency-interest] Lock-free mania

Joseph Seigh jseigh_cp00 at xemaps.com
Mon Apr 16 06:47:56 EDT 2007

Szabolcs Ferenczi wrote:

>On 16/04/07, David Holmes <dcholmes at optusnet.com.au> wrote:
>>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.
>I am afraid both flavour addresses the situation when there is
>conflict/contention. The main difference is in the abstraction level.
>The "lock-based" solution stays at a high abstraction level and does
>not specify how to solve the locking. It only defines that
>conflict/contention must be avoided. Locking can be implemented by
>descheduling threads but it can be implemented by spin locking as
>well. It depends on the implementation.
>On the other hand, the "lock-free" solution defines how to schedule
>the threads (manually). And it is both complicated and difficult to
>prove or test.
>Do not forget that we are speaking of short term scheduling. Note that
>for long term scheduling "lock-free" versions are inefficient.

You're making a lot of unsupported suppositions here.  One of the issues 
is  forward progress.
Lock-free (by definition) guarantees at least one thread makes forward 
progress.  Wait-free
guarantees the current thread will make forward progress.   Conventional 
(mutexes and condvars) don't make any guarantees about forward progress, 
they only
make guarantees about when forward progress will not be made, i.e. 
negative guarantees.
The early Java docs used to make statements about only using cooperative 
threads in part
because of this.  You could only guarantee forward progress in a thread 
if in the case
where it didn't make forward progress, eventually enough other threads 
would block and
allow the former to make forward progress.  Competive threading patterns 
don't guarantee
forward progress for all threads.  Some threads may be allowed to starve.

As far as proving correctness, lock-free implementations aren't any more 
difficult to prove than
lock implementations in my experience.  Proving anything in general is 
fairly diffcult, though.
Mostly it's figuring out which assertions to prove.

Testing isn't necessarily all that difficult either.  Some lock-free 
algorithms allow you to make
observations that aren't available to lock based algorithms.  You can 
use this to verify that
your code works under some boundary conditions, e.g. that you've avoided 
certain race

Joe Seigh

More information about the Concurrency-interest mailing list