The Compatible Time Sharing System: A Programmer's Guide

Front matter

The Compatible Time-Sharing System A Programmer's Guide

The M.I.T. Computation Center

The M.I.T. Press Massachusetts Institute of Technology Cambridge, Massachusetts, 1963

Preface

This handbook is an attempt to document the techniques of using a current version (Model 13) of the compatible time-sharing-system (CTSS) which has been developed at the MIT Computation Center. It is primarily a manual of how to use the system, in contrast to many of the research memos, which have been more detailed in their documentation of the techniques of implementation. Because CTSS is basically a system which will allow an evolutionary development of time-sharing while continuing to allow more conventional background systems to operate, it is expected that the present manual will of necessity be revised many times before it reaches a final form. A good deal of the difficulty arises from, on the one hand, the rather drastic change in user operating techniques which time-sharing permits, and on the other hand the immense amount of programming required to fully implement the system.

The present work, although not highly polished, is being presented now to assist in this evolutionary process. It is expected to be a supplement to the Computation Center's Procedures Handbook which explains many of the general administrative details of the Center. Furthermore, a knowledge of programming is assumed of the reader. It has been our objective to present to an experienced programmer a reasonably complete manual which will allow him to use wisely the present version of the time-sharing system.

Because of the rapidity with which many of the features are being implemented, and the delays in distributing the inevitable revisions, some features are described here which are not yet accomplished. The reason for this is that it was felt to be important to indicate the intended scope and objectives of the system so that individual users could plan ahead in their applications. The features which are not implemented will be found listed in an appendix which will be revised periodically. In addition, each of the chapters can be expected to be periodically revised.

Since the present work is primarily a handbook, no attempt has been made to make any comparisons with the several other time-sharing and remote-console efforts which are being developed by groups elsewhere. The only other general purpose time-sharing system known to be operating presently, that of the Bolt, Beranek and Newman Corporation for the PDP-1 computer, was recently described by Professor John McCarthy at the 1963 Spring Joint Computer Conference. Other time-sharing developments are being made at the Carnegie Institute of Technology with a G20 computer, at the University of California at Berkeley with a 7090, at the Rand Corporation with Johnniac,and at MIT (by Professor Dennis) with a PDP-1. Several systems resemble our own in their logical organization; they include the independently developed BBN system for the PDP-1, the recently initiated work at IBM (by A. Kinslow) on the 7090 computer, and the plans of the System Development Corporation with the Q32 computer.

To establish the context of the present work, it is informative to trace the development of time-sharing at MIT. Shortly after the first paper on time-shared computers, by C. Strachey at the June 1959 UNESCO Information Processing Conference, H. M. Teager and J. McCarthy at MIT delivered an unpublished paper "Time-Shared Program Testing" at the August 1959 ACM Meeting. Evolving from this start, much of the time-sharing philosophy embodied in the CTSS system has been developed in conjunction with an MIT preliminary study committee (initiated in 1960), and a subsequent working committee. The work of the former committee resulted, in April 1961, in an unpublished (but widely circulated) internal report. Time-sharing was advocated by J. McCarthy in his lecture, given at MIT, contained in "Management and the Computer of the Future" (MIT, 1962). Further study of the design and implementation of man-computer interaction systems is being continued by a recently organized institute-wide project under the direction of Professor Robert M. Fano. In November 1961 an experimental time-sharing system, which was an early version of CTSS, was demonstrated at MIT, and in May 1962 a paper describing it was delivered at the Spring Joint Computer Conference.

As might be expected, the detailed design and implementation of the present CTSS system is largely a team effort with the major portions of it being prepared by the following: Mrs. Marjorie M. Daggett, Mr. Robert Daley, Mr. Robert Creasy, Mrs. Jessica Hellwig, Mr. Richard Orenstein, and Professor F. J. Corbató. Important contributions to some of the commands and the background system have been made by Mrs. Lynda Korn. Valuable criticism and advice has been offered by Professor Jack Dennis, Mr. J. R. Steinberg, and members of the Computation Center Staff. Mrs. Leslie Lowry, Mr. Louis Pouzin, and Mrs. Evelyn Dow have contributed to the preparation of the commands.

Special credit is given to Professor Herbert Teager for the design and development of his Flexowriter control subchannel which allowed the original experimental version of the present system to be developed, tested, and evaluated; only with such an opportunity was it possible to have the confidence to make the present pilot development of the CTSS system.

We should also like to extend our thanks to the Computer Center of the University of Michigan where Professor Bernard Galler, Mr. Bruce Arden, and Mr. Robert Graham have been very helpful in advising us on the use of their Mad Compiler in our time-sharing system. In addition, Mr. Robert Rosen kindly made available the Madtran editing program for processing Fortran II subprograms to Mad subprograms.

We should further like to take this occasion to acknowledge partial support by the National Science Foundation, the Office of Naval Research, and the Ford Foundation, of the development of our present system. We also add our appreciation for the support provided the Computation Center by the IBM Corporation.

Finally, we should like to encourage the readers of this handbook to examine the present system with a view toward improvements, and we shall welcome such criticisms.

F. J. Corbató

Cambridge, Massachusetts May 1963

Introduction

The motivation for time-shared computer usage arises out of the slow man-computer interaction rate presently possible with the bigger, more advanced computers. This rate has changed little (and has become worse in some cases) in the last decade of widespread computer use.

In part, this effect has been due to the fact that as elementary problems become mastered on the computer, more complex problems immediately become of interest. As a result, larger and more complicated programs are written to take advantage of larger and faster computers. This process inevitably leads to more programming errors and a longer period of time required for debugging. Using current batch monitor techniques, as is done on most large computers, each program bug usually requires several hours to eliminate, if not a complete day. The only alternative hitherto available was for the programmer to attempt to debug directly at the computer, a process which is grossly wasteful of computer time and hampered seriously by the poor console communication usually available. Even if a typewriter is the console, there are usually lacking the sophisticated query and response programs which are vitally necessary to allow effective interaction. Thus, what is desired is drastically to increase the rate of interaction between the programmer and the computer without large economic loss and also to make each interaction more meaningful by extensive and complex system programming to assist in the man-computer communication.

In addition to allowing the development of usable and sophisticated debugging techniques, an efficient time-sharing system should make feasible a number of relatively new computer applications which can be implemented only at great cost in a conventional system. Any problem requiring a high degree of intermixture of computation and communication on a real-time basis should readily lend itself to time-sharing techniques. Examples of this type of application include: decision-tree problems; real-time management problems (airline reservations, hospital administration, etc.); gaming problems; sociological experiments; teaching machines; language learning problems; library retrieval; text editing; algebra manipulators; and many more.

The Compatible Time-Sharing System (CTSS) is a general-purpose programming system which allows a new form of computer operation to evolve and yet allows most older pre-time-sharing programming systems to continue to be operated. CTSS is used at a console which may be of several varieties, but which in essence is an electric typewriter. Each console user controls the computer (i.e. as seen by him) by issuing standard commands, one at a time. The commands allow convenient performance of most of the routine programming operations such as input, translation, loading, execution, stopping and inspection of programs. This command convenience, although it has a fixed format, is with no loss of generality since a command can also be used to start an arbitrary programming subsystem with its own control language level.

The consoles of CTSS form the foreground system, with computation being performed for the active console users in variable-length bursts, on a rotation basis, according to a scheduling algorithm. The background system is a conventional programming system (slightly edited for the time-sharing version) which, at the least, operates whenever the foreground system is inactive, but which may also be scheduled for a greater portion of the computer time. The entire operation of the computer is under the control of a supervisor program which remains permanently in the 32,768 word A-bank of core memory; all user programs are either kept in the 32,768 word B-bank of core memory, or swapped in and out of the disk (or drum) memory as needed.

Not only are the active user programs swapped in and out of the two secondary memory disk modules (4.6 x 106 words each) and the drum (.2 x 106 words) but it is expected that all console users will utilize the disk memory for semi-permanent storage of their active program and data files. Cards and magnetic tapes will still serve in secondary roles as long-time and back-up storage devices; they will be usable in CTSS only through the central Computation Center facilities and not directly through the remote user consoles.

Figure 1.1 is a system diagram of the 7090 computer at the Computation Center, which is to be converted to a 7094 Model 1 in August, 1963, with the addition of the 7320 drum at the same time. The motivation for the equipment configuration is described in the next chapter.

Figure 1.1 7090/94 System Diagram

History, Plans, and Current Status of System

Initially an experimental time-sharing system was developed using the special three-Flexowriter subchannel designed and built under H. Teager's direction. The first public demonstrations of this system were in November 1961, and the work was reported at the Spring Joint Computer Conference in May, 1962. During the latter half of 1962, in addition to refinement of the initial system, studies were made of how to remove several limitations in the system, namely: 1) the limited number of typewriter console stations, 2) difficulties of installing and maintaining remote connections, 3) lack of compatibility of operation with other 7090 programming systems, and 4) problems of information retrieval and information security associated with a large on-line secondary memory.

These studies resulted in plans for the conversion of the experimental time-sharing system to a pilot system which would be capable of operating simultaneously with most of the work load already handled by the 7090 at the Center. These plans for the 7090 included: 1) the implementation of the interrupt clock, memory protection, and relocation features; 2) the addition of an IBM 7750 communications channel which allows up to 112 Teletype consoles to be attached via phone lines at remote locations; 3) the addition of a second bank of 32,768 words of core memory; 4) the installation of the IBM 1301 disk file; and 5) the design and programming of a master disk control subroutine (memo CC-196) and an associated disk editor program (memo CC-208) for flexibility in using the crucial secondary memory. As separate experiments, two smaller computers are being specially attached to the 7750 channel by telephone line links: the Electrical Engineering PDP-1 is to be used as an experimental display console, and the Civil Engineering IBM 1620 will be used to control remote analog input-output equipment such as a pen plotter. All of the above equipment and attachments should be installed by spring, 1963, and the necessary programming adaptation required for the first pilot version of the time-sharing system is expected to be completed by summer, 1963. In fall, 1963, the addition of an IBM 7320 moderate-speed drum should further increase system performance by allowing somewhat faster secondary memory access and transmission speeds for swapping programs in and out of core memory, although the drum memory capacity is limited. At this time the general performance of the 7090 will be improved by upgrading it to a 7094 Model 1.

To implement effective operation of a pilot time-sharing system, the initial 16 Teletype consoles have been deployed as follows: two consoles for the Center system programming staff to assist in implementation and evaluation; one in the programmer consulting office to allow rapid assistance to users in the location of errors; one with the Center keypunch operators for service keypunching directly into the disk memory; one for the 7090 computer console operator; one for the 7090 tape-mount operator; one in Professor Minsky's research group for their applications and system evaluation; one in Professor Corbató's office for analysis, monitoring, demonstrations, and programming purposes; one more remotely located at Professor Miller's Civil Engineering Computation installation; and seven in an open pool for general time-sharing users at the Center.

One of the principal design features of the pilot system is that most older pre-time-sharing systems may be operated in the role of a background program simultaneously with the foreground time-sharing console system (memo CC-202-1). Because of the weakness of input-output memory protection in the 7090, it was necessary to develop an intricate input-output analyzer-monitor program for safe operation of older programs which had been developed without time-sharing in mind. Besides easing the programming transition problems of changing from batch processing to time-sharing techniques, this compatibility feature eliminates the necessity for immediately satisfying all of the Center's 400 research users (and a similar number of student users) with the initial version of the time-sharing system.

To achieve programming compatibility, the time-sharing system uses the same programming languages normally available in the major Center system, FMS: Fap, Mad, and Fortran in the form of the nearly equivalent Madtran (memo CC-188). Initial requirements dictated special core-memory-only versions of these compiler programs, but this restriction is being eliminated.

To contrast with batch-computing techniques, it is informative to summarize a typical time-sharing usage. A user has written a subprogram in a compiler language and wishes to incorporate it into his set of programs already developed and kept in the central disk file. After sitting down at a console, he first gives a login command to identify himself. His next command, input, turns his console into a pseudo-keypunch. Using simple conventions, he types in his subprogram for storage with other subprograms on the disk. If he should note any typing or logic errors in his new file, now or at any later time, he can correct the file using an edit command. (If he wanted to avoid the tedium of typing a long program, a suitably trained keypunch operator could just as easily have done the operation in advance.) Using an appropriate command the user can compile his subprogram, and if he has no diagnostics requiring correction, he can prepare to test it. Using the load command, he collects in core the newly compiled subprogram in binary form, any subprograms previously prepared, and the necessary library subprograms drawn from as many libraries as he wishes. If loading is successful, and does not require re-entry for the addition of missing subprograms, a start command initiates his program. He notes the results (if any) that he receives, and after stopping the program, if necessary, inspects the status of various locations and variables within the set of subprograms loaded. After a suitable amount of probing he detects his programming error, makes the necessary corrections, and continues in this manner until he wishes to terminate the session by giving a logout command.

To the above basic time-sharing system, which consists presently of a few dozen commands, many new features and additional commands must be added before it will be generally acceptable. Among the more important ideas are the ability 1) to request from the consoles large-scale delayed printing or punching of programs and cards at the central Center facility; 2) to create delayed graphical plots at the Center; 3) to allow foreground-initiated jobs to be run as background after a user leaves his console; 4) to assign by user request, for the duration of a console session, various input-output units, such as tape units, from the common central pool; 5) to allow inter-user console communication for activities such as management games; 6) to be more flexible and versatile in the allowable debugging techniques such as traces, interpreters, selective dumps, and so forth. Specifications for some of these features are described in later sections.

In addition to the obviously heavy programming development required for the above improvements, there are large operational questions which will need to be determined in the areas of reliability, error detection, programming system and hardware maintenance under conditions of near-continuous operation, automatic traffic and performance monitoring, and automatic accounting.

Finally, in the areas of hardware, there are evaluations to be made of the various consoles: the various model Teletypes, especially models 28 and 33, the Kleinschmidt 311 Teleprinter, the IBM 1050 Selectric typewriter, as well as possibly others. Vast questions lie in the area of self-maintaining display consoles, and finally questions of improved high-speed drums and future memory hierarchy schemes will need to be studied.

General Description and Usage Techniques

The foreground system is organized around commands, which each user gives at his console, and the user's private program files which are kept on the disk. For convenience, the format of the disk files is such that they have titles with name and class designators. (Files can be entered from cards or punched out at disk editing time.)

The Supervisor

The supervisor program remains in A-core at all times when CTSS is in operation. Its functions include: handling of all input and output for the consoles; scheduling of console-initiated (foreground) and offline-initiated (background) jobs; temporary storage and recovery of programs during the scheduled swapping; monitoring of all input and output from the disk, as well as input and output performed by the background system; and performing the general role of monitor for all foreground jobs. These tasks can be carried out by virtue of the supervisor's direct control of all trap interrupts, the most crucial of which is the one associated with the Interval Timer Clock.

The Interval Timer Clock is set for a small quantum of time, q. Every q seconds the supervisor can interrupt the program currently running in B-core in order to accept input from the consoles or to issue output to the consoles. If the input from a console is other than a command line, it is left in the supervisor's core buffers until it is read by the user's program (whether a command or a user-written program). If the input line is a command, it is given immediate priority and the supervisor, after dumping as much as necessary of the current B-core program onto drum or disk, brings in the requested command program from the disk.

Except for this initial top priority, the time-sharing programs are each run for a burst of time which is some multiple of q determined according to the scheduling algorithm. At the end of each program's appropriate time the supervisor determines which user is to be run next.

It must then determine whether the program or programs currently in core must be dumped (to disk or drum), in part or entirely, to leave room in core for the next user. The next user must then be retrieved from secondary storage together with the proper machine conditions.

In addition to maintaining input and output buffers for each user console, the supervisor keeps a record of the status of each user. The status of a user may be: "working," where a program is ready to continue running whenever it is next brought in; "waiting command," where the user has just completed a command line at his console; "input-wait" or "output-wait," where the program is temporarily held up waiting to get a console line in or out; "dormant," where the program has stopped running and returned control to the supervisor, but machine conditions and the status of memory are preserved for inspection, modification, or re-entry; and "dead," where the program has terminated, control has been returned to the supervisor, and machine conditions and the status of memory have been scrapped.

It should be noted that command programs are handled in exactly the same manner as the user's own programs, with respect to status and scheduling. The background system is also considered another user; at present it has a different place in the scheduling algorithm, with permanently lowest priority. In addition there will be another type of background, consisting of batch jobs initiated from consoles but left to run without console interaction; these jobs will be run with exactly the same type of scheduling as normal foreground programs.

Command Format

The commands are typed by the user to the time-sharing supervisor (not to his own program) and thus can be initiated at any time regardless of the particular program in memory. (For similar reasons of coordination, the supervisor handles all input-output of the foreground system typewriters.) Commands are composed of segments separated by blanks; the first segment is the command name, and the remaining segments are parameters pertinent to the command. Each segment consists of the last 6 characters typed (initially an implicit 6 blanks). A carriage return is the signal which initiates action on the command. Whenever a command is received by the supervisor, "WAIT" is typed back. When the command is completed, "READY" is typed back. Where possible, the computer responses are in the opposite color from the user's typing. A command may be abandoned at any stage, including during the typing of the command line or during command output, by giving the "quit signal" peculiar to the console.

Command Initiation

A user starts a command when he completes a command line at his console and is automatically placed in a waiting command status. The time-sharing supervisor uses the interrupt clock feature every quantum of time to interrupt the user program being run and assign the users in waiting command status to a working status with an initial priority based on the size of the requested command program.

Program Termination

A foreground program leaves the working status by two means. It can re-enter the supervisor in a way which eliminates itself and places the user in a dead status; alternatively, by a different entry the program can be placed in a dormant status (or be manually placed there by the user giving a quit signal). The dormant status differs from the dead status in that the user may still restart or examine his program.

Input and Output Wait States

User input-output is through each typewriter via the supervisor, and even though the supervisor has a few lines of buffer space available, it is possible for a program to become input-output limited. Consequently, there is an input-wait status and an output-wait status, both similar to dormant, into which the user program is automatically placed by the supervisor whenever input-output delays develop. When buffers become nearly empty on output or nearly full on input, the user program is automatically returned to working status; thus waste of computer time is avoided.

Scheduling

In order to optimize the response time to a user's command or program, the supervisor uses a multi-level scheduling algorithm. The basis of the algorithm is the assignment of each user program, as it enters the system to be run (or as a response to a user is completed), to an th level priority queue. Programs are initially entered into a level corresponding to their size, such that

where is the number of words in the program, is the number of words which can be transmitted in and out of the high-speed memory from the secondary memory in the time of one quantum, q, and the bracket indicates "the integral part of". Ordinarily the time of a quantum, the basic time unit (currently about 200 ms.), is as small as possible without excessive overhead losses when the supervisor switches from one program in high-speed memory to another. The process starts with the time-sharing supervisor operating the program at the head of the lowest-level occupied queue, , for up to quanta of time, and then if the program is not completed (i.e. has not made a response to the user) placing it at the end of the level queue. If there are no programs entering the system at levels lower than , this process proceeds until the queue at level is exhausted; the process is then iteratively begun again at level , where now each program is run for quanta of time. If during the execution of the quanta of a program at level , a lower level, , becomes occupied, the current user is replaced at the end of the th queue and the process is reinitiated at level .

Change of Program Size

Similarly, if a program of size at level , during operation requests from the time-sharing supervisor a change in memory size to , then the enlarged (or reduced) version of the program should be placed at the end of the queue where

Again the process is re-initiated with the head-of-the-queue user at the lowest occupied level .

Message Interaction Considerations and Usage Times

Because a user cannot "see" his program running, it is important that the programmer resort to appropriate cues and confirmation messages in his programming. Thus when input is expected, a good technique is to have the program first type out a message such as "type next data set" or "A=". Similarly after input it is often reassuring, if a long computation is required, to see some program output acknowledging the receipt (and perhaps the accuracy) of the input message.

The reply response time is governed by the basic scheduling algorithm described earlier and depends on the number of other users. In the current implementation of the algorithm a user-computer interaction consists of the period from an input message to an output message. Although the response time is only a few milliseconds if the user's program is already in core, whenever there is more than one user the usual minimum time for a response, which is the minimum computer usage time per response, is (in the current drumless system) approximately seconds plus the response computation time, where is the number of program words in thousands. For example, eight different user programs, of one thousand words each, could simultaneously respond within a second to input messages requiring only negligible computation.

For those interactions which require non-trivial computation, the computer usage time is approximately given by the sum of two series, the first of which is for the computation:

where the th term of the series is that just necessary to complete the computation. As can easily be seen, in the limit of large computations the ratio of usage time to computation time asymptotically approaches one.

Storage Allocation

Presently only one user program is kept in core memory at a time. However, in order to improve response time, as many user programs as possible should be left in core memory. When required, as much as necessary of the lowest priority program in the scheduling algorithm may be moved to the disk (or drum) memory to make more core memory available. Because of the relative slowness of the 7320 drum and the 1301 disk transfers, moving program segments about in core is an effective way to consolidate space into which to read the user program next to be run. Thus the swap time required to give a response to a user will be only that dictated by the size of his own program. To carry out this procedure, several storage allocation algorithms are under consideration.

Although other possibilities exist, as in the Atlas Computer, initially no attempt will be made to operate any user program unless all of its program segments are contiguous and sequential in core memory. Also the possibility exists of performing a look-ahead operation of swapping a user program in or out while operating another user program (i.e. multiprogramming). Again, initially no attempt will be made to implement the look-ahead feature, since the effectiveness is seriously reduced if scheduling changes (i.e., program completions) are frequent, or if there is frequent competition with the operating program for use of the drum or disk channel.

Memory Protection and Relocation

To avoid fatal conflicts between the supervisor and multiple users, the CTSS IBM 7090/94 includes a special modification which behaves as follows:

Core memory is considered to be divided into 256-word blocks. There are two 7-bit protection registers which, when the computer is in the normal mode, can be set by program to any block numbers. Whenever a user program is run, the supervisor, as a final step just before transferring to the user program, switches the computer to a special mode such that if execution of any memory address outside the range of the protection register block numbers is attempted, the normal mode is restored and a trap occurs to the supervisor.

There is also a 7-bit relocation register which modifies every memory address, during executions, by addition of the relocation register block number. Thus programs which have been interrupted by the supervisor may be moved about in memory, if necessary, with only the proper readjustment of the relocation register required.

Finally, if the user program, while in the special mode, should attempt to execute any instructions concerning input-output, changes in mode or core bank reference status, or resetting of the protection or relocation registers, the normal mode is restored and a trap occurs to the supervisor program in core bank A.