Page Address Registers

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 figurep. 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.

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 [1])

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.