www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Condition variables?

reply David Brown <dlang davidb.org> writes:
Hopefully I'm missing something obvious here, but D and phobos seem to
be missing any kind of condition variables.  It's really hard to do
non-trivial thread programming without this kind of synchronization.

In fact, I'm not sure how I could even go about implementing
something, since there doesn't seem to be any way of easily accessing
the object's monitor, which would be needed to do condition variables
that work with 'synchronized'.

I can think of other ways of doing synchronization, but not in a
terribly efficient way:

  - Use Thread's pause() and resume().  I would have to implement wait
    queues and getting synchronization right on this would be
    challenging.

  - Use another OS mechanism such as pipes to sleep and wakeup.  This
    is also not very efficient.

I'm just kind of wondering why std.thread even exists without
condition variables, since it really isn't useful for all that much,
by itself, and doesn't seem to even have the needed hooks to implement
any other mechanism.

David Brown
Sep 29 2007
next sibling parent "Janice Caron" <caron800 googlemail.com> writes:
On 9/30/07, David Brown <dlang davidb.org> wrote:

 Hopefully I'm missing something obvious here, but D and phobos seem to
 be missing any kind of condition variables.


I'm not sure what this has to do with D. It's a platform thing, not a
language thing. Linux has condition variables; Windows doesn't.
Windows has Events, Linux doesn't. What you're talking about is the
pthreads (posix threads) library. That's written in C, so you should
be able to call all the functions in it no problem - but don't expect
your program to run on Windows.

Exactly the same problem exists in C or C++, which is why I said it's
not a language thing.
Sep 29 2007
prev sibling next sibling parent reply downs <default_357-line yahoo.de> writes:
David Brown wrote:

 Hopefully I'm missing something obvious here, but D and phobos seem to
 be missing any kind of condition variables.  It's really hard to do
 non-trivial thread programming without this kind of synchronization.


:snip:

 David Brown


What does one need condition variables for?
I'm honestly curious. I've written a few multithreaded programs in D
and, so far, haven't needed them :)

 --downs
Sep 29 2007
parent reply "Janice Caron" <caron800 googlemail.com> writes:
On 9/30/07, downs <default_357-line yahoo.de> wrote:

 What does one need condition variables for?
 I'm honestly curious. I've written a few multithreaded programs in D
 and, so far, haven't needed them :)


I would guess you're a Windows programmer?

You don't need them in Windows. Windows has plenty of other mechanisms
for doing synchronisation. Condition variables is "the linux way".

Still, I've never really got the hang of them either, so I'd love for
David to explain further.

In any case, I don't think they could be put into Phobos except as a
wrapper around pthreads ... which doesn't exist on Windows. Oh what
joy.
Sep 29 2007
next sibling parent downs <default_357-line yahoo.de> writes:
Janice Caron wrote:

 On 9/30/07, downs <default_357-line yahoo.de> wrote:

 What does one need condition variables for?
 I'm honestly curious. I've written a few multithreaded programs in D
 and, so far, haven't needed them :)


 
 I would guess you're a Windows programmer?
 


Started out on linux, but all my D code runs cross-platform.


 You don't need them in Windows. Windows has plenty of other mechanisms
 for doing synchronisation. Condition variables is "the linux way".
 


Yes, but I still don't see what thread synch you need them for that
can't be done in a few lines of synchronized() code.


 Still, I've never really got the hang of them either, so I'd love for
 David to explain further.
 
 In any case, I don't think they could be put into Phobos except as a
 wrapper around pthreads ... which doesn't exist on Windows. Oh what
 joy.


Joy! ;)

 --downs
Sep 29 2007
prev sibling parent reply Roald Ribe <rr.nospam nospam.teikom.no> writes:
Janice Caron wrote:

 On 9/30/07, downs <default_357-line yahoo.de> wrote:

 What does one need condition variables for?
 I'm honestly curious. I've written a few multithreaded programs in D
 and, so far, haven't needed them :)


 
 I would guess you're a Windows programmer?
 
 You don't need them in Windows. Windows has plenty of other mechanisms
 for doing synchronisation. Condition variables is "the linux way".
 
 Still, I've never really got the hang of them either, so I'd love for
 David to explain further.
 
 In any case, I don't think they could be put into Phobos except as a
 wrapper around pthreads ... which doesn't exist on Windows. Oh what
 joy.


No?

http://sourceware.org/pthreads-win32/

Roald
Sep 30 2007
next sibling parent "Janice Caron" <caron800 googlemail.com> writes:
On 9/30/07, Roald Ribe <rr.nospam nospam.teikom.no> wrote:

 http://sourceware.org/pthreads-win32/


Oooh! I like! (And it's got condition variables in it)

Well, since it turns out there really /are/ pthreads on all platforms,
how hard can it be to make a D wrapper around pthreads? I'd like to
see that as part of Phobos, but I certainly wouldn't complain if it
showed up as a third-party D module.

Thanks for telling us about that, Roald.
Sep 30 2007
prev sibling parent "Kris" <foo bar.com> writes:
Condition-variables are also part of Tango. Cross platform and all :)

- Kris


"Roald Ribe" <rr.nospam nospam.teikom.no> wrote in message 
news:fdnqiv$pmb$1 digitalmars.com...

 Janice Caron wrote:

 On 9/30/07, downs <default_357-line yahoo.de> wrote:

 What does one need condition variables for?
 I'm honestly curious. I've written a few multithreaded programs in D
 and, so far, haven't needed them :)


 I would guess you're a Windows programmer?

 You don't need them in Windows. Windows has plenty of other mechanisms
 for doing synchronisation. Condition variables is "the linux way".

 Still, I've never really got the hang of them either, so I'd love for
 David to explain further.

 In any case, I don't think they could be put into Phobos except as a
 wrapper around pthreads ... which doesn't exist on Windows. Oh what
 joy.


 No?

 http://sourceware.org/pthreads-win32/

 Roald
Sep 30 2007
prev sibling next sibling parent "Kris" <foo bar.com> writes:
That probably ought to be part of the library ... in Tango it lives in 
tango.core.sync.Condition.

Using pause() and resume() is prone to deadlock, so it's surprising that 
they exist in Phobos

- Kris


"David Brown" <dlang davidb.org> wrote in message 
news:20070930045805.GA2735 a64.davidb.org...

 Hopefully I'm missing something obvious here, but D and phobos seem to
 be missing any kind of condition variables.  It's really hard to do
 non-trivial thread programming without this kind of synchronization.

 In fact, I'm not sure how I could even go about implementing
 something, since there doesn't seem to be any way of easily accessing
 the object's monitor, which would be needed to do condition variables
 that work with 'synchronized'.

 I can think of other ways of doing synchronization, but not in a
 terribly efficient way:

  - Use Thread's pause() and resume().  I would have to implement wait
    queues and getting synchronization right on this would be
    challenging.

  - Use another OS mechanism such as pipes to sleep and wakeup.  This
    is also not very efficient.

 I'm just kind of wondering why std.thread even exists without
 condition variables, since it really isn't useful for all that much,
 by itself, and doesn't seem to even have the needed hooks to implement
 any other mechanism.

 David Brown
Sep 29 2007
prev sibling next sibling parent reply "Janice Caron" <caron800 googlemail.com> writes:
On 9/30/07, David Brown <dlang davidb.org> wrote:

 It's really hard to do
 non-trivial thread programming without this kind of synchronization.


When I first tried to do thread programming on Linux I was baffled by
the absence of Events or anything similar. But surely, I said, it's
really hard to do non-trivial thread programming without this kind of
synchronization. Aha!, I was told, Linux has these things called
condition variables instead. (I still haven't quite got the hang of
them as I'm basically a Windows person).



 I'm just kind of wondering why std.thread even exists without
 condition variables, since it really isn't useful for all that much,
 by itself, and doesn't seem to even have the needed hooks to implement
 any other mechanism.


Yes, I certainly agree that std.thread is limited - it doesn't have
condition variables /or/ Events, and surely you need one or the other?

For that matter it doesn't even have mutexes (unless you count the
ones built into every Object, and they're not necessarily the right
tool for every job).
Sep 29 2007
parent David Brown <dlang davidb.org> writes:
On Sun, Sep 30, 2007 at 06:55:33AM +0100, Janice Caron wrote:


 Yes, I certainly agree that std.thread is limited - it doesn't have
 condition variables /or/ Events, and surely you need one or the other?


I think I now understand why this has been left out of the thread package.
The problem is that under Linux, there isn't any way to properly use
conditions.  I can either make my own mutexes, and ignore the
'synchronized' construct, or hack into the object representation to use it
myself.


 For that matter it doesn't even have mutexes (unless you count the
 ones built into every Object, and they're not necessarily the right
 tool for every job).


Interestingly, Microsoft has chosen condition variables for synchronization

less prone to problems than events.  My experience is that people can
easily mess up with either.

It would be nice to have something like condition variables implemented in
Phobos that would work portably across multiple platforms.  I think most
platforms other than windows will already have something similar to
condition variables, since it is what Posix defines.

I guess this is only a problem because I'm liking what 'synchronized'
provides, in that it releases the mutex no matter what.  Without it, I'm
left having to do something like (off of the top of my head).

   {
      mutex.lock ();
      scope (exit) mutex.unlock ();

      ...operation...
   }

which looks a bit odd, although less odd than most other languages.

Dave
Sep 29 2007
prev sibling next sibling parent reply "David Wilson" <dw botanicus.net> writes:
On 30/09/2007, Janice Caron <caron800 googlemail.com> wrote:

 On 9/30/07, David Brown <dlang davidb.org> wrote:

 Hopefully I'm missing something obvious here, but D and phobos seem to
 be missing any kind of condition variables.


 I'm not sure what this has to do with D. It's a platform thing, not a
 language thing. Linux has condition variables; Windows doesn't.
 Windows has Events, Linux doesn't. What you're talking about is the
 pthreads (posix threads) library. That's written in C, so you should
 be able to call all the functions in it no problem - but don't expect
 your program to run on Windows.

 Exactly the same problem exists in C or C++, which is why I said it's
 not a language thing.


Hi Janice,

Condition variables are a much more theoretical concept than simply
"implemented in POSIX", and FWIW were finally added to Vista:

   http://msdn.microsoft.com/msdnmag/issues/07/06/Concurrency/default.aspx

Quoth:

   The condition variable has existed in other threading libraries for some
   time and has been sorely missed from the Windows SDK.

There's a hundred and one different things in the text books
implemented in terms of them, Windows just took the approach of
providing abstractions instead.


David.






 Sep 29 2007



  parent  Sean Kelly <sean f4.ca>  writes:


David Wilson wrote:

 
 There's a hundred and one different things in the text books
 implemented in terms of them, Windows just took the approach of
 providing abstractions instead.


Unfortunately, those abstractions (ie. Event) are broken.  I'll never 
understand why the Win32 folks ignored decades of research into thread 
primitives and used nonstandard names and behavior for the Win32 stuff.


Sean



 Sep 30 2007



prev sibling next sibling parent  Sean Kelly <sean f4.ca>  writes:


David Brown wrote:

 Hopefully I'm missing something obvious here, but D and phobos seem to
 be missing any kind of condition variables.  It's really hard to do
 non-trivial thread programming without this kind of synchronization.
 
 In fact, I'm not sure how I could even go about implementing
 something, since there doesn't seem to be any way of easily accessing
 the object's monitor, which would be needed to do condition variables
 that work with 'synchronized'.


Tango has them in tango.core.sync.Condition.  They need to work with 
Tango's mutexes (tango.core.sync.Mutex), and those mutexes work with 
'synchronized':

auto   m = new Mutex;
auto   c = new Condition;
data[] d;

// thread A
synchronized( m )
{
     while( d.length == 0 )
         c.wait();
     // use data
}

// thread B
synchronized( m )
{
     d ~= something;
     c.notify();
}


Sean



 Sep 30 2007



prev sibling  parent reply Graham St Jack <grahams acres.com.au>  writes:


I have tried to get conditions into the language before, without success 
(or even much interest from others). I find Conditions absolutely 
essential in multi-threaded applications, and can't understand why they 
are missing.

The Condition class in Tango isn't quite there yet - it needs to be 
something like the code below, which I am using in my own project (only 
works for Linux so far). Note the use of an Object's monitor's mutex, 
and the reasonably easy syntax for using it. IMO something along these 
lines belongs in both Phobos and Tango.

You use it like this (incomplete pseudo-code):

class ProtectedQueue(T) {
     Condition ready;
     int count;

     this() {
         ready = new Condition(this);
     }

     synchronized void add(T item) {
         add_item_to_queue;
         ++count;
         ready(count > 0);
     }

     synchronized T remove() {
         ready.wait;       // wait until count is > 0
         --count;
         ready(count > 0);
         return remove_item_from_queue;
     }
}





//---------------------------------------------------------------
// A condition
// Allows a thread to wait for the condition to be true.
//---------------------------------------------------------------

// stuff to get access to an Object's Monitor's mutex
// Note - the mutex is created on-demand, so we have to defer
// accessing it until the first time we use it.
// Modeled on monitor.c in Phobos and Tango (they are different)

private {
     version(Tango) {
         struct Monitor {
             void * impl;
             posix.pthread_mutex_t mutex;
         }
     }
     else {
         struct Monitor {
             size_t len;
             void * ptr;
             posix.pthread_mutex_t mutex;
         }
     }

     Monitor* getMonitor(Object obj) {
         return cast(Monitor*) (cast(void**) obj)[1];
     }

     posix.pthread_mutex_t * getMutex(Object obj) {
         return &getMonitor(obj).mutex;
     }
}


class Condition {
     alias value opCall;

     Object object;
     bool satisfied;
     posix.pthread_cond_t condition;
     posix.pthread_mutex_t * mutex;

     // construct a Condition which object's monitor's mutex
     this(Object object) {
         this.object = object;
         satisfied = false;
         posix.pthread_condattr_t attributes;
         posix.pthread_condattr_init(&attributes);
         int rc = posix.pthread_cond_init(&condition, &attributes);
         assert(!rc);
         posix.pthread_condattr_destroy(&attributes);
     }

     // destroy a condition
     ~this() {
         int rc = posix.pthread_cond_destroy(&condition);
         assert(!rc);
     }

     // wait until the condition is satisfied.
     // Must only be called from a synchronized method
     // in the object specified in the constructor of this Condition.
     void wait() {
         // FIXME - need an assertion that we have locked the mutex
         if (!mutex) {
             mutex = getMutex(object);
         }
         while (!satisfied) {
             int rc = posix.pthread_cond_wait(&condition, mutex);
             assert(!rc);
         }
     }

     // wait for timeout seconds, returning true if succeeded,
     // false if timed out.
     bool wait(double timeout) {
         // FIXME - need an assertion that we have locked the mutex
         if (!mutex) {
             mutex = getMutex(object);
         }
         posix.timespec t;
         long nsecs = cast(long) (timeout * 1000000000L);
         t.tv_sec   = cast(int)  (nsecs   / 1000000000L);
         t.tv_nsec  = cast(int)  (nsecs   % 1000000000L);
         while (!satisfied) {
             int rc = posix.pthread_cond_timedwait(
                     &condition, mutex, &t);
             if (rc != 0) {
                 return false;
             }
         }
         return true;
     }

     // set the condition to val, notifying a waiting thread if true.
     // Should only be called from a synchronized method in the object
     // provided in this condition's constructor.
     void value(bool val) {
         // FIXME - need an assertion that we have locked the mutex
         if (val != satisfied) {
             satisfied = val;
             if (satisfied) {
                 posix.pthread_cond_signal(&condition);
             }
         }
     }

     // getter for the value of the condition.
     bool value() {
         // FIXME - need an assertion that we have locked the mutex
         return satisfied;
     }
}



David Brown wrote:

 Hopefully I'm missing something obvious here, but D and phobos seem to
 be missing any kind of condition variables.  It's really hard to do
 non-trivial thread programming without this kind of synchronization.
 
 In fact, I'm not sure how I could even go about implementing
 something, since there doesn't seem to be any way of easily accessing
 the object's monitor, which would be needed to do condition variables
 that work with 'synchronized'.
 
 I can think of other ways of doing synchronization, but not in a
 terribly efficient way:
 
   - Use Thread's pause() and resume().  I would have to implement wait
     queues and getting synchronization right on this would be
     challenging.
 
   - Use another OS mechanism such as pipes to sleep and wakeup.  This
     is also not very efficient.
 
 I'm just kind of wondering why std.thread even exists without
 condition variables, since it really isn't useful for all that much,
 by itself, and doesn't seem to even have the needed hooks to implement
 any other mechanism.
 
 David Brown





 Oct 01 2007



 next sibling parent reply "Janice Caron" <caron800 googlemail.com>  writes:


On 10/2/07, Graham St Jack <grahams acres.com.au> wrote:

 You use it like this (incomplete pseudo-code):

 class ProtectedQueue(T) {
      Condition ready;
      int count;

      this() {
          ready = new Condition(this);
      }

      synchronized void add(T item) {
          add_item_to_queue;
          ++count;
          ready(count > 0);
      }

      synchronized T remove() {
          ready.wait;       // wait until count is > 0
          --count;
          ready(count > 0);
          return remove_item_from_queue;
      }
 }


I do believe that would deadlock. If thread A was waiting inside a
synchronized block, then thread B would never be able to enter the add
function, and hence would never be able to trigger the condition.

Incidently, the same psuedo-code written using Events instead of
Conditions (with the dealock still in place) would be:

class ProtectedQueue(T) {
    Event ready;
    int count;

    this() {
        ready = new Event;
    }

    synchronized void add(T item) {
        add_item_to_queue;
        ++count;
        ready.signal;
    }

    synchronized T remove() {
        ready.wait;       // wait until count is > 0 -- not a good
idea inside synchronized!
        --count;
        if (count > 0) ready.signal;
        return remove_item_from_queue;
    }
}



 Oct 02 2007



 next sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com>  writes:


"Janice Caron" wrote

 On 10/2/07, Graham St Jack <grahams acres.com.au> wrote:

 You use it like this (incomplete pseudo-code):

 class ProtectedQueue(T) {
      Condition ready;
      int count;

      this() {
          ready = new Condition(this);
      }

      synchronized void add(T item) {
          add_item_to_queue;
          ++count;
          ready(count > 0);
      }

      synchronized T remove() {
          ready.wait;       // wait until count is > 0
          --count;
          ready(count > 0);
          return remove_item_from_queue;
      }
 }


 I do believe that would deadlock. If thread A was waiting inside a
 synchronized block, then thread B would never be able to enter the add
 function, and hence would never be able to trigger the condition.


Conditions are supported by an atomic "unlock mutex and wait" operation. 
For example,  in windows, by the SignalObjectAndWait function.  You are 
basically saying: unlock this mutex and wait for the condition to be 
signaled, then lock the mutex and return.  The operation has to be atomic so 
that the thread can't be switched out of context just after unlocking and 
miss the signal.  It is actually invalid to wait on a condition without 
having the mutex locked.

So the code above has to do something special by unlocking the object before 
waiting using an atomic operation.  I think this requires some language 
support.

BTW, I'm not sure what the ready(count > 0) function does?  Can someone 
explain it?  It appears that it is the signal, but I'm not sure why the 
condition is required.

-Steve 



 Oct 02 2007



 next sibling parent reply Sean Kelly <sean f4.ca>  writes:


Steven Schveighoffer wrote:

 
 So the code above has to do something special by unlocking the object before 
 waiting using an atomic operation.  I think this requires some language 
 support.


Doing this efficiently typically requires OS support.  The library must 
indicate to the OS that a context switch may not occur while certain 
portions of the code are executing.  It is possible to implement 
condvars without OS support as well, but the implementation tends to be 
fairly complicated.  Look for version(Win32) blocks in the Tango 
implementation for one such example.


 BTW, I'm not sure what the ready(count > 0) function does?  Can someone 
 explain it?  It appears that it is the signal, but I'm not sure why the 
 condition is required.


That call encapsulates some of the logic normally written by hand in 
mutex/condition blocks.  The "count > 0" is the boolean operation to be 
evaluated.  Personally, I think it's kind of an odd design.


Sean



 Oct 02 2007



 next sibling parent reply "Kris" <foo bar.com>  writes:


"Sean Kelly" <sean f4.ca> wrote
[snip]

 That call encapsulates some of the logic normally written by hand in 
 mutex/condition blocks.  The "count > 0" is the boolean operation to be 
 evaluated.  Personally, I think it's kind of an odd design.


Mesa vs Hoare ? 



 Oct 02 2007



  parent reply David Brown <dlang davidb.org>  writes:


On Tue, Oct 02, 2007 at 09:18:14AM -0700, Kris wrote:

"Sean Kelly" <sean f4.ca> wrote
[snip]

 That call encapsulates some of the logic normally written by hand in 
 mutex/condition blocks.  The "count > 0" is the boolean operation to be 
 evaluated.  Personally, I think it's kind of an odd design.


Mesa vs Hoare ? 


I guess so.  Usually, I've just seen that as the difference between needing
'if' vs 'while'.
Since I've never used a system with real Hoare semantics, I'm just not used
to determining the condition on the signalling side.  To me, it puts the
logic in the wrong place.

Dave



 Oct 02 2007



  parent  Sean Kelly <sean f4.ca>  writes:


David Brown wrote:

 Since I've never used a system with real Hoare semantics, I'm just not used
 to determining the condition on the signalling side.  To me, it puts the
 logic in the wrong place.


Same here.


Sean



 Oct 02 2007



prev sibling  parent reply "Steven Schveighoffer" <schveiguy yahoo.com>  writes:


"Sean Kelly" <sean f4.ca> wrote in message 
news:fdtqpn$259o$1 digitalmars.com...

 Steven Schveighoffer wrote:

 So the code above has to do something special by unlocking the object 
 before waiting using an atomic operation.  I think this requires some 
 language support.


 Doing this efficiently typically requires OS support.  The library must 
 indicate to the OS that a context switch may not occur while certain 
 portions of the code are executing.  It is possible to implement condvars 
 without OS support as well, but the implementation tends to be fairly 
 complicated.  Look for version(Win32) blocks in the Tango implementation 
 for one such example.


Why can't you use SignalObjectAndWait?  Are you not using Win32 Mutexes in 
Win32?

I implemented a C++ OS abstraction library, and I had no problems 
implementing conditions on Win32 using OS support...

-Steve 



 Oct 02 2007



  parent  Sean Kelly <sean f4.ca>  writes:


Steven Schveighoffer wrote:

 "Sean Kelly" <sean f4.ca> wrote in message 
 news:fdtqpn$259o$1 digitalmars.com...

 Steven Schveighoffer wrote:

 So the code above has to do something special by unlocking the object 
 before waiting using an atomic operation.  I think this requires some 
 language support.


 Doing this efficiently typically requires OS support.  The library must 
 indicate to the OS that a context switch may not occur while certain 
 portions of the code are executing.  It is possible to implement condvars 
 without OS support as well, but the implementation tends to be fairly 
 complicated.  Look for version(Win32) blocks in the Tango implementation 
 for one such example.


 
 Why can't you use SignalObjectAndWait?  Are you not using Win32 Mutexes in 
 Win32?


Nope.  Critical sections.  For what it's worth, the Tango condvar 
implementation is pretty similar to the one in Boost.


 I implemented a C++ OS abstraction library, and I had no problems 
 implementing conditions on Win32 using OS support...


Frankly, I've never used SignalObjectAndWait.  I think the only place 
things may get a bit weird is in a notifyAll routine.  I guess you'd 
have to use a semaphore for the wait object and perhaps a separate 
counter to track the number of threads waiting on it?


Sean



 Oct 02 2007



prev sibling  parent reply Graham St Jack <grahams acres.com.au>  writes:


Steven Schveighoffer wrote:

 "Janice Caron" wrote

 On 10/2/07, Graham St Jack <grahams acres.com.au> wrote:

 You use it like this (incomplete pseudo-code):

 class ProtectedQueue(T) {
      Condition ready;
      int count;

      this() {
          ready = new Condition(this);
      }

      synchronized void add(T item) {
          add_item_to_queue;
          ++count;
          ready(count > 0);
      }

      synchronized T remove() {
          ready.wait;       // wait until count is > 0
          --count;
          ready(count > 0);
          return remove_item_from_queue;
      }
 }


 I do believe that would deadlock. If thread A was waiting inside a
 synchronized block, then thread B would never be able to enter the add
 function, and hence would never be able to trigger the condition.


 
 Conditions are supported by an atomic "unlock mutex and wait" operation. 
 For example,  in windows, by the SignalObjectAndWait function.  You are 
 basically saying: unlock this mutex and wait for the condition to be 
 signaled, then lock the mutex and return.  The operation has to be atomic so 
 that the thread can't be switched out of context just after unlocking and 
 miss the signal.  It is actually invalid to wait on a condition without 
 having the mutex locked.
 
 So the code above has to do something special by unlocking the object before 
 waiting using an atomic operation.  I think this requires some language 
 support.
 
 BTW, I'm not sure what the ready(count > 0) function does?  Can someone 
 explain it?  It appears that it is the signal, but I'm not sure why the 
 condition is required.


If you read the source for the Condition class under the example, you 
will see that all it does is sets the Condition's satisfied member, 
possibly signaling the underlying pthread_condition_t. Putting this 
boolean into the Condition class makes it FAR easier to avoid coding errors.


 
 -Steve 
 
 





 Oct 02 2007



  parent reply "Steven Schveighoffer" <schveiguy yahoo.com>  writes:


"Graham St Jack" wrote

 Steven Schveighoffer wrote:

 BTW, I'm not sure what the ready(count > 0) function does?  Can someone 
 explain it?  It appears that it is the signal, but I'm not sure why the 
 condition is required.


 If you read the source for the Condition class under the example, you will 
 see that all it does is sets the Condition's satisfied member, possibly 
 signaling the underlying pthread_condition_t. Putting this boolean into 
 the Condition class makes it FAR easier to avoid coding errors.


Doh!  Another case of not reading the whole post, I didn't see that the 
Condition variable was implemented underneath the example code.

I see what it means:

ready(condition)

is equivalent to:

if(condition)
  ready();

Interesting concept, so instead of the waiting thread deciding whether the 
condition is satisfied, the signalling thread decides.  Personally, I'd put 
a test around the wait statement too in case another thread signalled with a 
different reason, just to be sure, but I can see how it works now.

-Steve 



 Oct 03 2007



  parent  David Brown <dlang davidb.org>  writes:


On Wed, Oct 03, 2007 at 11:20:06AM -0400, Steven Schveighoffer wrote:


Interesting concept, so instead of the waiting thread deciding whether the 
condition is satisfied, the signalling thread decides.  Personally, I'd put 
a test around the wait statement too in case another thread signalled with a 
different reason, just to be sure, but I can see how it works now.


This is more like Hoare originally thought of monitors.  My problem with it
is that it puts the logic in a non-obvious place.  It also requires fully
synchronized condition variables (which the example has) where the internal
operations
    unlock mutex
    wait for condition
    lock mutex

are done atomically, and nobody can get in between the wakeup of the wait,
and the relock.  It also generally requires that the signalling of the
condition immediately yield to the one waiting, which isn't how Posix
condition variables are implemented.

So, it is how Hoare thought of it, but not generally how they are used.  I
would suggest not putting the condition into the variable, since it makes
them very different than at least what pthreads users are used to.

Realistically, once we have a functioning condition mechanism, we should
probably implement some higher-level, more useful abstractions.  My
favorite being the 'MVar' (from haskell):

   The MVar is a synchronization variable which can be thought of as a box
   that is either empty or full.  It only has two operations, take and put.

   - put - puts a value into the box.  If the box is already full, it waits.
   - take - takes a value out of the box.  If the box is empty it waits.

They are quite useful.  It can be extended to queues and other types of
things.

Dave



 Oct 03 2007



prev sibling  parent  Graham St Jack <grahams acres.com.au>  writes:


Janice Caron wrote:

 On 10/2/07, Graham St Jack <grahams acres.com.au> wrote:

 You use it like this (incomplete pseudo-code):

 class ProtectedQueue(T) {
      Condition ready;
      int count;

      this() {
          ready = new Condition(this);
      }

      synchronized void add(T item) {
          add_item_to_queue;
          ++count;
          ready(count > 0);
      }

      synchronized T remove() {
          ready.wait;       // wait until count is > 0
          --count;
          ready(count > 0);
          return remove_item_from_queue;
      }
 }


 
 I do believe that would deadlock. If thread A was waiting inside a
 synchronized block, then thread B would never be able to enter the add
 function, and hence would never be able to trigger the condition.


It won't deadlock because because the ready.wait call calls 
condition.wait, which atomically unlocks the mutex.



 
 Incidently, the same psuedo-code written using Events instead of
 Conditions (with the dealock still in place) would be:
 
 class ProtectedQueue(T) {
     Event ready;
     int count;
 
     this() {
         ready = new Event;
     }
 
     synchronized void add(T item) {
         add_item_to_queue;
         ++count;
         ready.signal;
     }
 
     synchronized T remove() {
         ready.wait;       // wait until count is > 0 -- not a good
 idea inside synchronized!
         --count;
         if (count > 0) ready.signal;
         return remove_item_from_queue;
     }
 }





 Oct 02 2007



prev sibling next sibling parent reply David Brown <dlang davidb.org>  writes:


On Tue, Oct 02, 2007 at 09:56:58AM +0930, Graham St Jack wrote:


 I have tried to get conditions into the language before, without success 
 (or even much interest from others). I find Conditions absolutely essential 
 in multi-threaded applications, and can't understand why they are missing.


On Linux, there isn't much else you can do.  You can use events on Windows
and such, but I think it is hard to get event-based programming right.


 You use it like this (incomplete pseudo-code):

 class ProtectedQueue(T) {
     Condition ready;
     int count;

     this() {
         ready = new Condition(this);
     }

     synchronized void add(T item) {
         add_item_to_queue;
         ++count;
         ready(count > 0);
     }

     synchronized T remove() {
         ready.wait;       // wait until count is > 0
         --count;
         ready(count > 0);
         return remove_item_from_queue;
     }
 }


I've normally seen condition code where the wait decision is made as part
of the wait, not as part of the signal.  It allows different waiters to
have different conditions (although having multiple waiters is complicated,
and requires access to pthread_cond_broadcast).

    synchronized void add(T item)
    {
      add_item_to_queue;
      count++;
      ready.signal;
    }

    synchronized T remove()
    {
      while (count == 0)
        ready.wait
      count--;
      return remove_item_from_queue;
    }

When I get to needing threads, I'll definitely look into your condition
code, and see if I can get it to work.  It shouldn't be too complicated, I
just wasn't sure how to get access to the object's monitor.

Is it possible to make 'this' synchronized?

Dave



 Oct 02 2007



  parent  Sean Kelly <sean f4.ca>  writes:


David Brown wrote:

 
 I've normally seen condition code where the wait decision is made as part
 of the wait, not as part of the signal.  It allows different waiters to
 have different conditions (although having multiple waiters is complicated,
 and requires access to pthread_cond_broadcast).
 
    synchronized void add(T item)
    {
      add_item_to_queue;
      count++;
      ready.signal;
    }
 
    synchronized T remove()
    {
      while (count == 0)
        ready.wait
      count--;
      return remove_item_from_queue;
    }


This is the classic approach for using condition variables, and I think 
it's more straightforward than the other method suggested.


 When I get to needing threads, I'll definitely look into your condition
 code, and see if I can get it to work.  It shouldn't be too complicated, I
 just wasn't sure how to get access to the object's monitor.
 
 Is it possible to make 'this' synchronized?


Yup.  In Tango, it's possible to set a Mutex instance as the monitor for 
another object.  Doing so currently requires some pointer magic, but it 
would be simple to encapsulate in a function.

Sean



 Oct 02 2007



prev sibling next sibling parent  David Brown <dlang davidb.org>  writes:


On Tue, Oct 02, 2007 at 08:27:44AM +0100, Janice Caron wrote:


I do believe that would deadlock. If thread A was waiting inside a
synchronized block, then thread B would never be able to enter the add
function, and hence would never be able to trigger the condition.


Aside from the fact that the example isn't quite right (see my other
posting), condition variables _must_ be taken inside of a synchronize
statement.  The underlying condition variable requires a mutex as well as
the condition variable.  The wait operation atomically unlocks the mutex
and goes to sleep.  Upon re-awakening, it then reacquires the lock without
allowing someone else to sneak in.

This feature is the very magic about condition variables that makes race
free synchronization possible where it isn't with events.

   <http://en.wikipedia.org/wiki/Monitor_(synchronization)>

David



 Oct 02 2007



prev sibling  parent reply "Janice Caron" <caron800 googlemail.com>  writes:


On 10/2/07, David Brown <dlang davidb.org> wrote:

 Aside from the fact that the example isn't quite right (see my other
 posting), condition variables _must_ be taken inside of a synchronize
 statement.  The underlying condition variable requires a mutex as well as
 the condition variable.  The wait operation atomically unlocks the mutex
 and goes to sleep.  Upon re-awakening, it then reacquires the lock without
 allowing someone else to sneak in.


Aha! Thanks. Well, I freely admit my ignorance concerning condition
variables. (I've never used them).



 This feature is the very magic about condition variables that makes race
 free synchronization possible where it isn't with events.


Now that part is not right. Race-free synchronization is /always/
possible with events. (Note, however, that I say "possible", not
"guaranteed". There's nothing to stop you writing crap code). That
Queue class of yours could easily be done with events, and race-free
too, but the pseudo code would look quite different.

I guess it's just what you're used to.



 Oct 02 2007



  parent reply Sean Kelly <sean f4.ca>  writes:


Janice Caron wrote:

 On 10/2/07, David Brown <dlang davidb.org> wrote:
 

 This feature is the very magic about condition variables that makes race
 free synchronization possible where it isn't with events.


 
 Now that part is not right. Race-free synchronization is /always/
 possible with events. (Note, however, that I say "possible", not
 "guaranteed".


How so?  Win32 events are widely regarded as broken on 
comp.programming.threads specifically because of race issues with them. 
  Personally, I think they're fine with only one consumer, but things 
get a bit odd with multiple consumers.


Sean



 Oct 02 2007



 next sibling parent reply "Janice Caron" <caron800 googlemail.com>  writes:


On 10/2/07, Sean Kelly <sean f4.ca> wrote:

 Janice Caron wrote:

 Now that part is not right. Race-free synchronization is /always/
 possible with events. (Note, however, that I say "possible", not
 "guaranteed".


 How so?


class ThreadsafeQueue(T)
{
    Event e;

    this()
    {
        e = new Event;
    }

    sychronized void opCat(T x)
    {
        add_item_to_queue;
        e.signal;
    }

    T remove()
    {
        T x;
        for (;;)
        {
            e.wait;
            synchronized(this)
            {
                if (queue.length != 0)
                {
                    x = remove_item_from_queue;
                    e.signal;
                    return x;
                }
            }
        }
    }
}



 Win32 events are widely regarded as broken on
 comp.programming.threads


That's prejudice for you.



 Oct 02 2007



  parent reply Sean Kelly <sean f4.ca>  writes:


Janice Caron wrote:

 On 10/2/07, Sean Kelly <sean f4.ca> wrote:

 Janice Caron wrote:

 Now that part is not right. Race-free synchronization is /always/
 possible with events. (Note, however, that I say "possible", not
 "guaranteed".


 How so?


 
 class ThreadsafeQueue(T)
 {
     Event e;
 
     this()
     {
         e = new Event;
     }
 
     sychronized void opCat(T x)
     {
         add_item_to_queue;
         e.signal;
     }
 
     T remove()
     {
         T x;
         for (;;)
         {
             e.wait;
             synchronized(this)
             {
                 if (queue.length != 0)
                 {
                     x = remove_item_from_queue;
                     e.signal;
                     return x;
                 }
             }
         }
     }
 }


That pseudocode doesn't help much, I'm afraid.  Is this an auto or 
manual reset event?  Is PulseEvent or SetEvent being called by e.signal?


 Win32 events are widely regarded as broken on
 comp.programming.threads


 
 That's prejudice for you.


I'm not sure that prejudice has a lot to do with it.  They complain 
about pthreads nearly as often, though for different reasons.


Sean



 Oct 02 2007



  parent  "Janice Caron" <caron800 googlemail.com>  writes:


On 10/2/07, Sean Kelly <sean f4.ca> wrote:

 That pseudocode doesn't help much, I'm afraid.  Is this an auto or
 manual reset event?  Is PulseEvent or SetEvent being called by e.signal?


Bugger! I was trying to keep things simple. Auto reset and SetEvent.
When you signal, at most one thread wakes up. When a thread wakes up,
the event is reset.



 Oct 02 2007



prev sibling next sibling parent  "Janice Caron" <caron800 googlemail.com>  writes:


Of course, I could have written that pop function as

     T remove()
     {
         for (;;)
         {
             e.wait;
             synchronized(this)
             {
                 if (queue.length != 0)
                 {
                     e.signal;
                     return remove_item_from_queue;
                 }
             }
         }
     }

And of course I'm assuming that add_item_to_queue and
remove_item_from_queue will adjust queue.length. If not, you'd keep a
count variable.



 Oct 02 2007



prev sibling  parent  David Brown <dlang davidb.org>  writes:


On Tue, Oct 02, 2007 at 09:52:35AM -0700, Sean Kelly wrote:

 Janice Caron wrote:

 On 10/2/07, David Brown <dlang davidb.org> wrote:

 This feature is the very magic about condition variables that makes race
 free synchronization possible where it isn't with events.


 Now that part is not right. Race-free synchronization is /always/
 possible with events. (Note, however, that I say "possible", not
 "guaranteed".


 How so?  Win32 events are widely regarded as broken on 
 comp.programming.threads specifically because of race issues with them.  
 Personally, I think they're fine with only one consumer, but things get a 
 bit odd with multiple consumers.


It's certainly possible, but it requires a possibly unbounded loop to
detect and recover from the race case.  It would only loop in the unlikely
even of the exact timing needed to make the race happen each iteration.

The real problem is that the obvious way of doing things is the way that
has the race, and then it gets missed and things deadlock.

Condition variables can have starvation problems with multiple consumers.
Generally, with multiple consumers, it is best to build a higher-level
abstraction that can be reasoned through for correctness and fairness, and
then used.

Dave



 Oct 02 2007