Memory: Virtual Memory (using Disk as Memory)
CS 321 Lecture,
Dr. Lawlor, 2006/02/20
So you're the OS. When a program needs a new piece of memory, you give it to them by:
Note that you don't actually have to give them this memory until they
really use it--any use of unmapped memory will result in a page fault,
which the OS can intercept and use however it likes.
- Finding a free piece of physical memory.
- Pointing the process's page table entry to that piece of physical memory.
What happens in step 1 above if you're out of physical memory
space? Well, you need to get rid of some old piece of
memory. Since you can't just throw away memory, you have to store
the old page somewhere, like on disk (called "paging out"), and
possibly load in the new page (called "paging in"). That is, you
can "fake" a large amount of memory by *unloading* an old piece of
memory in step 1 and unlinking it from the process's page table. What
happens if a program accesses the memory you unloaded? You just
load it back in, possibly unloading something else! See Section
9.2 of Silberschatz for pictures and a more coherent description of
How do you choose which page to get rid of?
This is the problem of "cache replacement": remove an old piece of data to make room for a new piece of data. There's a decent web applet to demonstrate this process. Section 9.4 of Silberschatz also describes the process in exquisite detail.
First try "LRU" (Least Recently Used) cache replacement, and a fully
"Associative" cache of size 5 blocks. Type in the string "1 2 3 4
5 1 2 3 4 5 1 2 3 4 5 ", "Enter", and then "Start". Note that
everything's OK--once the cache "warms up", everything's a cache
hit. Now try "1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6". Note
that everything's a cache miss; LRU is outsmarting itself by throwing
away the oldest data.
The most common, and my personal favorite cache replacement algorithm
is Random replacement, which Silberschatz doesn't even describe.
Here, you just pick a random page to replace. Sometimes (not very
often), you'll make a really bad choice; sometimes you'll do great; but
you'll never make the wrong choice every time like a deterministic
Where do you put the pages you've evicted from RAM?
- Disk--write old pages to the disk, into a special "paging
file"(called "pagefile.sys" on Windows) or a "swap partition".
This is totally standard, and impossibly slow. The fastest disks have
an access time of about 5ms; which is 100,000 times slower than main
- Network. There are trust and reliablity issues with
paging over a network, but ethernet could give 100us paging times,
which would be way better than disk. "Pixie" used to do this back
in the 1980's.
- Just compress them in main memory. A fast runlength encoder
could take a few dozen microseconds per page. The Classic MacOS
"RamDoubler" program used to do this.
- Store them on the graphics card's memory (suggested by Ben
Hartman after class). Graphics cards have up to 512MB of very
fast RAM, and the CPU can access this at in excess of 500MB/s, or 10us
per page. If you're not playing a graphics-intensive game, this
RAM usually isn't doing anything. I don't know of any system that
actually does this, which is silly.
- Store them to a flash drive. Flash access times are low and
dropping, although there may be problems with cost and reliability
(flash sectors can fail after a few hundred thousand write cycles).