Re: Explicit Posix/Notify() vs Guards

[stt@houdini.camb.inmet.com (Tucker Taft)]

Dale Stanbrough (dale@goanna.cs.rmit.EDU.AU) wrote:

: The Posix/Threads model (and Java) provide explicit notification schemes
: for informing sleeping threads when to reevaluate any barrier conditions.
: Ada provide guards on entries, and relies on the run time system to 
: recognise when the condition associated with a guard _may_ have changed.

: Clearly the Ada model may end up being overly conservative,
: recalculating the barrier condition more often than is needed.
: In some ways it may be less flexible in that other tasks may be
: unable to cause reevaluation of the guards, in the same way
: that an explicit notify would.

: Is this a reasonable analysis, and what benefits are gained from
: Ada's model?

A major advantage of the Ada model is that as more operations are
added to a protected type, the compiler keeps track of what are
the "interesting" state changes.  With an explicit notify, every
operation must decide when to notify which condition variables.
When the number of operations increase, you can begin to encounter
a combinatorial explosion of cases.

The most important advantage of the Ada model is that it is
state oriented, meaning that the programmer identifies the
interesting states via the barriers, and the compiler+run-time-system
worries about making sure these states are satisfied at the
time the corresponding entry body executes.

With the explicit notification approach, there is no guarantee
that the desired state is still present when a task wakes up,
so the required paradigm is that all "wait"s are inside while-loops,
rechecking the desired state on every wakeup.  This can result
in unnecessary wakeups, or even worse, missed wakeups.

Furthermore, with the explicit notification model, a context
switch must be performed in addition to a lock ownership change
to accomplish every operation.  With Ada, the "convenient" thread
performs the entry body whose barrier becomes true, without any
necessary lock ownership transfer, and without extra context
switches.  It is relatively easy to show that with a simple
producer/buffer/consumer example, the Ada approach can result in
one third as many context switches, and half as many locks and
unlocks as the explicit notify approach.

: Dale

--
-Tucker Taft   stt@inmet.com   http://www.inmet.com/~stt/
Intermetrics, Inc.  Burlington, MA  USA