Virtual Memory: Atlas

In early computer systems peripheral transfers took place under direct program control using input/output instructions which normally required several milliseconds for their completion. By the time the Atlas computer was developed, the disparity between processor and peripheral speeds had become so great (of the order of 1000:1) that it was essential that peripherals be operated on a time division basis, with each peripheral interrupting the main program when it required attention. Since the routines controlling these peripherals were required to be resident in store concurrently with the main user program, and since the system was extended to allow several user programs to co-exist in store, it was no longer feasible either to optimise programmed transfers between the core and drum stores (so as to eliminate the drum access time of 6 ms) or even to allow users to program transfers within a shared physical store when they had no knowledge of other users' requirements. Consideration of these problems led to the idea of providing users with a virtual memory and to the development of a paging system to map virtual addresses on to the real, physical storage devices. Thus the integration of the Atlas core-drum combination into an apparently one-level store [1] was a function of the machine itself, rather than a software facility, as it had been on earlier machines such as Mark 1 and Mercury.

Real and Virtual Addresses

In a virtual addressing system the programmer is allowed to use all available store addresses, but these virtual addresses do not refer directly to real store addresses, and each user programmer can assume that he or she has sole use of the entire address range. In the hardware the virtual address space is considered to be split up into a series of contiguous pages of some convenient size (512 words in Atlas), which may be represented as follows:

PAGE 0123  4    5    ...  
WORDS 0-511512-10231024-15352048-2557 ...

Not all virtual pages contain information, since virtual addressing allows users to locate their code and data in areas which they find convenient, and which need not be contiguous. Thus the core and drum in Atlas might have contained, at some stage in the execution of a particular user program, virtual pages as shown in the table below, where ** indicates an empty core block.

CORE BLOCK   0    1    2    3    4    5    ...  
VIRTUAL PAGE  147**  40    5    ...  
DRUM BLOCK   32    33    34    35    36    37    38    39    ...  
VIRTUAL PAGE 12133926541 ...

If the program called for a virtual address in page 7, for example, the hardware would have been required to translate this into a request to a real address in block 2 of the core store. This required the existence of a page table relating virtual and real addresses, as shown the followung table.

VIRTUAL REAL
0 5
1 0
2 36
3 34
4 1
5 38
6 37
7 2
. .
. .

Page Address Registers

In developing the hardware to implement the translation between virtual and real addresses, the designers of Atlas made the following observations

  1. Every virtual address generated within the processor has to be translated into a real address by a table look-up, and this involves an extra contribution to the store access time.

  2. If the number of virtual pages is large, the table is large and therefore slow to access.

  3. The requested virtual addresses must be in the core store most of the time if the system is to operate efficiently; a page on the drum must be moved into core before the processor can access individual words within it. Thus a small table containing only the entries corresponding to pages in core can be looked at initially, and the full table accessed only when the small table does not contain the required page address.

The system of Page Address Registers (PARs) used to implement this table is shown in the figure. To locate a page, the 11 PAGE digits of the required address were presented to an associative store containing one register for each of the 32 blocks of core store. These registers were implemented in such a way that a check for equivalence between the presented PAGE bits and the contents of each register took place in parallel, thereby minimising the address translation overhead.

Atlas page address registers

Figure Atlas page address registers

If an equivalence occurred between the required page and a page address stored in one of the associative registers, that register indicated a 1 while the others indicated a 0. Thus for virtual page 7 in our example, line 2 would have contained the value 7 and given equivalence when an address in page 7 was requested. The 32 outputs from the associative registers were encoded into a 5-bit binary number and concatenated with the 9 LINE digits from the required virtual address to produce the real address to be sent to the core store.

If no equivalence occurred, the required page was not in the core store, and the program could not continue until it was. A page fault interrupt was therefore generated and the assistance of the operating systems (known as the Supervisor in Atlas) invoked. The Supervisor used the full page table in order to locate the required page, initiated the necessary transfer from the drum into an empty core block, and set up the corresponding Page Address Register. It also initiated the transfer of an existing page from the core back to the drum in order to maintain an empty core block in readiness for the next page fault.

The choice of page to transfer out of core was made by a learning programwhich attempted to optimise these transfers such that pages currently in use were not chosen for rejection. The operation of this program was assisted by the provision of a usedigit in each page register, which was set every time the corresponding page was accessed. All 32 digits were read and reset at regular intervals (normally every 1024 instructions), and their values added to a set of running totals maintained and used by the learning program. This program was the first example of a page rejection algorithm. Page rejection algorithms now form an important part of most operating systems (see, for example [2]

Each of the Page Address Registers in Atlas also contained another digit, the lock-outdigit, which prevented user programs from accessing a page even though it was core-resident. This served two purposes. Firstly, it prevented programs from accessing pages to which drum, magnetic tape or peripheral transfers were taking place; with the lock-out digit set, access to that page was only permitted if the address had been generated by the drum or tape systems, or as a result of a peripheral transfer. Secondly, it prevented interference between programs co-existing in the core store; whenever the Supervisor caused a change from one program to another, it protected the pages belonging to the suspended program by setting their lock-out digits. In the subsequent Manchester University computer (MU5), this inter-program protection was extended by the inclusion of a 4-bit process number in each paging register. The current process number was held in a register within the processor and updated by the operating systems at a process change. The contents of this register were concatenated with each address generated by the processor, so that addresses could only produce equivalence in those paging registers that contained the appropriate process number.

The Atlas virtual memory/paging system, and the concept of dynamic address translation which it introduced, have had a profound influence on the design of many other computer systems, among which are the DEC PDP-10, the IBM System/370 series, the CDC STAR-100, and their successors. The full implications of virtual memory and its attendant advantages and disadvantages are still subjects of controversy.

References

  1. ^ T. Kilburn, D.B.G. Edwards, M.J. Lanigan and F.H. Sumner
    "One-level Storage System"
    IRE Trans., Vol EC-11, pp 223-234 1962
  2. ^ A.M. Lister
    "Fundamentals of Operating Systems" 4th edition, Macmillan, London, 1988
Return to Storage Hierachies