Re: Threads

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