Re: aborting RPCs

[Jonathan S. Shapiro]

On Wed, 2007-01-10 at 20:37 +0100, Neal H. Walfield wrote:
> At Wed, 10 Jan 2007 18:50:37 +0100,
> Tom Bachmann wrote:
> > As has been discussed on the list, the most complex problem is callers
> > revoking donated time pools at arbitrary times. [shap adds: or simply
> > running out of time]
> 
> How to do this can be inferred from section 3.4: the revocation case
> is similar to that when a thread exhausts its budget and there are
> other waiting threads.  Another thread pushes the blocked thread
> through on its own time.

This is a fancy way of saying that one guy steals resource from the
other. If you're willing to tolerate that, why bother with schedule
donation?

There is a difference between

  (a) transfer my schedule capability in such a way that the other
      guy runs on it until exhausted, and then falls back on **their
      own** schedule.

  (b) donate the rest of my slice, in the optimistic hope of quick
      return and cache liveness preservation, but without any
      permanency of continued use.

  (c) transfer my schedule capability in the optimistic hope that
      it will run out of time and somebody else will pay for my
      computation.

Case (a) is a pain to implement. Case (c) is simply a multiplication of
mechanism providing no advantage over a simple priority inversion
scheme. Case (b) is an optimization hack, but it's easy to do and often
helpful.

> After this is described, the authors then appear to mention a caveat:
> 
>   In a normal priority-based system threads always block on a thread
>   with lower priority.  With reservations threads may also block on
>   threads with higher priority and an expired capability reserve.

Um. I'm not sure which way is lower and which higher, and I haven't read
the paper...

Oh. Yes. The problem here is a reservation whose reserve capability is
expired. It is therefore not elligible to run at all, so my important
thread trying to call it will block indefinitely. This is no different
from trying to call a server that never enters an open wait.

The whole problem seems contrived to me. It only arises when an
end-to-end scheduling contract is necessary. In this scenario, solving
the problem with priority inversion works ONLY if the system has
stack-like messaging behavior. General messaging systems, in practice,
do NOT have this behavior, and it is pretty easy to donate slice to the
wrong thread as a result.

A more principled solution is to make these services multithreaded and
actually build an end-to-end schedule using a single scheduling
capability for all of the processes involved. In this case the only
constraint is to ensure that you can get the failed thread out of any
critical section. There are a variety of known techniques for dealing
with that.

However, the multithread solution is not good in a scheduler activation
system. Interesting issue.

-- 
Jonathan S. Shapiro, Ph.D.
Managing Director
The EROS Group, LLC
+1 443 927 1719 x5100