Page:CTSS programmer's guide.djvu/25

From Wikisource
Jump to navigation Jump to search
This page has been proofread, but needs to be validated.

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

11