# [concurrency-interest]RE: RE :RE: JSR 166 draft API (David Holmes)

Alexander Terekhov TEREKHOV@de.ibm.com
Mon, 12 Aug 2002 22:31:07 +0200


David Holmes wrote:
[...]
> To use a classic example of the BoundedBuffer:
>
>   public class BoundedBuffer {
>       Condition notFull = new Condition(this);
>       Condition notEmpty = new Condition(this);
>
>       int size = 0;
>       final int CAPACITY = 10;
>
>       public synchronized void put(Object o) {
>           while (size == CAPACITY)
>               notFull.await();
>
>           // store o
>           size++;
>           notEmpty.signalAll();
>      }
>
>      public synchronized Object get() {
>          while (size ==0)
>              notEmpty.await();
>          size--;
>          Object temp = ... // remove
>          notFull.signalAll();
>          return temp;
>      }
> }

Well, frankly, I'd probably opt for:

  public class BoundedBuffer {

      // non-recursive/non-interruptible PThreads-like "locable" thing
      Mutex      mutex   = new Mutex();
      Condition  notFull = new Condition(mutex);
      Condition  notEmpty = new Condition(mutex);
      SomeCollection buffer = new SomeCollection();

      final int CAPACITY = 10;

      public void put(Object o) {

        apply_lock_unlock_statement( mutex ) {
          while (buffer.size() == CAPACITY)
            notFull.await();
          buffer.push(o);
        }

        notEmpty.signal();

     }

     public Object get() {

       Object o;

       apply_lock_unlock_statement( mutex ) {
         while (buffer.empty())
           notEmpty.await();
         o = buffer.pop();
       }

       notFull.signal();

       return o;
     }
}

regards,
alexander.

P.S. My Butenhof's quote-of-the-day: ;-)

Unfortunately, many implementations don't do "wait morphing",
and as a result signalling while holding the mutex can result
in significant costs.

One of the main reasons for signalling while holding the mutex
is "increased predictability". However, the increase is relatively
small, and doesn't provide any absolute guarantee. (It's based on
the fact that mutex contenders and condition waiters will queue in
priority order on the mutex; but that helps only if they're all
actually waiting concurrently, and you're using realtime priority
threads on a uniprocessor.)

The only real requirements are that:

  1) The condition wait be based on a shared data PREDICATE
     condition, and

  2) The predicate is manipulated while holding the mutex
     specified in the condition wait, BEFORE effecting the
     wakeup via signal or broadcast of the condition waiter(s).

Some may find these more easy to manage when you set the predicate
and immediately signal the waiter while still holding the mutex.
You'll often want to change some value and then conditionally signal
based on the new value... if you are going to unlock first you may
need to remember the decision by copying the predicate into a local
variable to avoid unsynchronized (and hence unreliable) access after
unlocking.

This may increase the chances of spurious ("stolen") wakeups because
some other thread may change the predicate between the time you unlock
and the time the awakened thread starts running. That may argue also
in favor of signalling while you still hold the mutex despite the risk
of inefficiency. (On the other hand, stolen wakeups, and other types
of "spurious wake" can occur anyway, so this again at best somewhat
reduces the risk and cost, but cannot remove it entirely.)

Some have argued for FIFO mutexes that grant ownership in order of
request; applied to condition waiters using the mutex, that would
seem to remove (or at least reduce) the risk of stolen wakeups.
However, FIFO wakeup is relatively expensive, and substantially
reduces concurrency that is, on the whole, far more valuable.
Furthermore, nearly all intended requirements for FIFO are in
any case doomed to failure because they are based on the mistaken
idea that threads can viably COMPETE with each other (e.g., in a
"thread per client" server). Threads are inherently cooperative,
because they share far too many resources to effectively or fairly
compete; the goals of threaded programming are better served by
efficient and simple synchronization on which cooperative
applications can build their own task/data scheduling.

And then, if the thread implementation you use implements wait
morphing, the cost of signalling while you hold the mutex is
inconsequential. So one might argue that, if you have a quality
implementation, it really doesn't matter whether you hold the
mutex. ;-)



"David Holmes" <dholmes@dltech.com.au>@cs.oswego.edu on 08/08/2002 06:01:38
AM

Sent by:    concurrency-interest-admin@cs.oswego.edu


To:    "Eric D Crahen" <crahen@cse.Buffalo.EDU>,
       <concurrency-interest@altair.cs.oswego.edu>
cc:
Subject:    RE: #  [concurrency-interest]RE: RE :RE: JSR 166 draft API
       (David Holmes)


> Is the Condition class now less like a POSIX condition variable and more
> like an abstraction for a monitor? It just adding the ability to wait
> uninterruptably or will there be subclasses that sort waiter lists or
> something along those lines?

I'm not sure what you mean by this last part but the Condition class is
used
to provide the effect of multiple condition/wait queues per monitor.

To use a classic example of the BoundedBuffer:

  public class BoundedBuffer {
      Condition notFull = new Condition(this);
      Condition notEmpty = new Condition(this);

      int size = 0;
      final int CAPACITY = 10;

      public synchronized void put(Object o) {
          while (size == CAPACITY)
              notFull.await();

          // store o
          size++;
          notEmpty.signalAll();
     }

     public synchronized Object get() {
         while (size ==0)
             notEmpty.await();
         size--;
         Object temp = ... // remove
         notFull.signalAll();
         return temp;
     }
}

Condition also allows uninterruptible waiting and timedwaits that don't
require you to jump through hoops to see if you timed out.

The order in which waiting threads are signalled is not specified - as per
Object.wait().

A Condition class with ordering guarantees would have to use a "specific
notification" style approach.

David Holmes


_______________________________________________
Concurrency-interest mailing list
Concurrency-interest@altair.cs.oswego.edu
http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest