A model for masking rotational latency by dynamic disk allocation

ABSTRACT

This paper presents the background and algorithms for masking the rotational latency of a disk or drum. It discusses the anticipatory input and output of blocks of data to buffer and primary memories for a mono-programmed computer system. A basic permutation algorithm and several variations are given. Because of the anticipatory nature of the I/O scheduling, these algorithms are restricted to classes of programs with predictable behavior. While the methods are not restricted to numerical computations, matrix and partial differential equation methods are typical examples of their use. It is shown that latency may be masked using a small amount of buffer memory. The methods discussed are independent of the overall size of the data base being considered.

REFERENCES

• 1: Baker, F.T. Chief programmer team management of production programming. IBM Syst. J. 11, I (1972), 56-73.
• 2: Bernott, B.A. Disk I/O for non-core-contained P.D.E. meshes and arrays. M.S. Th. Rep. 31 I, Dept. of Comput. Sci., U. of Illinois at Urbana-Champaign, Mar. 1969.
• 3: Fuller, S.H. An optimal drum scheduling algorithm. IEEE Trans. oil Comput. 21 (Nov. 1972), 1153-1165.
• 4: Gill, A. The optimal organization of serial memory transfers. IRE Trans. Elect. Comput. EC-9 (Mar. 1960), 12-15.
• 5: Gold, D.E., and Kuck, D.J. Implementation considerations for masking rotational latency by dynamic disk allocation. Dept. of Comput. Sci., U. of Illinois at Urbana-Champaign.
• 6: Hall, M. Jr. Combinatoricd Theory. Blaisdell, Waltham, Mass., 1967.
• 7: Donald E. Knuth, Minimizing Drum Latency Time, Journal of the ACM (JACM), v.8 n.2, p.119-150, April 1961 [doi>10.1145/321062.321063]
• 8: Opferman, D.C., and Tsao-Wu, N.T. On a class of rearrangeable switching networks, Pt I : Control algoritlam. Bell Syst. Tech. J. 50 (May-June 1971), 1579-1600.
• 9: Pugh, E.W. Storage hierarchies: gaps, cliffs and trends. IEEE Trans. oll Maw. WAG-7, 4 (Dec. 1971), 810-814.
• 10: Ryser, H.J. Combinatorial Mathematics. Wiley, New York, 1963.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Allocation/deallocation strategies

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.4 Communications Management
          Subjects: Buffering

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Permutations and combinations

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Scheduling

General Terms:
Algorithms

Keywords:
buffer memory, memory hierarchy, permutation algorithm, rotational latency, staging, storage allocation