An Optimised CPU Scheduling Algorithm with Adaptive Time Quantum Approach

Open Access

Year : 2021 | Volume : | Issue : 2 | Page : 1-18
By

    Pradyut Nath

  1. Sumagna Dey

  2. Srija Nandi

  3. Subhrapratim Nath

  1. Students, Department of Computer Science and Engineering, Meghnad Saha Institute of Technology, West Bengal, India
  2. Department Head and Assistant Professor, Department of Computer Science and Engineering, Meghnad Saha Institute of Technology, West Bengal, India

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: Operating system, scheduling algorithms, weighted average, round robin, resource management

[This article belongs to Journal of Operating Systems Development & Trends(joosdt)]

How to cite this article: Pradyut Nath, Sumagna Dey, Srija Nandi, Subhrapratim Nath An Optimised CPU Scheduling Algorithm with Adaptive Time Quantum Approach joosdt 2021; 8:1-18
How to cite this URL: Pradyut Nath, Sumagna Dey, Srija Nandi, Subhrapratim Nath An Optimised CPU Scheduling Algorithm with Adaptive Time Quantum Approach joosdt 2021 {cited 2021 Aug 10};8:1-18. Available from: https://journals.stmjournals.com/joosdt/article=2021/view=90339

Full Text PDF Download

Browse Figures

References

1. 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.
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. 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.
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 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.
8. 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.
9. 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.
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 Marcus B. The Weighted Moving Average Technique. Wiley encyclopedia of operations research and management science; February 15, 2011. doi: 10.1002/9780470400531.eorms0964.
12. 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.
13. 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.
14. 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.
15. 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.
16. 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.
17. 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.


Regular Issue Open Access Article
Volume 8
Issue 2
Received July 1, 2021
Accepted July 27, 2021
Published August 10, 2021