Dynamic Address Translation and the 16 MB Line

Variable partitions fail on fragmentation, and the failure is not repairable by better allocation. The storage key scheme that made partitions safe says nothing about where a partition sits, so a job that needs 30 KB of contiguous space can be refused while 60 KB sits free in two pieces. Free storage between resident jobs is a set of holes, and a job that needs a contiguous region larger than any single hole cannot run no matter how much total free storage exists. Compaction would fix it, but compaction means moving a running program, and a program on a machine without relocation hardware holds absolute addresses in its registers, its branch targets, and its data. Moving it means rewriting all of them, which is impossible in general because the program may compute an address from data.

Dynamic address translation removes the constraint by interposing a mapping between the address a program computes and the address the hardware uses. The program’s addresses become virtual; the hardware’s are real. Storage can then be handed out in fixed-size pieces, a job’s pieces need not be contiguous, and moving a piece is a table edit rather than a rewrite of the program.

Two levels, because one would be too large

The translation structure is a two-level table, and the reason for two levels is arithmetic.

A virtual address is 24 bits, so the address space is 16 megabytes, and the unit of mapping is a page of 4,096 bytes. Covering 16 megabytes at 4 KB per page requires 4,096 page table entries. If a flat page table were used, every job would need a 4,096-entry table, and each entry of the era occupies a few bytes; the table would be tens of kilobytes per job, allocated whether or not the job touched the corresponding pages. With a dozen jobs that is a large fraction of storage spent on tables for pages that are never referenced.

The two-level structure fixes that by making the table sparse in two dimensions. In the 24-bit format the segment index occupies bits 8 through 11, the page index occupies bits 12 through 19, and the byte index within the page occupies bits 20 through 31. Four bits of segment index gives sixteen segments, and each segment is one megabyte, so the sixteen segments tile the 16 MB space exactly. Each segment table entry points to a page table of 256 entries, and 256 pages of 4 KB is the one megabyte that the segment covers.

The saving is not in the total number of entries, which is still 4,096 if every segment is in use. It is in the entries that exist at all. A page table is allocated when a segment is first touched, so a job whose working storage occupies two megabytes in two segments needs two page tables and 512 entries, while a flat table for the same job would need 4,096 entries covering the whole address space including the fourteen megabytes the job never touches. A job with a small region and a large declared address space pays almost nothing.

The same split is what made the later extension to 31-bit addressing cheap. Seven more bits are prepended as an additional level of segment index, so the 24-bit format remains a subset: a program that uses only 24-bit addresses produces virtual addresses whose high seven bits are zero, and it therefore sees only the first sixteen segments. No instruction format changes, and no existing program needs reassembly.

The segment table entry carries the real address of the page table, a length field, and a validity bit. The page table entry carries the real address of the page frame, plus control bits: invalid, changed, and reference. The valid bit is what makes a page absent; the changed bit records that the page has been stored into, which is what decides whether it must be written out before its frame is reused; the reference bit records that the page has been touched, which is the input to the replacement decision.

The translation, step by step, and its cost

Translation happens on every storage reference, so it has to be cheap, and it is not cheap enough to do in full every time.

The hardware reads the segment table entry named by bits 8 through 11. That entry gives the real address of a page table. The hardware reads the page table entry named by bits 12 through 19. That entry gives the real address of the page frame. The hardware concatenates that frame address with the twelve-bit byte index and performs the access. Three storage references for one access, in the naive case: one for the segment entry, one for the page entry, and one for the data.

Three-for-one is unacceptable, so the machine keeps a translation lookaside buffer, a small associative memory holding recently used segment-and-page pairs with their translations. A hit costs nothing beyond the lookup. A miss costs the two table reads, and the table reads themselves touch storage, which is why the tables must be reachable without translation. This is the crucial constraint of the design: on the first implementation, page and segment tables had to reside in real storage, at addresses that are not themselves translated. A table entry cannot point to a table that needs translating, because resolving it would require another translation, which would require another table entry, without end.

The constraint has a visible cost in table management. The operating system cannot page its own page tables, so every page table for every active job occupies real storage permanently while that job is resident. A job with a large working set of scattered pages consumes real storage for the tables as well as for the pages. The later fix is to allow a second level of translation for the tables themselves, with a small set of real-storage frames holding the table pages that are currently in use; that keeps the invariant that at least one level of table is untranslated while removing the requirement that all of it be.

Faults, and the difference between two kinds of absence

An invalid page table entry produces a page translation exception, which is a program check that transfers control to the supervisor. The supervisor inspects the virtual address, decides whether the page is legitimately part of the job’s address space, and if it is, allocates a frame, reads the page in from the paging data set, fills in the entry, and returns. The interrupted instruction is re-executed and this time translates.

Three details in that sequence decide whether it works.

The first is that the fault must be precise. The instruction that caused it must be restartable with no side effects, or the supervisor must be able to determine how far it got. The architecture provides for this by making the page fault an interruption that suppresses the instruction’s effect, and by recording enough state that the instruction can be retried. An instruction that has already stored to one page and faults on the next cannot simply be retried, since the first store would happen twice. The instruction set’s design avoids multi-page stores in a single instruction precisely to keep this property.

The second is that the fault handler must not fault. If the supervisor’s own code or data is paged out, handling a page fault would need to handle another page fault. The usual answer is that the supervisor is either resident or locked in real storage, and the paging data set’s control structures are in real storage, so the handler’s path is always translatable.

The third is that a page can be absent for two entirely different reasons. It can be not present, meaning it is on the paging data set and can be brought in. Or it can be not allocated, meaning the address is not part of the job’s space at all and the reference is a bug. The entry has to distinguish them, because the correct response differs: one is a fault to service, the other is a program check to report. The distinction is carried in the invalid entry’s format, and a supervisor that conflates them either loops on a genuine bug or kills a job that only needed a page.

The 16 MB line as a hardware fact

The 24-bit address is the reason the address space is 16 megabytes. The address field in the instruction format is 24 bits wide, the base and displacement registers are 24 bits, and the channel command word’s address field is 24 bits. Every one of these was chosen when 16 megabytes was far more storage than any machine would hold, and every one of them became a constraint when storage grew.

The constraint is not merely that a job cannot be larger than 16 megabytes. It is that the boundary is a line in the address space: addresses below 16 megabytes are reachable with the original instruction formats, and addresses at or above it are not reachable at all without new formats. Storage above the line is real storage that the machine can hold but that a program cannot address directly. It can be used, but only through mechanisms that hide the address: a window in the low 16 megabytes mapped to high storage, or a data-in-virtual facility that copies between a high buffer and a low one.

The later architectures extended addressing to 31 bits and then to 64, and the transition was deliberately staged so that existing programs kept working. A program using 24-bit addresses continues to run and sees only the low 16 megabytes; a program using 31-bit addresses sees up to two gigabytes; a program using 64-bit addresses sees the full space. Each stage preserved the old instruction formats as a subset of the new, which is why a program assembled decades earlier still runs, and why the phrase “above the line” survived as a term of art long after the line moved.

What translation bought beyond fragmentation

Fixing fragmentation was the immediate motive, and translation delivered three things that were not on the original list.

It made sharing cheap. Two jobs that need the same read-only code can have page table entries pointing at the same frames, which saves storage in proportion to the number of sharers. The protection bits in the page entry prevent a store from either job. The same trick applied to a shared data area requires write access and coordination, but the read-only case is free.

It made sparse address spaces cheap. A job can have a large virtual space with most of it never touched, because the untouched parts have no page table allocated. This is what allows a compiler to allocate a large area for a symbol table without charging every job for it.

It made the paging decision a policy rather than a structure. Once every reference goes through a table, the supervisor can choose which pages are resident, and the choice can be made by any algorithm. Belady’s work on replacement algorithms, including the anomaly that bears his name, is a study of exactly this new degree of freedom, and it exists because translation made the question askable.

The cost is on every memory reference: a TLB lookup in the best case, two table reads in the worst, plus the storage permanently occupied by tables that cannot be paged. That is the trade, and it is the same trade every virtual memory system since has made, with larger pages and more levels to keep the table size proportional to the space actually used rather than to the space addressable.