Subj : Re: posix and lock-free algorithms
To   : comp.programming.threads
From : David Schwartz
Date : Thu Aug 11 2005 12:54 am


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

> Why isn't this just as
> correct (or not), and slightly better?
>
>  Singleton* Singleton::instance () {
>    Mutex m;
>    if (pInstance == 0) {
>      Lock lock;
>      if (pInstance == 0) {
>        Singleton* tmp = new Singleton;
>        m.lock(); m.unlock(); // just a memory barrier
>        pInstance = tmp;

    While this 'pInstance=tmp;' is executing, another thread could see 
'pInstance' as zero but not see the Singleton. Your error is in thinking 
that the thread that creates the singleton invoking a memory barrier has any 
effect on other threads that don't themselves call memory barrier functions.

    Another thread could see 'pInstance == 0' and not see 'tmp' as complete 
because that thread doesn't call any memory barrier functions after testing 
pInstance but before accessing 'tmp'.

>      }
>    }
>    else { m.lock(); m.unlock(); } // just a memory barrier
>    return pInstance;
>  }

    This code is not guaranteed on all platforms:

Start:

i=0;
j=0;

Thread 1:
i=1;
barrier();
j=1;

Thread 2:
if(j==1) ASSERT(i==1);

    You must do this:

if(j==1)
{
 barrier();
 ASSERT(i==1);
}

    There is no guarantee that a platform only requires memory barriers on 
stores and not on fetches as well. The compiler could legally optimize this:

if(j==1) ASSERT(i==1);

    To this:

int tmp=i;
if(j==1) ASSERT(tmp==1);

    Because, without a memory barrier, the two code sections are equivalent.

    You might thing it's unreasonable, but actually it's quite reasonable. 
The compiler might emit the following pseudo-code:

Read j to register
Read i to register
if(register(i)==1) ASSERT(register(j==1))

    And there's no memory barrier between the two reads, so if 'i' is in 
cache and 'j' is not, the latter read might finish before the former.

    This is so much more complex than most people think it is.

    DS

.