[gclist] Mars Rover info from comp.risks

[Jerry Leichter]

| > ...In a Hoare monitor, a condition variable is scoped to be accessible
| > only inside of one monitor, and further the monitor's semantics is such
| > that only one thread can be "in the monitor" at a time.  Hence, you know
| > whose priority to raise:  When any process enters the monitor, its
| > priority is raised to match the highest priority of any process waiting to
| > enter the same monitor.  The relevant "resource" is the monitor itself,
| > and the compiler/run time system always knows
| 
| This isn't usually possible for either Hoare monitors or Java wait().  There
| is no requirement when I call wait() that there be any other thread in the
| monitor. Usually there won't be.  A producer thread may wait for a slot in a
| buffer to become available.  The monitor protects the buffer.  There may be
| multiple consumer threads running the following in a loop:
| 
|   acquire lock on the buffer
|   remove buffer entry or entries
|   signal availability of buffer slot
|   release buffer lock
|   process buffer entry
| 
| Typically most of the time will be spent in the last step.  (If I expect any
| concurrency, most of the time better be spent in the last step.)  Thus a
| producer thread encountering a full buffer is likely to not see anybody in
| the monitor, and it has no way of telling which thread will remove a buffer
| entry next....

You're asking too much of priority inheritance here.  Priority inheritance
deals with the problem of *locks* being held by intermediate-priority
threads.  It doesn't even attempt to deal with the problem of *resources*
being held by intermediate- or even low-priority threads.  That's what you've
got here.  In fact, priority inheritance never helps when there are only two
threads involved.  Here, the conflict arises between a single consumer and a
single producer - and no locks are being held during the conflict.

In fact, what you *probably* want here is a priority boost for a thread that
has just completed a wait.  When the consumer releases the buffer lock, the
producer, which has been waiting, should get the CPU next.  That helps here,
but causes too much context switching in many other, equally reasonable,
cases.  However, it's probably reasonable to say that the thread that is
chosen by cond_signal() should be given a priority boost.  This issue goes
back to Hoare monitors: There has always been a debate as to which thread
should be run when a condition variable was signalled:  The signaller or the
previous waiter.  It's easier to let the signaller keep running, but there
is a sound argument for letting the previous waiter run:  The signaller may or
may not have more work that it's able to do, but the waiter almost certainly
does, since it just got what it was waiting for.  However ... if you try
making that change with the code as written above, you get an immediate
context switch to the waiter, which promptly blocks on the buffer lock - at
which point you switch back to the previous thread so that it can unlock the
lock, and switch contexts again.  You can't build this kind of policy out of
separate, non-communicating primitives!  You need to have a primitive for
"block the scheduler; find the thread to signal; bump its priority; make it
runnable; release the lock; unblock the scheduler".

							-- Jerry