Re: self-paging

[Jonathan S. Shapiro]

On Sat, 2005-12-03 at 09:30 +0100, Bas Wijnen wrote:
> On Fri, Dec 02, 2005 at 01:41:53PM -0500, Jonathan S. Shapiro wrote:
> > 
> > 2. Tuning knobs: app gives jaggy video, user turns a quality knob.
> 
> What I mean by settings for the user really is 2, except that 2 seems very
> window-oriented.  The point I'm making is that the user may want something to
> get resources which isn't in the foreground.  For real-time video this is
> obviously not the case, but computationally intensive tasks are often
> uninteresting until they're done.  Consider a fractal generator.  If you want
> generation to be fast, you minimize the window so it doesn't waste time on
> drawing intermediate states.  It is not desirable if that means the generation
> is even slower because much of its resources are revoked.

I don't agree. First, there is no reason to imagine that tuning knobs
are limited to visible windows, so I don't really agree with that
concern. The user has X amount of real-time slice to divide up and give
out, and has an interface that lets them decide who gets it.

Second, I don't agree with the background fractal example. If the user
puts the fractal generator in the background and then starts a movie,
they are saying "my attention is on the movie". I think that the
principle here is that real time guarantees have to do with responding
in a timely fashion where the focus of attention is. The background
fractal problem may be a motivator for a high priority, but it is *not*
a motivator for a real time guarantee.

Yes, I can see that we may construct other scenarios that will make
real-time background schedules motivated. Fair-share scheduling comes
immediately to mind, but note that fair-share scheduling was in
hindsight a silly idea.

> > I'm curious what application you have in mind where you feel that the
> > resource should be dynamically adaptive without user intervention. I can
> > think of some, but for most of them I end up concluding that dynamic
> > adaptivity isn't well motivated.
> > 
> > So: what application are you thinking about?
> 
> Many applications need resources only every now and then.  For example a game
> may need much more memory to generate a level than to play it.  It is
> impractical if the user needs to manually change the quota every time a new
> level is generated.  However, it is unacceptable if the game gets the physical
> memory reservation all the time, even when there is pressure.

This is not a good motivator. Level generation is not a real-time
activity. At worst, it is an interactive-time activity. Why should it
involve a residency quota at all?

> > Clever observation. I had failed to consider exploiting the multiplexing
> > behavior of the user. Clearly we need to assign well-defined schedules
> > to the users, and constrain them to act according to those
> > schedules. ;-)
> 
> I'm not sure if people will want to use our OS then. ;-)

Nah. Lock them in a padded room and let them play with windows for a
month. I promise you, they'll *beg* for the Hurd.

> So it boils down to: There always is a covert
> channel with dynamic quota, and all we can do is limit the bandwidth.

More generally: all you can do with *any* covert channel is limit the
bandwidth.

> This is true, but things I do in the background aren't usually movies.  Movies
> are a typical example of something which may be completely stopped when not
> visible.  Many other applications though (computationally intensive things
> like simulations) can do very useful things of which the user will only want
> to see the end result.  If they need to be in the foreground in order to keep
> their resources, that very much stimulates single tasking.

I understand that you want these things to be fast. That is not the same
as wanting them to be real-time.

> For example the user
> may start a game of mine sweeper waiting for mp32ogg to finish.  This doesn't
> mean that mine sweeper is more important than mp32ogg.

Actually, it does. If minesweeper's interaction is inadequate, it
doesn't satisfy. In this example, minesweeper needs a guaranteed slice
(though it doesn't need to be very big).

The problem here underneath it all is that you are imagining a policy
defined by the user about where you want resources to go, but you aren't
proposing a way for the user to articulate the policy, and the system
simply isn't able to guess the answer. If you want to be able to
articulate this, you're going to need a tuning interface somewhere that
says "it's really important to me that mp32ogg finishes soon, and I'm
willing to tolerate a low render rate in doom3 until it does."

> During this thread I got more and more the idea that it isn't cumbersome at
> all, really. :-)  The program needs to request a page anyway.  So add an extra
> argument to that call which specifies where that page is in the list...

I think that you are not considering the kernel-level implications well
enough. I'm not sure which design is better. Here is what I do know:

  1. The design that I have in mind had a prototype implementation
     at one point. We know it is feasible. We don't know if it is
     good enough to do what you want. We need to find out.

  2. The design that you propose is tricky, because it involves
     attaching ordering state to each frame. This is not as easy
     as it sounds. What happens when you and I share the same frame,
     and you say "put it in position 4" and I say "put it in position
     10"? Where does the position info get stored? Hint: can't be done
     in the kernel, and then we are going to get a reductio problem
     here.

> > I think the application should instead define working set contexts for
> > regions in its virtual address space, and then define a replacement policy
> > for each context. The association between a frame and its dominating context
> > is maintained within the OS, and is not explicitly disclosed to the
> > application.
> 
> I don't quite see what you're saying here.  If the policy is not disclosed to
> the application, then it isn't the application which sets it I suppose?  Who
> does set it then?  It will be a property of the space bank, which isn't
> controlled by the parents of the process.

It is not a property of the space bank. It is a property of the kernel.

What I would actually propose initially is that the kernel implements
approximate LRU w.r.t. a pool, and the application manages contention by
keeping separate pools separate.

> I'm not really sure what you mean, but I don't think I like it. ;-)  Adding a
> layer of contexts with different behaviour on top may in some cases be a good
> idea, but I'd do that in the pager (which does most of the list rearranging),
> only for pagers which want to make use of it.  Otherwise it just adds extra
> baggage to processes which don't use it.

You can't do this in the pager. The pager itself may need to remain
resident. The residency requirement needs kernel support at the bottom
level. The problem I have with your proposal is mainly that you haven't
connected the dots that far and I can't see how to implement it.

> My idea was to do the changes at fixed intervals, indeed.  I guess I forgot to
> say that. ;-)  However, I would also do it gradually.  So every update should
> change the quota of a given process at most +/-P pages, where P isn't very
> large (but also not too small, otherwise starters have problems).

Yes, oscillation is bad for you.


shap