Samuel H. Fuller
Abstract
This article investigates the application of minimal-total-processing-time (MTPT) scheduling disciplines to rotating storage units when random arrival of requests is allowed. Fixed-head drum and moving-head disk storage units are considered, and emphasis is placed on the relative merits of the MTPT scheduling discipline with respect to the shortest-latency-time-first (SLTF) scheduling discipline. The results of the simulation studies presented show that neither scheduling discipline is unconditionally superior to the other. For most fixed-head drum applications, the SLTF discipline is preferable to MTPT, but for intra-cylinder disk scheduling the MTPT discipline offers a distinct advantage over the SLTF discipline. The computational requirements of an algorithm that implements the MTPT scheduling discipline are shown to be comparable to SLTF algorithms. In both cases, the sorting procedure is the most time-consuming phase of the algorithm.
- 1 Abate, J., and Dubner, H. Optimizing the performance of a drum-like storage. IEEE Trans. on Computers C-18, 11 (Nov. 1969), 992-996.Google Scholar
Digital Library
- 2 Abate, J., Dubner, H., and Weinberg, S.B. Queueing analysis of the IBM 2314 disk storage facility. J. ACM 15, 4 (Oct. 1968), 557-589. Google ScholarDigital Library
- 3 Coffman, E.G. Analysis of a drum input/output queue under scheduling operation in a paged computer system. J. ACM 16, 1 (Jan. 1969), 73-90, and Erratum, J. ACM 16, 4 (Oct. 1969), 646. Google ScholarDigital Library
- 4 Denning, P.J. Effects of scheduling on file memory operations. Proc. AFIPS 1967 SJCC Vol. 30, AFIPS Press, Montvale, N.J., pp. 9 21.Google Scholar
- 5 Frank, H. Analysis and optimization of disk storage devices for time sharing systems. J. ACM16, 4 (Oct. 1969), 602-620. Google ScholarDigital Library
- 6 Fuller, S. H., and Baskett, F. An analysis of drum storage units. Tech. Rep. 26, Digital Syst. Lab., Stanford U., Stantord, Calif. (Aug. 1972). J. ACM (to appear). Google ScholarDigital Library
- 7 Fuller, S.H. A simulator of computer systems with storage units having rotational delays. Tech. Note 17, Digital Syst. Lab., Stanford U., Stanford, Calif., Aug. 1972.Google Scholar
- 8 Fuller, S.H. An optimal drum scheduling algorithm. IEEE Trans. on Computers C-21, 11 (Nov. 1972), 1153-1165.Google ScholarDigital Library
- 9 Fuller, S.H. Random arrivals and MTPT disk scheduling disciplines. Tech. Rep. 29, Digital Syst. Lab., Stanford U., Stanford, Calif., Aug. 1972. Google ScholarDigital Library
- 10 Fuller, S.H. The expected difference between the SLTF and MTPT drum scheduling disciplines. Tech. Rep. 28, Digital Syst. Lab., Stanford U., Stanford, Calif., Aug. 1972. Google ScholarDigital Library
- 11 IBM 3830 storage control and 3330 disk storage. Order No. GA26-1592-1.Google Scholar
- 12 Seaman, P.H., Lind, R.A., and Wilson, T.L. An analysis of auxiliary-storage activity. IBMSyst. J. 5, 3 (1969), 158-170.Google Scholar
- 13 Stone, H.S., and Fuller, S.H. On the near-optimality of the shortest-latency-time-first drum scheduling discipline. Comm. ACM 16, 6 (June 1973), 352-353. Google ScholarDigital Library
- 14 Teorey, T.J., and Pinkerton, T.B. A comparative analysis of disk scheduling policies. Comm. ACM 15, 3 (Mar. 1972), 177-184. Google ScholarDigital Library
Index Terms
- Minimal-total-processing time drum and disk scheduling disciplines
Recommendations
On the near-optimality of the shortest-latency-time-first drum scheduling discipline
For computer systems in which it is practical to determine the instantaneous drum position, a popular discipline for determining the sequence in which the records are to be accessed is the so-called shortest-latency-time-first, SLTF, discipline. When a ...
Summary of minimal-total-processing-time drum and disk scheduling disciplines
SOSP '73: Proceedings of the fourth ACM symposium on Operating system principlesThis article investigates the application of minimal-total-processing-time (MTPT) scheduling disciplines to rotating storage units when random arrival of requests is allowed. Fixed-head drum and moving-head disk storage units are considered and ...
Summary of minimal-total-processing-time drum and disk scheduling disciplines
This article investigates the application of minimal-total-processing-time (MTPT) scheduling disciplines to rotating storage units when random arrival of requests is allowed. Fixed-head drum and moving-head disk storage units are considered and ...
Comments