Subj : Re: posix and lock-free algorithms
To   : comp.programming.threads
From : David Schwartz
Date : Mon Aug 01 2005 11:47 am


<peter.koch.larsen@gmail.com> wrote in message 
news:1122897299.177100.309120@z14g2000cwz.googlegroups.com...

> David Schwartz skrev:

>> "John Doug Reynolds" <smspiff@fastmail.fm> wrote in message
>> news:1122829815.237744.74450@o13g2000cwo.googlegroups.com...

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

>>     Mutexes only protect memory access that occur while the mutex is 
>> held.
>> In principle, that could be optimized by a sufficiently smart 
>> implementation
>> to nothing.

> Hi David

> Could you elaborate on this? Do you mean to imply that objects that
> might be in two states, where one state assumes that no locking is
> required and the other one does are completely broken? That scenario is
> quite common I believe, e.g. having the object be in the non-locking
> phase during construction.
>
> object* o = create(...);         //  no mutex!
> o->some_extra_initialisation();  //  no mutex!
> make_available_to_others(o);     //  e.g. insertion into some shared
> queue
>
> If some other thread grabs o and uses it - could it be that it will not
> see the "correct" image of o?

    It all depends what "make_available_to_others" does. The statement I 
made above is not completely true, mutexes do slightly more than protect 
accesses while the mutex is held, but they do nothing unless another thread 
acquires the same mutex.

    You are correct that you can do:

object *o=create(...) // no mutex!
o->SomeInitialization(); // no mutex!

    However, to ensure that 'o' is visible to other threads, your 
'make_available_to_others' function must acquire some mutex those other 
threads also acquire to find the object. (Or you must meet the memory 
visibility rules some other way.)

    But a mutex is *NOT* guaranteed to act as a memory barrier. 
Specifically, if thread A acquires mutex A and then thread B acquires mutex 
B, thread B is *not* guaranteed to see changes made by thread A. (And how 
could it? What would force B's actions to be after A's? You only can rely on 
ordering you enforce.)

    DS

.