User:Phillipedison1891/Sandbox

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 ${\textstyle \ell }$th level priority queue. Programs are initially entered into a level ${\textstyle \ell _{O}}$ corresponding to their size, such that

$$\ell _{O}=\left[\log _{2}\left({\frac {w_{p}}{w_{q}}}+1\right)\right]$$

where ${\textstyle w_{p}}$ is the number of words in the program, ${\textstyle w_{q}}$ 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, ${\textstyle \ell }$, for up to ${\textstyle 2^{\ell }}$ 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 ${\textstyle \ell +1}$ level queue. If there are no programs entering the system at levels lower than ${\textstyle \ell }$, this process proceeds until the queue at level ${\textstyle \ell }$ is exhausted; the process is then iteratively begun again at level ${\textstyle \ell +1}$, where now each program is run for ${\textstyle 2^{\ell +1}}$ quanta of time. If during the execution of the ${\textstyle 2^{\ell }}$ quanta of a program at level ${\textstyle \ell }$, a lower level, ${\textstyle \ell ^{\prime }}$, becomes occupied, the current user is replaced at the end of the ${\textstyle \ell }$th queue and the process is reinitiated at level ${\textstyle \ell ^{\prime }}$.

Change of Program Size

Similarly, if a program of size ${\textstyle w_{p}}$ at level ${\textstyle \ell }$, during operation requests from the time-sharing supervisor a change in memory size to ${\textstyle w_{p}^{\prime \prime }}$, then the enlarged (or reduced) version of the program should be placed at the end of the $\ell ^{\prime \prime }$ queue where

$$\ell ^{\prime \prime }=\ell +\left[\log _{2}\left({\frac {w_{p}^{\prime \prime }}{w_{p}}}\right)\right]$$