Re: self-paging

[Bas Wijnen]

On Tue, Nov 29, 2005 at 04:45:59PM -0500, Mike Small wrote:
> > > My question, I guess, is how do you handle fairness among processes?
> > 
> > That is not something that my idea solves.  The idea just allows
> > self-paging, and it tries to narrow the bandwidth of a covert channel.
> > How exactly the quota degrades with time and who gets more when several
> > processes are asking is a different question.  This is the fairness
> > question.  It needs to be answered anyway, but I wasn't trying to do so.
> > ;-)
> > 
> > > If I've understood you correctly, I think this way degrades to a game of
> > > King of the Castle.
> > 
> > I don't think I understand what you mean with that, so I cannot confirm
> > that you understood me correctly.
> 
> Sorry, should have thought better than to use that reference.  It's a game
> played by children in Canada where everyone tries to race to the top of a
> snowbank and the "King" is the one who manages to stay up there and push the
> other kids back down.  So I was thinking of it in terms of processes racing
> to get the largest quota allocations possible up until the point where
> memory pressure problems start.  At that point the processes that moved
> fastest earlier are in a much better position, i.e. they're metaphorically
> higher up the snow bank.

Ah, ok.  Well, no, I don't think the system enforces this.  If this happens
depends on how the decay and regeneration works.  If each process has a
"physical memory priority", the regeneration may work such that the ratio
between them fits their priorities.  For example take two processes A and B,
with priorities of 1 and 2 respectively (higher is better).  A holds 10 pages,
B holds 10 as well.  Then there is memory pressure.  A's pages will be swapped
out until it has only 5.  At that point, both A and B's pages will be swapped
out.  There is some slowness in this to narrow the covert channel, but having
more pages doesn't give you a better position for defending them.

Anyway, this is just one example of how to handle the distribution of pages
(that is, which process gets how much and when).  Other ways are possible for
that with my system, and all those ways can be used with a different system.
What I'm asking for is if there are big drawbacks to my proposal.  Since this
fairness isn't coupled to the type of paging system, I don't think it's
relevant here.  It is interesting as well though, and we need to think about
it, so perhaps we should start a new thread.  However, first you have to agree
that these are indeed different questions (or convince me that they aren't ;-)
).

> I have trouble understanding how the fairness issue can be handled
> separately from the self-paging issues your solving (other than by not
> solving it).  Suppose a process is slow to the punch and hasn't grabbed
> itself a very large quota before memory pressure sets in.  Then as it's
> addressing new parts of its virtual address space it must page out its own
> pages rather than win pages from other processes as might happen with global
> paging (at least until the slow release part kicks in enough that more
> physical pages are freed up), right?

Right.  But this slowness shouldn't more than a few seconds, otherwise the
performance will be unacceptable.

> If it happens that this process didn't build up enough of an allocation for
> its effective working set before memory pressure happened it could find
> itself thrashing while other processes are fat and happy.

Yes, but only for a short time.  This is the cost of narrowing the covert
channel.  If we think that cost is too high, then we should not use my
proposed system.  I think the cost is acceptable, especially because it is
only relevant when the system is actively swapping, which isn't the usual
situation most of the time.

> Looked at another way, it seems like the memory pressure
> situation can be brought about from other processes being greedy or making
> bad estimates of how large their ideal working set should be in a way that
> wouldn't happen with a global pager.

Why wouldn't that happen with a global pager?  Note by the way, that in my
proposal there _is_ a global pager.  This global pager decides on the physical
memory quota for all processes.  It has some built-in slowness because of the
covert channel.  The self-paging part is just that applications say which
pages they want in memory, not how many.

> To make things more fair, something external to what you've described would
> either have to give out quota increases in a way where processes converge to
> the memory pressure scenario in a more egalitarian way

Right.  This is the global pager.  I wasn't very explicit about its existence
so far, sorry.

> or it would have to intervene after memory pressure had already happened.

Indeed it would, because of the covert channel.  If it would work instantly,
the channel would be wide open.

> Could either of those approaches be done in a way that wouldn't introduce
> the covert channel you wanted to avoid?

No.  If you want to avoid the covert channel, the physical memory quota must
be static.  This is not acceptable for the system we have in mind.  All we can
do is narrow the bandwidth.  This can be done by making the responses less
instantly (which is what I propose) and by adding extra noise (randomly
decreasing some quota every now and then).  All this will never close the
channel completely though.

> I guess I'm dwelling on this fairness issue, but it seems as if dealing with
> it separately might re-open whatever covert channels you'd closed.

I don't think so.  The covert channel is a matter of knowing that some other
process wants more memory (or less).  The harder it is to know this, the less
bandwidth there is.  Instant notifications obviously make it very easy, so we
want to avoid them.  That's what my proposal is about.

Fairness on the other hand is about distributing the quotas.  If changes which
are fair are instantly active or not does not matter much for the answer to
that question.  Fairness just means that the ratio of the quota will be
correct (with respect to priorities) when two processes compete for memory.
In my proposal, during changes, the ratio isn't correct.  It only converges to
the correct value.  During those changes, the ones who were there first have
the advantage.  While strictly speaking this may be considered unfair, I think
it is quite acceptable.  Other than that, the fairness question is separate
from the paging mechanisms I think (conceptually, obviously the implementation
will be close together or even combined).

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