Boost logo

Boost :

From: William Kempf (sirwillard_at_[hidden])
Date: 2000-08-23 17:21:58


--- 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 monitor is a special type of "class". For true C++ monitors as
defined in the classic paper we'd need a language change, which would
result in code like this:

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

The keyword "monitor" replaces the keyword "class" (or "struct") for
monitor types. The compiler would then automatically synchronize all
calls to methods of the monitor. Conditions are native types (so
condition is a keyword) that can be declared only within a monitor at
class scope. The wait and signal are operators that can only be used
on conditions and only within monitor method scope. (Boy, isn't this
complicated.) Because of these constraints it follows that the
hidden mutex must always be locked when a call to signal or wait is
made (after all, they can only be made within the monitor by
definition of the language).

As a library, we can only use artificial constraints for these
requirements. This has two major consequences: the programmer must
lock the mutex on entry to all monitor functions explicitly which can
be error prone, and all rules given for conditions can not be
enforced by the library. I don't think we can address the lock
issue, short of specifying useage patterns. The condition issues,
however, can be addressed in various ways. We can insure we have a
lock in a call to wait (the most critical one) by having the
interface require a lock object be passed in. For the signal we can
relax the requirement that the mutex be locked, provided that this
doesn't result in a race condition. I'm not sure that it will,
especially considering that this is the recommended approach in
pthreads, but I'd love to hear the arguments that explain why it is.

Another key point in this example: the classic paper only defines a
signal() which is analogous to notify_one(). There is nothing
analogous to notify_all(). This simplifies the definition of a
condition to a construct as simple as:

class condition
{
public:
   condition() : m_count(0) { }

   void signal()
   {
      if (m_count > 0) m_semaphore.up();
   }
   template <typename L>
   void wait(L lock)
   {
      m_count++;

      // use the lock to unlock the mutex

      m_semaphore.down();

      // use the lock to relock the mutex

      m_count--;
   }

private:
   semaphore m_semaphore;
   int m_count;
};

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.

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(). 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).


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk