Slides for tomorrow night

[Maged Michael]

>> Slide 12: Add disadvantages: Subject to livelock, high memory 
contention,
>> hard to control backoffs, ...
>> 
>>   (I like lock free algorithms a lot, but that's because I know when 
not
>>   to use them :-)
>
> Thanks, good points which I'll integrate. But I didn't think CAS-based 
> programming is prone to livelocks... Maged?

Using the following the definition of lock-free, it is livelock-free: 
Whenever a thread executes some finite number of steps towards an 
operation on a shared lock-free object, it is guaranteed that during the 
execution of these steps, some operation on the object has completed.

Obstruction-free is the one that is livelock-free. Lock-free is 
obstruction-free and livelock-free. Wait-free is lock-free and 
starvation-free. 
Non-blocking used to be synonymous with lock-free, but recently with 
papers on obstruction-free, non-blocking stands for obstruction-free 
(which by definition is a superset of lock-free, which in turn is a 
superset of wait-free).

>> The slides look good.  If you feel time is tight you might consider 
>> moving the slides about lock-free structures as backup. The simple and 
>> compelling case is made by the flag example and user-level locking.

> Thanks. Why do you think CAS-based stuff should be a backup argument?

I just thought that a general statement about lock-free algorithms (that 
they have (sometimes) performance and flexibility advantages over 
conventional locking, e.g., signal safety, immunity to deadlock under 
priority inversion) can have the same effect as the 3 slides, especially 
that there is no time to give concrete examples (other than 
single-variable read-modify-write).

One possibility is to extend the ticker example to a buffer of ticker 
data, unless the buffer is full the producer doesn't wait for the 
consumer. This what the Linux tracing tool (contributed by IBM K42) does, 
except that the producer doesn't wait for the consumer, if the consumer is 
slow, the producer keeps going and overwrites old events (which may 
acceptable also for ticker symbols). I don't recall the exact algorithm 
details so I don't know if this example is simple enough to fit the time, 
and whether we have the time to write a bug-free example in a few hours.
http://www.opersys.com/LTT/

Maged
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://shadbolt.decadentplace.org.uk/pipermail/cpp-threads/attachments/20041018/c0c8a698/attachment.html