Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming.threads > #845 > unrolled thread

Mutex required for a simple shared-variable case?

Back to article view | Back to comp.programming.threads

Contents

  Mutex required for a simple shared-variable case? Lasse Kliemann <lasse-usenet-2011@mail.plastictree.net> - 2012-04-03 15:31 +0200
    Re: Mutex required for a simple shared-variable case? Marcel Müller <news.5.maazl@spamgourmet.com> - 2012-04-04 01:45 +0200
    Re: Mutex required for a simple shared-variable case? Joshua Maurice <joshuamaurice@gmail.com> - 2012-04-05 17:08 -0700

#845 — Mutex required for a simple shared-variable case?

A number of threads execute a loop each. Once one of them finds a 
certain condition, it shall signal all the other threads to stop.

My first idea was to implement this with a shared variable. It is 
passed to each of the threads as a pointer to an integer, say 
'go_on'. It is set to 1 in the beginning, before the threads 
start. If any of the threads finds the stopping condition given, 
it sets this variable to 0 and terminates. Each of the loops 
looks like this:

for(...; ... && (*go_on); ...) { ...

So it will not do another iteration if the place pointed to by 
'go_on' shows 0.

Inside the loop, the stopping condition is checked for:

   if ...; *go_on = 0;

Are there any mutexes required to read or write to the place 
pointed to by 'go_on'?

All resources on thread programming emphasize how important 
mutexes are for shared data. But I do not quite see why it should 
be necessary in such a simple case. And for performance reasons, 
I would rather keep it as simple as possible.

Can someone give me a quick explanation? I would be satisfied 
with a Pthreads-specific answer, since that's what I am using.

Thank you!

[toc] | [next] | [standalone]

#846

On 03.04.2012 15:31, Lasse Kliemann wrote:
> A number of threads execute a loop each. Once one of them finds a
> certain condition, it shall signal all the other threads to stop.
>
> My first idea was to implement this with a shared variable. It is
> passed to each of the threads as a pointer to an integer, say
> 'go_on'. It is set to 1 in the beginning, before the threads
> start. If any of the threads finds the stopping condition given,
> it sets this variable to 0 and terminates. Each of the loops
> looks like this:
>
> for(...; ...&&  (*go_on); ...) { ...

Well, this is a common use case. A mutex is possible but it might not 
suit your needs very well. As long as you do not care how long the other 
threads respond delayed to a stop signal, it is not that difficult. It 
will work on almost all platforms without any further actions. But 
strictly speaking the code is broken without any synchronization. The 
other threads might never see the change.

First of all the variable might be placed in a register by the 
optimizer. To avoid this you need to declare your flag as volatile.
In practice the volatile is rarely needed because functions you call 
from inside the loop are allowed to change the global flag as well. So 
the compiler is in general not allowed to cache the value the whole 
time. But the optimizer might know the code of all called functions and 
analyze it. And then it could do a invariant code motion optimization 
and move the check in front of the loop.

But volatile is still not sufficient, because CPU caches might intercept 
your intention in a similar way. Usually they do not hold values for 
very long, but who knows? To work around this you need a memory barrier. 
More specifically you need acquire semantics when setting the 
termination indicator.


> Are there any mutexes required to read or write to the place
> pointed to by 'go_on'?

No, there is no mutex /required/, since there are other ways to get 
defined behavior.

> Can someone give me a quick explanation? I would be satisfied
> with a Pthreads-specific answer, since that's what I am using.

I am not very familiar with pthreads, but AFAIK the pthreads API does 
not provide explicit access to memory barriers. But any call to a 
pthreads synchronization function includes a full memory barrier. So you 
are fine if you deal with mutexes in you loop anyway.

If you are using gcc you might have a look at its built in atomic 
primitives. If you compile C++ std::atomic<> will also do the job.


Marcel

[toc] | [prev] | [next] | [standalone]

#847

On Apr 3, 6:31 am, Lasse Kliemann <lasse-
usenet-2...@mail.plastictree.net> wrote:
> A number of threads execute a loop each. Once one of them finds a
> certain condition, it shall signal all the other threads to stop.
>
> My first idea was to implement this with a shared variable. It is
> passed to each of the threads as a pointer to an integer, say
> 'go_on'. It is set to 1 in the beginning, before the threads
> start. If any of the threads finds the stopping condition given,
> it sets this variable to 0 and terminates. Each of the loops
> looks like this:
>
> for(...; ... && (*go_on); ...) { ...
>
> So it will not do another iteration if the place pointed to by
> 'go_on' shows 0.
>
> Inside the loop, the stopping condition is checked for:
>
>    if ...; *go_on = 0;
>
> Are there any mutexes required to read or write to the place
> pointed to by 'go_on'?
>
> All resources on thread programming emphasize how important
> mutexes are for shared data. But I do not quite see why it should
> be necessary in such a simple case. And for performance reasons,
> I would rather keep it as simple as possible.
>
> Can someone give me a quick explanation? I would be satisfied
> with a Pthreads-specific answer, since that's what I am using.

Well, the formal answer according to C++11, C1x, pthreads, and as best
as anyone can determine win32 threads, is that this would be a data
race, and thus formally undefined behavior. In practice? Meh. My
company's code does the exact same thing - not that I'm saying it's
safe, but it may well be.

As noted else-thread, the simplest option would be C++11 std::atomic
et. al. with memory order "relaxed". There is a C++11 guarantee that
all atomic operations will become visible to other threads in a
"reasonable" amount of time (or some such wording). (A similar rule
probably exists in C1x.) In effect, the intent is to have "relaxed"
operations be performed without memory barriers of any kind, just
simple stores and loads.

So, if you're using pthreads, your options AFAIK are:
1- undefined behavior that's probably (?) harmless and may work as
expected, but it's still UB and that makes me squirm, or
2- use a mutex. If it's not in a really tight loop, it probably won't
be a measurable performance hit. Of course, test and measure.
I'd suggest using a mutex.

The problem is if it decides to keep the stop flag in a register, or
if it never gets flushed from a core local cache, etc.

I suppose that implementations of C++11 and C1x have to pay a little
attention to ensure that this does not happen in the std::atomic case.
Then again, with the rule that "for(;;);" is undefined behavior... (a
story for another time). Nevermind, no. Even accounting for the "no
side-effect-free infinite loop" rule, an implementation would probably
have to go out of its way a little bit to guarantee "all atomic writes
become visible to all threads in a 'reasonable' amount of time". I'm
not sure how an implementation would do that reasonably though... I
leave with more questions than when I entered.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming.threads

csiph-web