Skip to main content
SpringerLink
Log in

Amortized analysis of some disk scheduling algorithms: SSTF, SCAN, andN-StepSCAN

  • Part I Computer Science
  • Published:
BIT Numerical Mathematics Aims and scope Submit manuscript

Abstract

The amortized analysis is a useful tool for analyzing the time-complexity of performing a sequence of operations. The disk scheduling problem involves a sequence of requests in general. In this paper, the performances of representative disk scheduling algorithms,SSTF, SCAN, andN-StepSCAN, are analyzed in the amortized sense. A lower bound of the amortized complexity for the disk scheduling problem is also derived. According to our analysis,SCAN is not only better thanSSTF andN-StepSCAN, but also an optimal algorithm. Various authors have studied the disk scheduling problem based on some probability models and concluded that the most acceptable performance is obtained fromSCAN. Our result therefore supports their conclusion.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. J. L. Bentley and C. C. McGeoch,Amortized analyses of self-organizing sequential heuristics, Comm. ACM 28, No. 4 (1985), pp. 404–411.

    Article  Google Scholar 

  2. T. S. Chen, W. P. Yang and R. C. T. Lee,Amortized analyses of disk scheduling algorithms: SSTF and SCAN, Proc. of National Computer Symposium, Taiwan, R.O.C., (1989), pp. 831–836.

  3. T. S. Chen and W. P. Yang,Amortized analysis for a continuum of disk scheduling V(R), Proc. of International Conference on Information and Systems, AMSE, Hangzhou, China, (1991), pp. 1277–1280.

    Google Scholar 

  4. E. G. Coffman, L. A. Klimko and B. Ryan,Analysis of scanning policies for reducing disc seek times, SIAM Journal on Computing, 1, (1972), pp. 269–279.

    Article  MATH  Google Scholar 

  5. H. M. Deitel,Operating Systems (Second Edition), Addison-Wesley Publishing Co. Reading Mass., (1990).

    Google Scholar 

  6. P. J. Denning,Effects of scheduling on file memory operations, Proc. AFIPS, Montvale, N.J., (1967), pp. 9–21.

    Google Scholar 

  7. M. L. Fredman, R. Sedgewick, D. D. Sleator and R. E. Tarjan,The pairing heap: a new form of self-adjusting heap, Algorithmica No. 1 (1986), pp. 111–129.

  8. H. Frank,Analysis and optimization of disk storage devices for time sharing systems, J. ACM 16, No. 4 (1969), pp. 602–620.

    Article  MATH  Google Scholar 

  9. R. Geist and S. Daniel,A continuum of disk scheduling algorithms, ACM Trans. Computer Syst. 5, No. 1 (1987), pp. 77–92.

    Article  Google Scholar 

  10. E. F. Grove,The harmonic online k-server algorithm is competitive, In Proc. 23rd ACM Symposium on Theory of Computing, (1991), pp. 260–266.

  11. M. Hofri,Disk scheduling FCFS vs. SSTF revisited, Comm. ACM 23, No. 11 (1980), pp. 645–653.

    Article  Google Scholar 

  12. R. C. T. Lee, R. C. Chang and S. S. Tseng,Introduction to the Design and Analysis of Algorithms, Prentice Hall, (1989).

  13. M. Manasse, L. A. McGeoch and D. D. Sleator,Competitive algorithms for on-line problems, In Proc. 20th Annual ACM Symposium on Theory of Computing, (1988), pp. 322–333.

  14. M. Manasse, L. A. McGeoch and D. D. Sleator,Competitive algorithms for server problems, Journal of Algorithms, 11 (1990), pp. 208–230.

    Article  MATH  MathSciNet  Google Scholar 

  15. B. M. E. Moret and H. D. Shapior,Algorithms from P to NP, Volume I: Design and Efficiency, The Benjamin/Cummings Publishing Company, Inc. Redwood City, CA 94065 (1991).

    Google Scholar 

  16. P. W. Purdom, Jr. and C. A. Brown,The Analysis of Algorithms, CBS College Publishing, (1985).

  17. A. Silberschatz and J. L. Peterson,Operating System Concepts, Addison-Wesley Publishing, Reading Mass., (1988), pp. 263.

    Google Scholar 

  18. D. D. Sleator and R. E. Tarjan,Self-adjusting binary search trees, J. Assoc. Comput. Mach. 32, No. 3 (1985), pp. 652–686.

    MATH  MathSciNet  Google Scholar 

  19. D. D. Sleator and R. E. Tarjan,Self-adjusting heaps, SIAM J. Comput. 15, No. 1 (1986), pp. 52–69.

    Article  MATH  MathSciNet  Google Scholar 

  20. R. E. Tarjan,Data structure and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, Pa., (1983).

    Google Scholar 

  21. R. E. Tarjan,Amortized computational complexity, SIAM J. Alg. Disc. Math. 6, No. 2 (1985), 306–318.

    Article  MATH  MathSciNet  Google Scholar 

  22. T. J. Teorey and T. B. Pinkerton,A comparative analysis of disk scheduling policies, Comm. ACM 15, No. 3 (1972), pp. 177–194.

    Article  MATH  Google Scholar 

  23. N. C. Wilhelm,An anomaly in disk scheduling: a comparison of FCFS and SSTF seek scheduling using an empirical model for disk accesses, Comm. ACM 19, No. 1 (1976), 13–17.

    Article  MATH  Google Scholar 

  24. W. P. Yang and T. S. Chen,The study of amortized complexity on disk system, Technical Report, NSC79-0408-E009-01, National Chiao Tung University, Hsinchu, Taiwan, R.O.C., (1989).

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science and Information Engineering, National Chiao Tung University, Hsinchu, Taiwan, ROC

    Tung-Shou Chen, Wei-Pang Yang & R. C. T. Lee

  2. Department of Computer and Information Science, National Chiao Tung University, Hsinchu, Taiwan, ROC

    Tung-Shou Chen, Wei-Pang Yang & R. C. T. Lee

  3. Department of Computer Science, National Tsing Hua University, Hsinchu, Taiwan, ROC

    Tung-Shou Chen, Wei-Pang Yang & R. C. T. Lee

Authors
  1. Tung-Shou Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Wei-Pang Yang
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. R. C. T. Lee
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

This research was supported by the National Science Council, Taiwan R. O. C. under contract: NSC80-0408-E009-11.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Chen, TS., Yang, WP. & Lee, R.C.T. Amortized analysis of some disk scheduling algorithms: SSTF, SCAN, andN-StepSCAN. BIT 32, 546–558 (1992). https://doi.org/10.1007/BF01994839

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01994839

CR categories

Keywords

Search

Navigation