Machines with large virtual addresses require some scheme to define the map from virtual address to real address. The kernel must provide this map and the hardware must apply it. Programs that run with the map enabled are largely or completely oblivious to the real addresses in use. These programs are said to use virtual memory which serves them much as real memory served on previous generations.

A nearly universal choice is to divide the virtual address into three or four portions at fixed boundaries. Starting from the most significant portion, each portion, but the last, is used to index into a table in RAM. Each of these tables provides the real address of the next table and the last table holds the real address for the page. The first table is located by a control register. Entries in the last table with real page addresses are called “PTE”s, (Page Table Entries). We call these tables collectively mapping tables here. This was the pattern from earliest such machines, when RAM was core.

Any of these tables may contain invalid entries. When the hardware encounters such an entry, a memory fault occurs and the hardware traps to the kernel.

Better architectures have RO bits in these table entries and an address translated with the help of such an entry can not be used to modify the data, but would cause a trap instead.

In a multi address space OS the control register locates different top level tables for different processes. Most OSes share subsidiary tables between address spaces in order to share storage.

As far as I know all hardware systems include a cache of recent translations in the form of an associative memory, normally called the TLB. Thus the memory maps in RAM need not be consulted on each memory reference. The kernel must be aware of this so as to signal the hardware to invalidate cached translation entries when it changes the mapping tables. Most architectures never put invalid entries into the TLB and for those machines the kernel could change a mapping table from invalid to valid without purging the cache. The IBM 158 put invalid entries in the TLB for it fetched pairs of PTE at once. It always went to RAM again rather than faulting on a invalid TLB entry.

This remains the most common scheme for memory maps although the PowerPC is different.

Not so Classic

The CDC Star 100 provided 48 bit virtual addresses. The mapping table was a list of pairs of virtual and real addresses. The table was “conceptually” in core and linearly searched on each reference. The matching reference was always put at the head of the search list and the entries that were passed over in the search each moved down one entry. This move was an integral part of the search. Locality of reference meant that this was vastly more efficient than a random pattern of memory accesses would cause. The first few (32?) were really kept in registers. Thus was the TLB conceptually unified with the mapping table proper. The move operation used split cycle core access and banked memory and was thus much faster than one might otherwise imagine. Here is some detailed information.

There were considerable problems in taking page faults during vector operations. The problems were not resolved until considerably after production began. Meanwhile there was no demand paging.

See Tiny Alice map for another idea.