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:
  1. Finding a free piece of physical memory.
  2. 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?