Re: [boost] Re: Threads

From: Greg Colvin (gcolvin_at_[hidden])
Date: 2000-08-21 16:47:37

From: William Kempf <sirwillard_at_[hidden]>
> > From: William Kempf <sirwillard_at_m...>>
> >  --- In boost_at_[hidden], "Greg Colvin" <gcolvin_at_u...> wrote:
> > > > From: "William Kempf" <sirwillard_at_m...>
> > > > > --- In boost_at_[hidden], "Greg Colvin" <gcolvin_at_u...> wrote:
> > > > > > From: "William Kempf" <sirwillard_at_m...>
> > > > > > > --- In boost_at_[hidden], "Greg Colvin" <gcolvin_at_u...> wrote:
> > > > Makes perfect sense to me.  See the example code below.
> > > > 
> > > > > You've set it up so the only way to notify a condition is by first 
> > > > > waiting on a second condition.  I don't see how this would even 
> > > > > work.  Who would notify your "in" condition?  How would they insure 
> > > > > at compile time that the mutex was locked?  I see nothing solved here 
> > > > > and see little purpose in having an "out" condition.
> > > > 
> > > > Typically the conditions start out signaled, so the very
> > > > first attempt to wait on them returns immediately.
> 
> CVs aren't like Win32 events.  They don't "remain signaled".  I 
> realize that our own CVs could behave differently, allowing this to 
> work the way you describe, but see my point below.

I didn't say they would "remain signaled", just that they would start
out signaled so that when you have a set of blocks in a monitor, each
waiting on a condition, there is some way for one of the blocks to
start running and signal the others.

> I should also note that your proposal assumes some relationship 
> between the two CVs.  Often there will be no relationship at all.  It 
> seems like you've simply attempted to find a resolution for a single 
> problem instead of thinking about general useage patterns.

No, I'm trying to find a safe C++ representation of the "monitor"
concept, which previous work in computer science has shown to be a
sufficient basis for multi-threaded programming.  I'm using the bounded
buffer as the classic example, in which there is one monitor and two
related queues (a.k.a. "condition variables").  Of course if the
conditions are unrelated they won't be combined in a single wait/notify
block.

> > > > Here is the classic two-condition example, where after waiting on
> > > > nonfull you need to notify nonempty, and after waiting on nonempty
> > > > you need to notify nonfull.
> > > > 
> > > >    class buffer : mutex {
> > > >       int p,c,n;
> > > >       vector<int> buf;
> > > >       condition nonfull, nonempty;
> > > >    public:
> > > >       buffer(int n) : p(0),c(0),n(0),buf(n){}
> > > >       void send (int m) {
> > > >          wait entry(this,(free1 == buf.size()) (n),nonfull,nonempty);
> > > >          buf[p] = m;
> > > >          p = (p+1)%buf.size();
> > > >          ++n;
> > > >       }
> > > >       int receive() {
> > > >          wait entry(this,(free1 == 0)(n),nonempty,nonfull);
> > > >          int i = buf[c];
> > > >          c = (c+1)%buf.size();
> > > >          --n;
> > > >          return i;
> > > >       }
> > > >    };
> > > 
> > > And if we have only one condition?  What will you do then, use an 
> > > artificial second condition just to satisfy the need for two 
> > > conditions?  What if we have three conditions we must wait on?
> > 
> > I previously presented a single condition variation, but
> > left it out of this example to keep it simple.  Sorry.
> 
> So you're proposing seperate CV implementations depending on the 
> number of conditions used?

I think that zero-, one- and two-condition variants may suffice.

> > I don't see any difficulty with more than two conditions.
> 
> Which "out condition" do you signal?  Both?

Whichever one is made true.  I see each monitor function as causing
a transition from an entry state to an exit state, so you can string
as many of them together as you like.  Where this might break down is
a problem that requires conditional signalling.  For that a three-
condition variant with a extra expression will be needed.  So in all
I see four forms:

   wait(monitor)

   wait(monitor,entry_lambda,condition)

   wait(monitor,entry_lambda,entry_condition,exit_condtion)

   wait(monitor,entry_lambda,entry_condition,
        exit_lambda,if_exit_condition,else_exit_condition)

> > > Again, I see no purpose to signal a second condition on exit of the 
> > > wait in a general fashion.  It may work in some specific cases, but 
> > > it's pointless in most.
> > 
> > In a multi-queue setup you will always want to signal a condition
> > at the end of each handler.  How else to make any progress?
> 
> This isn't necessarily true.  However, the biggest problem is that 
> you're addressing the "bounded buffer/producer consumer" problem 
> specifically, with out thinking about how the CV can be used outside 
> of this single problem domain.

I'd like to see examples of problems that can't be solved with monitors
and closely related condition variables.  I agree that always tying the
signal to monitor exit is limiting.  My point is that it is a common and
useful pattern that can be supported safely at compile-time.  It is still
an open question whether all necessary patterns can be so supported.