Subj : Re: posix and lock-free algorithms
To   : comp.programming.threads
From : Joe Seigh
Date : Sun Jul 31 2005 02:37 pm

John Doug Reynolds wrote:
> [from the 19 May 2005 posting by Joe Seigh]
> 
>>The only thing we can say about Posix is there are a few well known
>>thread design patterns that are widely considered as being supposed
>>to work in Posix.  DCL (DCSI) as being an example of a pattern that
>>does not work in Posix.  I'd name some patters that do work in Posix
>>but I don't think we have names for those patterns.
> 
> 
> Joe,
> 
> I have been following c.p.t archives on DCL/DCSI going back seven
> years, starting with Dave Butenhof's FAQ (wonderful resource, thanks
> Dave!), but somehow I've missed the conclusion you stated here, and
> I'm hoping you can point me to where the explanation is given.
> 
> Most postings I've read so far seem to conclude that DCSI is possible,
> the only problem being how to implement it under Posix.  That's where
> the statements usually get pretty vague, and I'd like to understand
> this point.  If it's just a problem of implementation, can we expect
> that some future version of Posix will support this pattern?
> 
> I get the idea that the issue is that Posix does not provide explicit
> memory barriers.  If so, then there must be some reason why this
> construct does not do the trick:
> 
> 	void memory_barrier() { mutex m; m.lock(); m.unlock(); }

That will work but the point of DCSI or DCL is to avoid using a
mutex in the first place.  It just becomes regular locked access.
There's some atomicity guarantees that are needed so you need to
put accesses of the DCSI check variable inside the locked region.

> 
> Is this explained somewhere?  Or is it that--as I believe David Holmes
> has stated--even memory barriers do not fix this pattern?  If so, why
> is it only a problem of implementation under Posix, and not a
> fundamental flaw in the pattern itself?

He might have been referring to atomicity.

> 
> Also, you mention the existence of some lock-free patterns that can be
> implemented under Posix but don't have well known names.  Can you
> offer some keywords that I might search on?

I wasn't referring to lock-free patterns.  They're regular pthread
usage patterns, just nobody I think has given names to the common
ones.  Maybe reader/writer with rwlocks and producer/consumer with
semaphores or condvars but those are instances of the more general
patterns.

You might look at Doug Lea's book on concurrent programming in Java.
He might have names for some of the patterns.  Java supports lock-free
programming to some extent so you'll find some of that there also.  The
main things Java has to support lock-free is atomicity and JSR-133 volatile
semantics which give volatile variables acquire and release semantics if
I got that right.

-- 
Joe Seigh

When you get lemons, you make lemonade.
When you get hardware, you make software.

.