CTSS Scheduler

Description: The Compatible Time Sharing System (CTSS) was an influential operating system that was not only an early time-sharing operating system, it also influenced the design and programmers of the UNIX and MULTICS operating systems. It was intended to be compatible with the Fortran Monitor System (FMS) from IBM.

Here, we focus mostly on an early implementation of the CTSS process scheduler that implemented time-sharing.

Introduction

Compatible Time-Sharing System (CTSS) was developed at MIT using the MAD (Michigan Algorithm Decoder) language. (The “compatible” part refers to an old 709 batch processing system that it emulated in order to facilitate migration to the new world of timesharing.) CTSS was later demonstrated in 1961 on the IBM 709, and later on the IBM 7090 (seven-oh-ninety). The time-sharing system was accompanied by a paper presented at the Spring Joint Computer Conference the following year titled “An Experimental Time-Sharing System.” It was deployed in the summer of 1963 and kept in use through 1971. The goal of this initial time-sharing system was to allow for multiple users on a single large system. Of particular importance is the scheduling algorithm in CTSS, which makes use of a multi-level priority queue.

Background

In 1959, John McCarthy sent a memo to P. M. Morse proposing the idea of time-sharing. In the introduction, McCarthy wrote “The proposal requires a complete revision in the way the machine is used, will require a long period of preparation, the development of some new equipment, and a great deal of cooperation and even collaboration from IBM. Therefore, if the proposal is to be considered seriously, it should be considered immediately.” McCarthy’s memo inspired a number of groups in the MIT community. The first working system was demonstrated by Corbató and his team in 1961 on an IBM 709.

The first of its kind, CTSS was one of the most influential time-sharing operating systems. This system was later modified to work on the IBM 7090, and became the basis for Project Mac, the organization that created Multics. Multics went on to inspire the design of UNIX. CTSS also inspired the design of the Incompatible Timesharing System (ITS) — a competing system created by a group of people at MIT who did not agree with the design of CTSS. ITS focused heavily on AI, and was oddly counter-cultural at MIT.

Many of the developers of CTSS ended up working on UNIX, and CTSS arguably ended up influencing UNIX as much or more than Multics did. For example, Doug McIlroy participated in CTSS (and Multics, then UNIX; he was known for pipes, but also did a lot of other things, such writing a PL/I compiler for Multics).

John Backus, creator of FORTRAN, summarized the significance of time-sharing in the 1954 summer session at MIT when he said that “By time-sharing, a big computer could be used as several small ones; there would need to be a reading station for each user.” Time-sharing systems virtually obsoleted the inefficient batch-processing systems of the time. Furthermore, time-sharing systems paved the way for modern operating systems and the personal computer.

This code example is from the code for the priority-based scheduling algorithm to enable time sharing and is central to how time sharing worked in CTSS. This version is from 1965 and was re-typed from the program listings maintained in the Fernando Corbato collection at the MIT Archive.

Overview

The scheduling algorithm of CTSS has the following functions:

1. Determining which user is to run next
2. Determining when the next user is to run
3. Determining how long the next user is to run
4. Charging users for swapping and running time
5. Keeping track of the status of each user

An event, argument, and user are scheduled as a group.

Design

Summary of portions of Corbató:

In running a time-sharing computing system, many jobs are given processor cycle time in a fair and efficient manner. The central focus here becomes a scheduler that plans and allocates processor time to its list of running programs. In CTSS, this is handled by a multi-level scheduling algorithm.

Programs are initially entered into an lth-level priority queue at level $l_0$ based on their size such that $l_0=[{log}_2([\frac{w_p}{w_q}]+1)]$ where $w_p$ is the number of words in the program and $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. The time of a quantum is kept as low as possible without excessive losses due to the overhead incurred by switching programs.

The time-sharing supervisor starts at the head of the lowest occupied level of the queue. This program gets up to 2lquanta before being placed at the end of the queue at the level one below l. If a new process is put into a lower level than the current one, then the current one is placed back at the head of level l and execution picks up at the lower level.

When a program requests a change in the size of its memory, it is reinserted into the queue at level $l^{\prime\prime}$ according to the equation $l^{\prime\prime}=l+\left[{log}_2\left(\frac{w_p^{\prime\prime}}{w_p}\right)\right]$ where wp” is the new size of the program in number of words, l is the old level of the program.

Given the algorithm above, we can draw several important conclusions which allow us to bound the performance of the system. A program must be operated for at least the time required to move the program in and out of secondary memory (i.e. swap time). As such, computational efficiency cannot be lower than one-half. In other words, the real-time computing speed of the system as observed by one of n active users is no worse than if there were 2n active users with programs in high-speed memory.

The worst case for response time occurs when all active users are on the same level of the multi-level priority queue. Hence, an individual user is guaranteed a response time of $t_r\le2Nq([\frac{w_p}{w_q}]+1)$ where N is the maximum number of active users.

Assuming programs of equal size enter the queue at the same time and run for multiple quanta, response time is at worst approximately twice the response-time that results from a single quantum round-robin procedure. With the multi-level algorithm, total delay for the program at the end of the queue when programs are started at the first level is $T_m\approx q\cdot2^l[n\ \left(2^j-1\right)+\left(n-1\right)\cdot2^j]$ where n is the is number of equal-sized programs, and the first quantum is run at the level $l + j$ . The equivalent round-robin delay before a response is $T_s\approx q\cdot2^l[n\ (2^j -1)]$ , which follows from the fact that the user at the end of the queue has used $2^l\cdot2^j-1$ quanta.

As a result, we find $\frac{T_m}{T_s}\approx1+(\frac{n\ -\ 1}{n})\ (\frac{2^j}{2^j-1})\approx2$ .

The level classification procedure for programs in the multi-level algorithm is entirely automatic; it depends on performance and program size rather than a user’s claims about a particular program. Degradation of the performance of the system occurs progressively starting with the higher level users of programs that are either large or long-running. With a large number of users and many active users at lower levels, it’s possible that users at the higher levels no longer get scheduled. The bound on this cut-off point is described by the relation below:

$l_a\le[{log}_2(\frac{t_u}{Nq})]$

This relation describes N active users at level l each running $2^l$ quanta, terminating, and reentering the system again at level l at a user response time, $t_u$ , later. If there is no service at level $l+1$ , then computing time, $Nq(2^l)$ , must be at least $t_u$ .

Flow of the Scheduling Algorithm

CTSS Console Commands

login	Log into system
logout	Log out of system
listf	List files in the directory
input	Input source code, fixed size lines
edit	Edit source code in a BASIC style with line numbers
printf	Print file starting from a line number
fap	FAP assembler
mad	MAD compiler
madtrn	Fortran II to MAD translator
load	Load binaries (linking in memory)
use	Load missing binaries
start	Run program loaded into memory
save	Save program in the memory to file
resume	Load saved program and resume running it
pm	Get post-mortem information of the program in memory
patch	Edit memory
tra	Create transfer to a relative location in a program
stopat	Create transfer to stop the program at a location
rename	Rename file
chmode	Change the mode of the file
delete	Delete file, had * wildcards
split	Split file
combin	Join files, also binary files, making libraries
cpu	Get the current machine conditions
octlk	Print memory
memo	Input text files, variable size lines
modify	Edit text files, similar to edit
ditto	Print text files with formatting (footnotes, pages)

CTSS Filesystem

Each user had their own directory, resembling the home directory in Unix. Files had two names, the latter of which is similar to an extension.

File modes: temporary, permanent, read-only class 1, read-only class 2

R-O class 2 prevented the user from changing the file mode.

Output of listf showing contents of directory:

10 FILES 20 TRACKS USED
DATE       NAME        MODE       NO. TRACKS
5/20/63    MAIN MAD    P          15
5/17/63    DPFA SYMTB  P          1
5/17/63    DPFA BSS    P          1
5/17/63    DPFA FAP    P          2

Code Snippets

The code was written in the MAD (Michigan Algorithm Decoder) programming language that is loosely inspired by ALGOL. “:R” refers to remarks and are comments in MAD.

The following resources will help with understanding the key snippets below.

MAD Manual

https://drive.google.com/file/d/157qHtzpv07lNCgUvmI3Vf_1wGNnCtmRf/view?usp=sharing

MAD Reference

http://www.bitsavers.org/pdf/univOfMichigan/mad/L2-UOI-MAD1-2-RX_MADum_62.pdf

Snippet 1: User Switching

This snippet switches out the current user with the next one.

:R
:R.. The next three events always occur in sequence
:R.. when control is transferred from ‘OLDUSR’ to ‘NEWUSR’
:R.. as a result of ‘SWAP’ being set non-zero
:R.. ‘NEWUSR’ pays for core freeup and his own load
:R
:R.. ‘EVENT’ .E. 3, saving of ‘USR'(‘|USER’) is beginning
:R.. EVENT 3 may be called for any of hte following:
:R 1. freeing up core B because ‘CURUSR’ extended size
:R 2. freeing up core A drum buffers for swapping
:R 3. dumping ‘OLDUSR’
:R 4. dumping other users to make room for ‘NEWUSR’
BOOLEAN SWPSW, FIRST3, SWAP
EVNT(3) WHENEVER SWPSW
WHENEVER FIRST3
FIRST3 = 0B
EXECUTE CHARGE.(PAYUSR, DELTIM.(PAYTIM))
TIMLEV(I.(OLDUSR)) = TIMLEV(I.(OLDUSR)) + DELTIM.(LEVTIM)
PAYUSR = NEWUSR
END OF CONDITIONAL
TRANSFER TO CHANGE
END OF CONDITIONAL
TRANSFER TO RETURN
:R
:R.. ‘EVENT’ .E. 4, RESTORING OF ‘NEWUSR’ is beginning
EVNT(4) WHENEVER STATUS(I.(OLDUSR)) .E. 2,
:1 WATTIM(I.(OLDUSR)) = GETOTL.(0)
CURUSR = NEWUSR
TRANSFER TO CHANGE
:R
:R.. ‘EVENT’ .E. 5, ‘NEWUSR’ begins running after restore
:R.. NEWUSR’s time allotment is set to the quantum at this
:R.. level less his two-way swap time from drum, and less
:R.. any time already run at this level
EVNT(5) TDEL = DELTIM.(PAYTIM)
WHENEVER TDEL .G. BGMAX
EXECUTE CHARGE.(PAYUSR, BGMAX)
EXECUTE CHARGE.(OLDUSR, TDEL-BGMAX)
OTHERWISE
OLDUSR = CURUSR
BACKGR = 0
END OF CONDITIONAL
:R
:R.. CALL MONSC2. IF COMMON CHANGED, ELSE JUST RETURN
TRANSFER TO MONITR
CHANGE CONTINUE
EXECUTE MONSC2.
EXECUTE PLOT2.
RETURN FUNCTION RETURN
:R
:R
:R.. Internal functions
:R.. ‘TRUN’ – computes run time for user ‘DU’ at level ‘DL’
INTERNAL FUNCTION TRUN.(DU, DL) = QUNATM*(2.P.DL)
:R
:R.. ‘LEVELF’ – compute priority level based on length ‘LEN’
INTERNAL FUNCTION(LEN)
ENTRY TO LEVELF.
WHENEVER LEN .GE. FULLEN
L = FULLVL
OTHERWISE
L = EMPLVL + ILOG2.(LEN/(FULLEN/(2 .P. (FULLVL-EMPLVL))))
END OF CONDITIONAL
FUNCTION RETURN L
END OF FUNCTION
:R
:R.. ‘PREMPT’ – is true if preemption is permitted
:R.. based on time interrupter will run ‘INTRUN’
BOOLEAN PREEMPT.
INTERNAL FUNCTION PREMPT.(INTRUN) =
:1 INTRUN .L. GETOTL.(0) – BEGTIM
:R
:R
:R.. Common variables
INSERT FILE MADCOM
:R.. user machine conditions status table
:R.. (not referred to by mad programs)
END OF FUNCTION

Snippet 2: Charging

This snippet is responsible for checking a user’s time and charging for used time. It also disconnects inactive users.

EVNT(1) MONITR = RETURN
ICUR = I.(CURUSR)
T = GETOTL.(0)
:R.. Do the following checking every 10 seconds
:R.. charge paying user for time
:R.. also logout inactive users
:R.. and hangup inactive lines
:R.. decrease level of user not meeting percentage by 1
:R.. percentage calculated on time since user entered
:R.. working status
WHENEVER T .G. CHECKT
CHECKT = T + 600
EXECUTE CHARGE.(PAYUSR, DELTIM.(PAYTIM))
THROUGH KLOOP, FOR K = 0, 1, K .G. UMAX
WHENEVER K .E. CURUSR, TRANSFER TO KLOOP
KUSER = I.(K)
WHENEVER K .G. 2
DELT = T – WATTIM(KUSER)
WHENEVER STATUS(KUSER) .E. 3 .OR. STATUS(KUSER) .E. 2
WHENEVER DELT .G. QNTWAT .AND. LEVEL(KUSER) .G. MINLVL
MONITR = CHANGE
EXECUTE DELQUE.(K)
LEVEL(KUSER) = LEVEL(KUSER) – 1
EXECUTE ENDQUE.(K)
WATTIM(KUSER) = T
TIMLEV(KUSER) = 0
END OF CONDITIONAL
OR WHENEVER PROBN(KUSER) .NE. 0
WHENEVER DELT .G. INACTV
MONITR = CHANGE
NOTIME(KUSER) = 2
WATTIM(KUSER) = T
END OF CONDITIONAL
END OF CONDITIONAL
END OF CONDITIONAL
WHENEVER WRKTIM(KUSER) .L. (PB(KUSER)/100.)*(TIMNOW-
:1 STRTIM(KUSER)) .AND. (STATUS(KUSER) .E. 2 .OR
:2 STATUS(KUSER) .E. 3) .AND. LEVEL(KUSER) .G. MINLVL
MONITR = CHANGE
EXECUTE DELQUE.(K)
LEVEL(KUSER) = LEVEL(KUSER) – 1
EXECUTE ENDQUE.(K)
END OF CONDITIONAL
KLOOP CONTINUE
END OF CONDITIONAL
:R
:R.. MOVE LONG RUNNING ‘CURUSR’ down in priority
WHENEVER T .G. MAXTIM .AND. .NOT. SWAP
MONITR = CHANGE
EXECUTE DELQUE.(CURUSR)
WHENEVER LEVEL(ICUR) .L. MAXLVL,
:1 LEVEL(ICUR) = LEVEL(ICUR) + 1
EXECUTE ENDQUE.(CURUSR)
LEVTIM = T
TIMLEV(ICUR) = 0
MAXTIM = T + TRUN.(CURUSR, LEVEL(ICUR))
END OF CONDITIONAL
TRANSFER TO DECIDE

Full Code

            :R******TIME SHARING SCHEDULING ALGORITHM***********
            :R    T. Hastings and R. Daley
            :R    Minor Modifications by G. Schroeder when NEW
            :R    I/O Package Installed....Summer, 1965
            :R
            :R  The Scheduling Algorithm Performs the following functions
            :R   1. Determines which user is to run next
            :R   2. Determines when next user is to run
            :R   3. Determines how long next user is to run
            :R   4. Charges users for swapping and running time
            :R   5. Keeps track of the status of each user
            :R
            :R The scheduling algorithm is called from the supervisor by
            :R  Execute sched.(event, user, arg)
            :R    after all traps have been disabled
            :R 'User' is between 0 and the max. No. of users, 'MXUSR
            :R The significance of 'user' and 'arg' depend on 'event'
            :R   or are meaningless as described BELOW
            :R   'event'     Description
            :R   0           initialization of sched.
            :R   1           clock interrupt
            :R   2           'user' has changed to state 'arg'
            :R   3           Beginning of saving 'user' core image
            :R   4           Beginning of restoring 'user' core image
            :R   5           'user' begins running, after swapping
            :R   6           'user' core image now has length 'arg'
            :R   7           Operator set background keys to 'arg'
            :R   8           'user' logged in, 'arg' is line multiplier
            :R   9           'user' logged out
            :R  10            is 'newuser' still runable
            :R  11           'user' dialed up computer
            :R  12           schedule background
            :R
            :R To clarify the order in which events happen, blocks
            :R   of coding bracketed by comments have been placed in
            :R   typical order of execution for a command
            :R All time is kept in sixtieths of a second and variables
            :R   ending with 'TIM' are times since system was
            :R   loaded with the exception of 'SYSTIM'
            :R Sched. has sole responsibility for setting and INTERCHANGING
            :R   the following common arrays and variables
            :R
            :R The following common arrays are used
            :R  'status' - the status of each user
            :R  where status(J) may be
            :R       0 Dead - Not waiting to run and no core image
            :R       1 Dormnt - not waiting to run
            :R       2 Working - waiting in queues or running
            :R       3 Waiting command - Waiting in queues for com.
            :R       4 Input wait - Program waiting for input
            :R       5 Output wait - Output buffers filled
            :R       6 File wait - Lock on file to be read or written
            :R       7 Fib wait - FIB monitor has nothing to do
            :R  'Length' - length of user core image in words
            :R  'Level' - User's priority level (0, ... , 'MAXLVL')
            :R  'Timlev' - Elapsed time run at current level
            :R  'Wattim' - The last time that a user began to wait
            :R  'linmul' - user line multiplier
            :R  'plist' - The position list specifies the positions
            :R            of the users which are in the working queues
            :R  'ulist' - The user list indicates the user numbers
            :R            which correspond to these queue positions
            :R  'endptr' - endptr(J) is end of queue J in plist
            :R  'notime' - notime(J) is set to 2 if user inactive
            :R    and user J will subsequently be logged out
            :R  'PB' - percentage user must run while in work stat
            :R
            :R    The following common variables are used
            :R  'MXUSRS' - Max. No. of foreground users
            :R  'CURUSR' - Current user, running or swapping
            :R  'OLDUSR' - Last user to be run, when 'SWAP' .ne. 0
            :R  'NEWUSR' - Next user to be run, when 'SWAP' .ne. 0
            :R  'PAYUSR' - The User currently paying for time
            :R  'SYSTIM' - Time System was initialized
            :R  'BEGTIM' - The last time 'CURUSR' began to run
            :R  'QUANTM' - Maximum running time at level 0
            :R  'TBASE' - Base time for computing 'MAXTIM'
            :R  'PAYTIM' - Last time a user was charged for time
            :R  'LEVTIM' - Last time 'CURUSR' was running at current level
            :R  'SWAP' - Non-zero requests supervisor to run
            :R             'NEWUSR' as soon as it can
            :R  'MAXLVL' - The maximum priority level(0 ... 'MAXLVL')
            :R  'MINLVL' - The minimum priority level allowed
            :R  'FULLEN' - length for entry at level 'FULLVL'
            :R  'ESTTIM' - Time limit for current FIB job
            :R  'QNTWAT' - Quantm waiting time before level change
            :R             to next highest priority level
            :R  'LEVINC' - Amount priority level is increased when
            :R    user returns to working from input or output waiting
            :R  'INACTV' - Max. time inactive before logout
            :R  'HANGUP' - Max. time before inactive line is hungup
            :R
            :R   Common Variables referred to by sched. but
            :R     not set or change by sched.
            :R  'BKGTIM' - total time background has run
            :R  'SWPSW' - non-zero when supervisor is swapping and
            :R     command loading
            :R  'PROBN(J)' - non-zero when user J is logged in
            :R  'ADOPT(J)' - PROBN(J) .and. ADOPT(J) .E. 1B then
            :R    user J is adopted
            :R
            :R    Sched. calls the following subroutines
            :R  INITQ. - initializes queues
            :R  HEDUSR. - returns the head of queue user
            :R       at highest non-empty priority level or 0
            :R  DELQUE.(J) - deletes user J from queues
            :R  ENDQUE.(J) - places user J at end of queue LEVEL(J)
            :R  BEGQUE.(J) - places user J as beg of queue LEVEL(J)
            :R  ILOG2.(N) - returns integer part of log to base 2 N
            :R  I.(J) - converts forward index 'J' to backward
            :R           index for referring to MAD arrays
            :R  INITIM. - initialize time accounting
            :R  INTIM. - User 'U' logged in
            :R  OUTIM. - User 'U' logged out
            :R  CHARGE.(U,T) - Charge USER 'U' for time 'T'
            :R  GETOTL. - returns the total time system has run
            :R  DELTIM.(T) - returns delta 'T' - the difference
            :R       between 'GETOTL.()' and time 'T'
            :R       time 'T' is also set to GETOTL.(0)
            :R  CURTIM.(0) - returns the current time since midnight
            :R      of day system was initialized
            :R  MONSC1.(EVENT, USER, ARG) monitors sched.
            :R  MONSC2. is called when sched. changes common
            :R  PLOT1.(EVENT.USER, ARG) plots system on esl scope
            :R  PLOT2. is called when sched. changed common
            :R
            EXTERNAL FUNCTION(A, B, C)
            ENTRY TO SCHED.
            NORMAL MODE IS INTEGER
            :R
            :R.. Shorten linkage, setup user index, call monitoring sub.,
            :R..   call plotting routine
            :R..   assume common will be changed, and dispatch on 'EVENT'
            :R
            EVENT = A
            USR = B
            IUSER = I.(USR)
            ARG = C
            EXECUTE MONSC1.(EVENT, USR, ARG)
            EXECUTE PLOT1.(EVENT, USR, ARG)
            MONITR = CHANGE
            STATEMENT LABEL MONITR, RETURN, CHANGE
            TRANSFER TO EVNT(EVENT)
            :R
            :R.. 'EVENT' .E. 0, initialize scheduling algorithm for N users
            :R..   initialize independent common variables
EVNT(0)     MXUSRS = 31
            MAXLVL = 8
            MINLVL = 0
            FULLVL = 3
            EMPLVL = 2
            FULLEN = 4096
            QNTWAT = 3600
            LEVINC = 0
            QANTM = 30
            INACTV = 216000
            HANGUP = 7200
            :R
            :R..   initialize queues and time accounting
            EXECUTE INITQ.
            EXECUTE INITIM.
            :R
            :R..   initialize tables
            THROUGH JLOOP, FOR J = 0, 1, J .G. UMAX
              JUSER = I.(J)
              PB(JUSER) = 0
JLOOP         LINMUL(JUSER) = 1
            :R
            SYSTIM = CURTIM.(0)
            SWAP = 1B
            FIRST3 = 1B
            BGMAX = 120
            TRANSFER TO CHANGE
            :R
            :R.. schedule background (USER 0) at LEVEL 9
EVNT(12)    EXECUTE DELQUE.(0)
            LEVEL(I.(0)) = 9
            PB(I.(0)) = 0
            STATUS(I.(0)) = 2
            TRANSFER TO CHANGE
            :R
            :R.. 'EVENT' .E. 1, clock interrupt
            :R..   assume common will not be changed
EVNT(1)     MONITR = RETURN
            ICUR = I.(CURUSR)
            T = GETOTL.(0)
            :R.. Do the following checking every 10 seconds
            :R..   charge paying user for time
            :R..   also logout inactive users
            :R..   and hangup inactive lines
            :R..   decrease level of user not meeting percentage by 1
            :R..     percentage calculated on time since user entered
            :R..     working status
            WHENEVER T .G. CHECKT
              CHECKT = T + 600
              EXECUTE CHARGE.(PAYUSR, DELTIM.(PAYTIM))
              THROUGH KLOOP, FOR K = 0, 1, K .G. UMAX
                WHENEVER K .E. CURUSR, TRANSFER TO KLOOP
                KUSER = I.(K)
                WHENEVER K .G. 2
                DELT = T - WATTIM(KUSER)
                WHENEVER STATUS(KUSER) .E. 3 .OR. STATUS(KUSER) .E. 2
                  WHENEVER DELT .G. QNTWAT .AND. LEVEL(KUSER) .G. MINLVL
                    MONITR = CHANGE
                    EXECUTE DELQUE.(K)
                    LEVEL(KUSER) = LEVEL(KUSER) - 1
                    EXECUTE ENDQUE.(K)
                    WATTIM(KUSER) = T
                    TIMLEV(KUSER) = 0
                  END OF CONDITIONAL
               OR WHENEVER PROBN(KUSER) .NE. 0
                 WHENEVER DELT .G. INACTV
                   MONITR = CHANGE
                   NOTIME(KUSER) = 2
                   WATTIM(KUSER) = T
                 END OF CONDITIONAL
               END OF CONDITIONAL
               END OF CONDITIONAL
               WHENEVER WRKTIM(KUSER) .L. (PB(KUSER)/100.)*(TIMNOW-
            :1   STRTIM(KUSER)) .AND. (STATUS(KUSER) .E. 2 .OR
            :2   STATUS(KUSER) .E. 3) .AND. LEVEL(KUSER) .G. MINLVL
                  MONITR = CHANGE
                  EXECUTE DELQUE.(K)
                  LEVEL(KUSER) = LEVEL(KUSER) - 1
                  EXECUTE ENDQUE.(K)
                END OF CONDITIONAL
KLOOP         CONTINUE
            END OF CONDITIONAL
            :R
            :R..   MOVE LONG RUNNING 'CURUSR' down in priority
            WHENEVER T .G. MAXTIM .AND. .NOT. SWAP
              MONITR = CHANGE
              EXECUTE DELQUE.(CURUSR)
              WHENEVER LEVEL(ICUR) .L. MAXLVL,
            :1      LEVEL(ICUR) = LEVEL(ICUR) + 1
              EXECUTE ENDQUE.(CURUSR)
              LEVTIM = T
              TIMLEV(ICUR) = 0
              MAXTIM = T + TRUN.(CURUSR, LEVEL(ICUR))
            END OF CONDITIONAL
            TRANSFER TO DECIDE
            :R
            :R.. 'EVENT' .E. 6, 'USR'('IUSR') CORE is of length 'ARG'
            .R..   just before entering waiting command
            .R..   or length changed while running
EVNT(6)     LENGTH(IUSER) = ARG
            TRANSFER TO CHANGE
            :R
            :R.. 'EVENT' .E. 2, 'USR'('IUSER') changed state
            :R..   dispatch on new state, ignore redundant transitions
EVNT(2)     WHENEVER USR .NE. 0, TRANSFER TO STAT(ARG)
            TRANSFER TO RETURN
            :R
            :R..    'USR'('IUSER') began waiting for a command
STAT(3)     LEV = LEVELF.(LENGTH(IUSER))
            WHENEVER STATUS(IUSER) .E. 2 .OR. STATUS(IUSER) .E. 3
              WHENEVER LEV .G. LEVEL(IUSER)
                EXECUTE DELQUE.(USR)
                TRANSFER TO COMAND
              END OF CONDITIONAL
            OTHERWISE
COMAND        LEVEL(IUSER) = LEV
              EXECUTE ENDQUE.(USR)
              TIMLEV(IUSER) = 0
              WATTIM(IUSER) = GETOTL.(0)
            END OF CONDITIONAL
            STATUS(IUSER) = 3
            TRANSFER TO DECIDE
            :R
            :R.. 'EVENT' .E. 10, is 'NEWUSR' still runable
EVNT(10)    WHENEVER STATUS(I.(NEWUSER)) .E. 2
            :1            .OR. STATUS(I.(NEWUSR)) .E. 3, TRANSFER TO RETURN
            SWAP = 0B
            TRANSFER TO DECIDE
            :R
            :R.. The next three events always occur in sequence
            :R..   when control is transferred from 'OLDUSR' to 'NEWUSR'
            :R..   as a result of 'SWAP' being set non-zero
            :R.. 'NEWUSR' pays for core freeup and his own load
            :R
            :R.. 'EVENT' .E. 3, saving of 'USR'('|USER') is beginning
            :R..  EVENT 3 may be called for any of hte following:
            :R    1. freeing up core B because 'CURUSR' extended size
            :R    2. freeing up core A drum buffers for swapping
            :R    3. dumping 'OLDUSR'
            :R    4. dumping other users to make room for 'NEWUSR'
            BOOLEAN SWPSW, FIRST3, SWAP
EVNT(3)     WHENEVER SWPSW
              WHENEVER FIRST3
                FIRST3 = 0B
                EXECUTE CHARGE.(PAYUSR, DELTIM.(PAYTIM))
                TIMLEV(I.(OLDUSR)) = TIMLEV(I.(OLDUSR)) + DELTIM.(LEVTIM)
                PAYUSR = NEWUSR
              END OF CONDITIONAL
              TRANSFER TO CHANGE
            END OF CONDITIONAL
            TRANSFER TO RETURN
            :R
            :R.. 'EVENT' .E. 4, RESTORING OF 'NEWUSR' is beginning
EVNT(4)     WHENEVER STATUS(I.(OLDUSR)) .E. 2,
            :1    WATTIM(I.(OLDUSR)) = GETOTL.(0)
            CURUSR = NEWUSR
            TRANSFER TO CHANGE
            :R
            :R.. 'EVENT' .E. 5, 'NEWUSR' begins running after restore
            :R.. NEWUSR's time allotment is set to the quantum at this
            :R.. level less his two-way swap time from drum, and less
            :R.. any time already run at this level
EVNT(5)     TDEL = DELTIM.(PAYTIM)
            WHENEVER TDEL .G. BGMAX
              EXECUTE CHARGE.(PAYUSR, BGMAX)
              EXECUTE CHARGE.(OLDUSR, TDEL-BGMAX)
            OTHERWISE
              OLDUSR = CURUSR
              BACKGR = 0
            END OF CONDITIONAL
            :R
            :R.. CALL MONSC2. IF COMMON CHANGED, ELSE JUST RETURN
            TRANSFER TO MONITR
            CHANGE CONTINUE
            EXECUTE MONSC2.
            EXECUTE PLOT2.
            RETURN FUNCTION RETURN
            :R
            :R
            :R.. Internal functions
            :R..   'TRUN' - computes run time for user 'DU' at level 'DL'
            INTERNAL FUNCTION TRUN.(DU, DL) = QUNATM*(2.P.DL)
            :R
            :R..   'LEVELF' - compute priority level based on length 'LEN'
            INTERNAL FUNCTION(LEN)
            ENTRY TO LEVELF.
            WHENEVER LEN .GE. FULLEN
              L = FULLVL
            OTHERWISE
              L = EMPLVL + ILOG2.(LEN/(FULLEN/(2 .P. (FULLVL-EMPLVL))))
            END OF CONDITIONAL
              FUNCTION RETURN L
            END OF FUNCTION
            :R
            :R..   'PREMPT' - is true if preemption is permitted
            :R..     based on time interrupter will run 'INTRUN'
            BOOLEAN PREEMPT.
            INTERNAL FUNCTION PREMPT.(INTRUN) =
            :1    INTRUN .L. GETOTL.(0) - BEGTIM
            :R
            :R
            :R.. Common variables
            INSERT FILE MADCOM
            :R.. user machine conditions status table
            :R..   (not referred to by mad programs)
            END OF FUNCTION