Report Number: CS-TR-73-352
Institution: Stanford University, Department of Computer Science
Title: The expected difference between the SLTF and MTPT drum
scheduling disciplines (digest edition).
Author: Fuller, Samuel H.
Date: August 1972
Abstract: This report is a sequel to an earlier report [Fuller, 1971]
that develops a minimal-total-processing-time (MTPT) drum
scheduling algorithm. A quantitative comparison between MTPT
schedules and shortest-latency-time-first (SLTF) schedules,
commonly acknowledged as good schedules for drum-like storage
units, is presented here. The analysis develops an analogy to
random walks and proves several asymptotic properties of
collections of records on drums. These properties are
specialized to the MTPT and SLTF algorithms and it is shown
that for sufficiently large sets of records, the expected
processing time of a SLTF schedule is longer than a MTPT
schedule by the expected record length. The results of a
simulation study are also presented to show the difference in
MTPT and SLTF schedules for small sets of records and for
situations not covered in the analytic discussion.