An anomaly in disk scheduling: a comparison of FCFS and SSTF seek scheduling using an empirical model for disk accesses

ABSTRACT

A model for disk accesses based on published measurements is developed. The model is used to show that under highly probable conditions, FCFS seek scheduling is superior to SSTF scheduling in the sense of having a lower mean queue length. A simple example of an arrival sequence illustrating this anomaly is presented.

REFERENCES

• 1: Denning, P.J. Effects of scheduling on file memory operations. AFIPS Conf. Proc., Vol. 30, 1967 SJCC, AFIPS Press, Montvale, N.J., 1967, pp. 9--21.
• 2: H. Frank, Analysis and Optimization of Disk Storage Devices for Time-Sharing Systems, Journal of the ACM (JACM), v.16 n.4, p.602-620, Oct. 1969 [doi>10.1145/321541.321550]
• 3: Toby J. Teorey , Tad B. Pinkerton, A comparative analysis of disk scheduling policies, Communications of the ACM, v.15 n.3, p.177-184, March 1972 [doi>10.1145/361268.361278]
• 4: Teorey, T.J. Properties of disk scheduling policies in multiprogrammed computer systems. AFIPS Conf. Proc., Vol. 41, 1972 FJCC AFIPS Press, Montvale, N.J., 1972, pp. 1-11.
• 5: Samuel H. Fuller, Minimal-total-processing time drum and disk scheduling disciplines, Communications of the ACM, v.17 n.7, p.376-381, July 1974 [doi>10.1145/361011.361062]
• 6: C. C. Gotlieb , G. H. MacEwen, Performance of Movable-Head Disk Storage Devices, Journal of the ACM (JACM), v.20 n.4, p.604-623, Oct. 1973 [doi>10.1145/321784.321789]
• 7: W. C. Lynch, Do disk arms move?, ACM SIGMETRICS Performance Evaluation Review, v.1 n.4, p.3-16, December 1972 [doi>10.1145/1041603.1041604]
• 8: Cox, D.R., and Smith, W.L. Queues. Chapman and Hall, London, 1961.
• 9: Wilhelm, N.C. A general model for the performance of disk systems (unpublished).
• 10: Wilhelm, N.C., Analysis of FCFS and SSTF seek scheduling using an empirical model for disk accesses. Tech. Rep. 64, Digital Systems Lab., Stanford U., Aug. 1973.
• 11: Michael A. Crane , Donald L. Iglehart, Simulating Stable Stochastic Systems, I: General Multiserver Queues, Journal of the ACM (JACM), v.21 n.1, p.103-113, Jan. 1974 [doi>10.1145/321796.321805]

INDEX TERMS

Keywords:
disk scheduling, disks, seek scheduling