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.

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

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

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

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

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

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

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

"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

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.