October 02, 2007
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.
October 02, 2007
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
October 02, 2007
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.
October 03, 2007
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;
>     }
> }
October 03, 2007
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 
> 
> 
October 03, 2007
"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


October 03, 2007
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
1 2 3 4
Next ›   Last »