Disk arm movement in anticipation of future requests

ABSTRACT

When a disk drive's access arm is idle, it may not be at the ideal location. In anticipation of future requests, movement to some other location may be advantageous. The effectiveness of anticipatory disk arm movement is explored. Various operating conditions are considered, and the reduction in seek distances and request response times is determined for them. Suppose that successive requests are independent and uniformly distributed. By bringing the arm to the middle of its range of motion when it is idle, the expected seek distance can be reduced by 25 percent. Nonlinearity in time versus distance can whittle that 25 percent reduction down to a 13 percent reduction in seek time. Nonuniformity in request location, nonPoisson arrival processes, and high arrival rates can whittle the reduction down to nothing. However, techniques are discussed that maximize those savings that are still possible under those circumstances. Various systems with multiple arms are analyzed. Usually, it is best to spread out the arms over the disk area. The both arms should be brought to the middle.

REFERENCES

• 1: ATWOOD, J. W., MACLEOD, A., AND Yu, K. An empirical study of a CDC 844-41 disk subsystem. Perform. Eval. 2 (1982), 29-56.
• 2: A. R. Calderbank , E. G. Coffman, Jr. , L. Flatto, Optimum Head Separation in a Disk System with Two Read/Write Heads, Journal of the ACM (JACM), v.31 n.4, p.826-838, Oct. 1984 [doi>10.1145/1634.1638]
• 3: CALDERBANK, i. R., COFFMAN, E. G., AND FLATTO, L. Sequencing problems in two-server systems. Math. Oper. Res. 10, 4 (Nov. 1985), 585-598.
• 4: COFFMAN, E. G., KLIMKO, L., AND RYAN, B. Analysis of scanning policies for reducing disk seek times. SIAM J. Comput. I, 3 (Sept. 1972), 269-279.
• 5: COFFMAN, U. G., JR., AND HOFRI, M. i class of FIFO queues arising in computer systems. Oper. Res. 26, 5 (Sept.-Oct. 1978), 864-880.
• 6: COHN, O. Personal communication, 1986.
• 7: 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]
• 8: Michael A. Crane , Donald L. Iglehart, Simulating Stable Stochastic Systems, II: Markov Chains, Journal of the ACM (JACM), v.21 n.1, p.114-123, Jan. 1974 [doi>10.1145/321796.321806]
• 9: CRANE, M. A., AND IGLEHART, D. Simulating stable stochastic systems, IV: Approximation techniques. Manage. Sci. 21, 11 (July 1975), 1215-1224.
• 10: DENNING, P.J. Effects of scheduling on file memory operations. In Proceedings of the AFIPS Spring Joint Computer Conference 30 (1967), pp. 9-21.
• 11: 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]
• 12: Robert Geist , Stephen Daniel, A continuum of disk scheduling algorithms, ACM Transactions on Computer Systems (TOCS), v.5 n.1, p.77-92, Feb. 1987 [doi>10.1145/7351.8929]
• 13: Robert Geist , Robert Reynolds , Eve Pittard, Disk scheduling in System V, ACM SIGMETRICS Performance Evaluation Review, v.15 n.1, p.59-68, May 1987
• 14: 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]
• 15: P. Heidelberger , P. A. W. Lewis, Regression-adjusted estimates for regenerative simulations, with graphics, Communications of the ACM, v.24 n.4, p.260-273, April 1981 [doi>10.1145/358598.358641]
• 16: Micha Hofri, Disk scheduling: FCFS vs.SSTF revisited, Communications of the ACM, v.23 n.11, p.645-653, Nov. 1980 [doi>10.1145/359024.359034]
• 17: HOFRI, M. Should the two-headed disk be greedy?--Yes, it should, inf. Process. Lett. 16 (Feb. 1983), 83-85.
• 18: HYDE, J.S. Personal communication, 1986.
• 19: 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]
• 20: MCNUTT, B. A case study of access to VM disk volumes. In CMG Proceedings (Dec. 1984), 175-180.
• 21: MCNUTT, B. The impact of 2-to-1 volume folding on seek time: A comparison of five cases. IBM General Products Div., TR 02.1219, (June 1985).
• 22: MCNUTT, B. Personal communication, 1989.
• 23: No, S.W. Design alternatives for disk duplexing. IBM Research, RJ 5481, Jan. 1987.
• 24: Walter C. Oney, Queueing Analysis of the Scan Policy for Moving-Head Disks, Journal of the ACM (JACM), v.22 n.3, p.397-412, July 1975 [doi>10.1145/321892.321902]
• 25: SCRANTON, R. A., THOMPSON, D. A., AND HUNTER, D. W. The access time myth. IBM Research, RC 10197, Sept. 1983.
• 26: Alan Jay Smith, Remark on "Disk Cashe—miss ratio analysis and design consideration", ACM Transactions on Computer Systems (TOCS), v.5 n.1, p.93-93, Feb. 1987 [doi>10.1145/7351.8930]
• 27: Toby Jackson Teorey, The role of disk scheduling in multiprogrammed computer systems, 1972
• 28: 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]
• 29: 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]

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Secondary storage

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.8 Performance
          Subjects: Modeling and prediction; Simulation

General Terms:
Algorithms, Performance