869
Subj : Re: posix and lock-free algorithms
To   : comp.programming.threads
From : John Doug Reynolds
Date : Thu Aug 04 2005 06:28 am

> 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

Sean, thanks for the article!

The authors seem to conclude that DCSI could be implemented portably
in C/C++ under Posix, if Posix supported explicit memory barriers.
They do not discuss constructing a memory barrier from the available
Posix synchronization primitives, or explain why

     void memory_barrier() { mutex m; m.lock(); m.unlock(); }

does not work for that purpose.  According to David Schwartz,

 "In principle, that could be optimized by a sufficiently smart
  implementation to nothing."

If so, then as you say, it is a language issue, not a failure of Posix
to provide the necessary tools.  But I wonder about David's claim.
While it's obvious to the human reader that my function is an
expensive no-op, the compiler has to actually prove this, right?  And
from what Meyers and Alexandrescu said in their article, wouldn't the
implementions of pthread_mutex_lock() and pthread_mutex_unlock() act
as "hard sequence points" and so stop the compiler from combining and
removing them?  But perhaps I misunderstand.  In any case, this sounds
like a question for a different news group.

> The whole point of DCL is to avoid the cost of a mutex lock whenever
> possible, so this method makes little sense.

I'm only trying to avoid locking _contention_ between reader threads,
and while this may not be the most efficient solution possible, it
does at least have the property that the function will never be
hindered by another thread.

So I'm left with my original question: if it just requires the use of
portable memory barriers to implement DCSI in C/C++ under Posix, why
is it so generally considered to be impossible?  What really is the
reason why a memory barrier can't be constructed from other
synchronization primitives?

Doug

.

0