AN EXPERIMENTAL TIME-SHARING SYSTEM
Fernando J. Corbat¨, Daggett, . Center, Massachusetts Institute of Technology
Cambridge, Massachusetts
[Scanned and transcribed by F. J. Corbat¨ from the original SJCC Paper of May 3, 1962]
Copyright By PowCoder代写 加微信 powcoder
It is the purpose of this paper to discuss briefly the need for time-sharing, some of the implementation problems, an experimental time-sharing system which has been developed for the contemporary IBM 7090, and finally a scheduling algorithm of one of us (FJC) that illustrates some of the techniques which may be employed to enhance and be analyzed for the performance limits of such a time-sharing system.
Introduction
The last dozen years of computer usage have seen great strides. In the early 1950¡¯s, the problems solved were largely in the construction and maintenance of hardware; in the mid-1950¡¯s, the usage languages were greatly improved with the advent of compilers; now in the early 1960¡¯s, we are in the midst of a third major modification to computer usage: the improvement of man-machine interaction by a process called time-sharing.
Much of the time-sharing philosophy, expressed in this paper, has been developed in conjunction with the work of an MIT preliminary study committee, chaired by H. Teager, which examined the long range computational needs of the Institute, and a subsequent MIT computer working committee, chaired by J. McCarthy. However, the views and conclusions expressed in this paper should be taken as solely those of the present authors.
Before proceeding further, it is best to give a more precise interpretation to time-sharing. One can mean using different parts of the hardware at the same time for different tasks, or one can mean several persons making use of the computer at the same time. The first meaning, often called multiprogramming, is oriented towards hardware efficiency in the sense of attempting to attain complete utilization of all components (refs.5,6,7,8). The second meaning of time-sharing, which is meant here, is primarily concerned with the efficiency of persons trying to use a computer (refs.1,2,3,4). Computer efficiency should still be considered but only in the perspective of the total system utility.
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 (ref.10).
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 presently available is 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 to drastically 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.
To solve these interaction problems we would like to have a computer made simultaneously available to many users in a manner somewhat like a telephone exchange. Each user would be able to use a console at his own pace and with-out concern for the activity of others using the system. This console could as a minimum be merely a typewriter but more ideally would contain an incrementally modifiable self-sustaining display. In any case, data transmission requirements should be such that it would be no major obstacle to have remote installation from the computer proper.
The basic technique for a time-sharing system is to have many persons simultaneously using the computer through typewriter consoles with a time-sharing supervisor program sequentially running each user program in a short burst or quantum of computation. This sequence, which in the most straightforward case is a simple round-robin, should occur often enough so that each user program
which is kept in the high-speed memory is run for a quantum at least once during each approximate human reaction time (~.2 seconds). In this way, each user sees a computer fully responsive to even single key strokes each of which may require only trivial computation; in the non-trivial cases, the user sees a gradual reduction of the response time which is proportional to the complexity of the response calculation, the slowness of the computer, and the total number of active users. It should be clear, however, that if there are n users actively requesting service at one time, each user will only see on the average 1/n of the effective computer speed. During the period of high interaction rates while debugging programs, this should not be a hindrance since ordinarily the required amount of computation needed for each debugging computer response is small compared to the ultimate production need.
Not only would such a time-sharing system improve the ability to program in the conventional manner by one or two orders of magnitude, but there would be opened up several new forms of computer usage. There would be a gradual reformulation of many scientific and engineering applications so that programs containing decision trees which currently must be specified in advance would be eliminated and instead the particular decision branches would be specified only as needed. Another important area is that of teaching machines which, although frequently trivial computationally, could naturally exploit the consoles of a time-sharing system with the additional bonus that more elaborate and adaptive teaching programs could be used. Finally, as attested by the many small business computers, there are numerous applications in business and in industry where it would be advantageous to have powerful computing facilities available at isolated locations with only the incremental capital investment of each console. But it is important to realize that even without the above and other new applications, the major advance in programming intimacy available from time-sharing would be of immediate value to computer installations in universities, research laboratories, and engineering firms where program debugging is a major problem.
Implementation problems
As indicated, a straightforward plan for time-sharing is to execute user programs for small quantums of
computation without priority in a simple round-robin; the strategy of time-sharing can be more complex as will be shown later, but the above simple scheme is an adequate solution. There are still many problems, however, some best solved by hardware, others affecting the programming conventions and practices. A few of the more obvious problems are summarized:
Hardware Problems:
1. Different user programs if simultaneously in core memory may interfere with each other or the supervisor program so some form of memory protection mode should be available when operating user programs.
2. The time-sharing supervisor may need at different times to run a particular program from several locations. (Loading relocation bits are no help since the supervisor does not know how to relocate the accumulator, etc.) Dynamic relocation of all memory accesses that pick up instructions or data words is one effective solution.
3. Input-output equipment may be initiated by a user and read words in on another user program. A way to avoid this is to trap all input-output instructions issued by a user¡¯s program when operated in the memory protection mode.
4. A large random-access back-up storage is desirable for general program storage files for all users. Present large capacity disc units appear to be adequate.
5. The time-sharing supervisor must be able to interrupt a user¡¯s program after a quantum of computation. A program-initiated one-shot multivibrator which generates an interrupt a fixed time later is adequate.
6. Large core memories (e.g. a million words) would ease the system programming complications immensely since the different active user programs as well as the frequently used system programs such as compilers, query programs, etc. could remain in core memory at all times.
Programming Problems:
1. The supervisor program must do automatic user usage charge accounting. In general, the user should be charged on the basis of a system usage formula or algorithm which should include such factors as computation time, amount of high-speed memory required, rent of secondary memory storage, etc.
2. The supervisor program should coordinate all user input-output since it is not desirable to require a user program to remain constantly in memory during input-output limited operations. In addition, the supervisor must coordinate all usage of the central, shared high-speed input-output units serving all users as well as the clocks, disc units, etc.
3. The system programs available must be potent enough so that the user can think about his problem and not be hampered by coding details or typographical mistakes. Thus, compilers, query programs, post-mortem programs, loaders, and good editing programs are essential.
4. As much as possible, the users should be allowed the maximum programming flexibility both in choices of language and in the absence of restrictions.
Usage Problems
1. Too large a computation or excessive typewriter output may be inadvertently requested so that a special termination signal should be available to the user.
2. Since real-time is not computer usage-time, the supervisor must keep each user informed so that he can use his judgment regarding loops, etc.
3. Computer processor, memory and tape malfunctions must be expected. Basic operational questions such as “Which program is running?” must be answerable and recovery procedures fully anticipated.
An Experimental Time-sharing system for the IBM 7090
Having briefly stated a desirable time-sharing performance, it is pertinent to ask what level of performance can be achieved with existent equipment. To begin to answer this question and to explore all the programming and operational aspects, an experimental time-sharing system has been developed. This system was originally written for the IBM 709 but has since been converted for use with the 7090 computer.
The 7090 of the MIT Computation Center has, in addition to three channels with 19 tape units, a fourth channel with the standard Direct Data Connection. Attached to the Direct Data Connection is a real-time equipment buffer and control rack designed and built under the direction of H. Teager and his group. [This group is presently using another approach (ref.9) in developing a time-sharing system for the MIT 7090.] This rack has a variety of devices attached but the only ones required by the present systems are three flexowriter typewriters. Also installed on the 7090 are two special modifications (i.e. RPQ¡¯s): a standard 60 cycle accounting and interrupt clock, and a special mode which allows memory protection, dynamic relocation and trapping of all user attempts to initiate input-output instructions.
In the present system the time-sharing occurs between four users, three of whom are on-line each at a typewriter in a foreground system, and a fourth passive user of the back-ground Fap-Mad-Madtran-BSS Monitor system similar to the Fortran-Fap-BSS Monitor System (FMS) used by most of the Center programmers and by many other 7090 installations.
Significant design features of the foreground system are:
1. It allows the user to develop programs in languages compatible with the background system,
2. Develop a private file of programs,
3. Start debugging sessions at the state of the previous session, and 4. Set his own pace with little waste of computer time.
Core storage is allocated such that all users operate in the upper 27,000 words with the time-sharing supervisor (TSS) permanently in the lower 5,000 words. To avoid memory allocation clashes, protect users from one another, and simplify the initial 709 system organization, only one user was kept in core memory at a time. However, with the special memory protection and relocation feature of the 7090, more sophisticated storage allocation procedures are being implemented. In any case, user swaps are minimized by using 2-channel overlapped magnetic tape reading and writing of the pertinent locations in the two user programs.
The foreground system is organized around commands that each user can give on his typewriter and the user¡¯s private program files which presently (for want of a disc unit) are kept on a separate magnetic tape for each user.
For convenience the format of the private tape files is such that they are card images, have title cards with name and class designators and can be written or punched using the off-line equipment. (The latter feature also offers a crude form of large-scale input-output.) The magnetic tape requirements of the system are the seven tapes required for the normal functions of the background system, a system tape for the time-sharing supervisor that contains most of the command programs, and a private file tape and dump tape for each of the three foreground users.
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 user program in memory. For similar coordination reasons, the supervisor handles all input-output of the foreground system typewriters. Commands are composed of segments separated by vertical strokes; 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 (starting with an implicit 6 blanks) so that spacing is an easy way to correct a typing mistake. A carriage return is the signal which initiates action on the command. Whenever a command is received by the supervisor, “WAIT”, is typed back followed by “READY.” when the command is completed. (The computer responses are always in the opposite color from the user¡¯s typing.) While typing, an incomplete command line may be ignored by the “quit” sequence of a code delete signal followed by a carriage return. Similarly after a command is initiated, it may be abandoned if a “quit” sequence is given. In addition, during unwanted command typeouts, the command and output may be terminated by pushing a special “stop output” button.
The use of the foreground system is initiated whenever a typewriter user completes a command line and is placed in a waiting command queue. Upon completion of each quantum, the time-sharing supervisor gives top priority to initiating any waiting commands. The system programs corresponding to most of the commands are kept on the special supervisor command system tape so that to avoid waste of computer time, the supervisor continues to operate the last user program until the desired command program on tape is positioned for reading. At this point, the last user is read out on his dump tape, the command program read in, placed in a working status and initiated as a new user program. However, before starting the new user for a quantum of computation, the supervisor again checks for any waiting command of another user and if necessary begins the look-ahead positioning of the command system tape while operating the new user.
Whenever the waiting command queue is empty, the supervisor proceeds to execute a simple round-robin of those foreground user programs in the working status queue. Finally, if both these queues are empty, the background user program is brought in and run a quantum at a time until further foreground system actively develops.
Foreground user programs leave the working status queue by two means. If the program proceeds to completion, it can reenter the supervisor in a way which eliminates itself and places the user in dead status; alternatively, by a different entry the program can be placed in a dormant status (or be manually placed by the user executing a quit sequence). The dormant status differs from the dead status in that the user may still restart or examine his program.
User input-output is through each typewriter, and even though the supervisor has a few lines of buffer space available, it is possible to become input-output limited. Consequently, there is an additional input-output wait status, similar to the dormant, which the user is automatically placed in by the supervisor program whenever input-output delays develop. When buffers become near empty on output or near full on input, the user program is automatically returned to the working status; thus waste of computer time is avoided.
To clarify the scope of the foreground system and to indicate the basic tools avail-able to the user, a list of the important commands follows along with brief summaries of their operations:
1. | alpha
alpha = arbitrary text treated as a comment.
2. login | alpha |beta
alpha = user problem number
beta = user programmer number
Should be given at beginning of each user¡¯s session. Rewinds user¡¯s private file tape; clears time accounting records.
Should be given at end of each user¡¯s session. Rewinds user¡¯s private file tape; punches on-line time accounting cards.
Sets user in input mode and initiates automatic generation of line numbers. The user types a card image per line according to a format appropriate for the programming language. (The supervisor collects these card images at the end of the user¡¯s private file tape.) When in the automatic input mode, the manual mode may be entered by giving an initial carriage return and typing the appropriate line number followed by | and line for as many lines as desired. To reenter the automatic mode, an initial carriage return is given.
The manual mode allows the user to overwrite previous lines and to insert lines. (cf. File Command.)
5. edit | alpha | beta alpha = title of file
beta = class of file
The user is set in the automatic input mode with the designated file treated as initial input lines. The same conventions apply as to the input command.
6. file | alpha | beta
alpha = title to be given to file
beta = class of language used during input
The created file will consist of the numbered input lines (i.e. those at the end of the user¡¯s private file tape) in sequence; in the case of duplicate line numbers, the last version will be used. The line numbers will be written as sequence numbers in the corresponding card images of the file.
For convenience the following editing conventions apply to input lines:
a. an underline signifies the deletion of the previous characters of the line.
b. a backspace signifies the deletion of the previous character in the field.
The following formats apply:
a. FAP: symbol, tab, operation, tab, variable field and comment.
b. MAD, MADTRAN, FORTRAN: statement label, tab, statement. To place a character in the continuation column: statement label, tab, backspace, character, statement.
c. DATA: cols. 1-72. 7. fap | alpha
Causes the file designated as alpha,fap to be translated by the FAP translator (assembler). Files alpha,symtb and alpha,bss are added to the user¡¯s private file tape giving the symbol table and the relocatable binary BSS form of the file.
8. mad | alpha
Causes file alpha,mad
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com