Disk scheduling: FCFS vs.SSTF revisited

ABSTRACT

We report on a rather extensive simulation effort directed at evaluating the merits of two scheduling strategies, FCFS and SSTF, for moving-arm disks under stationary request arrival process. For First-Come-First-Served (FCFS) scheduling, analytic results for the mean waiting time are also given (in a closed form). If the objective of a schedule is to minimize the mean waiting time (or queue size) and its variance, the results seem to confirm the overall superiority of Shortest-Seek-Time-First (SSTF), particularly for medium and heavy traffic. This holds also when the input is highly correlated or addresses the cylinders nonuniformly. These results contradict some statements published in recent years. The domain of policies where SSTF is optimal is considered. The simulation methodology is described in some detail.

REFERENCES

• 1: L. Boi , Patrice Cros , J. P. Drucbert , J. Y. Rousselot , Paul Bourret , R. Trepos, A Performance Evaluation of the CII SIRIS 8 Operating System. Methodology, Tools and First Results, Proceedings of the International Workshop organized by the Commision of the European Communities on Modelling and Performance Evaluation of Computer Systems, p.67-80, October 04-06, 1976
• 2: Coffman, E.G., Jr., and Hofri, M. A class of FIFO queues arising in computer systems. Operations Res. 26, 5 (Sept.-Oct. 1978), 864- 880.
• 3: 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]
• 4: Hofri, M. Queueing phenomena at computing storage devices. TR #78, Dept. of ComPtr. Sci., Technion, Israel Inst. of Technology, June 1976.
• 5: Neuts, M.F. Some explicit formulas for the steady-state behavior of a queue with semi-Markovian service times. Adv. AppL Prob. 9, 1 (Jan. 1977), 141-157.
• 6: Neil C. Wilhelm, An anomaly in disk scheduling: a comparison of FCFS and SSTF seek scheduling using an empirical model for disk accesses, Communications of the ACM, v.19 n.1, p.13-17, Jan. 1976 [doi>10.1145/359970.359977]
• 7: Lippman, S.A. Applying a new device in the optimization of exponential queueing systems. Operations Res. 23, 4 (July-Aug. 1975), 687-710.
• 8: Teorey, T.J. Properties of disk scheduling policies in multiprogrammed computer systems. Proc. AFIPS Fall Joint Comptr. Conf., Vol. 41, Arlington, Va., 1972, pp. 1-11.

INDEX TERMS

Keywords:
FCFS, SSTF, correlated input, moving-arm disk, optimal schedule, scheduling, simulation