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:

Finding a free piece of physical memory.
Pointing the process's page table entry to that piece of physical memory.

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.

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 this process.

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 algorithm!

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 memory.
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).