Email this article 
Open Access
Subscription or Fee Access
Optimal Real Time Disk Scheduling Algorithms for Tasks with Fixed Deadlines
Abstract
This paper summarizes the state of the art algorithms in the areas of scheduling and operating system kernels suited for real time. Given the vast amount of work that has been done by both the operations research and computer science communities in the scheduling area, five traditional scheduling approaches are discussed. A good scheduling algorithm should be fast and fair and should be able to serve as many I/O requests as possible in a given period of time, while not causing starvation for some requests. The two main concerns of disk scheduling algorithms are, therefore, to reduce the total time needed to serve a number of requests (access time) and the average time between the arrival of requests and them being served (waiting time). The access time for any I/O consists of the time needed for the disk arm to move the head to the requested track (seek time) in addition to the time required for the disk to rotate to the specified sector on track (rotational latency). The dominant factor of the access time is the seek time; hence, rotational latency is usually ignored by scheduling algorithms. Traditional real-time disk-scheduling algorithms service real time tasks according to their deadlines. Such a priority based algorithm, although satisfying real-time constraints, yields low disk utilization due to the excessive disk-seek time. Furthermore, it results in prolonged response time or even starvation for periodic tasks. The problem of disk scheduling to enhance disk performance is presented. According to the results obtained, the best competing of the conventional scheduling algorithms are the C-LOOK and the LOOK algorithms.
Keywords
References
Prashant Shenoyy Harrick M. Vin, ‘ Cello: A Disk Scheduling Framework for Next Generation Operating Systems’ Department of Computer Science, Department of Computer Sciences, University of Massachusetts at Amherst University of Texas at Austin Amherst, MA 01003 Austin, TX 78712, June 1998.
Kartik Gopalan and Tzi-cker Chiueh. ,‘Real-time disk scheduling using deadline sensitive SCAN’ Technical Report TR-92, Experimental Computer Systems Labs, Dept. of Computer Science, State University of New York, Stony Brook, NY, January 2001.
Wenming Li, Krishna Kavi , Robert ,‘A non-preemptive scheduling algorithm for soft real-time systems’ The University of North Texas, Computer Science and Engineering, P.O. Box, 311366, Denton TX 76203, United States Akl, January 2006.
Saman Zarandioon and Alexander Thomasian, ‘Optimization of online disk scheduling algorithms’. ACM SIGMETRICS Performance Evaluation Review, March 2006, pages 42-46.
T. Kim, J. Park, S. Ahn, K. Koh, Y. Won, and H.Bahn, ‘A heuristic-based real-time disk scheduling Algorithm for mixed-media workload’ , in IMSA’06:Proceedings of the 24th IASTED international conference on Internet and multimedia systems and applications. Anaheim, CA, USA: ACTA Press, 2006, pp. 165–170.
H.-P. Chang, R.-I. Chang, W.-K. Shih and R.-C. Chang, ‘GSR: A global seek-optimizing real-time disk scheduling algorithm’, Journal of System Software, vol. 80, no. 2, February 2007, pp. 198–215.
A. Povzner, T. Kaldewey, S. Brandt, R. Golding, T. M. Wong, and C. Maltzahn, ‘Efficient guaranteed disk request scheduling with fahrrad’ , SIGOPS Oper. Syst. Rev., vol. 42, no. 4,July 2008, pp. 13–25.
Ammar Muqaddas, Hanady Abdulsalam, and Ayed Salman, ‘S-LOOK: A Preemptive Disk Scheduling Algorithm for Offline and Online Environments’ Computer Science & Information Technologies, Lviv, Ukraine, October 2009.
Abhinav Gupta Qualcomm, Xiaojun Lin, R. Srikant, ‘Low-complexity distributed scheduling algorithms for wireless networks’ Published in IEEE/ACM Transactions on Networking (TON) archive Volume 17 Issue 6, December 2009 .
S.Y.Amdani, G.R.Bamnote, H.R.Deshmukh, S.A.Bhura, ‘A Novel Disk Scheduling Algorithm in Real-time Database Systems’ International Journal of Computer Applications, Published By Foundation of Computer Science© 2010 by IJCA Journal Number 29 – Article 1, February 2010.
Mukil Kesavan, Ada Gavrilovska, Karsten Schwan, ‘On Disk I/O Scheduling in Virtual Machines’ published in the Second Workshop on I/O Virtualization (WIOV’10), Pittsburgh, PA, USA, March 2010.
Valente, P.,Checconi, F.;Univ. di Modena e Reggio Emilia, Modena, Italy, ‘High Throughput Disk Scheduling with Fair Bandwidth Distribution ’Published in Computers, IEEE Transactions, Volume: 59 Issue:9, Sept. 2010 ,On page(s): 1172 - 1186 ,ISSN: 0018-9340.
Hossein Rahmani, Mohammad Reza Bonyadi, Amir Momeni, Mohsen Ebrahimi Moghaddam, Maghsoud Abbaspour, ‘Hardware design of a new genetic based disk scheduling method’, Published in: Journal Real-Time Systems, Volume 47 Issue 1, Kluwer Academic Publishers Norwell, MA, USA, January 2011.
Chou, J., Jinoh Kim; Rotem, D.; ‘Energy-Aware Scheduling in Disk Storage Systems’ Published in International Conference, Distributed Computing Systems (ICDCS), June 2011, On page(s): 423 – 433, Minneapolis, MN ,ISSN: 1063-6927.
Ibrahim, S.; Hai Jin; Lu Lu; Bingsheng He; Song Wu;Cluster & Grid Computer. Lab., Huazhong Univ. of Sci. & Technol., Wuhan, China, ‘Adaptive Disk I/O Scheduling for MapReduce in Virtualized Environment’ published in International Conference in Parallel Processing (ICPP) , Sept. 2011, On page(s): 335 – 344,Taipei City, ISSN: 0190-3918.
Refbacks
- There are currently no refbacks.
This work is licensed under a Creative Commons Attribution 3.0 License.