Optimization of online disk scheduling algorithms

ABSTRACT

Disk scheduling policies have a significant effect on disk performance. SPTF is one of the well-known policies that can increase disk performance near to optimality [1]. One of the drawbacks of the regular implementation of SPTF is its high computational cost. "The computational cost [of SPTF] (as indicated crudely by our simulation times) is very high" [2]. This paper shows that computational cost of SPTF is not the characteristic of SPTF, but it is a matter of implementation. The experience shows that this approach can improve the efficiency over 80% compared to naïve implementation. Finally, an algorithm for efficient implementation of lookahead algorithms is introduced.

REFERENCES

• 1: G. Gallo, F. Malucelli, and M. Marre. "Hamiltonian Paths Algorithms For Disk Scheduling", Technical Report 20/94, Dipartimento di Informatica, Universita di Pisa, 1994
• 2: Bruce L. Worthington , Gregory R. Ganger , Yale N. Patt, Scheduling algorithms for modern disk drives, Proceedings of the 1994 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.241-251, May 16-20, 1994, Nashville, Tennessee, United States
• 3: D. M. Jacobson and J. Wilkes. "Disk scheduling algorithms based on rotational position", Technical Report HPLCSP-91-7, HP Labs, 1991.
• 4: M. Andrews, M. A. Bender, and L. Zhang. "New Algorithms for the Disk Scheduling Problem." Algorithmica, 32(2): 277--301, 2002
• 5: Alexander Thomasian , Chang Liu, Disk scheduling policies with lookahead, ACM SIGMETRICS Performance Evaluation Review, v.30 n.2, September 2002 [doi>10.1145/588160.588165]

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.4 Communications Management
          Subjects: Input/output

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Mass storage (e.g., magnetic, optical, RAID)

  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques; Reliability, availability, and serviceability

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Scheduling
      D.4.3 File Systems Management

General Terms:
Algorithms, Design, Management, Performance

Keywords:
SPTF, disk scheduling, online scheduling, shortest positioning time first