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.

 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
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?

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

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.

--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
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 "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
prev sibling next sibling parent "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
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 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 in C#. I have heard hearsay that programming with condition variables is 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 "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 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 next 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 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 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
parent 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".


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
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 "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 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.

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;
      }
 }

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 "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
prev sibling next sibling parent 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
prev sibling 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 next sibling parent 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
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 next sibling parent "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
prev sibling next sibling parent "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
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 next 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.

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
prev sibling 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