Pascal Costanza wrote:
> On 28 Oct 2010, at 14:43, Michael Weber wrote:
>> On Oct 28, 2010, at 14:33 , Pascal Costanza wrote:
>>> CAS-based algorithms can also suffer from live locks
>> Care to elaborate with a small example?
>> (CAS by itself is pretty nicely composable, unless you rebuild locks
>> with it (write-in-progress bit, etc.). Only the ABA problem needs to be
>> taken care of, in particular in the presence of GC.
> You can also build CAS out of locks. Nikodemus example shows this. So
> depending on how you use locks, they are also 'composable'.
You can write a CAS-like operation with locks; but this example does not
qualify as a true CAS. If an unfortunate SLEEP or other scheduling occurs
inside it, then deadlock will occur just like any other locking mechanism.
> CAS is typically used like this:
> (loop for old-value = (get-vale-from store)
> for new-value = (perform-some-computations)
> until (cas store old-value new-value))
> Depending on how unlucky you get, two or more threads may attempt to
> change the same memory location at the same time using this approach, and
> may roll each other back indefinitely. There are some heuristics you can
> use to try to avoid such a situation (like waiting for increasing amounts
> of time before trying another attempt, in order to allow other threads to
> make progress), but to the best of my knowledge, there is no solution that
> guarantees that such live locks will never occur.
The current literature distinguishes between nonblocking, lock-free, and
The latter are generally hard to develop, and there may be restrictions on
> A dead lock is easier to debug, because you know when you have one, and
> you can analyze where it comes from. A system that just keeps on running
> without making progress is harder to analyze.
Ah, but once you attach a debugger to some of the offending threads, the
problem goes away. ;)
There's also another problem that people often forget when composing CAS
operations: your critical section may be bigger than a single CAS... Say
I'm updating a doubly-linked list. I can't then CAS the prev, CAS the
next, and say I'm thread safe. If I get paused, you could easily see the
nodes in an inconsistent state. This can even lead to persistent errors:
I CAS prev, you CAS prev, you CAS next, I CAS next -- now we are both
done, but prev and next don't reciprocate.
Conclusion: For many things, CAS composes much better than locks.
However, it is still no magic bullet; and for many tasks, CAS is much
harder to reason about.