University of Edinburgh Department of Computer Science EMAS — The Edinburgh Multi-Access System H. Whitfield and A.S. Wight EMAS Report 1 James Clerk Maxwell Building The King's Buildings Edinburgh EH9 3JZ 031-667 1081 April 1974 This paper has appeared in the British Computer Society publication The Computer Journal, vol. 16, no. 4, November 1973. EMAS—The Edinburgh Multi-Access System H. Whitfield* and A. S. Wight Department of Computer Science, University of Edinburgh, The King's Buildings, Mayfield Road, Edinburgh EH9 3JZ, Scotland EMAS is a general-purpose time-sharing system for the ICL System 4-75 computer, with provision for fully interactive and background processing. It is a virtual memory system with a three level storage hierarchy. An outline description of the system is given together with a more detailed description of the paging and scheduling software, which is based on the working set concept. Detailed performance figures are included. (Received October 1972) The Edinburgh Multi-Access System (EMAS) is a general purpose time-sharing system for the ICL System 4-75 Computer. Work began in August 1966 and for four years was under the control of the Edinburgh Multi-Access Project (EMAP); a joint project between the University of Edinburgh Department of Computer Science and International Computers Limited (ICL). The computer itself was delivered in December 1968 and the disc-file followed in June 1969. The Computer Science Department took over the development of the system in October 1970 and service began in October 1971. The Edinburgh Regional Computing Centre (ERCC) which runs the computing service has taken an increasing role in the development and maintenance of the system since October 1970 and has now (October 1972) taken it over almost completely. The ERCC has also been involved in a major way in the provision of the compilers for IMP (Stephens, 1973), the language in which the system is written, and in the provision of other subsystem software. About 25 programmers of various levels of experience were involved in the production of the software during the first four years. During the past two years about seven people of very considerable experience have been working on the software much of which has been re-written either totally or in part. EMAP was intended as a research and teaching project as well as a production exercise. It is clear in retrospect that all three functions cannot be reconciled and attempts to do so inevitably lead to delays in production. The first part of this paper is intended to give a broad picture of the organisation of EMAS sufficient to enable the second part and the other papers to be placed in their proper context. The second part contains a description of the resident supervisor. Where the system follows well understood principles only brief descriptions will be given. We have tried to give actual statistics and performance figures where we have them. We do not believe that these are necessarily better than those of other systems, but we do feel that there is a great lack of hard facts in this area. We must apologise that we do not yet have a coherent performance model of our system and offer the statistics in the hope that others will be encouraged to publish similar figures. 1. Hardware The ICL System 4-75 computer is the largest of the System 4 range and has paging (address translation) hardware. The non-privileged instruction set of the System 4-75 is the same as that of the IBM 360 series machines. The channel arrangements are also similar but the channel program command codes are not the same. The interrupt and associated context switching arrangements are similar to those on the RCA Spectra 70 series machines, in that System 4-75 has four sets of General Purpose Registers corresponding to four different states called P-states. Normal interrupts, such as channel or program error interrupts, cause entry to the P3 state and the corresponding registers are used by the processor. Power fail and machine check interrupts cause entry to P4 state and the processor then uses the P4 registers. Some of the registers of the P3 and P4 states are aliases for special registers of all four states. Each state has an interrupt mask register, an interrupt status register and a program counter. These fulfil a similar role to the program status words on the IBM 360 series and are amongst the aliased registers. It is not very convenient to run significant amounts of program in P3 or P4 states because the number of registers available for general use is reduced. The programs which run on entry to these states contain instructions which cause an immediate change to P2 state, where further processing is done. P1 and P2 states each have the full set of 16 registers and none of these are aliased or used for special purposes. The P1 and P2 states are completely equivalent. Because most of the supervisor is compiled from a high-level language and uses all of the registers, we have chosen to use P2 state for the resident (unpaged) supervisor and P1 state for all paged programs. A consequence of having the four P-states is that no storing and restoring of registers in main memory is necessary on a switch of context from one state to another. There is, however, only one set of Floating-Point Registers. Although these are addressable in all four P-states we have chosen to regard them as registers of P1 state. Normally they are not changed by the other three states, but parameters are passed between P1 and P2 states in these registers. The configuration in use at Edinburgh is as follows: 4-75 CPU†, operator typewriter and console. 768K bytes 1μ sec core store—4 bytes/access and two way interleaved. 2 × 2M byte magnetic drums on one channel, transfer rate of 860K bytes/sec. Each drum has 128 tracks and there are 4 pages (of 4096 bytes) per track. Revolution takes 20 mS. 2 × 350M byte non-replaceable disc-file with moving arms, consisting of two devices on one channel. Transfer rate 256K bytes/sec. Revolution takes 40 mS. Average arm movement takes 60 mS. 3 × 7·5M byte replaceable disc drives. 4 × 120K bytes/sec 9 track tape drives. 1 7-track tape drive. *Present Address: Mathematisch Instituut, Rijksuniversiteit te Groningen, Postbus 800, Groningen, The Netherlands. †Typical instruction execution times are given in Table I. Table 1 Sample instruction execution times
MNEMONIC DESCRIPTION FORMAT MICROSECS.
LR Load RR 0-80
L Load RX 1-65
ST Store RX 1-25/1-47
STM Store Multiple RS 6-13 for 8 words
A Add RX 1-93
AR Add RR 1-09
MR Multiply RR 5-45
MVC Move SS 12-09 for 16 bytes
BALR Branch and Link RR 1-79
BC Branch on Condition RX 1-44/1-67
BCR Branch on Condition RX 1-31
ADR Add Normalised (Long) RR 3-22
MDR Multiply (Long) RR 11-04
2 Line printers. 2 Card readers. 1 Card punch. 1 Paper tape reader. 1 Paper tape punch. 1 Communications multiplexer with 64 Permanently wired teletypes, 16 Datel 200 ports, 4 1200 baud buffers with character video terminals, 5 2400 baud synchronous buffers. 1 British Standard Interface which connects to a PDP-15 with interactive graphics hardware. Authorised enhancements are: 1 × 2M byte magnetic drum to go on the existing channel. 256K bytes 1μ sec core store. The paging hardware The 24 bit effective address which is generated by the usual process of address computation is regarded as a virtual address and is translated by the paging hardware into a physical address. The method of translation is sketched in Fig. 1. Although there is a segment table and a segment field in the virtual address, it is not true (or symbolic) segmentation as the segment and within segment addresses are not computed independently. However, it will be seen later that many of the desirable properties of segmentation can still be realised. The segment and page tables must be set up by the supervisor so that the virtual to physical address mapping is correct. The page table entries have availability bits to indicate whether a page is in core and an interrupt occurs if access is attempted to a non-available page. The associative memory has eight cells and remembers the eight distinct most recent accesses avoiding the two extra core cycles needed to access the segment and page tables most of the time. It can be seen that this paging unit is similar to that on the IBM 360/67*. However the System 4 unit provides 256 segments of 16 pages (each of 4096 bytes), whereas the 24 bit IBM 360/67 provides 16 segments of 256 pages. This larger number of segments allows the segmentation to be used in a more convenient fashion. *The recently announced dynamic translation unit on the IBM 370 series machines has four models of operation, one of which is essentially the same as the IBM 360/67 and one the same as the ICL 4-75. System software EMAS is a virtual memory system. Each foreground or background user runs programs in an independent virtual memory and each such user process has a share of the resources of the system (core, CPU, etc.). At system interface level each user has a virtual memory of maximum size \(2^{24}\) bytes organised as 256 segments each of \(2^{16}\) bytes. Segments 0–31 of each virtual memory are used by the director processes and are not available to the user. Central to EMAS is its File System which contains named files belonging to all users. Each file is a completely unstructured sequence of bytes of arbitrary length (in units of one page or 4096 bytes). Files have two part names as follows MAC007.FRED where the first part is the name of a user of the system (the owner of the file) and the second part is his chosen name for the file. All files are held on-line and so are immediately available. Files are accessed by connecting them, i.e. by having a mapping set up between the whole file and a segment (or several contiguous segments) of virtual memory. This mapping is done by a request to the system and once established access to the file is by direct reference to the appropriate virtual address. The system provides for controlled access to files in read/read-write and shared/unshared modes. When files are used in a shared mode all users have access to the same physical copy whether this is on disc, drum or in core. This facility is used extensively to share the code of programs at various levels in the system and results in marked saving of core, drum and disc space. Input from cards or paper tape is handled by a system process called demons and appears as files in the file system. Output to printers, etc. is also handled by demons which prints files as soon as possible after receiving a request. The foreground consoles are the only devices which communicate directly with running user processes. The user appearance of the system is sketched in Fig. 2. Files reside on the disc-file where they are stored in page (4096 byte) blocks. The system uses the drums and core to buffer parts of files while they are being operated upon. The system software can be thought of as a set of concentric shells. In the centre we have interrupt analysis, the CPU despatcher, the basic synchronising primitives and message passing software. Then there are the supervisor processes. These are concerned with the following functions: ![Diagram showing the paging hardware, including entry respondent, associative memory, segment table, page table address, page tables, availability bit, and STB.](page_1012_1342_388_388.png) Fig. 1 Paging hardware Fig. 2 User appearance of EMAS (a) Driving the fast devices—e.g. drums and disc-file. (b) Driving the communication devices—e.g. typewriter consoles. (c) Providing minimal support for slow devices—e.g. tapes, card readers, line printers. (d) Supporting virtual memories—i.e. the paging software. (e) Scheduling of CPU-time and core for paged processes. (f) Control of CPU errors. Code for these processes is permanently resident. The next shell of the set consists of the director processes. Each user process has an associated director process which performs (primarily) file system and console communication services on its behalf. The director process has access to the whole of the virtual memory whereas the user process can access segments 32-255 only. The director process is superior to the user process and can start or stop it and perform various recovery functions. The intention here is to handle all non-time critical system activities in paged processes and it is easier to have such a paged director for each process. Where appropriate (e.g. when accessing file indexes) the directors are interlocked via a semaphore scheme. They all share identical code and use the same physical copy. It should be noticed that supervisor overlays are in this way made unnecessary, as the paging of the directors by the standard paging software provides a similar function in a much more elegant way. It can be remarked here that it has been a general principle in our design not to place any system function at a more central position than is strictly necessary. Further system functions such as user vetting on logging in and the input and output functions mentioned above are handled by the demons process (Hayes, 1973). The detailed organisation of the director is described in an accompanying paper (Rees, 1973), but it is worth looking immediately at the relationship between the paged director and the resident supervisor. Fig. 3 shows the mapping on the first 32 segments of each virtual memory. Segment 0 is not normally used for somewhat bizarre reasons connected with a design difficulty in the addressing system. Segment 1 is the buffer segment which addresses the buffers into which all console and slow device input/output takes place. Segment 1 is common to all director processes and the pages which are allocated as buffers are locked in core while transfers are in progress. Segment 2 is the master segment; it is in read-write unshared mode and contains the working variables for this incarnation of director. These consist of a static-storage area and a stack; there is also one page (page 0) used as the master page. This contains the mapping of segments onto files for this virtual memory and space for copies of the register sets* of the director and user processes. It also contains usage information for pages of files in active use. These tables on the master page are the only ones accessed by both the director and the paging software. It is the responsibility of directors, which control the file system, to write to the master page correct mapping information which relates segment numbers to the physical disc locations of the desired files. The paging software operates entirely from the master page and has no knowledge of files as such or to whom they belong. When a process is loaded to core the master page must always be fetched—all other pages can if necessary be demand-paged using the information on the master page. Segment 3 addresses the file containing the director code. This pure-procedure program file is accessed in read shared mode by all directors. Segments 4-31 address the file indexes of all accredited users and are accessed in read-write shared mode by all directors. Subsystem software The items of software mentioned above, viz. the resident supervisor, the directors and the demons process, constitute the system, i.e. that part of the whole software complex which the ordinary user cannot change. This basic system provides the virtual memory support and file protection mechanisms. A user at a console or a background user requires a great deal more than this, e.g. command interpretation, job control language analysis, loading operations, use of commands or catalogued procedures and use of utilities for the creation, *A register set consists of the program counter, the general purpose registers and the floating point registers. ![Block diagram showing user appearance of EMAS](page_68_120_627_495.png) ![Mapping on segments 0-31](page_1012_1202_323_323.png) management, compilation and execution of programs. In EMAS these facilities are provided by ordinary programs which are protected and shared by the normal file control and file access mechanism. A powerful subsystem (or collection of such facilities) with a good range of commands has been provided for the user, but there is nothing to prevent a user adding his own commands (merely by compiling a program) or indeed from choosing to use a completely different subsystem. This is useful to the subsystem programmers who can test new subsystems without affecting other users of the system. The standard subsystem is described in a separate paper (Millard, Rees and Whitfield, 1973). The compilers in the standard subsystem produce pure-procedure code in a standard layout and observe parameter passing and linkage conventions which permit cross-calling between routines in different languages. The files of the standard subsystem belong to a user of the system called manager who also owns the password lists and is responsible for accrediting new users. History and current status When work on EMAS began in October 1966 we naturally turned to the paper on Multics (Corbató and Vyssotsky, 1965) as a starting point. This greatly influenced our thinking as did the paper by Arden, Galler, O'Brien and Westerveld (1966). Work on Multics began in 1964, two years earlier than on EMAS, but intermediate results from the Multics Project did not come out soon enough to have much influence on the subsequent course of our work. It is therefore interesting to compare the present state of EMAS with that of Multics (Corbató, Saltzer and Clingen, 1972). We have not been able to explore those areas which require a multi-processor configuration because of our hardware provision and we deliberately chose not to have hierarchically structured file directories and system administration (our standard subsystem does however provide a hierarchical structure of libraries of entry points of programs). Apart from this we have set ourselves essentially the same goals as Multics and have attained them in all essential respects. The ICL 4-75 computer on which EMAS works is a slightly modified 4-70 computer. The only additions are the paging unit and 'the use and change' markers on the core keys. The drums do not have hardware queueing facilities but a similar effect is organised in the drum software. The hardware became available for software development over the first half of 1969, again two years later than in the case of Multics. Until then we used the KDF9 computer with an IMP compiler which produced code which simulated the effect of the same program on System 4. By September 1970 we had put a good deal of the system together. However, it was apparent that a major re-design was necessary in the file system area. Here again the similarity to the Multics experience is remarkable. The cause of necessary re-design was not so much coding as a failure to keep the software sufficiently simple in concept to minimise the amount of code required. In particular we had not realised that interacting paged processes, competing for the same core, would take so long in elapsed time to complete complex sequences of operations. We very much simplified our specification to include only the minimum features logically necessary, simplified the management of the file system, and improved the interfaces between certain components. However, it was not necessary to change the design of the resident supervisor. We have since re-written the file system twice more to provide improved facilities, to use file disc space efficiently, and to make the director more efficient in its paging characteristics. The supervisor has also been improved in many significant ways although it has not been necessary to re-write it. The iterative technique of program design suggested by Corbató et al. (1972) is entirely in accord with our experience. By early 1971 (again two years later than Multics) EMAS was sufficiently effective for us to be able to use it for all our development. At this point we began to make rapid progress. By October 1971 the system was made available to general users. EMAS currently supports 150 accredited users, and is operated 18 hours per day Monday to Friday and 10 hours on alternate Saturdays. The system currently supports about 30 fairly demanding users using one CPU and 768K bytes (equivalent to 192K 32 bit words). Most of the user consoles are within two miles of the computer building and are used by staff and research students of the University of Edinburgh and by Government Research Council Institutes in the Edinburgh area. The system performs a great deal of error detection and recovery, and is reasonably proof against all but errors in the CPU. Fig. 4 shows the crashes for the first half of 1972. The software time between crashes is large despite the fact that the system is under continuous development. We would expect the software error rate to fall to zero if we ceased development. After a crash we take a dump to magnetic tape and re-IPL. This takes less than a minute. The EMAS system, i.e. resident supervisor, director and demons, consists of 11 modules, totalling about 20,000 source statements in all. These compile into about 180K bytes of code. The basic subsystem, including compilers, commands and basic libraries, consists of another 33,000 statements and 500K bytes of code. Details are given in Tables 2 and 3. The compiler ![Mean time between crashes induced by software, hardware, and all reasons including above, based on 20-day moving average.](page_120_180_627_496.png) Fig. 4 Table 2 Sizes of system components
COMPONENT FUNCTION LOCATION SOURCE TEXT (STATEMENTS) CODE SIZE (BYTES†) STATIC DATA (BYTES†)
SPAM PAGING RESIDENT 5,200 A,370 1,9C0
CEDRIC COMMUNICATIONS RESIDENT 1,425 2,3C8 1,C18
PART PARAMETER RESIDENT 1,705 3,F88 3,510
PASSING AND
OPERATOR CONTROL
FAST DISC
DRUM
LOADUP		 RESIDENT 1,525 2,6E0 1,C68
TAPE MAGNETIC TAPE RESIDENT 1,308 3,2A8 A98
SLOW SLOW DEVICES RESIDENT 741 1,520 8D0
PERM* RESIDENT 618 140
DIRECTOR FILE SYSTEM COMMUNICATIONS PAGED 3,500 9,600 1,C98
DEMONS ACCOUNTING PAGED 3,849 C,978 1,089
SPooling
BACKGROUND JOB
INITIATION
LOGGING ON
†In hexadecimal *In Assembly Language Compiled code run-time routines Table 3 Sizes of selected subsystem components
COMPONENT FUNCTION SOURCE TEXT (STATEMENTS) CODE SIZE (BYTES†) STATIC DATA (BYTES†)
ACP & BCI ERROR CONTROL and COMMAND INTERPRETATION 818 2,680 5B0
EDCP STREAM-FILE MAPPING 1,203 3,FC0 1,928
FPD VM LAYOUT and PROGRAM LOADING 1,412 4,880 1,410
BCLL BASIC COMMANDS 1,308 6,298 9E0
EDIT EDITOR 977 2,CA8 308
FORTE FORTRAN COMPILER 7,749 10,058 1,4D0
IMPS IMP COMPILER 9,800 16,A78 D10
†In Hexadecimal operates at about 60 statements a second. Linkage of supervisor takes less than one second. A complete system generation takes less than 10 minutes and a new component can be introduced in less than two minutes. The size of the resident supervisor is 95K bytes of code and for a 30 user load about 128K bytes of data and buffer areas. We make new supervisors and directors about three times a week. New subsystems are introduced about twice a month, but new versions can be tested at any time. About 120 man years of effort have gone into the system to date, a figure which is similar to the Multics experience. The cost of the software was about £450,000 including about £200,000 paid to the ERCC for some 3,000 hours of computing time during the development period. In the past two years the design and implementation has been in the hands of six people who understand the system and subsystem between them in complete detail. It is estimated that this team, using the existing system as a tool, could move the whole system to a suitable new machine with a different order code in one to two years or to a very similar machine such as an IBM 370 series machine with paging in about six months. Like Multics, EMAS allows each user to choose the program file which is mapped onto the virtual memory before his process is initiated. The appearance of the system is determined partly by the routines in this sub-system base file and partly by the other files and services to which the user has access. EMAS too has a stack-oriented, pure procedure environment with libraries mainly in IMP and FORTRAN IV. Appendix 1 lists some of the facilities available. It cannot be stressed too strongly how important the use of IMP has been to the whole exercise. It is only by use of a high-level language that the size of the text of the system can be kept down to a level where a very few people can understand all of it. Why system programmers should continue to deprive themselves of facilities which they feel obliged to provide for others is beyond our comprehension. Good compile time and run time diagnostics make for rapid program development and an optimising mode in the compiler for validated programs solves the efficiency problems. In systems programming it is important that the language make the relationship between the source text and the object code efficiency fairly obvious so that the programmers avoid awkward constructions. In cases where the ultimate in code efficiency is required we have used in-line machine code rather than separate code subroutines which always suffer from routine calling and return overheads. The IMP compiler has 90K bytes of code and uses 25K bytes of data. 2. The EMAS supervisor The kernel At the heart of the EMAS supervisor is the CPU despatcher. It is not possible to have more than one CPU in a System 4-75 configuration so the despatching problem is slightly simplified. *Each servicing routine may be regarded as the code of a supervisor process. The supervisor consists of a number of servicing routines*. Each of these provides a set of associated services. For every service there is a service number which can be regarded as identifying a private semaphore (Dijkstra, 1968). A supervisory service is activated (kicked) by sending a request message. This can be regarded as a V-operation on its semaphore with the queuing of the associated message. There is a queue (the MAIN-Q) of services awaiting attention by the CPU. They are queued initially in order of arrival, but second or subsequent requests for the same service are held on side chains so that all requests on a particular service can, where appropriate, be serviced at one time. MAIN-Q → 70 → 31 → 89 → 43 ↓ ↓ ↓ ↓ 70 89 ↓ ↓ 89 The despatcher, which runs in P2 state, selects the first item on the MAIN-Q and calls the appropriate routine. The routine is then executed until it returns to the despatcher, all interrupts other than machine checks and program errors being masked off in P2 state. In the course of execution the routine may kick other servicing routines causing further items to be placed on the MAIN-Q. When it is called the servicing routine is passed the request message. It may ask for any other messages on the MAIN-Q side chain if it wishes. When the routine has no more to do it returns to the despatcher. This can be regarded Table 4 The category table
CATY PRIORITY CORE (PAGES) RESTIME (SECONDS) LOOKTIME (SECONDS) NCY1 NCY2 NCY3 NCY4
114410·1251413911
211310·53202
312610·54323
423910·54434
511310·58605
611320·59705
721350·510705
812610·511958
922620·5121068
1032650·5131078
1123910·51412811
1223930·51413911
134397·50·7515131011
1435220·514151211
154527·50·7515151311
Demons starts in category 2 and all other paged processes in category 1. as a wait or P-operation on its private semaphore. Routine calls are also provided to enable a servicing routine to inhibit or uninhibit the activation of particular services. These are used, for example, by routines which maintain internal queues of their own for optimisation purposes. When their queues are full they inhibit further requests until servicing of some of the existing requests is complete. The despatcher normally works through all the uninhibited requests on the MAIN-Q causing execution of the servicing routines in P2 state before switching to the execution of the current PI state paged process. However, it does examine the interrupt flag register before calling a new servicing routine and if high priority channel interrupts (drum or disc-file) are present it exits to PI-state immediately, to enable the interrupt to be taken (PI-state is run with all interrupts enabled). When interrupts occur a request is placed on the MAIN-Q in the normal way for the servicing routine. However, the high priority interrupts cause immediate execution of the servicing routine which effectively comes to the head of the MAIN-Q. A request message or reply is always a 32-byte record with the following format
DSNO DACT SSNO SACT NOT USED LINK Variable parameters
DSNO is the service number being kicked. DACT is an activity number often used to indicate a sub-service where more than one type of request is handled on the same service number. SSNO is the service number of the requesting servicing routine in case a reply is required. SACT is its subservice number which is always returned (in DACT) in replies. LINK is a chain link (see below). All service request messages and replies are stored in a common list-processed area. At present there is space for 192 messages. The system maintains a free list and the MAIN-Q consists of a list of head cells to chains in this parameter area. The restriction to 32 bytes was made to allow a consistent scheme for paged and non-paged processes. Requests from paged processes are made by placing the 32-byte record in the \(4 \times 64\) bit floating-point registers and issuing the supervisor call (SVC) instruction. The floating point registers were chosen because they are the only registers common to all four P-states and it is not convenient to place SVC parameters in memory in a paged system. It has been found that this restriction to 32 bytes has rarely been an embarrassment. Each director and each user process also has a service number. Messages for paged processes are held in the same area but the head cells are not on the MAIN-Q and are held separately. A useful feature of the parameter passing scheme is the service exchange. This has a table which relates service numbers to the servicing routine or paged process. By changing this table servicing routines can be moved around the system, e.g. between supervisor and demons, without the problems of changing all occurrences of the service number. Closely connected to this is a facility which enables selected services to be monitored. A printout is produced showing all messages entering and leaving the associated servicing routines. This is a most useful diagnostic facility as it enables software errors to be located very precisely. Servicing routines normally deal with groups of associated services. For example there is a DRUM routine which handles requests for transfers and termination interrupt messages. The IMP language in which the system is written allows the use of own variables and this feature is used to store information between one call of DRUM and the next. Because all servicing routines return to the despatcher to wait, it is necessary to have one stack only for all the routines of supervisor—indeed the organisation of the routines has been made with this in mind. It is perhaps worth remarking that servicing routines often have at their head a jump to a switch label (vector label) controlled by an own variable, set on the previous entry. EMAS also has a conventional semaphore scheme for the Table 5 Priority ratio table
PRIORITY FREQUENCY
121/32
28/32
32/32
41/32