The Atlas Operating System, described in section 5 above, is designed to overlap the operation of those parts of the computing system which can function concurrently, namely, input and output peripherals, magnetic tapes, the central computer, and the human operators. We have seen how the input and output wells are used to achieve overlap of input and output operations with computing; jobs whose peripheral input is complete are assembled in main store, prior to execution, from the system input tape, and program results occupy the output well in main store before being recorded on the system output tape.
The scheduler is the part of the supervisor program which determines the order in which the available jobs awaiting execution should be assembled in main store, and should be compiled and executed. In the following sections it will be assumed that no special priority has been attached to jobs by the operator, and that the scheduler is permitted to select jobs in any order; we shall consider later how this order may be influenced by the action of operators.
After recognizing that the proposed dynamic buffering scheme on Atlas means that normally all slow peripheral transfers are indirect and overlapped with computing operations, the merit of doing anything other than executing jobs in precisely the same order as they enter the computer might be open to doubt. However, this simple method of operation can lead to extremely inefficient use of the computer. This would be the case, for example, if a long sequence of jobs all produced output for one peripheral, while other peripherals, which later jobs wished to use, remained idle. On a very large computing system the order in which jobs are executed is not so important since there may be enough peripherals to deal with any load, irrespective of the order in which jobs are executed.
However, it is uneconomical to buy a computing system with more than the minimum number and types of peripherals, which, if used efficiently, can handle the expected load.
If jobs are sorted by the operator before they enter the computer, inefficiencies of this type are less likely to occur. However, due to the speed at which the machine executes jobs, and also the operator's comparative lack of knowledge of the immediate state of the machine, the task of efficiently ordering a large number of jobs is extremely difficult. A far better method of operation is for the operator to take no account of the types of job entering the computer (all jobs being fed in as soon as they appear), and for a scheduling system, which at any instant knows the exact state of the computer, to determine the order of execution.
A sophisticated and efficient scheduling system is the ultimate object of the overall Atlas supervisor, made possible by the special time-sharing features of the Atlas hardware and basic supervisor routines. If a computing system does not have built-in features for protecting and interrupting programs during execution, then anything other than a very simple scheduling system is probably not worth-while, even if it is possible to design some elegant system. In these circumstances the advantages of an efficient scheduling system are offset by the time and effort required to devise the system, and then, when the scheduler is working, by the time spent in the scheduling routines.
The object of the operating system on At]as is to maintain the fullest possible useful activity in those parts of the computing system which can function simultaneously; that is, to reduce to a minimum periods of idleness in any part of the system which is required for further use. Such periods can be caused by a delay in passing information from one branch of the system to another; for example, if a job is using a magnetic tape, either the central computer may be idle awaiting the conclusion of a transfer between store and tape, or the tape may be idle awaiting a command from the central computer. A period of idleness can also occur when a peripheral is free and no attempt is being made to execute available jobs which could use this equipment.
The scheduler may be visualized as arranging for the transfer of jobs from a list of available jobs to a list of jobs in course of execution. The supervisor program on Atlas permits sharing of the central computer between several object programs in course of execution, and thus the Execute List may hold more than one job at anyone time, if this is necessary to achieve efficiency; the composition of this list will be described in this section. At first sight, it would appear that maximum efficiency would be obtained if the Execute List comprised one job using each output peripheral and magnetic tape, together with a base-load job to use any available central computer time. Due to the wide difference in the rate of use of information by the peripherals and the central computer, the central computer might be expected to be in use for only a small proportion of the total time on anyone problem, and whilst not in use for this problem could be used by other problems. The presence of so many problems on the Execute List is not necessary to achieve efficiency, however, and is to be avoided in the interests of efficient use of store. The operative parts of such problems must be in core store to permit fast switching of control between problems without the need for transfers between core and drum stores; this would imply an excessively large core store, anyone part of which is only in use for a small proportion of the total time. Inefficient use of store also results from the fact that, for many problems, the combined core and drum store required for execution considerably exceeds that required for storage of input material, and hence total storage requirements are lessened by reducing the number of problems present at anyone time on the Execute List. Since frequent switching of control between object programs is not desirable, the supervisor program is designed to provide rapid switching of control between an object program and supervisor routines, rather than between two object programs.
A straightforward reduction in the length of the Execute List is achieved by using the output well in core and drum store and on the system output tape to collect output information from all object programs for all output peripheral equipments. Problems which are output limited (that is, those which use an output peripheral for a longer time than they use the central computer) can then be executed in series, filling the output well. During their execution, such jobs are not held up for peripheral transfers. Only when the output well is filled for all peripherals is control switched to programs which are computer limited, only one of which need be in course of execution at anyone time. The output well is emptied by the output peripherals until a low level of available output is reached for any peripheral, when output-limited jobs are again executed in series to refill the output well. In the absence of jobs using magnetic tape, therefore, the presence of two jobs on the Execute List achieves efficiency, and for most of the time only one of these is actually active. Jobs using magnetic tapes cannot be dealt with in this way, since it is impractical for the supervisor program to provide an adequate buffer for information transferred to and from magnetic tapes. If tape-limited problems arc run, therefore, it is essential in the interests of efficiency to maintain these on the Execute List in addition to the two entries described above; the central computer will use tape waiting time to proceed with other jobs in the Execute List. One such problem will be be sufficient under normal conditions.
The object of the scheduler is to maintain a supply of problems to the Execute List, and to arrange as far as possible that a vacancy on the Execute List can be filled immediately by a problem already assembled in the input well in main store. The scheduler will therefore be activated whenever a vacancy appears on the Execute List, through termination of a problem, and whenever input of a job through the input peripheral equipments is complete. Since no peripheral-limited problem (i.e. problems which arc entered to the Execute List in order to supply output to the peripherals) will be executed once the output well is full, and while the peripheral equipments are emptying it, the scheduler is also activated whenever the level of available output for any peripheral which is in use reaches a lower limit. Problems are then executed in series until the output well is filled, and then a vacancy is left on the Execute List. By this means, frequent interruption of a long computer-limited job by short output-limited jobs is avoided; the latter are run in bursts, during which the computer-limited job becomes inactive, and between these bursts the computer-limited job is free of interruption. Following sections will describe in more detail the types of jobs handled by the scheduler, and it will be found that the simple description so far given of the necessary entries in the Execute List is capable of extension to embrace all jobs which occur in practice.
Having stated the general aims and method of the scheduler there remains the practical problem of selecting the right type of job from those available, and assembling it for execution. The major difficulties connected with selecting jobs of the right type from a single long list of jobs are the time required for searching, and the possibility that some job may be permanently overlooked since it never fits into the desired category. A simple solution to these difficulties is obtained by sorting jobs into streams as they enter the computer. For scheduling purposes there is need for a computer and a tape stream, and for various peripheral streams. The tape and peripheral streams supply jobs which will maintain steady use of the tape decks and peripheral devices, whilst computer stream jobs keep the central computing unit active.
There are several factors which influence the types of jobs which enter the various streams; these are now listed and their effects on the composition of the streams discussed.
Taking all these factors into account, a reasonable solution as to the composition of the stream lists, which fits in with the rest of the scheduling system, is:
Jobs are sorted into their streams as they enter the computer, according to the information given in the job description. When a particular type of job is required on the Execute List, the appropriate stream is consulted and the first job chosen; by this means the search time is reduced to a minimum and there is no possibility of any jobs being overlooked. When a computer or tape job leaves the Execute List it is replaced by a job from the computer or tape stream. When a peripheral job ends and there is a peripheral whose backlog is below a certain desired level, or when there is no peripheral job on the Execute List and the output backlog for any peripheral falls below an emergency low level, then a job from the relevant peripheral stream is entered on the Execute List. Also, every time a new job joins a stream queue and becomes available for execution, the scheduler is consulted to see if this job is wanted on the Execute List. The limit of one tape job on the Execute List is relaxed when there are only tape jobs present; in this case, two tape jobs are allowed on the Execute List.
Since the stream queues must contain entries for every complete job in the computer they may become very long. It is essential, therefore, that entries in these lists be as short as possible to permit of efficient scanning by the scheduler and tape and space allocation routines without excessive use of central computer time, core store, and transfers to and from the drums. The simple method of choosing jobs in order from the stream queues for the Execution List make it possible to implement the system if each entry only contains a condensed form of the job title, some reference position of the job on tape, and a link with the next job in the stream. However, jobs have to pass through an assembly stage (see next section) before entry to the Execute List, and it is convenient if there is sufficient information (i.e. number of tape decks and system tapes required) in the stream queue to tell whether it is possible to go ahead and prepare the job. Also. in certain special circumstances it may be necessary to execute jobs out of their natural stream order. For these reasons approximate estimates of execution time, amount and type of output and space requirements, the type of compiler to be used, and any external priority of the jobs are kept. This information is also valuable to the routines which govern the allocation of tape decks and space. The whole of this information is kept in 120 bits. Precise information (names of tapes and system documents, location in store and on tape of each document, etc.) necessary for the assembly and preparation of jobs is contained in an internal job description, which is formed at input time from the programmer's job description and is recorded in an input stream as a separate document belonging to this job.
The computing speed of Atlas is such that small problems may be expected to occupy the central computer for only a few seconds during their execution. It is therefore essential that an entry in the Execute List should be able to be replaced rapidly by the next problem selected by the scheduler, and one of the tasks of the scheduler is to assemble problems in advance so that compiling and execution may begin immediately and are not subject to delays. The scheduler in fact selects in advance problems which are to be assembled, deals with any long-term preparations and then transfers these from the list of available jobs to an Active List, which comprises jobs in the course of assembly prior to execution. Normally long jobs are not entered on the Active List till the previous job is finished; since these jobs are long it is difficult to predict when the previous job is likely to finish, and a short delay between the running of these jobs can be tolerated. Peripheral jobs are entered on the Active List when they are likely to be selected for execution, and where possible one such job is kept on the list to ensure a ready supply of prepared jobs for the Execute List. When a problem is required for execution, only those problems on the Active List whose assembly is complete are considered.
Assembly of a problem involves collecting all the information required to run a problem so that it is available to the central computer with the minimum possible delay when the problem is entered to the Execute List. A completely assembled problem on the Active List has the relevant input information in the input well in the combined core and drum store, the required compiler or input routine in the drum store, and any private magnetic tapes mounted and their titles checked. For very long input streams, a limit is placed on the amount which is initially brought to store. The process of assembly may therefore consist of reading input information from the system input tape, reading documents previously recorded on private input tapes, reading a compiler into store where necessary, instructing the operator to mount magnetic tapes, and verifying the titles of all such tapes. The system may be easily extended to permit on-line use of other peripheral equipments which would be treated as being in the same class as magnetic tapes and prepared for use in a similar manner.
It is essential to observe that assembly of a problem may extend over a long period of time, although, of course, the central computer is only occupied for a small proportion of the time. Collection of a document from the system input tape may not be completed until a full swing of this tape has elapsed. Since the same tape is used both to write blocks received from input peripheral devices and read back previously written blocks to recover documents as they are required, the tape performs a swing action in which frequent scans are made over a few feet of tape, although it will gradually progress forwards. The mounting of magnetic tapes by the operator may be expected to occupy a variable length of time, but one which is necessarily long considering the speed of the central computer. The logic of the scheduler and the assembly routine takes into account these wide variations in assembly times, and attempts to minimize the effect of delay in any branch of the system on the other branches of the system which can operate concurrently.
The process of assembly is divided into two main phases. The first phase deals with long-term assembly of magnetic tapes. Not until this phase is completed is the assembly of any documents from the system input tape initiated. The space and tape allocation routines, to be described later, scan the complete job list and initiate the tape assembly phase for jobs at the head of the stream queue. As tape mechanisms become available, the operator is instructed to mount private tapes. As this stage of assembly of each problem is completed, the scheduler is activated, and should the problem be required on the Active List, any relevant documents are collected from the system input tape. The problem is, in fact, scanned by the routine controlling the system input tape; this routine collects documents required by any job on the Active List as the system input tape moves forwards to the writing position, and hence can assemble several problems during one swing of the system input tape. The location of documents is obtained from the internal job description which, if necessary, is read in from the system input tape on the backward swing. When all the relevant documents are assembled in the main store, the compiler is rwad in to the main store from the Supervisor tape. It should be noted that any or all of the phases of assembly are omitted where they are not required.
The scheduler can be independent of any operator scheduling, but there does exist a two-way communication system between the operator and scheduler. When the scheduler requires action by the operator, such as the mounting of magnetic tapes, an explicit command is printed out to the operator. Because of the comparative slowness of operator action, requests to the operator are given, where possible, well in advance of when the action is needed. In fact, it is advisable that jobs which require some operator action should be fully prepared before entering the execution phase, otherwise inefficiencies resulting from a prolonged delay in operator action can be serious.
It is possible for the operator to convey information to the scheduler, and an example of this is the allocation of an external job priority. From the scheduler's viewpoint external priorities given to a job through the operator at the user's request are necessary to satisfy the user, but may lead to gross inefficiencies in computer operation. The need to obtain the operator's approval before allocating a job special priority affords some protection, but it should be recognized that external priorities impinge on the scheduling system and determine independently what is to happen. Of course the change of state in the computer brought about by the allocation of an external priority is taken into account by the scheduler when determining the best course of action in the future. Also, the framework of routines set up to implement external priorities may be used by the scheduler to achieve its own ends.
The normal scheduling system on Atlas is based almost solely on efficiency considerations, and allocation of an external priority to a job by the operator affords the means whereby the individual user's requirements may be satisfied. There appears to be a need to allow four priorities-top, high, normal, and low, with the following functions.
The Atlas operating system normally requires three tape decks for its own use, viz. input tape, output tape, and supervisor tape; this means that three decks are occupied permanently by the supervisor, though the system is flexible enough to operate with fewer decks when absolutely necessary. When only two decks are available the input and output tapes are combined on one tape. Both tapes are normally used in a similar fashion, and the cost of combining them into one is a reduction in the effective size of input and output wells on tape. The operating system still functions when no decks are available, but only as efficiently as circumstances will allow, and care must be taken that input and output wells are not allowed to occupy all the free space in main store.
Part of the information which accompanies each job into the computer is a list of the tapes required and any documents which have to be obtained from system tapes. Thus, before a job commences execution, the number of decks it requires and the names of the tapes to be mounted are known; this information is valuable for scheduling purposes and the assembly of jobs prior to execution. However, in certain cases tapes are only required during part of their total time of execution, and thus tape decks can be called for or made free during the course of a job's execution; one common example is the use of tapes as temporary working space during compilation.
It is the job of the tape allocation routine to allot tapes to the various sources which require them in such a way that the scheduler can maintain efficient operation of the computer. There is clearly strong inter-action between the scheduler and the tape allocation routine, the behaviour of one affecting the decisions of the other. The normal order of priority for allocating tape decks is as follows:
Every block of main store space in Atlas is a member of a group, depending on its owner, and there are six main groups of owners; these are:
The basis of the space allocation routine is that a hierarchy is formed of all these owners and also of all requests for space, and no request is allowed to take space from an owner of higher priority. The ratings of each member of this hierarchy are essentially dynamic, depending on the state of the machine at the time.
There is an area of space in the machine which is readily available to any request; this consists of all free space and all blocks in input and output wells which have been duplicated on magnetic tape, copies of which have been kept in main store. The number of these available blocks is known at any time. Essentially, a request can only take space from this group, and if there is not sufficient space, then routines are activated which begin to free blocks of a lower priority than the request; when this happens, the request is put into the space request queue, and each time a block is freed, the top element in the queue is checked to see if there are enough free blocks for it. In certain cases the request is not queued but the space allocation routine returns to the routine which made the request with the information that the request has been refused, thus allowing the routine to take alternative action. For instance, the scheduler may ask for space to enter a peripheral job in the Execute List; if insufficient space is available, it may be possible for another smaller job on the Active List to fit into the space available. Certain other requests are allowed to by-pass this main queue; these are the types of requests which ask for single blocks at relatively infrequent intervals, and if the request is not granted some part of the computing system would be halted; i.e. if a request for input-well space is not granted then a peripheral may be halted.
The ordering of the space request queue is important because low priority requests for a large amount of space should not be allowed to block small, relatively high priority requests.
It is a complicated task to keep track of the information in the store, but a directory system has been devised which makes it possible to overwrite peripheral stream information from the input tape in units of one block. However, for other information it is necessary to dump or overwrite it in reasonably sized sections; i.e. even if only a few blocks are needed an entire document might be overwritten.
The actual routines which do this work are in two sections. One section is in the fixed store, and this is sufficient to take care of most requests for space. The other section contains the longer routines which deal with dumping and retrieving information. These space allocation routines, and in fact the whole supervisor, have been written in such a manner that it is possible to overwrite the major part of the main store routine.
It must be emphasized that the system outlined above is suitable for any type of Atlas installation, and is independent of the configuration of peripherals, core store, and drum store, apart, of course, from changes in essential parameters at different installations. However, the scheduling system has been designed in two parts, Routines called into action most frequently are held in the fixed store. They are called into action, and effectively controlled, by routines in the core and drum store and by parameters in the subsidiary working store, which can be changed in the light of experience, and to meet any particular requirements.
