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

Groups > comp.std.c++ > #641

Re: semantics of multithreading?

Show all headers | View raw

On Thursday, June 13, 2013 11:42:34 AM UTC-4, Martin Bonner wrote:
> On Monday, June 10, 2013 8:23:21 PM UTC+1, sieg...@googlemail.com wrote:
> > I am suspicious of the latter case because it could allow the
> > compiler to introduce a deadlock or livelock in some programs.
>
> I don't see how.  The compiler can optimize in a way that eliminates
> certain possible orderings, but if there is a deadlock in the ordering
> it chooses then that can happen anyway.

Example:

   void f1() { while x.load() {}; }
   void f2() { x.store(0); }
   x.store(1);
   p1 = fork(f1);
   p2 = fork(f2);
   p1.start(); p2.start();
   p1.join(); p2.join();

I would argue that the above program can terminate -- it is not livelocked.
This comes down to a minimum requirement of a fair scheduler -- it will not refuse to run an unblocked thread. (This is not exactly true -- thread priorities and other fancy features can make even that simple assumption difficult to obtain). I don't know if the standard says anything about this, but I would think it a bug if the standard makes it _impossible_ to assume such a fair scheduler.

If the compiler can refine the thread interleavings, however, then it can effectively transform the above program to:

   x.store(1);
   while x.load() {};
   x.store(0);


which will never terminate -- it is now livelocked. If this is allowed, then it is impossible to assume a minimally fair scheduler. The only reasonable way to allow the compiler to refine thread interleavings is to add the caveat that it cannot change the termination behavior in doing so.

I am wondering if the standard says anything about this.


> > Also, I associate "unspecified behavior" with choices that the compiler
> > may make, but if the choice has an stateful effect, then the program is
> > undefined.
>
> I don't understand that.

Yeah, my understanding of unspecified behavior was incorrect.



> > If choosing a particular thread interleaving does not result
> > in a different output (or "observable behavior"), may the
> > compiler do so? Does the standard allow new threads to be
> > introduced, e.g. to automatically parallelize a program?
>
> If you can't tell the difference, then the as-if rule says "yes".


My questions come down to what the language specification says about what one is able to "see". Only then can we decide if we can tell the difference.


Thanks for your time!
-cj


-- 
[ comp.std.c++ is moderated.  To submit articles, try posting with your ]
[ newsreader.  If that fails, use mailto:std-cpp-submit@vandevoorde.com ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

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

Thread

semantics of multithreading? siegebell@googlemail.com - 2013-06-10 12:23 -0700
  Re: semantics of multithreading? Jason McKesson <jmckesson@googlemail.com> - 2013-06-11 12:19 -0700
  Re: semantics of multithreading? Martin Bonner <martinfrompi@yahoo.co.uk> - 2013-06-13 08:42 -0700
    Re: semantics of multithreading? siegebell@googlemail.com - 2013-06-15 08:42 -0600
      Re: semantics of multithreading? Jason McKesson <jmckesson@googlemail.com> - 2013-06-16 19:58 -0600
        Re: semantics of multithreading? usenet@mkarcher.dialup.fu-berlin.de (Michael Karcher) - 2013-06-18 11:36 -0700
          Re: semantics of multithreading? siegebell@googlemail.com - 2013-06-23 19:19 -0600
        Re: semantics of multithreading? siegebell@googlemail.com - 2013-06-23 19:18 -0600

csiph-web