Re: self-paging

[Jonathan S. Shapiro]

[OOPS - I meant this to go to the list too. Sorry.]

On Tue, 2005-12-06 at 13:10 +0100, Bas Wijnen wrote:
> > It follows immediately that nothing else can be permitted to violate the
> > *schedulers* guarantee. In practice, this tends to mean that *anything* that
> > schedules hard resource commitments is real time (in the sense that it needs
> > to talk to the RT scheduler to get the guarantee).
> 
> > When you talk about not swapping a process out, you are talking about
> > pinning its pages.  This is a hard guarantee, so indeed you are proposing a
> > real-time situation.
> 
> No, I'm not.  What I'm saying is that its priority is so high compared to the
> others that the result is the pages will not be swapped out.  However, there's
> no guarantee at all: If the user lowers the priority, or sets the priority of
> some other process to a comparable value (or much higher), then it will be
> swapped out.

Okay. I now understand you. I would not have described that as "not
swapping the process out", because it isn't a hard guarantee. But the
confusion is purely a matter of word choice; what you describe seems
workable.

> > > Why must this be without user intervention?  Because it'd be very annoying
> > > for the user to turn the knobs all the time.  What the user wants to do is
> > > give the game high priority.
> > 
> > Nonsense. What the user wants to do is say "make that one run better".  The
> > user has probably never heard of priority.
> 
> If the user doesn't know this is called "giving it higher priority", that
> doesn't mean it's not what he wants.

Agreed. My point is that the interface used for most users wants to be
expressed in simpler terms.

> > And in any case, this *is* user
> > intervention. Now we are just arguing about the UI.
> 
> What I call user intervention is that the user actually has to do something.
> I don't want the user to do something every time the physical memory quota
> needs to change (which is on every big allocation, _and_ deallocation).

The user *did* do something: they used a UI to express a preference. I
agree that micromanaging the situation is undesirable. Fortunately it's
not desired.

> > The point I'm trying to make is that tuning knobs is actually a good
> > metaphor. The user wants to say "make that one go faster", but the problem
> > with this is that they don't really know why it is slow.
> 
> Right.  This is why I said the physical memory priority and the CPU priority
> may be the same variable.  As Antrik wrote, a market-based approach is an
> other option which aims at the same target.

You are now proposing unified multi-resource scheduling. I think that
everybody in the scheduling world agrees that this is the right approach
in principle, but nobody knows how to do it practically.

> > > ...  Then the system should just give it the memory it wants when it asks
> > > for it (at the cost of others, which have a lower priority).
> > 
> > I think you are confusing two things here: the allotment vs. the allocation.
> > The part that is tricky from the scheduling point of view is the allotment.
> > That was done when the user changed the tuning knob (at least indirectly, in
> > the sense that the user has told the long-term scheduler how to rebalance).
> > The allocation is then done according to process demand.
> 
> I don't think I was confusing things.  What you write here is exactly what I
> thought.  Which part of it did you think was not what I wrote?

Bas: when we get to the point where we are confused only about our
selection of words, it's a very good sign!

> 
> > > > I understand that you want these things to be fast. That is not the same
> > > > as wanting them to be real-time.
> > > 
> > > Indeed.  I wasn't talking about real-time (although giving it all the
> > > memory it asks for may hinder other applications which do want
> > > real-time)...
> > 
> > Please re-read your sentence. Do you now agree that you *were* talking about
> > real time?
> 
> No.  I was talking about having them done fast.

Yes. My confusion on this point went back to the misunderstanding about
what "do not swap this process" meant.

> > In EROS/Coyotos, the eviction decisions are made in the kernel guided by
> > application-defined policy. This is largely because of checkpoint. In
> > practice, it doesn't seem to restrict the feasible policies.
> 
> That sounds ok then.  On the other hand, this seems to be a part which can be
> moved out of the kernel to user space now you no longer demand that the kernel
> can handle any misbehaving application, even one in the TCB.

Probably not. There is still a strong motivation from separation of
concerns. In order for an application to deal with this, it would need
access to some data structures that must be updated by the kernel and
have SMP sensitivities. I think it is better that these data structures
always be handled by the same party.

The actual I/O is already handled at user level.

> > > First of all, note that there is a list of pages per process.  So
> > > "position 4" is meaningless to the process who puts it at position 10 in
> > > its own list.  The page will be stored in two lists, at its own position
> > > for each.
> > 
> > Yes, the problem is that the kernel is now going to have to ask two parties
> > for an eviction policy, and (whichever one is chosen) it will pick the wrong
> > one to ask...
> 
> There is no "wrong one".  When the kernel wants to increase the physical
> memory quota of a process (and there are no unused pages), it will have to
> decrease someone else's quota.

When sharing is considered, this stops being true. Suppose you and I
both need a page and have assigned it a position. I need it badly, you
need it less badly. You fault, and your pager says "shoot that one". The
problem is that I still need it. Getting this right requires a unified
management scheme for shared items.

> > > Every space bank has a certain number of "active" pages.  Those can be of
> > > three types:
> > > - currently in memory
> > > - currently in swap
> > > - currently nonexistant ("swapped-out" cache)
> > > The third one exists because the process doesn't need to reallocate it
> > > when it is "swapped out", it can just remap it, however there's no
> > > guarantee about the contents.
> > 
> > This has nothing whatsoever to do with space banks! Space banks allocate
> > disk storage, and the space bank data structure is a disk data structure!
> 
> Ok, perhaps I didn't understand what a space bank is.  Here's what I thought:
> A space bank gives space to store things.  Storage is either on disk, or in
> memory, or both.  Storage on disk is "swapped out".  Storage in memory and on
> disk is normal memory, with a reserved place to put it when it will be swapped
> out.  Storage only in memory is cache, which is lost when it would be swapped
> out.

Okay. I understand what you thought, but it doesn't work that way. In a
persistent system, *all* pages are disk pages, and residency is managed
orthogonally.

shap