STM Journals Peer-reviewed research from Consortium e-Learning Network

Journal of Operating Systems Development & Trends Article Open Access

An Optimised CPU Scheduling Algorithm with Adaptive Time Quantum Approach

  1. Pradyut Nath Department of Computer Science and Engineering, Meghnad Saha Institute of Technology
  2. Sumagna Dey Department of Computer Science and Engineering, Meghnad Saha Institute of Technology
  3. Srija Nandi
  4. Subhrapratim Nath

Abstract

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.

Keywords

References (17)

  1. Hanish AA. Operating systems and communication protocols. Proceedings of International Workshop on Object Orientation in Operating Systems. 166-170. doi:10.1109/iwoos.1995.470561
  2. Process scheduling: long, medium, short-term scheduler. Available from: guru99.com [cited Feb 1, 2021]. Available from: https://www.guru99.com/process-scheduling.html.
  3. Sanjoy Baruah. The limited-preemption uniprocessor scheduling of sporadic task systems. 17th Euromicro Conference on Real-Time Systems (ECRTS'05). 2005:137-144. doi:10.1109/ecrts.2005.32
  4. 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.
  5. 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.
  6. Mili. Patel, Rakesh P, SJRR CPU scheduling algorithm International Journal of Engineering and Computer Science. 2013;2(12).
  7. Dash AR, Sahu SK, Samantra SK. An Optimized Round Robin CPU Scheduling Algorithm with Dynamic Time Quantum. International Journal of Computer Science, Engineering and Information Technology. 2015;5(1):07-26. doi:10.5121/ijcseit.2015.5102
  8. Fang Z. A Weight-Based Multiobjective Genetic Algorithm for Flowshop Scheduling. 2009 International Conference on Artificial Intelligence and Computational Intelligence. 2009:373-377. doi:10.1109/aici.2009.130
  9. Arunekumar NB, Kumar A, Joseph KS. Hybrid bat inspired algorithm for multiprocessor real-time scheduling preparation. 2016 International Conference on Communication and Signal Processing (ICCSP). 2016:2194-2198. doi:10.1109/iccsp.2016.7754572
  10. Patel Jyotirmay, Solanki AK. Performance evaluation of CPU scheduling by using hybrid approach. Int J Eng Res Technol (IJERT). 2012;1(June).
  11. Perry MB. The Weighted Moving Average Technique. Wiley Encyclopedia of Operations Research and Management Science. 2011. doi:10.1002/9780470400531.eorms0964
  12. Balharith T, Alhaidari F. Round Robin Scheduling Algorithm in CPU and Cloud Computing: A review. 2019 2nd International Conference on Computer Applications & Information Security (ICCAIS). 2019:1-7. doi:10.1109/cais.2019.8769534
  13. A.Rajguru A, S. Apte S. A Performance Analysis of Task Scheduling Algorithms using Qualitative Parameters. International Journal of Computer Applications. 2013;74(19):33-38. doi:10.5120/13004-0308
  14. Dhotre S, Patil S. Cause of process starvation for linux completely fair scheduler with apache server. 2017 International Conference on Computing Methodologies and Communication (ICCMC). 2017:814-819. doi:10.1109/iccmc.2017.8282579
  15. Matarneh RJ. Self-Adjustment Time Quantum in Round Robin Algorithm Depending on Burst Time of the Now Running Processes. American Journal of Applied Sciences. 2009;6(10):1831-1837. doi:10.3844/ajassp.2009.1831.1837
  16. Behera HS, Mohanty R, Nayak D. A New Proposed Dynamic Quantum with Re-Adjusted Round Robin Scheduling Algorithm and Its Performance Analysis. International Journal of Computer Applications. 2010;5(5):10-15. doi:10.5120/913-1291
  17. Singh M, Agrawal R. Modified Round Robin algorithm (MRR). 2017 IEEE International Conference on Power, Control, Signals and Instrumentation Engineering (ICPCSI). 2017:2832-2839. doi:10.1109/icpcsi.2017.8392238
Support