[boost] condvar signaling and memory synchronization [was: Re: Threads Review]

From: Alexander Terekhov (terekhov_at_[hidden])
Date: 2002-10-17 12:23:49

David Abrahams wrote:
[...]
>    +------------------------------+...
>    | The sequence point at a call |...
>    | to a library function which  |...
>    | signals or broadcasts a      |...
>    | condition variable           |...
>    +------------------------------+...

A) This rule is *defective* because it would severely restrict
   "advanced compilation systems" from doing some reasonable
   optimization (e.g. keep the shared data in the registers) 
   across signal/broadcast. To me, it clearly contradicts the 
   POSIX rationale as well. As for as I can see it, of course. 
   BTW, below I'm attaching the message from David Butenhof on 
   this topic that I've received a year or so ago [at THAT time 
   (and when I've submitted the aardvark-comment requesting the 
   removal), I've unfortunately missed those "optimizations" 
   rationale bits. I will probably resubmit the aardvark again 
   in the next round... unless someone can really show some 
   "value" of this rule/restriction.

B) Check out Java's memory model paper. I guess, a *lot* can 
   be "stolen" from it.

< copy&paste >

Subject: Re: Global variable access from multiple threads. 
Date: 2002-10-09 07:15:51 PST 

Momchil Velikov wrote:
> 
> "Stefan Brozinski" <Stefan.Brozinski_at_[hidden]> wrote in message news:<ansk4s$gsjkg$1_at_[hidden]>...
> > "Alexander Terekhov" <terekhov_at_[hidden]>:
> >
> > > Rather:
> > http://www.opengroup.org/onlinepubs/007904975/basedefs/xbd_chap04.html#tag_0
> > 4_10
> >
> > I understand your very short comment as "the original poster should use
> > proper synchronization methods to ensure everything else is locked out while
> > a thread modifies a global memory ressource", and I agree totally.
> 
> I understand it slightly differently - the writer of the variable
> should ensure mutual exclusion during write 

with respect to other writers and/or readers. (and undefined 
"memory locations" aside ;-) )

> and take care of memory
> synchronization - i.e. pthread_unlock _must_ perform a write barrier
> before other CPU see the mutex as unlocked.

AFAIK, in general, pthread_mutex_lock() must perform 
"acquire" barrier and pthread_mutex_unlock() must perform 
"release"  barrier. And implementations aren't allowed to 
perform software "code motions"/reordering/"optimization" 
that would break acquire/release semantics as well(*). 
More on this: < Forward Inline >

<-------- Original Message -------->
Message-ID: <3DA2B34D.8B43D582_at_[hidden]>
Date: Tue, 08 Oct 2002 12:28:29 +0200
From: Alexander Terekhov <terekhov_at_[hidden]>
Subject: Re: volatile -- what does it mean in relation to member functions?

Johan Johansson wrote:
[...]
> >  Conforming applications may only use the functions listed to
> >  synchronize threads of control with respect to memory access.
> >  There are many other candidates for functions that might also be
> >  used. Examples are: signal sending and reception, or pipe writing
> >  and reading. In general, any function that allows one thread of
> >  control to wait for an action caused by another thread of control
> >  is a candidate. IEEE Std 1003.1-2001 does not require these
> >  additional functions to synchronize memory access since this
> >  would imply the following:
> >
> >      All these functions would have to be recognized by advanced
> >      compilation systems so that memory operations and calls to
> >      these functions are not reordered by optimization.
> 
> Should this be interpreted as saying that "advanced compilation 
> systems" *are* required to not reorder across calls to the functions 
> that are required to synchronize threads of control? 

Yep.

> I suppose that this in turn could mean that you can't optimize them 
> away. 

Nope (see "9 Optimizations" in the paper below, for example).

> I have spent a limited time looking at the link that Jamez Kanze 
> provided but I have not been able to locate anything that exactly 
> addresses the issue. I can't exclude at this time that it's there 
> though.

I don't think that memory model requirements/semantics are clearly 
spelled out in the POSIX standard(*). That would require something 
along the lines (Java's revised >>volatiles<< aside ;-) ) of:

http://www.cs.umd.edu/~pugh/java/memoryModel/semantics.pdf

Note that POSIX "memory model" is, unfortunately, kinda totally 
broken (``underspecified'' if you like) with respect to C/C++ 
language(s) and adjacent/compound objects (i.e. memory granules): 
< check out this entire thread >

 Subject: "memory location" 
 Newsgroups: comp.std.c
 Date: 2002-07-18 09:08:00 PST

regards,
alexander.

(*) You might also want to try this:

http://www.opengroup.org/publications/mem-online/c950/c950.pdf
http://www.opengroup.org/publications/mem-online/c951/c951.pdf
http://www.opengroup.org/publications/mem-online/c952/c952.pdf
http://www.opengroup.org/publications/mem-online/c953/c953.pdf
http://www.opengroup.org/publications/mem-online/c610/c610.pdf

Registration and free membership to get access:

http://www.opengroup.org/austin

</-------- Original Message -------->

(*) Now, IMO it's really kinda funny that an aardvark requesting
    a removal of "memory synchronization requirements" that are
    currently {rather stupidly} attached to pthread_cond_signal() 
    and pthread_cond_broadcast() WAS REJECTED... despite the 
    "rationale" about signaling functions above. I don't get it, 
    really. http://www.opengroup.org/austin/docs/austin_107r2.txt
    (see "Enhancement Request Number 10", COMMENT)... "The group 
    felt that this was not sufficient grounds for a change in the 
    standard. Leaving these functions on the list makes the 
    requirements explicit." This is really silly, IMHO.

Dave Butenhof <David.Butenhof_at_[hidden]>@sears.zko.dec.com 
on 08/21/2001 04:05:02 PM

Please respond to Dave Butenhof <David.Butenhof_at_[hidden]> 
Subject:	Re: "Programming with POSIX threads"/pg 89/rule N4

Alexander Terekhov wrote:

> you wrote (pg 89; 9th printing, Nov.2000):
>
> "4. Whatever memory values a thread can see when it signals
>     or broadcasts a condition variable can also be seen by
>     any thread that is awakened by that signal or broadcast.
>     And, one more time, data written after the signal or
>     broadcast may not necessarily be seen by the thread that
>     wakes up, even if it occurs before it awakens."
>
> i am really puzzled by this rule N4.. use of condition
> variables without predicate is illegal, AFAIK - due to
> "spurious" wakeups. use of predicate without mutex
> protection is illegal too (rule N1 and N2 on the same
> page) so, why is N4 needed at all?

Actually, it's not "illegal". There's nothing "wrong" with failing to
use a predicate, except that your results will be meaningless. (Just as
you can write many things in C or C++, or even in English, that are
"correct" but meaningless.)

You are, however, quite correct that because it's MEANINGLESS (and
pointless) to try to use a condition variable without a predicate, and
because the predicate must be protected by a mutex, which must also be
associated with the condition variable wait operation, the memory
visibility guarantees on the mutex operations are sufficient for correct
operation under normal circumstances. The waker must hold the mutex when
it sets the predicate, and the waiter will hold the mutex when it resume
execution.

We debated this quite a bit in the POSIX working group, but some people
insisted that the condition signal->wait visibility was important. I
can't imagine any implementation of condition signal and wait that
wouldn't meet the requirements, so why waste time arguing about a
needless requirement that we can't avoid meeting? (We had quite a few
more important disagreements to resolve.) There's no useful or correct
way to EXPLOIT the additional guarantee, though, and, in retrospect, I
wish I'd thought to argue that point more thoroughly. (Though I suspect
the ones I needed to convince wouldn't have "gotten" it.)

For example, one might hypothesize "private" data between the signaller
and the waiter, which could be set after unlocking the mutex (which
protected the predicate) but before signalling the waiter. That data
would be visible to the waiter when it resumed. True... as long as it
actually waited. However, if it finds the predicate already satisfied,
and didn't wait, it wouldn't be guaranteed to see that "private" data.

> in other words, if condition variables provide block/
> unblock mechanism to communicate the predicate state
> change to waiting threads with predicate been synchronized
> via mutex what should c.signal/broadcast synchronize in
> addition to predicate already synchronized via mutex?
>
> without some example i really do not get it!

No, no; you DO get it. It's just that you're in a small minority.
Congratulations.

When I wrote the book, I did make some occasional commentary on the
decisions of the working group. Honestly, I don't even remember whether
in this particular case I chose not to, or just didn't think about it at
the time. In any case, it is an accurate report on the meaning of the
standard. If I manage to find time to write a second edition (something
I'd very much like to do, if I could find an equation for "spare time"
that wasn't unsolvable), I'll try to remember to add some commentary.
Thanks for paying attention!

/------------------[ David.Butenhof_at_[hidden] ]------------------\
| Compaq Computer Corporation              POSIX Thread Architect |
|     My book: http://www.awl.com/cseng/titles/0-201-63392-2/     |
\-----[ http://home.earthlink.net/~anneart/family/dave.html ]-----/