[concurrency-interest] Lock-free mania
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
>>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
guarantees the current thread will make forward progress. Conventional
(mutexes and condvars) don't make any guarantees about forward progress,
make guarantees about when forward progress will not be made, i.e.
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
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
More information about the Concurrency-interest