Re: Resource Revocation

[olafBuddenhagen]

Hi,

On Thu, Aug 09, 2007 at 06:06:38PM +0200, Neal H. Walfield wrote:
> At Thu, 2 Aug 2007 20:22:00 +0200, <address@hidden> wrote:

> > Last year you proposed a design where a global pager would evict
> > pages when the number of pages available to a task is reduced due to
> > memory pressure; but otherwise tasks have full control over paging
> > by deciding what happens on a page fault. This looked like a quite
> > promising compromise: Avoiding the problems of explicit revocation,
> > but still leaving very much flexibility.
> 
> I don't remember this proposition and the details are unfortunately
> not clear enough that I completely understand how this mechanism is
> supposed to function.

Well, that was my reading of the mechanism proposed in the "access
decomposition and resource management" paper: The task can hook into the
page fault hander, so it can gain full control on how space for the new
page is created, instead of leaving the decision to the replacement
policy of the central pager... Maybe I misunderstood it.

> > What I'm saying is that I agree that swapping or discarding are
> > probably the only useful actions. I'm not sure how much a global
> > paging mechanism is limiting possible policies, though...
> 
> Yeah, that's the hypothesis I also reached.  It led to the following
> approach: design for the problems that you know about, and certainly
> not the ones that you can't imagine.

One of the mantras of "extreme prgramming" is "You ain't gonna need it."
I find that very useful most of the time: It means that one should never
make the design of the code more sophisticated than strictly necessary,
thinking of some anticipated later use -- because when you do this, it
invariably turns out that what is really required is different from what
was anticipated, thus the extra measures for the anticipated use are
just wasted effort. Beter just adapt the design once the additional
requirements are actually there.

However, this assumes that it's easy to change things later. Sometimes,
external constrains forbid that: Code in the operating system can't be
easily adapted the moment new needs emerge; users and applications are
bound by it. Thus, the Hurd tries to keep things as flexible as
possible, to allow for a wide range of custom designs; I'd say this is
one of the design principles. Whenever a design is chosen that limits
customisation possibilities, this is a compromise, which has to be
considered very carefully.

In this particular case, I'm not much worried about limiting the actions
of the cental pager to "evict" and "discard", as other variants seem
very unlikely. (Though still I'd prefer keeping the option to do
self-paging for possible special cases...) What bothers me though, is
that the choice of feasible eviction policies might be limited by the
ranking mechanism.

One example: Let's say we want to assign static priorities to some
special pages, and use LRU for the rest. Even this relatively simple and
certainly desirable policy is quite problematic. LRU requires that the
ranking of unused pages constantly drops. Manually updating all the
rankings for this probably would be way too expensive. I think the only
feasible way to implement it is to have a monotonically rising counter
to update the priorities of pages that are accessed. The relative
ranking of unused pages will fall behind after some time this way.

However, now there is a problem with the pages having static priority:
To prevent these from falling behind also, their rankings would have to
be updated all the time... I can't think of any other solution than
using two kinds of ranking mechanisms for that.

Another case to consider are two distinct LRU sets. (Haven't thought
about the implications of that...) In general, there is a danger that
other cases might also require special variants of the ranking
mechanism; I'm not sure it is possible to come up with something generic
enough to cover all cases. A pager with only a fixed set of ranking
mechanisms could easily turn out limiting here...

-antrik-