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.
http://i.stanford.edu/pub/cstr/reports/cs/tr/73/355/CS-TR-73-355.pdf