Page:CTSS programmer's guide.djvu/25

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]$$

11