[9fans] Virtual memory in BSD and Plan9

[9fans] Virtual memory in BSD and Plan9

[Wladimir Mutel]

	Hello,

	Could you please recommend me a reading on both architectures to
	understand differences between them. I read here that BSD paging has
	some drawbacks to AT&T one (used in Plan9). And I want to make this
	clear for myself.

	Thank you in advance for your advises.

Re: [9fans] Virtual memory in BSD and Plan9

[Russ Cox]

	Could you please recommend me a reading on both architectures to
	understand differences between them. I read here that BSD paging has
	some drawbacks to AT&T one (used in Plan9). And I want to make this
	clear for myself.

The discussions here were talking about many-years-old
systems.  I don't think anyone even mentioned Plan 9's VM system,
which is just about the simplest thing you could imagine.
The BSDs have oodles more ``features.''  I'd look in
www.researchindex.com for the latest stuff, and in McKusick et al.
(Design and Implementation of the 4.4BSD OS) for older stuff.
You can decide for yourself whether Plan 9 needs any of it.

Russ

Re: [9fans] Virtual memory in BSD and Plan9

[William Josephson]

On Thu, Oct 25, 2001 at 01:55:25PM -0400, Russ Cox wrote:
> The discussions here were talking about many-years-old
> systems.  I don't think anyone even mentioned Plan 9's VM system,
> which is just about the simplest thing you could imagine.
> The BSDs have oodles more ``features.''  I'd look in
> www.researchindex.com for the latest stuff, and in McKusick et al.
> (Design and Implementation of the 4.4BSD OS) for older stuff.
> You can decide for yourself whether Plan 9 needs any of it.

You probably want to take a look at Charles Cranor's PHd thesis from
Washington on UVM.  If I recall correctly, some of the *BSDs (NetBSD,
FreeBSD?) have picked it up or at least borrowed ideas.

 -WJ

Re: [9fans] Virtual memory in BSD and Plan9

[John S. Dyson]

wkj-despam@eecs.harvard.edu (William Josephson) wrote in message news:<20011025142927.B8085@honk.eecs.harvard.edu>...
> On Thu, Oct 25, 2001 at 01:55:25PM -0400, Russ Cox wrote:
> > The discussions here were talking about many-years-old
> > systems.  I don't think anyone even mentioned Plan 9's VM system,
> > which is just about the simplest thing you could imagine.
> > The BSDs have oodles more ``features.''  I'd look in
> > www.researchindex.com for the latest stuff, and in McKusick et al.
> > (Design and Implementation of the 4.4BSD OS) for older stuff.
> > You can decide for yourself whether Plan 9 needs any of it.
> 
> You probably want to take a look at Charles Cranor's PHd thesis from
> Washington on UVM.  If I recall correctly, some of the *BSDs (NetBSD,
> FreeBSD?) have picked it up or at least borrowed ideas.
> 
FreeBSD and NetBSD have different VM systems.  FreeBSD's (which I
am the primary implementer), is really a corrected and filled out
MACH VM for UNIX.  It provides lots of the necessary shortcuts
fully virtualized for the process VM forking and things like that.
The original MACH VM port really wasn't meant as being production
ready (per my discussions with Hibler), but was more of a feasibility
exercise.  Even though it wasn't fully made robust in the original
implementations, it wasn't that much worse than many commercial UNIX
VM behaviors.

Probably the biggest difference doesn't occur during 'normal'
memory resident situations, but where FreeBSD has rather advanced
paging stats, and really does put off the thrashfest until the
system doesn't have enough pages to supply an adequate resident
working set.  If there is minimally enough memory, FreeBSD will
converge reasonably quickly, without undue thrashing.  In my early
experiments, it was very satisfying to hear the system 'calm down'
after experiencing thrashing due to a necessary change in working
set population.  Most other systems tended to keep on thrashing
for long periods, even when there was obviously enough memory.  The
pseudo-random pagouts and invalidations from non-FreeBSD systems
tended to really screw up the page reference information on memory
segments being used by otherwise runnable processes.   The relatively
good behavior has been especially useful when running user-mode
windowing systems, where the blocking from poorly chosen page
invalidations can really stop-up the works.

Both FreeBSD's VM and NetBSD's VM work pretty well (no real complaints
from either party), and most/all of the limitations of the original
MACH VM have been expunged.  There were even cases of limitations
that I thought to be unsolvable in the FreeBSD code eventually simply
be an 'exercise in data structures', and the last REAL limitation
due to address space/fork inheritance was remedied as a result of
competition from NetBSD's new VM stuff.

FreeBSDs and NetBSDs code is both adequately portable, and that
should not be a deciding issue.  Frankly, the most important deciding
issue is probably based upon knowledge of the VM code that the
individual who might do the port to Plan 9.  One might make a
'decision' that the VM shouldn't page anyway (except in odd situations),
and so the relative advantages of the two systems becomes less
important.

My philosophy is based upon the fact that an OS MUST NOT just be a fair
weather friend, and from my rather VM-centered viewpoint, I believe that
this includes the fact that VM shouldn't randomly thrash, when it could
more actively converge to a reasonable working set (when possible.)

If starting from scratch, it is really easy to write some code that
works.   However, there is ALOT more work to making a VM system
function under load to maximize availability of CPU cycles.  Unfortunately,
it is clear that VM system behavior is almost always a secondary
priority, because it doesn't specify/benchmark very easily.

John

Re: [9fans] Virtual memory in BSD and Plan9

[rob pike]

I'm a radical here, but I think if a machine is paging, you've lost.
To me, VM is a pretty technique for memory management in the kernel,
something distinct from paging, which is a way to get the system
through temprorary overshoots in memory demand.

My boss when the first Plan 9 kernel was being written was Sandy
Fraser, who had worked on Atlas, one of the first VM systems.  When he
heard that I was putting VM into Plan 9 (a situation more accurately
described as building Plan 9's original memory manager around a VM
model), he literally called me on the carpet.  He said that he hated
VM bitterly because of the Atlas days, in which nothing got done
because the system was always thrashing.  I pointed out the
distinction between VM and paging, explained that I was implementing
VM but not paging (Phil W. put paging in a few years later), and
justified my decision by pointing out that with memory so cheap today,
there was really no reason to depend on the paging system to manage
your working set except for the occasional brief overrun on demand.

-rob

Re: [9fans] Virtual memory in BSD and Plan9

[Borja Marcos]

On Monday 29 October 2001 13:38, you wrote:
> I'm a radical here, but I think if a machine is paging, you've lost.
> To me, VM is a pretty technique for memory management in the kernel,
> something distinct from paging, which is a way to get the system
> through temprorary overshoots in memory demand.

	That's right. Virtual memory avoids, for example, the memory fragmentation 
problem. Memory is divided into fixed-size pages, and the address space of a 
process doesn't need to be contiguous. Processes see a "logical" address 
space which is translated to physical addresses by the MMU.

	So, virtual memory is in my opinion a very good thing.

	Regarding paging, it depends on *how* much does it page. I don't mind if my 
machine has to page sometimes. There are rules of thumb that specify a degree 
of "acceptable badness". ;-)




	Borja.

Re: [9fans] Virtual memory in BSD and Plan9

[Douglas A. Gwyn]

rob pike wrote:
> I'm a radical here, but I think if a machine is paging, you've lost.
> To me, VM is a pretty technique for memory management in the kernel,
> something distinct from paging, which is a way to get the system
> through temprorary overshoots in memory demand.

Seems to me that computing has evolved toward a "caching" model.
E.g. a register set operating on a multilevel RAM cache, which
is a window into the RAM, which may be the window into a large
(memory-mapped) file, which may be a cached portion of some huge
database on the other end of a network connection.  Something
like "paging" (cache remapping) is needed or else a task would
be confined to a very narrow window forever..

Re: [9fans] Virtual memory in BSD and Plan9

[John S. Dyson]

rob@plan9.bell-labs.com (rob pike) wrote in message news:<20011029123819.DCCD7199E4@mail.cse.psu.edu>...
> I'm a radical here, but I think if a machine is paging, you've lost.
> To me, VM is a pretty technique for memory management in the kernel,
> something distinct from paging, which is a way to get the system
> through temprorary overshoots in memory demand.
> 
In these days of 'inexpensive memory', I tend to agree with you, BUT:
VM is also a good tool to push out long unused pages so that they can
also be used for caching and other helpful purposes.   This is akin to
the 'temporary overshoot' issue, but slightly more active.

I have noticed in alot of cases, that such 'temporary overshoots' still
cause systems to thrash too much, trying to find the correct working
sets.  Some of the VM work in FreeBSD (not necessarily the whole package),
does alot of work to avoid the thrashing.

A system that is continually paging, even if the VM mgmt is really good,
will often not be a very friendly acting system.  The key to the VM
code is to make sure that in reasonable cases, the system isn't continually
paging.   Finding the reasonable working sets in a global sense (local
sense only causes less efficient behavior), so that paging activity is
minimized or converges to nil.

It is easy to define a 'finding' that the system will never actively
page, and assume that a system with 'insufficient' memory isn't well
configured.  This is a valid 'finding', but certainly can make the OS
VM less robust in a performance sense.   This is not necessarily a terrible
thing.

John

Re: [9fans] Virtual memory in BSD and Plan9

[Boyd Roberts]

A Virtual Address Space != Paging.  The former is essential,
the later is an implementation detail.

Re: [9fans] Virtual memory in BSD and Plan9

[Thomas Bushnell, BSG]

boyd@fr.inter.net (Boyd Roberts) writes:

> A Virtual Address Space != Paging.  The former is essential,
> the later is an implementation detail.

The latter (sp!) is essential for other purposes too.

My principle system is a computer with 256 MB of RAM and about 60 GB
of disk.  If I want to do a computation that requires more than 256 MB
of memory, then I'm pretty happy that my system is able to go and use
some of that disk to be able to complete the computation.

Now, it's ludicrous to me that my system forces me to decide ahead of
time which space is for "files" and which is for "backing
store"--these are all simply data objects--but that's a defect caused
by the conventional notion of "filesystem".  That diatribe for another
day.

Re: [9fans] Virtual memory in BSD and Plan9

[Ozan Yigit]

talking about VM, here is an interesting piece on the politics and
technology of linux VM. appearently there is a "simpler and faster"
[quotes for conceptual relativism :-] version...

http://www.byte.com/documents/s=1436/byt20011024s0002/1029_moshe.html

[i wish some of this hacker energy could be directed to plan9 projects]

oz
-- 
www.cs.yorku.ca/~oz	 | if you couldn't find any weirdness, maybe
york u. computer science | we'll just have to make some!   -- hobbes

Re: [9fans] Virtual memory in BSD and Plan9

[John S. Dyson]

Ozan Yigit <oz@blue.cs.yorku.ca> wrote in message news:<vi4itcxxj8q.fsf@blue.cs.yorku.ca>...
> talking about VM, here is an interesting piece on the politics and
> technology of linux VM. appearently there is a "simpler and faster"
> [quotes for conceptual relativism :-] version...
> 
> http://www.byte.com/documents/s=1436/byt20011024s0002/1029_moshe.html
> 
> [i wish some of this hacker energy could be directed to plan9 projects]
> 
Actually, doing the VM code 'correctly' only takes a little more work than
to do it at all.  Some of the advanced Linux VM code was a result of
discussions between Matt Dillon (the guy that took over my code on
FreeBSD) and the Linux developers.  The basic concept of the various
page queues actually was an evolution from the original MACH code.

One key to the 'better' page selection is to be able to find out the
pages that are often used recently, so that they won't be thrown
away in a flurry of paging activity.  To make the VM work well, there
has to be some resistance against throwing out the first page that
seems not to have been used during the most recent scan of free
pages, but to delve deeper into recent and not so recent usage.

The pageout daemon can only do so much, with it's limited knowledge
of recent activity, and too much page invalidation (and dissociation
with previous mappings) will only cause thrashing, and will NOT
improve overall system behavior.

Another mistake often made is the potential impulse change in buffer
cache size, and the subsequent destabilization of the balance of page
usage.   Think of the VM and buffer cache tension as a feedback and
control system -- if you change things too much too quickly, even a
relatively 'stable' situation will become unstable often due to hitting
limits (both rate limits and absolute limits.)   The work on FreeBSD
was meant to avoid errant behavior under changing loads, and is one
reason why it APPEARS to be self-tuning.   In fact, it really isn't
as self-tuning, but simply tries to function as one would intuitively
expect.  FreeBSD seldom really needed to be 'tuned' as expected,
and the system would mostly compensate for meddling tuning attempts,
as any stable 'feedback' system would behave.   Really useful tunables
included changing the paging queue lengths when more I/O devices
could be interleaved, or changing the size of the page queues based
upon memory size.

In all VM paging systems (those that allow for pageouts), mistakes
are made with respect to desirable pages being removed from working
sets.  The 2nd chance type algorithms (which it appears that Linux has
picked up), really help also.   In a way, one might think of this as
a 2nd level of paging, where there isn't really much work done, and
paging mistakes can be corrected.   I found that 2nd chance helped,
but didn't do as well as I had hoped, so other 2nd chance type mechanisms
were added so as to hide pageout choice mistakes.

One of the simplest changes that I made to the MACH VM, and is very
obvious, and wouldn't really be applicable to most sane VM designs:
a kind of free page queue was added that allowed the page to continue
to contain data.   This page queue was the first consulted during userland
memory needs, but maximized and buffered the availability of pages without
impact on memory usage efficiency.   Most (good) VM systems already
have this facility, but was something that marginally helped FreeBSD.

Frankly, with today's memory costs, and a definition that a machine
MUST contain enough memory, alot of effort need not be made in the
choice of pages to invalidate.   However, it doesn't take alot of effort
to make 'good choices.'   Unfortunately, I HATE to write long papers,
and even my earlier notes on the VM code terminology, and Matt Dillon's
cursory explaination of the code still don't get into the meat of
the subtle nature of the code.   When Matt first started wanting
to 'improve' the code, after I left, I had to seriously petition that
he not make any changes until he could benchmark and quantify the changes.
After that was successful, he tended to agree with my position that
it works 'especially well.'   There is some 'junk' in the code that
isn't magic to me, but looks like 'magic' on initial inspection.

ANYONE who is interested in specific ideas for VM paging code
(and VM code in general) is welcome to contact me (without prejudice.)
I don't really think that it is necessary to do things in the way
that I did the FreeBSD stuff, but there are concepts that are fairly
universal that often seem to be discounted.

I'd like to see 'cool' alternatives like Plan 9 make progress into
the marketplace, and all of the geek-talk that I might spew, along
with the REAL Plan 9 experts who really do know what they are
talking about WRT that OS, technical excellence isn't sufficient (or
even the primary predictor) of success.

I really don't think that the VM code needs to fully hide the size
of available physical memory, because such elite positions only create
polarization.   I do believe that if paging performance under exceptional
loading conditions is a criteria, then UP FRONT consideration for
being able to include design that avoids loop instabilities and
wise page choices would be a responsible position to take.

John

Re: [9fans] Virtual memory in BSD and Plan9

[Douglas A. Gwyn]

One big difference I've seen in past examples of paging systems
can be summarized as: page against everyone vs. page only against
oneself.  The latter is sometimes called the "working set" model.
The former tends to make the whole system unusable when a process
lets its address space get out of control, while the latter tends
to run other processes pretty much the same under such conditions.

Re: [9fans] Virtual memory in BSD and Plan9

[Dan Cross]

In article <3BE038E9.6AC0BD50@null.net> you write:
>One big difference I've seen in past examples of paging systems
>can be summarized as: page against everyone vs. page only against
>oneself.  The latter is sometimes called the "working set" model.
>The former tends to make the whole system unusable when a process
>lets its address space get out of control, while the latter tends
>to run other processes pretty much the same under such conditions.

Forsyth wrote an interesting paper years back called something along
the lines of, ``Sending Unix to the Fat Farm,''  wherein he details his
experience replacing various parts of the SunOS 3 kernel in an effort
to simplify the overall system.

Of particular interest was his replacement of the whole-system paging
scheme inherited from 4BSD with one based on the working set model.
Apparantly, the system performed much more gracefully under load as a
result, in addition to being far simpler and more maintainable.

One of the things that bothers me about the Linux and BSD camps is that
they don't learn from such experiences of the past, and instead forge
ahead with the status quo that they've inherited.  For instance, the
idea that Plan 9 would port one of the BSD paging subsystems is
ridiculous for the same reason that the idea of porting the sockets
subsystem is ridiculous; the system simply doesn't need it, it wouldn't
mesh well with the overall architecture, and possibly better solutions
exist in the literature.  In this specific case, the subtle nuances
that Dyson describes in the FreeBSD paging code are precisely the sort
of thing that Plan 9 does to great lengths to avoid.

Perhaps this could be accurately summed up as, ``what works for one
group of people is not necessarily appropriate for all groups.''


	- Dan C.

Re: [9fans] Virtual memory in BSD and Plan9

[John S. Dyson]

cross@math.psu.edu (Dan Cross) wrote in message news:<200110312021.PAA15416@augusta.math.psu.edu>...
> In article <3BE038E9.6AC0BD50@null.net> you write:
> >One big difference I've seen in past examples of paging systems
> >can be summarized as: page against everyone vs. page only against
> >oneself.  The latter is sometimes called the "working set" model.
> >The former tends to make the whole system unusable when a process
> >lets its address space get out of control, while the latter tends
> >to run other processes pretty much the same under such conditions.
>
> Forsyth wrote an interesting paper years back called something along
> the lines of, ``Sending Unix to the Fat Farm,''  wherein he details his
> experience replacing various parts of the SunOS 3 kernel in an effort
> to simplify the overall system.
>
> Of particular interest was his replacement of the whole-system paging
> scheme inherited from 4BSD with one based on the working set model.
> Apparantly, the system performed much more gracefully under load as a
> result, in addition to being far simpler and more maintainable.
>
> One of the things that bothers me about the Linux and BSD camps is that
> they don't learn from such experiences of the past, and instead forge
> ahead with the status quo that they've inherited.  For instance, the
> idea that Plan 9 would port one of the BSD paging subsystems is
> ridiculous for the same reason that the idea of porting the sockets
> subsystem is ridiculous; the system simply doesn't need it, it wouldn't
> mesh well with the overall architecture, and possibly better solutions
> exist in the literature.  In this specific case, the subtle nuances
> that Dyson describes in the FreeBSD paging code are precisely the sort
> of thing that Plan 9 does to great lengths to avoid.
>
Remember -- it was EXACTLY learning from the past that made the FreeBSD
VM outperform almost everything that exists to date (under load.)   The
old working set concepts are really not very good, because they work
alot like a 'command economy'.   Refer to the FreeBSD stats gathering,
plus the avoidance of resource depletion, plus the avoidance of long
queue lengths (maintains latency performance.)

Really, really -- there is alot to be said about learning from mistakes
in the past, and I holeheartedly agree.   However, the FreeBSD VM is
not just a follow-on to the MACH VM WRT it's behavior.   The incredible
thing about the FreeBSD VM is that it DOES do a good job of avoiding
the problems with the old concepts.

For alot of fun, just play with NT (a working set model VM), and FreeBSD,
and it will be pretty clear that FreeBSD tends to keep it's wits about
it.   There are some caveats in system configuration in order to maintain
performance under the grossest load conditions, and one is that multiple
heads makes a HUGE difference.   This is NOT because of bandwidth issues,
but due head contention.

John

Re: [9fans] Virtual memory in BSD and Plan9

[Thomas Bushnell, BSG]

rob@plan9.bell-labs.com (rob pike) writes:

> I'm a radical here, but I think if a machine is paging, you've lost.

Many times I have been grateful that I could perform a task thanks to
the availability of paging.  Certainly, paging is not a substitute for
having more memory.  But it is reasonable to want it as a technique.

Indeed, once years and years ago we had a horrid intractible kernel
debugging problem on BSD, when I worked for UNM, and we solved the
problem (I kid you not) by firing up emacs on /dev/mem, from which I
was able to find the problem when adb was not helpful.

Obviously, this strategy only worked because the system was able to
page.  If emacs buffers were limited to the size of memory, it would
not be possible to edit /dev/mem.

More prosaically, many times I have had some extensive data set to
operate on in a tool that needed to keep it all in "core", and while
it took much longer with paging than if I had more memory--it would
take forever (literally) if the kernel didn't support paging at all.

Thomas

Re: [9fans] Virtual memory in BSD and Plan9

[bwc]

[-- Attachment #1: Type: text/plain, Size: 219 bytes --]

I sense that this thread is about to enter the `Virtual address space is not
large enough to support the universe' phase.  Can we just insert a token
here and not actually issue the messages? :-)

  Brantley Coile

[-- Attachment #2: Type: message/rfc822, Size: 2137 bytes --]

From: "Douglas A. Gwyn" <DAGwyn@null.net>
To: 9fans@cse.psu.edu
Subject: Re: [9fans] Virtual memory in BSD and Plan9
Date: Tue, 30 Oct 2001 15:22:01 GMT
Message-ID: <3BDDE974.C140716C@null.net>

rob pike wrote:
> I'm a radical here, but I think if a machine is paging, you've lost.
> To me, VM is a pretty technique for memory management in the kernel,
> something distinct from paging, which is a way to get the system
> through temprorary overshoots in memory demand.

Seems to me that computing has evolved toward a "caching" model.
E.g. a register set operating on a multilevel RAM cache, which
is a window into the RAM, which may be the window into a large
(memory-mapped) file, which may be a cached portion of some huge
database on the other end of a network connection.  Something
like "paging" (cache remapping) is needed or else a task would
be confined to a very narrow window forever..

Re: [9fans] Virtual memory in BSD and Plan9

[bwc]

[-- Attachment #1: Type: text/plain, Size: 115 bytes --]

I would think that killing init, as indicated in the referenced web page, would
tend to reduce demand on memory.

[-- Attachment #2: Type: message/rfc822, Size: 1815 bytes --]

From: Ozan Yigit <oz@blue.cs.yorku.ca>
To: 9fans@cse.psu.edu
Subject: Re: [9fans] Virtual memory in BSD and Plan9
Date: Tue, 30 Oct 2001 15:23:10 GMT
Message-ID: <vi4itcxxj8q.fsf@blue.cs.yorku.ca>

talking about VM, here is an interesting piece on the politics and
technology of linux VM. appearently there is a "simpler and faster"
[quotes for conceptual relativism :-] version...

http://www.byte.com/documents/s=1436/byt20011024s0002/1029_moshe.html

[i wish some of this hacker energy could be directed to plan9 projects]

oz
-- 
www.cs.yorku.ca/~oz	 | if you couldn't find any weirdness, maybe
york u. computer science | we'll just have to make some!   -- hobbes

Re: [9fans] Virtual memory in BSD and Plan9

[David Gordon Hogan]

> One big difference I've seen in past examples of paging systems
> can be summarized as: page against everyone vs. page only against
> oneself.  The latter is sometimes called the "working set" model.
> The former tends to make the whole system unusable when a process
> lets its address space get out of control, while the latter tends
> to run other processes pretty much the same under such conditions.

I'm wondering if anyone's ever tried to treat this as a `bandwidth sharing'
issue, and applied techniques like Fair Queueing.

Admittedly it's more complex than a simple bandwidth sharing problem.
There are two resources to share: the page pool and the paging device
IO, and there are interactions between the two.

Re: [9fans] Virtual memory in BSD and Plan9

[Scott Schwartz]

| I'm wondering if anyone's ever tried to treat this as a `bandwidth sharing'
| issue, and applied techniques like Fair Queueing.

Wasn't there a usenix paper by someone at the labs a while back on
something like that?

Re: [9fans] Virtual memory in BSD and Plan9

[forsyth]

>>The old working set concepts are really not very good, because they work
>>alot like a 'command economy'.

what definition of `working set concept' are you using?
could you elaborate?