On Optimal Processor Scheduling for Multiprogramming
Leonard J. Bass · SIAM Journal on Computing · 1973
This paper investigates the problem of scheduling a processor to optimize throughput in a multiprogramming environment. A deterministic model is used to study the scheduling of a batch of k programs residing in main memory of a system consisting of a single processor and k input–output devices in such a way as to minimize the time to complete all k jobs. It is shown that for any set of independent programs a preemptive strategy is not necessary to obtain the minimum running time for the entire batch. There is always an interrupt driven schedule which is as good as the best preemptive schedule. It is also shown that processor bound programs are easy to schedule. A lower bound on the completion time for any set of programs is observed, and it is shown that with processor bound programs the lower bound can always be obtained. An algorithm for obtaining this bound is given. These results provide some insight into the workings of the dynamic scheduling algorithms in use in many modern computer systems.