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

Groups > comp.lang.c++ > #5167

Re: Please disprove this Double-Checked Locking "fix"

Show all headers | View raw

Joshua Maurice wrote:

> On May 18, 2:12 pm, Gerhard Fiedler <geli...@gmail.com> wrote:
>> Joshua Maurice wrote:
>>> With that, it sees:
>>>   someMutex.lock();
>>>   <blah1>
>>>   someMutex.unlock();
>>>   <blah2>
>>>   someMutex.lock();
>>>   <blah3>
>>>   someMutex.unlock();
>>
>>> The compiler sees a lock, unlock, lock, unlock, in straightline code,
>>> without branching (or exceptions, or volatile (to keep signal handlers
>>> correct)). The compiler is totally free to replace that with:
>>>   someMutex.lock();
>>>   <blah1>
>>>   <blah2>
>>>   <blah3>
>>>   someMutex.unlock();
>> 
>> This is exactly what I don't understand -- I guess I have to look
>> deeper into the different mutex/lock implementations and their
>> guarantees. I was under the impression that through the lock/unlock
>> pairs, it is guaranteed that <blah1> happens before <blah2>, and
>> that <blah3> happens after it.
> 
> Unless I'm totally off, this is a quite straightforward
> transformation. It may be bad from a QoI perspective depending on the
> particulars of the code, and it may be a bad optimization depending
> on the particulars, but it is definitely allowed by the C++0x memory
> model (and Java 1.5+ memory model) AFAIK.

FWIW, I was thinking of C++03 with pthread (GCC) or Windows (VC++)
threading models.

> You said that "I was under the impression that [...] it is guaranteed
> that <blah1> happens before <blah2>, [...]". Why is that? More
> particularly, what does that mean?
> 
> Let me try to explain. Taking a step back, consider:
>   int a = 1;
>   int b = 2;
>   global_c = a + b;
>   global_d = a - b;
> 
> We have no guarantees that the assignment to global_c happens before
> global_d. Why? This is equivalent to the phrasing that no conforming
> program could tell the difference if in fact the compiler "switched"
> the two. It's the basic "as-if" rule.

Understood and agreed -- without locks. I was under the impression that
locks change this, by adding "observable" points to the program.

> Going back to:
>   someMutex.lock();
>   <blah1>
>   someMutex.unlock();
>   <blah2>
>   someMutex.lock();
>   <blah3>
>   someMutex.unlock();
> 
> Using the "as-if" rule, the compiler is totally free to transform that
> to the following, under some rather specific rules.
>   someMutex.lock();
>   <blah1>
>   <blah2>
>   <blah3>
>   someMutex.unlock();
> 
> It can only do so under some very specific situations. The compiler
> has to be able to guarantee that no control flow path goes out of that
> block except the normal flow past the end. (Also volatile and signal
> handlers might be annoying, so let's ignore that for now.) Now, think
> of a program that could possibly tell the difference between those two
> code fragments? AFAIK, you could not. 

How about the typical situation: short-running, locked synchronizing
code with long-running, unlocked working code? blah1 (retrieving tasks
out of a shared queue) and blah3 (placing results into a shared queue)
each a few milliseconds, blah2 (calculating the results) a few hours or
days, and a few threads doing this in parallel. I'm sure I can tell the
difference between the two versions. 

> Because of the vagueries of scheduling, no conforming program would
> have its behavior changed in a way that would produce results not
> allowed by the memory model, and thus the compiler is entirely free
> to do that under the "as-if" rule.

I understand that this may be a QoI issue, but then again, if I can't
guarantee that the two days that blah2 runs are in fact unlocked, I
really can't use this system for this task. QoI of the compiler here
becomes QoI of the application, and if the compiler is free to do this,
it doesn't allow me to guarantee my application spec -- which I assume
to be a typical threaded application.

> To put that another way, the difference between the two programs is
> that another thread might acquire the mutex when the first thread is
> in <blah2>, and thus see <blah1> without being guaranteed to see
> <blah2> nor <blah3>. That is, it is allowed for the compiler and
> scheduler to do so. It is not required. 

In my example, which is nothing strange, it is required, and to
implement it, I need to use a compiler with a threading/memory model
that guarantees me that blah2 runs unlocked, so that it can run in
parallel. This of course if the scheduler allows it to do so -- but
since the compiler doesn't control the scheduler, it can't really assume
much about it and IMO needs to unlock after blah1, even though it
doesn't know what the scheduler does with this. Whether it makes sense
to unlock and relock around blah2 /I/ need to decide when writing the
program, considering the particularities of the scheduler I'm intending
to run it on.

> IIRC, there's some fluff in the C++0x standard that things must become
> visible to other threads "eventually", or even "in a reasonable
> amount of time", and probably (?) something similar along the lines
> that a thread waiting on a mutex will "eventually" acquire it, or
> even "in a reasonable amount of time". If you combine those two
> sections like that, you might have just broken the "eventually" or
> "in a reasonable amount of time" guarantees.

This doesn't sound good :)  This relates to my earlier comment that I
think I need to look into the guarantees that the individual
implementations provide -- if this here reflects the C++03 guarantees,
IMO they alone are not very useful in practice. To go back to the
example, I need to have the guarantee that blah2 runs unlocked (within
the overall scheduling granularity of the target system, of course).

Thanks,
Gerhard

Back to comp.lang.c++ | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Please disprove this Double-Checked Locking "fix" jl_post@hotmail.com - 2011-04-26 09:58 -0700
  Re: Please disprove this Double-Checked Locking "fix" Leigh Johnston <leigh@i42.co.uk> - 2011-04-26 18:17 +0100
  Re: Please disprove this Double-Checked Locking "fix" Pete Becker <pete@versatilecoding.com> - 2011-04-26 13:50 -0400
    Re: Please disprove this Double-Checked Locking "fix" Scott Meyers <NeverRead@aristeia.com> - 2011-05-01 17:14 -0700
      Re: Please disprove this Double-Checked Locking "fix" Joshua Maurice <joshuamaurice@gmail.com> - 2011-05-02 15:59 -0700
        Re: Please disprove this Double-Checked Locking "fix" Pete Becker <pete@versatilecoding.com> - 2011-05-03 08:39 -0400
  Re: Please disprove this Double-Checked Locking "fix" Joshua Maurice <joshuamaurice@gmail.com> - 2011-04-26 11:16 -0700
    Re: Please disprove this Double-Checked Locking "fix" Joshua Maurice <joshuamaurice@gmail.com> - 2011-04-26 11:19 -0700
    Re: Please disprove this Double-Checked Locking "fix" Pete Becker <pete@versatilecoding.com> - 2011-04-26 14:30 -0400
      Re: Please disprove this Double-Checked Locking "fix" Joshua Maurice <joshuamaurice@gmail.com> - 2011-04-26 11:50 -0700
    Re: Please disprove this Double-Checked Locking "fix" Joshua Maurice <joshuamaurice@gmail.com> - 2011-05-11 19:55 -0700
      Re: Please disprove this Double-Checked Locking "fix" Gerhard Fiedler <gelists@gmail.com> - 2011-05-13 19:56 -0300
        Re: Please disprove this Double-Checked Locking "fix" Joshua Maurice <joshuamaurice@gmail.com> - 2011-05-13 16:59 -0700
          Re: Please disprove this Double-Checked Locking "fix" Gerhard Fiedler <gelists@gmail.com> - 2011-05-18 18:12 -0300
            Re: Please disprove this Double-Checked Locking "fix" Joshua Maurice <joshuamaurice@gmail.com> - 2011-05-18 14:53 -0700
              Re: Please disprove this Double-Checked Locking "fix" Gerhard Fiedler <gelists@gmail.com> - 2011-05-19 13:46 -0300
                Re: Please disprove this Double-Checked Locking "fix" Joshua Maurice <joshuamaurice@gmail.com> - 2011-05-19 15:30 -0700
                Re: Please disprove this Double-Checked Locking "fix" Gerhard Fiedler <gelists@gmail.com> - 2011-05-21 11:55 -0300
                Re: Please disprove this Double-Checked Locking "fix" Joshua Maurice <joshuamaurice@gmail.com> - 2011-05-22 01:08 -0700
  Re: Please disprove this Double-Checked Locking "fix" James Kanze <james.kanze@gmail.com> - 2011-04-30 15:54 -0700
    Re: Please disprove this Double-Checked Locking "fix" Leigh Johnston <leigh@i42.co.uk> - 2011-05-01 21:49 +0100
      Re: Please disprove this Double-Checked Locking "fix" Pavel <pauldontspamtolk@removeyourself.dontspam.yahoo> - 2011-05-01 17:26 -0400
        Re: Please disprove this Double-Checked Locking "fix" Leigh Johnston <leigh@i42.co.uk> - 2011-05-01 22:44 +0100
          Re: Please disprove this Double-Checked Locking "fix" Leigh Johnston <leigh@i42.co.uk> - 2011-05-02 01:01 +0100
            Re: Please disprove this Double-Checked Locking "fix" Pavel <pauldontspamtolk@removeyourself.dontspam.yahoo> - 2011-05-01 22:04 -0400
            Re: Please disprove this Double-Checked Locking "fix" "Chris M. Thomasson" <cristom@charter.net> - 2011-05-04 11:49 -0700
              Re: Please disprove this Double-Checked Locking "fix" Pavel <pauldontspamtolk@removeyourself.dontspam.yahoo> - 2011-05-06 00:16 -0400
          Re: Please disprove this Double-Checked Locking "fix" Joshua Maurice <joshuamaurice@gmail.com> - 2011-05-02 15:43 -0700
        Re: Please disprove this Double-Checked Locking "fix" James Kanze <james.kanze@gmail.com> - 2011-05-01 14:53 -0700
          Re: Please disprove this Double-Checked Locking "fix" Pavel <pauldontspamtolk@removeyourself.dontspam.yahoo> - 2011-05-01 19:23 -0400
            Re: Please disprove this Double-Checked Locking "fix" James Kanze <james.kanze@gmail.com> - 2011-05-02 09:02 -0700
              Re: Please disprove this Double-Checked Locking "fix" Pavel <pauldontspamtolk@removeyourself.dontspam.yahoo> - 2011-05-05 23:46 -0400
      Re: Please disprove this Double-Checked Locking "fix" James Kanze <james.kanze@gmail.com> - 2011-05-01 14:47 -0700

csiph-web