Report Number: CS-TR-73-355
Institution: Stanford University, Department of Computer Science
Title: An analysis of central processor scheduling in
multiprogrammed computer systems (digest edition).
Author: Price, Thomas G.
Date: October 1972
Abstract: A simple finite source model is used to gain insight into the
effect of central processor scheduling in multiprogrammed
computer systems. CPU utilization is chosen as the measure of
performance and this decision is discussed. A relation
between CPU utilization and flow time is developed. It is
shown that the shortest-remaining-processing-time discipline
maximizes both CPU utilization and I/O utilization for the
queueing model M/G/1/N. An exact analysis of processor
utilization using shortest-remaining-processing-time
scheduling for systems with two jobs is given and it is
observed that the processor utilization is independent of the
form of the processing time distribution. The effect of the
CPU processing time distribution on performance is discussed.
For first-come-first-served scheduling, it is shown that
distributions with the same mean and variance can yield
significantly different processor utilizations and that
utilization may or may not significantly decrease with
increasing variance. The results are used to compare several
scheduling disciplines of practical interest. An approximate
expression for CPU utilization using
shortest-remaining-processing-time scheduling in systems with
N jobs is given.