A process running on CTSS (Compatible Time Sharing System) needs 30 quanta to complete. How many times must it be swapped in, including the very first time (before it has run at all)?

• Answer : The first time it gets 1 quantum. On succeeding runs it gets 2, 4, 8, and 15, so it must be swapped in 5 times.

why does it get 2,4,8,15 on the succeeding runs?

  • 2
    $\begingroup$ Presumably because CTSS' scheduler works that way... $\endgroup$
    – vonbrand
    Jan 25, 2016 at 15:40
  • $\begingroup$ What way? Please explain it to me shortly :( $\endgroup$
    – Luna M
    Jan 25, 2016 at 15:51
  • 1
    $\begingroup$ You'll have to look at the algorithms that system uses. I don't know them, but the behaviour sounds reasonable. $\endgroup$
    – vonbrand
    Jan 25, 2016 at 16:01
  • 1
    $\begingroup$ What have you tried? Have you found the algorithm for how CTSS's time scheduler works? If yes, have you tried running it by hand to see what happens? If no, where have you looked? We expect you to make a significant effort to answer your question on your own before asking, and to tell us in the question what you tried. $\endgroup$
    – D.W.
    Jan 25, 2016 at 22:08

1 Answer 1


According to this article: F. J. Corbató, M. M. Daggett, R. C. Daley, An Experimental Time-Sharing System (IFIPS 1962), CTSS uses a "multi-level scheduling algorithm":

The basis of the multi-level scheduling algorithm is to assign each user program as it enters the system to be run (or completes a response to a user) to an $\text{ell}$-th level priority queue. The process starts with the time-sharing supervisor operating the program at the head of the lowest level occupied queue, $\text{ell}$, for up to $2^\text{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 $\text{ell}+1$ level queue. Programs are initially entered into a level $\text{ell} = 0$.

A program at the ell-th level is assigned $2^{\text{ell}}$ quanta.

Now you know how to solve your exercise.


Not the answer you're looking for? Browse other questions tagged or ask your own question.