\documentstyle[6.033-ps,12pt]{article}
\title{Scheduling Resources in a Threaded Environment}
\date{February 26, 1991}
\setallmargins{1.25in}
\begin{document}
\maketitle

In Hoare's model, wait and signal are direct commands to the
scheduler.  When shared data needs to be protected against being
modified by multiple threads concurrently, the critical code is placed
inside a monitor function.  At the beginning of the monitor function,
a condition variable is waited on.  If no other thread is waiting on
the condition, execution continues, otherwise execution is blocked.
At the end of the monitor, the function signals the condition.  At
this point, exactly one blocked thread is allowed to begin execution
again.  If there are no blocked threads, the signal is ignored.

In contrast, in Birrell's model, the signal does {\em not} guarantee
that exactly one blocked thread will be started.  It is possible for
more than one thread to be started, and it is possible to broadcast on
a condition, which will cause all threads to continue.

The most important way in which these models differ is that after a
wait unblocks in the Hoare model, the thread knows that it has
exclusive access, and that no other thread has interposed since the
most recent thread signalled the condition.  Under the Birrell model, 
this is not guaranteed, and the thread must check that the condition
it was waiting for is really in the state the thread wants it in.

Because of the above difference, the Hoare model makes it easier to
reason about multi-threaded programs.  As long as all operations which
need to be atomic are protected inside monitor functions, there will
be no problems of timing-related data corruption.  With the Birrell
model, the programmer needs to be more careful about keeping his data
intact, as he must remember to check the state of his data before and
after the wait on the condition variable.  Most of the other issues of
correctness, such as deadlocking and efficiency, are essentially the
same in both models.

\end{document}
