Subj : Re: posix and lock-free algorithms
To   : comp.programming.threads
From : John Doug Reynolds
Date : Wed Aug 10 2005 09:52 pm

> Even if you stuck strictly to Posix functions, Posix doesn't address
> things like word tearing, so you couldn't write "correct" portable
> programs even if you wanted to.  Plus there's the fact that Posix
> has no formal semantics so you couldn't prove a program correct if
> you wanted to do that either.  The arguments that Posix functions
> could do this or that are a little silly.  A posix program could
> turn itself into a bunny rabbit and be compliant.

Ah!  I finally might understand!  DCSI requires an atomic update to
the memory being initialized, and Posix offers no way to guarantee
this without serializing both read and write access to that memory.
So, a portable implementation will require a compiler that is prepared
to align the variable in memory such that updates are atomic, and that
is not a language feature of C/C++.

If I have the above right, then the implementation suggested Meyers
and Alexandrescu can be completed (non-portably) as follows, assuming
a Posix compliant compiler and any architecture with atomic write to
pointer type.

> Singleton* Singleton::instance () {
>   Singleton* tmp = pInstance;
>   Mutex m; m.lock(); m.unlock(); // just a memory barrier
>   if (tmp == 0) {
>     Lock lock;
>     tmp = pInstance;
>     if (tmp == 0) {
>       tmp = new Singleton;
>       m.lock(); m.unlock(); // just a memory barrier
>       pInstance = tmp;
>     }
>   }
>   return tmp;
> }

Two things puzzle me about this.  First, surely they considered the
above, so why didn't they discuss it?  Second, what's with all the
extra copies to tmp?  I can't help suspecting that I still don't
really get how to think about this problem.  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;
      }
    }
    else { m.lock(); m.unlock(); } // just a memory barrier
    return pInstance;
  }

Thanks for your patience with what I have to imagine are rather
tedious questions!

Doug

.