Section 12.1
Basic Concepts of Virtual Memory

In the old days, memories were small and expensive. The IBM 1130, a minicomputer that IBM introduced in the mid-1960s, had 8 Kilowords, each word 16 bits long, giving it 16K bytes. About 15 years later, in 1981, another popular small, but cheaper, IBM computer, the IBM PC, was introduced with 16K memory. Just 15 years after that, 1996, many students have portable computers weighing 6 lbs and boasting 8 Megabytes of memory. That is 512 times as big as the venerable IBM PC.

However, a strange thing happened on the way to the present -- programs as well as memories got much much bigger. In fact, many people cannot subsist on a mere 8Mb of memory anymore. Windows 95 needs at least 16 meg. Though we can run some of the largest 1981 programs with ease on today's computers, we still need bigger and bigger memories for tomorrow's applications.

Back to the 1950s and 1960s, when memories were tiny--how did people write large, sophisticated programs on them? There must have been ways, since ambitious AI projects were conceived on those tiny machines, along with graphics, weather simulation, nuclear bomb computations, and many other programs.

Let's think back on the two main uses of memory: to hold programs (instructions), and to hold data that is acted on by those programs. Huge datasets were accommodated by those early machines by writing some of the values out to disk files. Whenever the data was needed in a computation, it was read back into memory. The programmer had the responsibility to explicitly read in this data when it was needed. This increased both the complexity of the program and its running time, but still it was possible to crunch large datasets.

Large programs posed a different problem, because the instructions of a program must be in memory before they can be fetched and executed. But like datasets, programs usually break into convenient chunks called subprograms or subroutines, and these could be saved on disk until the moment they were called. Such a technique was called overlaying because these subroutines overlaid old code in memory when they were executed.

Then around 1961, several groups succeeded in making overlay and data management entirely automatic and invisible. Programmers would not be constrained by memory size limitations nor would they have to break up their code into overlays. They could write programs that crunched ridiculously huge data areas and contained vast armies of subroutines and never know they were using a much smaller computing engine, except that it was a little slower. Thus, virtual memory was born.

The essential idea of virtual memory is to pretend there is a very large amount of memory and to use a combination of disk files and real memory to implement it. A program works in a virtual memory space, which seems to it like a very large real memory. Its size is usually constrained only by the size of the MAR which dictates the maximum address that a program can feed to memory. This virtual memory is broken into a number of equal sized chunks, called pages.

By contrast, there is some smaller amount of real memory, called physical memory. It is broken into chunks of the same size as pages, only these chunks of physical memory are called frames.

Pages are copied into frames when they are referenced, a process called demand paging. The operating system and the hardware collaborate to do this copying behind the scenes automatically, without the programmer even knowing it is happening.

As the program runs, it may use up all the physical memory. When this happens, and the program needs yet another page, special steps must be taken. The operating system selects one of the frames to be used for the new page. However, it cannot just overwrite the frame of physical memory if that frame had been changed by the program, or else errors would result. A page that has been modified by memory write operations is called dirty.

So the operating system copies the dirty page out to disk, and then uses that frame for the new page that is being brought in. Actually, if the frame's old contents were not altered, they could just be overwritten, saving a slow disk write. This would happen if the frame contained pure code or data that had not been changed.

All pages that are not currently in frames of physical memory are stored on the hard disk in the swap area, so called because the pages in it are constantly swapped in and out of real memory.

The next section makes all these words come alive through pictures.