l4-hurd
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: EROS/Coyotos fault handers vs l4 pager hierarchy


From: Marcus Brinkmann
Subject: Re: EROS/Coyotos fault handers vs l4 pager hierarchy
Date: Sat, 22 Oct 2005 12:39:12 +0200
User-agent: Wanderlust/2.14.0 (Africa) SEMI/1.14.6 (Maruoka) FLIM/1.14.7 (Sanjō) APEL/10.6 Emacs/21.4 (i386-pc-linux-gnu) MULE/5.0 (SAKAKI)

At Fri, 21 Oct 2005 09:43:38 -0400,
"Jonathan S. Shapiro" <address@hidden> wrote:
> I believe that the following is a counter-example:
> 
> Let A and B be communicating parties, A' and B' their respective pagers,
> and SPG the pager that is responsible for system-wide swap-paging.
> 
> A maps a region to B.
> 
> In order to evict an LRU page, SPG unmaps a page that exists within this
> shared region.
> 
> If B later needs to access this page, it must either (a) communicate
> with A', which will communicate with SPG, at the time of the re-load, or
> (b) make other arrangements at the time the mapping is established so
> that B' can communicate with SPG directly.
> 
> In either case, you cannot have a system that never invokes your pager.

That's not a bad counter-example.  Except that in the Hurd/L4 design,
swapping is voluntary and explicit.  However, we still have a good
counter-example in the Hurd/L4 design, that is very similar: Physmem
needs the right to revoke arbitrary fpages "temporarily" to reorganize
memory to make space for superpages.  Clearly, this has the same
effect on recursive mappings as you describe above.

> Our belief -- and this is not yet validated -- is that LRU is not really
> the problem in most cases. The real problem is that LRU is usually
> applied to the wrong set of pages. What is needed is a first-class
> notion of working set so that an application can say "this group of
> pages should only compete with itself". This does not solve the problem
> entirely, because there still exist things like LISP systems where the
> "old space" access pattern does not interact well with LRU policy. Given
> a working set mechanism, the two policies that seem to make sense to
> implement are LRU and random replacement. Possibly there are others.
> These are the two that I have seen used effectively in practice.

What about "toss immediately"?  Seems to be useful for databases,
streaming applications, etc.  If "toss immediately" is the best
strategy, LRU becomes the worst.  Don't know about random replacement.
 
> An additional, straightforward mechanism is an *advisory* mechanism that
> allows an application to say to the kernel "I am done with this page."
> This is straightforward to do, but not currently implemented.
> 
> The one thing that is very tricky is to set up a protocol where the
> kernel says "I need to replace a page, tell me which one to remove." I
> believe that I can see how this might be done safely by introducing the
> notion of a working set fault and an appropriate fault handler, and it
> is something that Anshumal Sinha tried to look at at one point, but we
> did not come to a comprehensive design for the fault handler
> interaction.

Sounds interesting.  I am looking forward to discuss this in more
detail (and I am sure Neal is as well).

Thanks,
Marcus





reply via email to

[Prev in Thread] Current Thread [Next in Thread]