Re: [boost] Re: Threads

From: Greg Colvin (greg_at_[hidden])
Date: 2000-08-23 19:27:47

From: William Kempf <sirwillard_at_[hidden]>
> --- In boost_at_[hidden], "William Kempf" <sirwillard_at_m...> wrote:
> > --- In boost_at_[hidden], Jens Maurer <Jens.Maurer_at_g...> wrote:
> > >  - Hoare's monitor pattern says that the mutex must be locked
> > > around notify() to avoid race conditions.  Even though pthreads
> > > doesn't seem to require this, it's still a good idea to follow the
> > > textbook pattern, I think.
> > 
> > Is that why the book I have on pthreads says that you must do this?  
> > Exactly where in Hoare's monitor pattern does it say this?  What's 
> > the quote?  I seem to have missed it.
> 
> I've been thinking about this one.  I'm still curious to hear what 
> quote from the original paper makes this claim, though in general it 
> must be true and I'll outline why.

A very clear exposition, thanks.  But I've snipped most of it to save
space.

> ...
> monitor buffer   // instead of class buffer
> {
> public:
>    buffer(int n) : buf(n), p(0), g(0), full(0) { }
> 
>    void send(int m)
>    {
>       if (c == buf.size())
>          wait(not_full);
>       buf[p] = m;
>       p = (p+1) % buf.size();
>       ++c;
>       signal(full);
>    }
>    int receive()
>    {
>       if (c == 0)
>          wait(full);
>       int m = buf[g];
>       g = (g+1) % buf.size();
>       --c;
>       signal(not_full);
>       return m;
>    }
> 
> private:
>    int p, g, c;
>    std::vector<int> buf;
>    condition full, not_full;
> };

I think you should wait on "not_empty" rather than "full", but that
is just a nit with your names.

> ...
> This is a *lot* less complex than the equivalent to a pthread 
> condition which must allow a notify_all().  However, notify_one() 
> isn't as safe or flexible as notify_all().  With notify_one() you 
> must always use one predicate for one condition.

Yes, though I think you can fake notify_all by having your own list
of threads and notifying each one.

> The point of all of this?  I'm not sure that we should exactly 
> conform to the classic monitor.  I think that notify_all() is safer 
> and more expressive than notify_one().

Isn't there a "thundering herd" performance hit for notify_all
that notify_one avoids?

>  By the same reasoning, it 
> *might* be safer and more efficient to allow notifications outside of 
> the mutex lock (this assumes there isn't truly a race condition by 
> doing so).

I'm not sure what efficiency is gained by allowing notify outside
the lock, but I am fairly sure there is a danger of a race.  Consider
what might happen if you unlocked the mutex just before your signal
calls above.  How to know that the condition being signaled is still
true when the wait ends?

By the way, I am currently looking at an interesting alternative
to the "monitor" approach being worked on for Java
   http://www.cs.ukc.ac.uk/projects/ofa/jcsp/ 
This amounts to a Java library modelled on the Occam programming
language, which itself is modeled on Hoare's Communicating
Sequential Processes.