Subj : Re: posix and lock-free algorithms
To   : comp.programming.threads
From : Sean Kelly
Date : Mon Aug 01 2005 05:11 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.

Scott Meyers and Andre Alexandrescu wrote a two-part article for Dr.
Dobbs Journal on this exact subject.  I found a link to a revised copy
here:

http://www.aristeia.com/Papers/DDJ_Jul_Aug_2004_revised.pdf

The basic problem is the "as if" rule and the fact that the C/C++
standards say nothing about concurrency.  For what it's worth, DCL does
work in D and (I think) in Java as well, as both redefine the meaning
of "volatile."

> 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.

I think support for DCL is really more of a language issue than a POSIX
issue, though the line does blur a bit at times.  Memory barriers are
only half the problem, as the compiler can reorder instructions as
well.

> 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(); }

The whole point of DCL is to avoid the cost of a mutex lock whenever
possible, so this method makes little sense.  As for memory barriers,
you might get lucky with specific implementations, but it isn't
something I would rely upon.

> 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?

See above.  It's the "as if" rule that's the trouble.  Around the time
the articles I mentioned were published, there was also a firestorm of
activity on comp.lang.c++.moderated and (I think) on comp.std.c++ on
this issue.  Searching for Alexander Terekhov's name would probably be
a good way to track down the threads :)


Sean

.