in main memory, or a secondary address in secondary memory. To facilitate address translation, both memories are divided into equally sized units called pages.

When the processor references a virtual address that corresponds to a physical address, the processor can immediately access the data. The only overhead beyond direct physical memory access is the translation of the virtual address into the physical address, a function usually performed by hardware.

However, if no physical address corresponds to the virtual address referenced, the processor must temporarily suspend execution in a page fault. Before the processor can continue, the virtual memory system must:

1. Select a physical page to replace with the virtual page referenced;
   
   
2. copy the current contents of that physical page to secondary memory, if it has been modified;
   
   
3. copy the requested virtual page from secondary memory into main memory; and
   
   
4. update the address translation mechanism to reflect the new state of affairs.

While a process is waiting for a page fault, it does not run and is said to be paging. The overhead of a page fault is quite high because the secondary memory is orders of magnitude slower than main memory, and because there is measurable overhead necessary in the selection of physical pages for replacement.

One implication of virtual memory is that memory writes are inherently more time-consuming than memory reads, because pages that have been modified must be saved to secondary memory. For example, it may be more efficient to say (unless (eql x y) (setf x y)) instead of simply (setf x y), to avoid needlessly modifying a page.



The Working Set of a Program

A program's behavior in a virtual memory processor is partially characterized by its working set [Denning 68]. The working set of a program is the set of all pages referenced by the program in a given time interval. Since modern paging algorithms try to keep recently referenced pages in main memory, the working set size of a program is strongly correlated to the time spent paging. When the working set size exceeds physical memory size, pages must be continuously copied into and out of physical memory, badly degrading performance. This situation is termed thrashing.

The working set concept is particularly important to application programmers, because it is something over which they have direct control. Although specific numbers are not typically assigned to working set size, it is important to recognize