[9fans] Virtual memory & paging
Andrew Simmons
and paging were quite distinct, whereas I'd always vaguely assumed they
were the same thing. Could some one explain the difference to me, or point
me in the direction of enlightenment? The issue came up in a friend's job
interview recently, and he wrongly assumed the same as me.
Thanks
andrey mirtchovski
hmm.. i just found the relevant textbook -- Operating Systems Concepts, 5th ed, (Silberschatz, Galvin) page 291
rob pike
virtual memory is a technique an operating system can use to manage
user memory, while paging is a technique for coping with a shortfall
in physical memory. VM manages memory by using page faults to fill in
the user address space; paging is just swapping a page at a time. The
relationship between these notions is primarily that both permit the
process to execute when it is not entirely resident.
By these definitions, it is possible (easy even) to build a system
with virtual memory but no paging. Even I can do it.
-rob
pres...@closedmind.org
exactly as it seems to an executing program, i.e., that
there exists some mapping between addresses as seen by the
execution unit and those on the bus to physical memory.
The mapping can happen a number of ways. The two more
popular are via paging hardware or segmentation hardware.
Pages are typically fixed size and segments variable size.
From the PDP-11 to the MIPS there have been enough flavors
that the distinction is a bit blurred.
If one is willing to move data between a backing store and
main memory in addition to chaging the mappings, one can
make the main memory appear larger than it really is. This
is usually termed demand paging or demand segmentation.
An earlier technique, still in use in addition to demand paging/
segmentation is swapping. If many processes are running on
a particular system, it may desirable to swap in main memory
one for another to give the illusion of a main memory that can
hold all of them.
And of course there is the even earlier technique of overlays.
Here one figures out the execution tree of routines in a
program. One might note that routine A will never be an
ancestor of routine B or vice versa. THerefore, there's no
requirement that they live in memory simultaneously and can
occupy the same memory locations, just at different times.
Andrew Simmons
>Virtual memory covers any memory that isn't laid out
>exactly as it seems to an executing program, i.e., that
>there exists some mapping between addresses as seen by the
>execution unit and those on the bus to physical memory.
>
physical memory, what would be the advantage of anything other than a one
to one mapping of execution unit and physical addresses?
>And of course there is the even earlier technique of overlays.
I wish you hadn't mentioned those. I'd almost managed to forget about them.
ge...@collyer.net
space, an obvious advantage to mapping addresses is to permit programs
linked to start at a fixed address (usually the second page of the
address space) to be run without first running a loading pass to
relocate all the addresses in the entire program.
In addition, memory management units normally provide varying forms of
protection for pages (e.g., instructions are usually made read- or
execute-only) and checking for out-of-bounds (unmapped) addresses. On
many machines, notably the PC, a read from an address with no
corresponding memory (i.e., out-of-bounds) yields garbage; with memory
management on, many such references can be caught. The MMU can thus
be used to ensure that a program doesn't access data in other programs
(including the kernel) without their consent.
Another potential use of mapping is to avoid copying data by remapping
pages.
I would turn the question around: when would you want a one-to-one
mapping of virtual to physical addresses? There are a few such cases:
if memory serves, the old VAX 750 Plan 9 file server ran with the MMU
off because it runs no user-mode processes and it was found that
running with the MMU off made the machine run much faster.
Andrew Simmons
Richard Uhtenwoldt
> Even if your physical memory were as large as your virtual address
> Another potential use of mapping is to avoid copying data by remapping
> pages.
Plan 9 has no DLLs. It has a C runtime library. I'm sure it's smaller
than the GNU C library, but is there a copy of the libary in every
executable in /bin?
is there a copy of it in every
process's memory or is it shared among all the processses?
if so, is memory mapping how the sharing is effected?
(I know this is undergrad material. Let me know if I should stop
asking elementary questions here.)
ge...@collyer.net
a copy of each library routine called, directly or indirectly, by the
program in question.
Sharing of instructions is done at the granularity of process text
segments, as in V6 or V7 Unix. The text segment of a process that
forks is shared between parent and child by page mapping. Also,
running (via exec) a program multiple times concurrently causes the
(pure) text segment to be shared by page mapping across those
processes. So all copies of rc and on a machine should share a text
segment.
Given that degree of sharing, the low cost of RAM, and the increase in
OS complexity, slowness and insecurity in the implementations of
dynamic libraries that I've seen, I don't see a need for dynamic
libraries. (Remember that the real impetus for adding them to Unix
was X11 and its big and badly-factored libraries, which most of us
aren't blessed with.) My terminal has 115 processes; all but 4 of
them share their text segment with at least one other process, usually
more. 74 of them are instances of rio, Mail, rc, acme, listen,
plumber and samterm. A CPU server has 141 processes; all but 2 share
text. 80 of them are listen, another 21 are rc, exportfs, kfs, dns
and consolefs. A quick sampling suggests that Plan 9 programs are
typically smaller than FreeBSD/386 programs even with shared
libraries. Here are some FreeBSD sizes:
: unix; size /bin/cat /bin/ed /usr/bin/awk /usr/X11/bin/sam
text data bss dec hex filename
54188 4324 9760 68272 10ab0 /bin/cat
122835 8772 81920 213527 34217 /bin/ed
135761 4772 15756 156289 26281 /usr/bin/awk
52525 1412 53448 107385 1a379 /usr/X11/bin/sam
Of those, awk and sam use shared libraries. The corresponding Plan 9
sizes are:
; cd /bin; size cat ed awk sam
15996t + 2208d + 944b = 19148 cat
45964t + 4212d + 41232b = 91408 ed
114731t + 35660d + 12040b = 162431 awk
86574t + 7800d + 66240b = 160614 sam
and the Plan 9 programs cope with Unicode and UTF.
for...@caldo.demon.co.uk
virtual memory is a technique an operating system can use to manage
user memory, while paging is a technique for coping with a shortfall
in physical memory. VM manages memory by using page faults to fill in
it's a distinction that certainly used to be made when teaching operating systems.
Boyd Roberts
> Given that degree of sharing, the low cost of RAM, and the increase in
> OS complexity, slowness and insecurity in the implementations of
> dynamic libraries that I've seen, I don't see a need for dynamic
> libraries.
Neither do I. Didn't the tests show that the implementation of them
on unix actually made things slower and more memory got used, not less?
Virtual memory usually refers to the management of the memory when you
allow more 'memory' to be used than you have physical memory. It always
implies a private virtual address space (unlike those Dragonball based
Palm things).
Hence you could have a private virtual address space but no virtual memory.
This would limit the size of the collection of processes on the machine to
not consume more that the amount of physical memory you had.
Once you have a private virtual address space [essential, except in certain
special cases] you can then manage the physical memory in any way you like.
Boyd Roberts
> Given that degree of sharing, the low cost of RAM, and the increase in
> OS complexity, slowness and insecurity in the implementations of
> dynamic libraries that I've seen, I don't see a need for dynamic
> libraries.
Oh, if it comes to DLLs, those things are 'orrible; every 'process'
shares the DLL's data segment. That's one reason why it is impossible
to write a correct windows program.
Ronald G Minnich
> Thanks for that - it was a dumb question.
actually not a dumb question I think. There have been supercomputers with
no VM hardware that were built, and the OS on these remapped (relinked)
executables at program load time, so as to avoid the overhead that you get
with VM (basically a bunch of logic in the address path). So in essence
the start address in your code and the address of your data would be
unique for each execution of your program.
Some of the more fancy ones wrapped base and bounds registers around each
program, and that was as far as protection went.
ron
Andrew Simmons
>to write a correct windows program.
>
bright.
Could anyone recommend a good book to help me remedy my profound ignorance
of these matters? I'm looking for a conceptual overview, nothing too heavy,
rather than something that will actually teach me how to write an OS.
Andrey mentioned Silberschatz & Galvin - would that fit the bill?
sk...@real.com
>
>By these definitions, it is possible (easy even) to build a system
>with virtual memory but no paging. Even I can do it.
>
>-rob
I have an amateur question: how would that work? would the compilers
need to cooperate for this to work? How would something like a stray
pointer be handled?
I'm not sure if "no paging" means no hardware memory management of
any kind.
Ronald G Minnich
>
> >
> >By these definitions, it is possible (easy even) to build a system
> >with virtual memory but no paging. Even I can do it.
> >
> >-rob
>
> I have an amateur question: how would that work? would the compilers
> need to cooperate for this to work? How would something like a stray
> pointer be handled?
see any old burroughs stack machine. Or the i286. Compilers do not
necessarily need to cooperate.
> I'm not sure if "no paging" means no hardware memory management of
> any kind.
no, it just means no paging :-)
ron
sk...@real.com
>
>see any old burroughs stack machine. Or the i286. Compilers do not
>necessarily need to cooperate.
Do you mean systems that had hardware like this memory bank switch:
http://home.swipnet.se/~w-68269/z80_mmu.pdf
>> I'm not sure if "no paging" means no hardware memory management of
>> any kind.
>
>no, it just means no paging :-)
>
>ron
I was confusing no-paging with no-hardware-mmu.
P.S. Would you believe that there is a memorymanagement.org, dedicated
to the subject?
Thomas Bushnell, BSG
> Given that degree of sharing, the low cost of RAM, and the increase in
> OS complexity, slowness and insecurity in the implementations of
> dynamic libraries that I've seen, I don't see a need for dynamic
> libraries.
Well, this sounds a little like "it's inherently buggy", which is
false. If you don't trust yourself to write a shared library
implementation correctly, then say so, but I think the Plan 9 authors
are certainly capable of writing one that works right.
There may be other reason to not want them--as I'm sure the Plan 9
authors have chosen. However, "we can't write an implementation
without bugs" is not a good reason.
Fco.J.Ballesteros
ge...@collyer.net
merely that the existing implementations I'm familiar with have
made the system slower (e.g., adding shared libraries in SunOS 4.0
hugely slowed down the fork system call of even the smallest possible process),
added complexity to the system and for the users (more kernel code,
two sets of libraries [shared and unshared], static vs. dynamic link
decisions, run-time loader paths, extra process start-up processing),
usually coped poorly with set-id programs, and the extra complexity made
the system more fragile in single-user mode (you need all the right
shared libraries on the root filesystem) and when manipulating libraries
generally. So I don't believe I've seen an existence proof that shared
libraries can do more good than harm; maybe they can, but given the
evidence to date, I'm skeptical. And given that we (outside the Labs anyway)
don't have the problem that made people add shared libraries to Unix, X,
and that our binaries are at least competitive in size with systems that do
have shared libraries, and that one can just add RAM cheaply to avoid swapping
anyway, why bother? Adding unneeded goo like shared libraries to a system
just makes it bigger, at minimum. Depending upon the quality of the implementation,
it may also make it slower, more complex and fragile, and create new security holes.
Such a deal.
Boyd Roberts
> Another reason of course is that we Windows programmers are simply not very
> bright.
There is that, but the environment is so hostile it really is hard.
> Could anyone recommend a good book to help me remedy my profound ignorance
> of these matters? I'm looking for a conceptual overview, nothing too heavy,
> rather than something that will actually teach me how to write an OS.
> Andrey mentioned Silberschatz & Galvin - would that fit the bill?
When I were a lad, we used this:
Fundamentals of Operating Systems
By A. Lister
Hardcover
161 Pages
Edition: 3rd ed
Published by Springer-Verlag New York, Incorporated
Date Published: 09/1985
ISBN: 0387912517
At 161 pages it makes it a 'readable' size. The rest I picked up 'the hard way'
(tm) or from brucee or maltby.
Boyd Roberts
> Such a deal.
Yeah, just put truss/strace on any shared libary binary. I assume
that all those mmap()s are to map the libraries in and each one of
those is a _system call_, plus all the stat/open's to find them.
It's a lot quicker (and simpler) in the kernel to get exec to do
the necessary.
david presotto
add DLL support without major bugs. It adds a lot
of complexity that spans the VM model, security,
and compilers. A lot of Plan 9's speed and usefulness
arises from its simplicity and this would be a major step in
away from that, not that we haven't been whores
before.
A major drawback right now is that, unless we change
our MMU handling in a drastic way,
we have to run the shared library at the same addresses
in all programs. Might be a bit of a problem (unless we
go to 64 bit addressing). The current MMU
model with its lazy evaluation and no need for a
intermachine shootdown is quite elegant and I'm not sanguine
to lose it just for DLL's.
As Geoff states, we don't seem to be losing out by not
having them, vis a vis memory size. Some things would
be more efficiently done with a shared library, shared
databases for example. I'm just not yet prepared to
pay the price in increased complexity. Others may be.
Ronald G Minnich
> >see any old burroughs stack machine. Or the i286. Compilers do not
> >necessarily need to cooperate.
>
> Do you mean systems that had hardware like this memory bank switch:
>
> http://home.swipnet.se/~w-68269/z80_mmu.pdf
actually just about everybody did that one with the z80. Lots of
companies (HP, TI, etc.) used z80s in embedded service, and ca. 1981 began
to put in bank-switch schemes.
And no, the burroughs did not work like that at all.
ron
Ronald G Minnich
> > Given that degree of sharing, the low cost of RAM, and the increase in
> > OS complexity, slowness and insecurity in the implementations of
> > dynamic libraries that I've seen, I don't see a need for dynamic
> > libraries.
and in the worst case you'll end up where GNU is now, with symbol
versioning, 21 different versions of opendir in glibc, and so on an so on.
Watching a simple 'ls' do hundreds of symbol fixups is really
enlightening. Especially when so many of them are for the same symbol with
slight variations on the name. My simple, formerly working, libc-based
private name spaces are still totally hosed due to this nonsense.
ron
Richard Maxwell Underwood
which drawer has the soap and whether a constructor has to be declared
in a private or public section of an object definition. I detest
software designs that have special cases or exceptions. I'm always
cursing Microsoft -- they seem to design all their software by random
accretion of features.
What's particularly odd to me is the pride some people take in their
mastery of clutter. It's especially true of techies -- they love to
indulge in the memorization of mountains of meaningless minutiae.
Indeed, I suspect that the pride they take in this pap influences the
design: software tools are most successful when they create a
priesthood knowledgeable in the arcane incantations required.
Perhaps this is all for the best -- after all, society can't afford a
high ratio of geniuses to grunts. Perhaps society has come up with the
perfect means of profitably employing those moiling masses of mental
midgets. They're not dullards -- they're specialists! They may not
understand much, but they certainly have gotten all the details of
c++, HTML, Java, perl, Windows 95, or JCL down pat. So I don't want to
be too hard on the mentality. But you must ask yourself where you fit
into the grand scheme of things. Are you one of those moiling mental
midgets, or do you seek grander things for yourself?
The truth is simple and obvious: you can only think clearly when you
purge your mind of clutter. Any real-world decision is impinged upon
by milliards of factors, but turns on only a few. The ability to slice
through all the secondary factors and zero in on the crucial ones is
central to good decision-making.
--
Richard Maxwell Underwood
The Internet Is Missing! http://www.satn.org/about/missinginternet.htm
Richard Maxwell Underwood
Anyways.
What I just posted is an excerpt from
http://www.erasmatazz.com/library/Mind/How_to_Think_Uncluttering.html
At first it seems offtopic, till you realize that software
preferences often mirror cognitive styles. What is important about
Plan 9, IMO, is not how the software differs from other software, but
rather how people who prefer Plan 9 differ from people who prefer,
eg, Linux or Perl.
The quote I just posted was written by someone with a BS and MS in
physics. Physics definitely has that property that the people who
do it well are the ones who have a habit of searching for the handful of
important facts among the milliards.