Nail AKAR, Çağlar TUNÇ, Mark GAERTNER, Fatih ERDEN

Disk scheduling with shortest cumulative access time first algorithms

A new class of scheduling algorithms is proposed for disk drive scheduling. As opposed to choosing the request with the shortest access time in conventional shortest access time first (SATF) algorithms, we choose an ordered sequence of pending I/O requests at the scheduling instant with the shortest cumulative access time. Additionally, we introduce flexibility for forthcoming requests to alter the chosen sequence. Simulation results are provided to validate the effectiveness of the proposed disk scheduler. Throughput gains of 3% and above are shown to be attainable, although this occurs at the expense of increased computational complexity.

PDF

___

[1] Deng Y. What is the future of disk drives, death or rebirth? ACM Comput Surv 2011; 43: 1-27.
[2] Arpaci-Dusseau RH, Arpaci-Dusseau AC. Operating Systems: Three Easy Pieces. Madison, WI, USA: ArpaciDusseau Books, 2015.
[3] Thomasian A. Survey and analysis of disk scheduling methods. ACM Comp Ar 2011; 39: 8-25.
[4] Denning PJ. Effects of scheduling on file memory operations. In: ACM 1967 Spring Joint Computer Conference; 1820 April 1967; Atlantic City, NJ, USA. New York, NY, USA: ACM. pp 9-21.
[5] Teorey TJ, Pinkerton TB. A comparative analysis of disk scheduling policies. ACM Commun 1972; 15: 177-184.
[6] Coffman EG, Klimko LA, Ryan B. Analysis of scanning policies for reducing disk seek times. SIAM J Comput 1972; 1: 269-279.
[7] Merten AG. Some quantitative techniques for file organization. PhD, University of Wisconsin, Madison, WI, USA, 1970.
[8] Geist R, Daniel S. A continuum of disk scheduling algorithms. ACM T Comput Syst 1987; 5: 77-92.
[9] Chen TS, Yang WP, Lee R. Amortized analysis of some disk scheduling algorithms: SSTF, SCAN, and N-Step SCAN. BIT 1992; 32: 546-558.
[10] Jacobson DM, Wilkes J. Disk Scheduling Algorithms Based On Rotational Position. Palo Alto, CA, USA: Hewlett Packard, 1991.
[11] Seltzer M, Chen P, Ousterhout J. Disk scheduling revisited. In: USENIX 1990 Technical Conference; 2226 January 1990; Washington, DC, USA. Anaheim, CA, USA: USENIX Association. pp. 313-324.
[12] Thomasian A, Liu C. Some new disk scheduling policies and their performance. In: ACM 2002 Measurement and Modeling of Computer Systems Conferences; 1519 June 2002; Marina del Rey, CA, USA. New York, NY, USA:ACM. pp. 266-267.
[13] Worthington BL, Ganger GR, Patt YL. Scheduling algorithms for modern disk drives. In: ACM 1994 Measurement and Modeling of Computer Systems Conference; 1620 May 1994; Nashville, TN, USA. New York, NY, USA: ACM.pp 241-251.
[14] Zhang AB. New algorithms for disk scheduling. Algorithmica 2002; 32: 277-301.
[15] Bachmat E. Average case analysis of disk scheduling, increasing subsequences and spacetime geometry. Algorithmica 2007; 49: 212-231.
[16] Mahesh Kumar MR, Renuka Rajendra B. An improved approach to maximize the performance of disk scheduling algorithm by minimizing the head movement and seek time using sort mid current comparison (SMCC) algorithm.Procedia Comput Sci 2015; 57: 222-231.
[17] Hooda P, Raheja S. A new approach to disk scheduling using fuzzy logic. J Comput Commun 2014; 2: 1-5.