Subj : Re: posix and lock-free algorithms
To   : comp.programming.threads
From : Joe Seigh
Date : Thu Aug 11 2005 11:40 am

John Doug Reynolds wrote:
> In transcribing their example I realize now that I obscured what I'm
> sure was their intention.  With apologies to Meyers and Alexandrescu,
> here is a clearer statement:
> 
>   Singleton* Singleton::instance (Mutex& shared) {
>     Mutex local;
>     if (pInstance == 0) {
>       shared.lock();
>       if (pInstance == 0) {
>         Singleton* tmp = new Singleton;
>         local.lock(); local.unlock(); // just a memory barrier
>         pInstance = tmp;
>       }
>       shared.unlock();
>     }
>     else { local.lock(); local.unlock(); } // just a memory barrier
>     return pInstance;
>   }
> 
> 
>>Because apart from the fact that your code is data-race UNfree,
>>lock-unlock under POSIX-compatible release consistency models
>>doesn't really substitute a bidirectional fence. It would sorta work
>>in your case (violation of POSIX data-race free requirement aside
>>for a moment), but only if you lock-unlock the *same* mutex on both
>>slow and "fast" paths, not different mutexes on the stacks of
>>participating threads.
> 
> 
> I'm uncertain whether you are objecting to the apparently local nature
> of the Lock in my original transcription, or whether you are pointing
> to a more fundamental problem.  If so, could you explain your
> assertions more fully?
> 

It has to be the same lock used by all the threads so a local lock won't
do anything since all storage accesses by a thread appear in program
logical order to that thread anyway.  Part of the problem here is that
Posix doesn't formally define its semantics so you really can't say what
Posix mutexes do or do not do.  I suppose I should post the formal
semantics for generic (not Posix) mutexes sometime.  It might help with
reasoning about what mutexes do and do not do.


-- 
Joe Seigh

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

.