Re: self-paging

[Bas Wijnen]

On Fri, Dec 02, 2005 at 01:41:53PM -0500, Jonathan S. Shapiro wrote:
> I think I made my statement badly. What I meant to say was: you don't
> need to notify the application in order to let the application specify
> how pages compete for residency.
> 
> That is: expressing preference about what to page out doesn't require
> notification. You don't need notification until your application wants
> to do adaptive overall residency.

Ok, but it seems nice to allow that.  Therefore I think the notifications are
a good idea.

> > >   2. Soft reservations are adjusted only in response to user action.
> > >      For example, when your window ceases to be in front, we can tell
> > >      you safely that your CPU contract and memory contract are reduced.
> > 
> > While this would not be an acceptable policy for me, I agree that the idea
> > can work.  I'm not sure if I'd like it though.  I think I prefer to have
> > settings for the quota which can be bound by the user (so dynamic values,
> > but limited to a range).
> 
> Two examples to consider:
> 
> 1. Video. Front window closes, resources get rotated so that the new
> front video window now gets "frontmost" resources.
> 
> 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'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.

> > >       [User-driven changes] does not create a channel issue,
> > 
> > It does.  The channel is just very low bandwidth...
> 
> Actually, it does not. The user's authority to change those resource
> commitments is explicit. It's an *overt* channel. What I was trying to
> say above is that there is no *covert* channel issue.
> 
> >   But if a process runs for
> > days, and some program is so slow at certain actions that the user will go
> > do something else while it's working, then that is noticable by other
> > processes and it can be used as a communication channel.
> 
> 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. ;-)  Anyway, the point is
that even in this case, there is a channel which the user doesn't know about
(that is, the user doesn't notice the communication) even if he is in the
communication path personally.  So it boils down to: There always is a covert
channel with dynamic quota, and all we can do is limit the bandwidth.

> > >       and it seems to deal very well with the problems that people are
> > >       really trying to solve when they do this type of adaptive
> > >       reservation.
> > 
> > The policy you gave (foreground == highest priority) is very
> > single-tasking oriented.  I like to do things in the background, and I
> > wouldn't like it if those things get less resources just because I'm
> > typing in an other window.  I think this is not just a nerd-thing.
> 
> Actually, I wasn't thinking in single-tasking terms. What I was thinking
> was based on a very basic observations: the human doesn't really care
> how fast the updates are on bits that are not visible. Further, if you
> have three movies stacked in overlapping windows, I'm pretty confident
> that you aren't watching the back movie at full fidelity.

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.

> So yes, there is some need for multitasking here, and it may be
> necessary not to penalize the second movie player too much. But
> ultimately, it's the *user* who has limited tasking capabilities, and if
> the goal is to support interactive applications it's reasonable to
> exploit that fact.

True, but not all programs need to give the user direct feedback.  Programs
which don't do that aren't always less interesting for the user, but they are
likely backgrounded while the user does something else.  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.

> > What your reply didn't comment on is the two big parts of my proposal:
> > 
> > - The application manages a list of its pages, thereby it can do its own
> >   paging (literally while the quota don't change, only preparing the order
> >   when they do).  What I didn't mention yet, is that I fear this may cause
> >   overhead (because the list must be managed with system calls to physmem).
> >   Perhaps this isn't a problem if the management is simply ignored until
> >   swapping starts.  What that happens, RPC performance is no longer a
> >   significant factor anyway.
> 
> What you are trying to achieve is fine, but I think that this particular
> mechanism will be cumbersome.

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.  Perhaps
with a flag to say if the rest should be moved up to make space in the list,
or the page where it goes should be moved to the end (leaving the rest of the
list as it is).  While not swapping, a process which doesn't really care about
policy could always insert new pages at the start of the list (so the new page
is always available itself).  That's fast and there's no thinking involved by
anyone, so I don't see why that would be cumbersome.  When there is memory
pressure (the physical memory quota is smaller than the number of pages), the
pages need to be arranged in a good way.  Processes which don't care about
policy can still use the same method as before and additionally moving any
swapped-out page they need to the front of the list.  This implements the LRE
policy.  I think this is very easy as well.

Now things change for processes which want to fine-tune the policy.  They need
to think about the order of the list, mark the correct pages as "cache", and
reorganize the list every now and then.  I agree that this can be cumbersome,
depending on the degree of fine-tuning.  However, this is a choice of the
process: If it wants that kind of control (self-paging, really), then it will
have to work for it.  I think you're saying that it's too much work to force
on a process, and therefore it should not be supported.  But I'm not forcing
it on the process, I just want them to have the choice.

> 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.

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.

> > - Change the quota very slowly, not immediately on every event, so the
> >   communication channel is narrowed.
> 
> Better still, change it at known intervals that are long enough to obscure
> individual behavior. For example, recompute every K seconds.

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).  Thinking
about this I do still see channels, and they might even transfer a bit per
update, which is more bandwidth than I hoped.  Well, perhaps there needs to be
extra noise then, by making the actual changes a bit random (but going in the
correct direction in general of course).

Thanks,
Bas

-- 
I encourage people to send encrypted e-mail (see http://www.gnupg.org).
If you have problems reading my e-mail, use a better reader.
Please send the central message of e-mails as plain text
   in the message body, not as HTML and definitely not as MS Word.
Please do not use the MS Word format for attachments either.
For more information, see http://129.125.47.90/e-mail.html

signature.asc
Description: Digital signature