An Optimised CPU Scheduling Algorithm with Adaptive Time Quantum Approach
Keywords:
Operating System, Scheduling Algorithms, Weighted Average, Round Robin, Resource ManagementAbstract
CPU scheduling is an essential mechanism implemented by the operating system to determine the execution of multiple processes by the CPU. The primary objective of the scheduling algorithms is to optimize the systems’ performance efficiently. The performance of a CPU scheduling algorithm depends on various factors and can be evaluated on various criteria like average turnaround time, average waiting time, throughput, fairness etc. This paper aims to present an optimal CPU scheduling algorithm, Adaptive Quantum Round Robin (AQRR) in a uniprocessor environment. Related work has been done on increasing the performance of existing Round Robin Algorithms using dynamic time quantum approaches, but the maximum percentage gain in turnaround time and waiting time using these approaches, over the traditional Round Robin algorithm is not more than 30% and 40% respectively. The proposed algorithm in this paper outperforms these algorithms in both turnaround time and waiting time. The AQRR algorithm is based on the standard Round Robin algorithm, but it is integrated with a dynamic time quantum which is self-adaptive triggered on the event of the arrival of new processes in the ready queue or the completion of a process in the process queue. The dynamic time quantum is updated based on the remaining burst time of the running processes in the process queue at that instance as well as a weightage associated with it. Finally, a comparative study between the prevailing similar scheduling algorithms and the proposed algorithm is observed and noted, based on different scenarios. The following algorithms are compared on two criteria: average turnaround time and average waiting time.
References
Hanish AA. Operating systems and communication protocols. Proceedings of the international workshop on object orientation in operating systems; 1995. p. 166-70. doi: 10.1109/IWOOS.1995.470561.
Process scheduling: long, medium, short-term scheduler. Available from: guru99.com [cited Feb 1, 2021]. Available from: https://www.guru99.com/process-scheduling.html.
Baruah Sanjoy. The limited-preemption uniprocessor scheduling of sporadic task systems 17th Euromicro Conference on Real-Time Systems (ECRTS’05); 2005. p. 137-44. doi: 10.1109/ECRTS.2005.32.
Kameda H. CPU scheduling for effective multiprogramming. Lecture Notes in Computer Science IBM Germany Sci Symposium Series 1980 Oct 1. 1982:(104-18). doi: 10.1007/3-540-11604-4_50.
Goel Neetu, Garg RB. A comparative study of CPU scheduling algorithms. Int J Graph Image Process. November 2012, Available from: arXiv:1307.4165 [cs.OS];2.
Mili. Patel, Rakesh P, SJRR CPU scheduling algorithm International Journal of Engineering and Computer Science. 2013;2(12).
Dash Amar Ranjan, Sahu Sk, Samantra SK. An optimized round robin CPU scheduling algorithm with dynamic time quantum. IJCSEIT. 2015;5(1, February):07-26. doi: 10.5121/ijcseit.2015.5102.
Fang Z. A weight-based multiobjective genetic algorithm for Flowshop scheduling International Conference on Artificial Intelligence and Computational Intelligence. Vol. 2009; 2009. p. 373-7. doi: 10.1109/AICI.2009.130.
Arunekumar NB, Kumar A, Joseph KS. Hybrid bat inspired algorithm for multiprocessor real-time scheduling preparation International Conference on Communication and Signal Processing (ICCSP). Vol. 2016; 2016. p. 2194-8. doi: 10.1109/ICCSP.2016.7754572.
Patel Jyotirmay, Solanki AK. Performance evaluation of CPU scheduling by using hybrid approach. Int J Eng Res Technol (IJERT). 2012;1(June).
Perry Marcus B. The Weighted Moving Average Technique. Wiley encyclopedia of operations research and management science; February 15, 2011. doi: 10.1002/9780470400531.eorms0964.
Balharith T, Alhaidari F. Round Robin Scheduling Algorithm in CPU and Cloud Computing: a review 2nd International Conference on Computer Applications & Information Security (ICCAIS). Vol. 2019; 2019. p. 1-7. doi: 10.1109/CAIS.2019.8769534.
Rajguru AA, Apte SS. A performance analysis of task scheduling algorithms using qualitative parameters. Int J Comput Appl;74(19):33-8. doi: 10.5120/13004-0308.
Dhotre S, Patil S. Cause of process starvation for Linux completely fair scheduler with Apache server International Conference on Computing Methodologies and Communication (ICCMC). Vol. 2017; 2017. p. 814-9. doi: 10.1109/ICCMC.2017.8282579.
Matarneh Rami J. Self-adjustment time quantum in round robin algorithm depending on burst time of the now running processes. Am J Appl Sci. 2009;6(10):1831-7. doi: 10.3844/ajassp.2009.1831.1837.
Dr. Behera HS, Mohanty R, Nayak D. A new proposed dynamic quantum with Re-adjusted round robin scheduling algorithm and its performance analysis. Int J Comput Appl. August 2010;5(5):10-5. doi: 10.5120/913-1291.
Singh M, Agrawal R. Modified Round Robin algorithm (MRR) IEEE International Conference on Power, Control, Signals and Instrumentation Engineering. 2017; p. 2832-9. doi: 10.1109/ICPCSI.2017.8392238.
