Better paging algorithm
Michael Veksler
is the scenario:
I am using Linux-1.1.13 for VHDL hardware simulation.
The runtime requirenment is about 11 Mega-Bytes.
My memory is limited (8 Megs of RAM), so I get a lot of page faults.
I have spoted an interesting event:
1) I force modified pages to be written to the swap-partition
(I start emacs and the exit).
2) Then the simulation finishes much faster (actually with higher
CPU percentage report - and less time).
My guess is that this happens because of the following sequence:
1) memory is read - since it is swapped, it has to be brought from swap.
2) there is no free RAM, the missing page can not be brought before
a page is freed.
3) To free a page, a modified page is writted to disk (seek+write)
4) Now the page can be read (seek+read).
This happens all the time, so most of the time is wasted on seeks (one
for write and one for read).
When I load emacs I force all modified pages to be written more rapidly
(I guess) in bigger chuncks - saving extra seek time.
If this is true, can the algorithm for paging be modified ?
I suggest:
when there is no free RAM, modifid pages will be written in big chunks,
saving a lot of time. You can say that this may hurt the avarage
case and improve my, but what about detecting this situation,
and implementing the CHUNK-algorith only then ?
Any sugestions ? comments ?
Michael
Larry McVoy
[ stuff about dirty pages and doing better I/O & paging ]
This problem comes up with every young Unix. The stages that you go
through are
1) it's slow
2) it's mostly the swap vnode that is the problem
3) let's do big i/o on swap
4) let's manage the swap free list intelligently
I went through this the first time with SunOS 4.1. I instrumented the
vnode layer so that all vnodes kept a count of dirty page, clean pages,
last pageout time & offset, last pagein time and offset. I also stuck
the basename of the vnode in the vnode itself (in the case of vnodes
with multiple hard links, it was the last name by which the vnode was
looked up; this was not an issue in practice).
I linked all the vnoes (NFS & UFS & etc) onto a global list. I made
fake vnodes for kernel text, kernel heap (kmem_alloc), the buffer
cache, the free page list, and something else I don't remember. The
point was that you should be able to add up the count of pages in each
vnode and get *exactly* the number of pages your system had - if you
didn't, I either forgot one or the system had lost some (it was always
that I had forgot one :-)
I then made something like top except I called it topvn (top vnodes)
that showed the name of the vnode, the number of pages in use,
reference times, etc, etc. Pretty much like top. It gave you output
something like what is included below (this is 3 years old, I'm a bit
fuzzy on the details).
The interesting thing is that the swap vnode is the big vnode. As
you add the window system, it gets bigger.
The swap vnode contains all the pages for the data segments for all the
processes. All mixed together. For years, I've wanted a data segment
vnode per process but as of yet I haven't figured out how to do that.
The reason I want is is because I believe that you should
a) implement the swap stuff on top of your local file system,
you should not use the raw device. The local file system is
fast enough. Also you can just grab space out of any of them.
b) if there was one vnode per process, then you can trivially
figure out which to keep in and which to keep out.
If someone wants to work on this or talk about, I'm happy to go reconstruct
the hard issues. I think they all revolve around copy on write and sharing
semantics of the data segment.
Here's the topvn snapshot:
Physmem: 4072
Maxmem: 3578
page_freelist_size: 2231
page_cachelist_size: 3
Total: 3227
Freemem: 2234
Mem in vnodes: 993
No. of vnodes: 125
No of vnodes w/ 0 pages: 40
No of vnodes w/ 1 pages: 65
No of vnodes w/ 2 pages: 1
No of vnodes w/ 3 pages: 1
No of vnodes w/ 4 pages: 3
No of vnodes w/ > 4 pages: 15
Name Type Vfs Mem Use GOff POff Gtime Ptime
SWAP BLK NONE 510 16 555 492 24 09:47:45 24 09:47:45
KMEM NON NONE 102 0 0 0 - -
libc.so.1.6 REG UFS 76 27 9 51 23 14:27:52 23 14:27:52
vmunix_small_vn REG UFS 49 49 349 0 24 09:47:45 24 09:47:45
ksh REG UFS 36 -33 38 17 23 15:15:53 23 15:15:53
termcap REG UFS 34 34 33 0 24 09:47:45 24 09:47:45
sh REG UFS 26 0 25 25 23 14:26:57 23 14:26:57
sendmail REG UFS 19 -15 12 24 23 14:27:34 23 14:27:34
automount REG UFS 14 -3 17 5 23 14:27:29 23 14:27:29
t REG NFS 10 2 9 7 23 15:15:11 23 15:15:11
ld.so REG UFS 8 6 9 9 23 14:27:43 23 14:27:43
find REG UFS 8 3 7 0 23 15:13:45 23 15:13:45
init REG UFS 7 -9 1 13 23 14:27:46 23 14:27:46
cron REG UFS 6 -2 1 4 23 14:27:52 23 14:27:52
in.routed REG UFS 6 2 5 6 23 14:27:37 23 14:27:37
inetd REG UFS 4 -2 3 5 23 14:27:26 23 14:27:26
syslogd REG UFS 4 -2 3 3 23 14:27:34 23 14:27:34
portmap REG UFS 4 -2 1 2 23 14:27:39 23 14:27:39
dev DIR UFS 3 2 2 0 24 03:15:18 24 03:15:18
bin DIR UFS 2 2 1 0 24 04:15:00 24 04:15:00
curses DIR UFS 1 1 0 0 24 03:15:23 24 03:15:23
dragon DIR UFS 1 1 0 0 24 03:15:23 24 03:15:23
sunbox DIR UFS 1 1 0 0 24 03:15:23 24 03:15:23
home DIR UFS 1 1 0 0 24 03:15:23 24 03:15:23
export DIR UFS 1 -4 0 0 24 03:15:23 24 03:15:23
crissy DIR UFS 1 0 0 0 24 03:15:23 24 03:15:23
sbox0 DIR UFS 1 1 0 0 24 03:15:22 24 03:15:22
slovax DIR UFS 1 -2 0 0 24 03:15:22 24 03:15:22
net DIR UFS 1 1 0 0 24 03:15:22 24 03:15:22
bin LNK UFS 1 -6 0 0 24 04:15:00 24 04:15:00
group REG UFS 1 1 0 0 24 03:15:23 24 03:15:23
home DIR UFS 1 1 0 0 24 03:15:22 24 03:15:22
export DIR UFS 1 1 0 0 24 03:15:22 24 03:15:22
ahkcus DIR UFS 1 1 0 0 24 03:15:22 24 03:15:22
sunbox0 DIR UFS 1 -8 0 0 24 03:15:22 24 03:15:22
sunbox-gw DIR UFS 1 0 0 0 24 03:15:22 24 03:15:22
slovax DIR UFS 1 1 0 0 24 03:15:22 24 03:15:22
lib DIR UFS 1 1 0 0 24 04:15:00 24 04:15:00
preserve DIR UFS 1 1 0 0 24 03:15:17 24 03:15:17
nfs DIR UFS 1 0 0 0 24 03:15:22 24 03:15:22
sbin DIR UFS 1 -1 0 0 24 03:15:22 24 03:15:22
auto DIR UFS 1 1 0 0 24 03:15:22 24 03:15:22
ucb DIR UFS 1 1 0 0 24 04:15:00 24 04:15:00
tmp_rex DIR UFS 1 1 0 0 24 03:15:22 24 03:15:22
binding DIR UFS 1 -1 0 0 24 03:15:18 24 03:15:18
mnt DIR UFS 1 -3 0 0 24 03:15:18 24 03:15:18
rfs DIR UFS 1 -1 0 0 24 03:15:18 24 03:15:18
servers DIR UFS 1 -4 0 0 24 03:15:18 24 03:15:18
nls DIR UFS 1 -32 0 0 24 03:15:18 24 03:15:18
net DIR UFS 1 1 0 0 24 03:15:18 24 03:15:18
--
---
Larry McVoy (415) 390-1804 l...@sgi.com
Captain Sarcastic
| Recently I switched from a swap file to a swap partition, after adding
| a second disk. This turned out to be a dramatic improvement in swap
| performance: the above program completes it task in a few seconds, instead
| of 20 seconds or so as it was before. This is not related to seeking
| as there is no other disk activity at this time, but apparently the
| swapping to a file is a lot less efficient. I had already noticed that
| the disk is only very lightly loaded when running the program with a
| swapfile on disk (judged by the intensity of the LED on the drive), and
| now it is much better.
| Of course, having the swap on another disk than the root and user filesystem
| has the added benefit that the seek problem you describe no longer occurs.
| You might consider finding a scrapped 40MB drive ('too small to be useful')
| somewhere, add it as a second drive to your system and use it only as
| a swapdisk.
Glad to hear this. I figured this would be the case, so I am in the
process of nabbing a scrapped 150M drive to add just for swap, or maybe
swap + tmp. Glad to hear it. My SCSI card is getting full...
--
Captain Sarcastic <kko...@nyx10.cs.du.edu> NO! Not alt.captain.sarcastic!!!
The first step to a person's heart is to confuse the fuck out of 'em.
Edmund Stephen-Smith
>r...@pe1chl.ampr.org (Rob Janssen) writes:
[...]
>| Of course, having the swap on another disk than the root and user filesystem
>| has the added benefit that the seek problem you describe no longer occurs.
>| You might consider finding a scrapped 40MB drive ('too small to be useful')
>| somewhere, add it as a second drive to your system and use it only as
>| a swapdisk.
>
>Glad to hear this. I figured this would be the case, so I am in the
>process of nabbing a scrapped 150M drive to add just for swap, or maybe
>swap + tmp. Glad to hear it. My SCSI card is getting full...
Maybe -- because swap is memory, it is usually put on the fastest
device. An older drive is usually a slower drive. It's likely to be
better to shift data that's not speed critical to the older drive
(e.g. /var/spool). Though this doesn't solve any excessive seek
problems.
Edmund.
--
Edmund Stephen-Smith work: <step...@solartron.com>
Edmund Stephen-Smith
>| has the added benefit that the seek problem you describe no longer occurs.
>| You might consider finding a scrapped 40MB drive ('too small to be useful')
>| somewhere, add it as a second drive to your system and use it only as
>| a swapdisk.
>
>Glad to hear this. I figured this would be the case, so I am in the
>process of nabbing a scrapped 150M drive to add just for swap, or maybe
>swap + tmp. Glad to hear it. My SCSI card is getting full...
Because swap is memory, it's usually put on the fastest device. An
older drive is usually a slower drive. A better idea is to shift data
Captain Sarcastic
| >| Of course, having the swap on another disk than the root and user filesystem
| >| has the added benefit that the seek problem you describe no longer occurs.
| >| You might consider finding a scrapped 40MB drive ('too small to be useful')
| >| somewhere, add it as a second drive to your system and use it only as
| >| a swapdisk.
| >
| >Glad to hear this. I figured this would be the case, so I am in the
| >process of nabbing a scrapped 150M drive to add just for swap, or maybe
| >swap + tmp. Glad to hear it. My SCSI card is getting full...
| Maybe -- because swap is memory, it is usually put on the fastest
| device. An older drive is usually a slower drive. It's likely to be
| better to shift data that's not speed critical to the older drive
| (e.g. /var/spool). Though this doesn't solve any excessive seek
| problems.
Well, I added the 150M CDC-90161 drive. It is slower than my ST-41600N
that I have everything else on. Yet, by moving my swap to that drive
(first 128M, rest blank...) I noticed (visually) a huge improvement. I
then ran through a number of tests where excessive swapping occurred, and
saw that it was indeed faster. Whereas before things were I/O bound, and
I was 96% idle while waiting for disk, now I use 60-70% of CPU and only
30-40% idle.
I think that's an improvement.
--
Captain Sarcastic <kko...@nyx10.cs.du.edu> NO! Not alt.captain.sarcastic!!!
When the going gets weird, the weird turn pro.
Darin Johnson
> out only what it really needs. The buffer cache normally occupies whatever
> memory is not used for other purposes, and hence gets very small.
Is there a way to test how much is really for buffers only?
I have an 8 meg machine, NOT running an X server, and it swaps very
often. I have few things running, a few X terms (clients to an
x terminal), some ls's, vi's, etc. According to xosview, I have
free memory, but swap space is also being taken up. To me, 8 megs
is the minimum, yet I hear of people running in 4 at times. How?
(Hmm, seems to be "xfs" is taking up most of the memory. It's got
tons of unreadable sources, and is buggy as all get out, but I need
it... Any replacements or fixed versions?)
--
Darin Johnson
djoh...@ucsd.edu
- Luxury! In MY day, we had to make do with 5 bytes of swap...
John A. Byerly
> To me, 8 megs
> is the minimum, yet I hear of people running in 4 at times. How?
V E R Y S L O W L Y
All I want for Christmas is more memory. I am currently running Linux on a 486/50
with 4 MB. Horrible! Emacs takes forever to start up, menus are slow in appearing
and compiles...well!
I recently compiled a new kernel. The README file said to do a "make" and go get
a cup of coffee or something 'cause "it will take about 20 minutes". I went to
bed after about three hours and it was still chunking away. My swap disk LED was
on nearly constantly.
Believe me, you don't want to run Linux with 4MB.
JAB
Daniel Quinlan
>> yet I hear of people running in 4 at times. How?
Fons Botman <bot...@rabo.nl> writes:
> Running 0.99.* if memory serves correctly. My 4MB ran several
> programs happily next to each other without any pain in the early
> days. Nowadays the kernel is much better (bugfree) and has a lot
> more functionality (many thanks to a lot of capable developpers).
> But that pour old 4MB machine is slowly degraded to a second console
> to another Linux machine, and is swapping like hell.
>
> I still hope to find the swap bug :-)
In 1.1.34 the memory manager for swapping was replaced and in 1.1.37
it was made the default. I think you'll find that if you upgrade to a
recent kernel version, your 4MB machines will be running much faster
(I have heard that kernel compilation is about 40% faster).
Dan
--
Daniel Quinlan <qui...@best.com>
Fons Botman
: yet I hear of people running in 4 at times. How?
Running 0.99.* if memory serves correctly.
My 4MB ran several programs happily next to each other without any pain
in the early days. Nowadays the kernel is much better (bugfree) and has
a lot more functionality (many thanks to a lot of capable developpers).
But that pour old 4MB machine is slowly degraded to a second console to
another Linux machine, and is swapping like hell.
I still hope to find the swap bug :-)
Fons
todd j. derr
Daniel Quinlan <qui...@best.com> wrote:
>In 1.1.34 the memory manager for swapping was replaced and in 1.1.37
>it was made the default. I think you'll find that if you upgrade to a
>recent kernel version, your 4MB machines will be running much faster
>(I have heard that kernel compilation is about 40% faster).
40%! Not quite, the change wasn't that drastic, all that was done was a
map was added to cover the case where a page was written out, read back
in, then reclaimed again before it gets dirty. if it hasn't been
overwritten on disk, we don't have to write it again.
my kernel compilation was ~3% faster. 40% is asking for a lot.
todd
Linus Torvalds
I heard of numbers up to 25% faster, but it depended on what you did.
Kernel compilation wasn't one of the good ones: the gcc memory footprint
is so large, and gcc tends to be very active in re-dirtying pages that
the swap cache never did help that much (also, exiting/re-starting the
processes often tends to not help the swap-cache as it will flush the
cached pages).
It seemed to help more with stuff like running X11 and swapping a lot
but without having just one program causing thrashing like gcc (a more
stable kind of memory usage: switching from one xterm to the other, for
example).
In some respects older kernels *are* faster, though: the new kernels not
only are larger, but they generally do quite a lot more checking, so
even with some of the optimizations done in newer kernels, other things
are going to be slower (another example: some of the optimizations will
use a lot more CPU-time to make IO more efficient: depending on your
setup, this may be slower/faster).
In general, a 4MB is never going to be fast, not when compiling or
running X11. And I'm afraid I don't optimize for those machines, either
(I have 16MB/32MB on my machines).
Linus
Edvard Tuinder
It may be a bit slow due to the amount of memory, but it works like a charm.
It uses 2Mb swap consistenly without a hickup..
>I still hope to find the swap bug :-)
Hmm, I'ld rather not ;-(
Ed
--
Edvard Tuinder e...@OW.org
The OpenWorld Foundation
PGP Fingerprint 41 5F 94 22 29 90 F4 D3 6E 7A 89 F6 A5 9C 0F 23
Arthur van Leeuwen
>In general, a 4MB is never going to be fast, not when compiling or
>running X11. And I'm afraid I don't optimize for those machines, either
>(I have 16MB/32MB on my machines).
Hmm... talking about *lots* of mem here. Well... it seems about time to
make a kernel that will run with as little as 1Mb. Will probably need
a complete rewrite though... :)
Doei, Arthur. (who wants to run Linux on his 1Mb 386sx laptop :))
--
Arthur van Leeuwen, arth...@sci.kun.nl
/\ / A friend is someone with whom you can dare to be yourself.
/--\ / Scientists are currently busy discovering the mnemonics of
/ \/__ our universe. Now if we could only program it ourselves...
Alan Cox
>In <3e0mvk$8...@klaava.Helsinki.FI> torv...@cc.Helsinki.FI (Linus Torvalds) writes:
>>In general, a 4MB is never going to be fast, not when compiling or
>>running X11. And I'm afraid I don't optimize for those machines, either
>>(I have 16MB/32MB on my machines).
>Hmm... talking about *lots* of mem here. Well... it seems about time to
>make a kernel that will run with as little as 1Mb. Will probably need
>a complete rewrite though... :)
Not really. Use one fs (xiafs or minixfs), no networking at all (edit by
hand to take out unix domain sockets). Install something like mcc and
rebuild getty and init to use the shared libraries. Add a swap file before
your fsck.
This leaves the last problem that modern kernels use a zBoot that wants 2Mb,
you'll need to fix that to use the old uncompressed boot (and wipe the BSS)
then it ought to go.
For software swap gcc with bcc, emacs with microemacs etc.
Alan
--
..-----------,,----------------------------,,----------------------------,,
// Alan Cox // iia...@www.linux.org.uk // GW4PTS@GB7SWN.#45.GBR.EU //
``----------'`--[Anti Kibozing Signature]-'`----------------------------''
One two three: Kibo, Lawyer, Refugee :: Green card, Compaq come read me...
Arthur van Leeuwen
>In article <D25Ly...@sci.kun.nl> arth...@sci.kun.nl (Arthur van Leeuwen) writes:
>>In <3e0mvk$8...@klaava.Helsinki.FI> torv...@cc.Helsinki.FI (Linus Torvalds) writes:
>>>In general, a 4MB is never going to be fast, not when compiling or
>>>running X11. And I'm afraid I don't optimize for those machines, either
>>>(I have 16MB/32MB on my machines).
>>Hmm... talking about *lots* of mem here. Well... it seems about time to
>>make a kernel that will run with as little as 1Mb. Will probably need
>>a complete rewrite though... :)
>Not really. Use one fs (xiafs or minixfs), no networking at all (edit by
>hand to take out unix domain sockets). Install something like mcc and
>rebuild getty and init to use the shared libraries. Add a swap file before
>your fsck.
>This leaves the last problem that modern kernels use a zBoot that wants 2Mb,
>you'll need to fix that to use the old uncompressed boot (and wipe the BSS)
>then it ought to go.
>For software swap gcc with bcc, emacs with microemacs etc.
Hmm... must try that then. Looks like the ultimate pet project... :)
But... gcc will not necessarily need to be swapped with bcc, now will
it? I mean... there still is something called swapping... :)
I know... it could get a bit hard with merely 40Mb HD, but still... >:)
Doei, Arthur. (Who thinks he actually *might* pull it off... :))
Greg Hudson
: Hmm... must try that then. Looks like the ultimate pet project... :)
: But... gcc will not necessarily need to be swapped with bcc, now will
: it? I mean... there still is something called swapping... :)
: I know... it could get a bit hard with merely 40Mb HD, but still... >:)
There is a compiler named lcc, which you can get from ftp.cs.princeton.edu
in pub/packages/lcc, that is ANSI compliant and is considerably smaller
than gcc. It appears to use a recursive descent parser, which may mean it
can't have as high-quality error recovery as gcc can, but that's a minor
issue. It also doesn't optimize as well as gcc; in particular, I don't
think register allocation works yet.
I'm not sure how important it is to have a Linux distribution that cuts
down so far on memory usage at the expense of features you might need from
an operating system, but that's another issue.