Resource Revocation

[Neal H. Walfield]

Because we want to be able to dynamically redistribute memory, there
must be a mechanism to enable the scheduler to reclaim it.  This
raises two concerns: which resource to revoke, and how to save the
state (in the case of bandwidth or CPU, how to alter the schedule).

There are two approaches to resource revocation: transparent and
visible revocation.  Transparent revocation is straightforward: the
scheduler chooses a resource to preempt, saves its state, and reuses
the resource.  Visible revocation is potentially more efficient as
applications can choose which resource to preempt and how, however, is
more complex as the scheduler must protect itself from destructive
interference.

With visible revocation, the scheduler may request that an activity
yield some memory.  The activity can then choose any frame it likes.
This is useful as if the scheduler relies on observed access patterns,
it may make a poor selection.  More importantly, perhaps, is that the
application can choose how to save the page.  For instance, instead of
saving a page of anonymous data to backing store, the application may
choose to simply free it based on the observation that it is cheaper
to recompute the results on demand.  It could also send the data over
the network and then free the frame.

The problem with this approach is that the scheduler must protect
itself from destructive interference: a program might not be
cooperative.  As such, a mechanism is required to either coerce the
activity to comply or use a fall back.  To coerce a program instance to
comply, Exokernel imposes a timeout.  If the timeout expires and the
program instance has not freed a sufficient amount of resources, the
program instance is simply aborted.  Thus, to ensure correctness, any
program running on such a system must promptly satisfy all revocation
requests.  This makes the preemption code a hard-real-time problem.
(And makes the code difficult to debug!)  This encourages conservative
strategies, and, as writing such code is difficult, will be less often
done.  Another problem is that resources are required to manage these
resources.  How these resources are supposed to be managed is rarely
explored.  These problems appear to eliminate most of the potential
benefits of visible revocation for a general-purpose operating system.

Visible revocation is only a mechanism: it is not an end.  The intent
behind visible revocation is to give the application more control over
how resources are preempted and to keep them informed thereby allowing
them to adapt.  Just as we have activities assign preferences to
composite activities, we can provide a mechanism to allow activities
to assign preferences to pages.  We can also assign policies to pages.
For instance, instead of sending a page to backing store, the
application may mark a page as discardable.  If such a page is chosen
for eviction, it should simply be freed.  (In this case, a fault needs
to be triggered on the next access.)  This strategy removes the major
source of destructive interference: the scheduler no longer waits on
the task; the task acts beforehand on its own initiative or it reacts
to a signal (not a request).  Further, because all resources are
accounted, the amount of crosstalk should be minimal even if the
activity makes a poor decision.

This solution is clearly more limiting: the appropriate strategies
must be identified beforehand.  However, not that many common
strategies come to mind.  In fact, I suspect that either sending to
backing store or simply freeing cover the most common scenarios.

In short, we want to enable applications to reveal their preferences
so as to allow the scheduler to make more intelligent allocation
decisions.  This appears to be possible to do for important scenarios
without introducing possibilities for destructive interference by
having the activity supply preferences beforehand or making the
application reactive.

Neal