Virtual memory, and when it stopped being controversial

1962The Atlas machine at Manchester

The first working implementation gave a program an address space larger than the physical memory, and moved blocks between fast memory and a drum automatically as they were referenced.

The point was not capacity. It was that the program did not have to know. Addresses meant the same thing whether or not the data behind them was currently in memory, and the machine dealt with the difference.

1950s and 1960sWhat programmers were doing instead

Before that, a program too large for memory was cut into pieces by hand, and the programmer wrote the code that loaded each piece over the last one at the right moment.

This was skilled work, it was specific to one machine's memory size, and it had to be redone when the program changed or the machine did. It was also a rich source of failures that appeared only under particular sequences of use.

1960sThe objection

The resistance was serious and was not nostalgia. A programmer who knows the program's structure can arrange transfers better than a machine reacting to references it cannot anticipate, and for carefully tuned programs that was demonstrably true.

Automatic paging was therefore argued to be a convenience purchased with performance, and for the programs its critics wrote, it was.

1969What settled it

Measurement, on ordinary programs rather than exemplary ones. A study comparing hand-arranged overlays against automatic paging found the automatic system competitive or better for most real programs, because most real programs were not carefully tuned and never would be.

The comparison that mattered was not against the best hand-written arrangement. It was against the arrangement an ordinary team would actually produce, under a deadline, and then fail to update.

1968When it fails, and why that has a name

The failure mode was characterised at the same time. A system whose active data does not fit spends its time moving pages rather than executing, and throughput collapses rather than degrading, because every eviction causes a fault that causes another eviction.

The useful concept is the set of pages a program is actually using over a recent interval. If that set fits, the system is fine; if it does not, no amount of tuning helps and the only remedies are less work or more memory.

present dayWhat the abstraction lets a system do

Once addresses are indirect, a great deal becomes possible that has nothing to do with running out of memory. Two processes can share a page without knowing. A file can be made to appear as memory. A copy can be deferred until somebody writes. Memory can be handed out that does not exist yet.

Almost every one of those is now load-bearing in ordinary software, and all of them are consequences of a mechanism introduced to avoid cutting programs into pieces by hand.

1960s onwardsThe hardware that had to exist first

The abstraction is only affordable because a dedicated piece of hardware translates addresses on every access, with a small cache of recent translations to keep the common case fast.

When that cache misses, the cost is substantial, which is why programs with scattered access patterns run slower than their instruction count suggests, and why arranging data for locality remains worthwhile long after the era of hand-managed overlays.

The size of a page, and why it is a compromise

Small pages waste less memory on partly-used regions and require more translation entries. Large pages need fewer entries and waste more. The figure that settled for general use is four kilobytes, chosen decades ago against memory sizes thousands of times smaller than today's.

Systems now offer much larger pages as an option, and using them is a manual decision with measurable effects, which means the hand-tuning the automatic system was meant to abolish has returned in a smaller and more specialised form.

present dayWhat the mechanism made possible much later

The security properties everybody now relies on are built on the same translation step: separating one process's memory from another's, marking regions as not executable, and placing things at unpredictable addresses.

None of that motivated the original work, which was about fitting large programs into small machines. It is the clearest case in this part of a mechanism outliving its purpose by being useful for something nobody had thought of.

present dayThe bill for the last one

Handing out memory that does not exist is the most consequential of those tricks and the least discussed. It works because programs ask for more than they use, and it fails when they do use it, at which point the system must take memory from something.

Which is why running out of memory is now a policy decision rather than a fact: something has to be chosen and stopped, by a rule somebody wrote, and the failure arrives at a process that may have nothing to do with the one that over-asked.

What we cannot verify

The machine, the studies and the working set model are published and checkable. Performance comparisons from the period are specific to their hardware and workloads and do not transfer. Accounts of how strongly the objection was held, and by whom, come largely from recollection and from the tone of contemporary correspondence rather than from any formal record.