Pages (and frames) range from 512 bytes up to 8K, with 1K, 2K and 4K being most common. There are problems when pages are too small or too large so a suitable balance must be struck, often by running a large number of real programs and watching how the patterns of addresses to determine if there is too much swapping.

Fig. 12.2.2 shows the program of Fig. 12.2.1 executing in several stages. The entire program is placed on disk initially. When the OS begins to execute it, one page is loaded into memory, the page containing the beginning of the main() function, called the program's entry point. If page 0 contains the entry point, page 0 would be loaded first. Over time, pages 1, 6 and 4 are referenced, so they are copied into frames. The data in frame 6 is then modified.

Suppose page 2 is referenced but all frames are in use, so a victim must be selected. At this stage, the operating system could make a good choice or a stupid choice of victim. The best choice would be to throw out the page that will never be used again or will be used farther in the future than all other pages. A stupid choice would be the page that was modified since that will require both a disk write and a disk read, or a page that will be needed right away. Of course, the operating system doesn't know if a page will be needed again soon, unless it can read the future. Don't laugh! Some systems do precisely that, by running a program, like a payroll program, that is used over and over again, keeping a history of addresses.

Victim selection is an extremely complicated topic and has been researched heavily in order to squeeze the best performance out of virtual memory systems. The most commonly used algorithms are variations on one called LRU for Least Recently Used which keeps a time stamp on each frame. Whenever a frame is referenced, i.e. whenever an address within the page that currently occupies that frame is generated during the instruction cycle, the current time is copied into a register associated with that frame. Then, when a victim is needed, the operating system looks at the time number on each frame and finds the oldest. It is a good bet that this frame, which was used farthest in the past, will not be needed again, so it is selected as the victim. This bet could be wrong, but it is frequently right.

In Fig. 12.2.3 the selected victim is page 0 since it was used farthest in the past and won't likely be needed again soon. It is evicted and the new page, number 2, is copied into its space.

Later, page 0 is needed again, at which point it is copied back in, perhaps into the frame now occupied by page 6. Since page 6 was modified in memory, we say it is dirty. Dirty pages must be copied back out to disk whenever the frame they sit in is given over to a new page, or else the changes will be lost.

This process continues until the program finishes.