Advances In CPU Scheduling Algorithms in Operating Systems
DOI:
https://doi.org/10.54097/9g6zbb91Keywords:
CPU scheduling algorithms; Performance; Round Robin; Time-Sharing System; Embedded System.Abstract
CPU scheduling algorithms significantly influence Operating System (OS) performance. Many studies have proposed optimized scheduling algorithms. This paper outlines the main characteristics of common scheduling algorithms, including First Come First Served (FCFS), Shortest Job First (SJF), Round Robin (RR), Priority Scheduling, and Highest Response Ratio Next (HRRN). It reviews comparative performance research on these algorithms and mentions their optimizations to summarize the progress in this field. This paper also analyses two specific operating systems - Time-Sharing Systems and Embedded Systems, and introduces scheduling algorithms applicable to these two systems and their typical applications. The review finds that SJF & SPTF perform better than FCFS and RR in terms of waiting time, while HRRN also significantly outperforms RR. The optimization of the scheduling algorithm mainly focuses on RR, by clustering techniques and dynamically resizing the quantum time. For time-sharing systems, RR is the most common strategy, while the Linux kernel adopts the Completely Fair Scheduler (CFS). For embedded systems, the real-time scheduling algorithms, Earliest Deadline First(EDF) and Least Slack Time(LST), are applicable to soft real-time systems.
Downloads
References
[1] Harki N, Ahmed A, Haji L. CPU scheduling techniques: A review on novel approaches strategy and performance assessment[J]. Journal of Applied Science and Technology Trends, 2020, 1(1): 48-55.
[2] Mostafa S M, Amano H. Dynamic round robin CPU scheduling algorithm based on K-means clustering technique[J]. applied sciences, 2020, 10(15): 5134.
[3] Sharma C, Sharma S, Kautish S, et al. A new median-average round Robin scheduling algorithm: An optimal approach for reducing turnaround and waiting time[J]. Alexandria Engineering Journal, 2022, 61(12): 10527-10538.
[4] Shafi U, Shah M A, Wahid A, et al. A novel amended dynamic round robin scheduling algorithm for timeshared systems[J]. Int. Arab J. Inf. Technol., 2020, 17(1): 90-98.
[5] Fiad A, Maaza Z M, Bendoukha H. Improved version of round robin scheduling algorithm based on analytic model[J]. International Journal of Networked and Distributed Computing, 2020, 8(4): 195-202.
[6] Gao Z. Multi-resource Fair Scheduler in Linux[D]. University of Waterloo, 2022.
[7] Kamoyedji A, Funabiki N, Htet H, et al. A proposal of dynamic job scheduling algorithm considering CPU core utilization for User-PC computing System[C]//2021 Ninth International Symposium on Computing and Networking Workshops (CANDARW). IEEE, 2021: 268-271.
[8] Wang Y, Zhou K, Wang Z, et al. Research on real-time embedded software scheduling model based on edf[J]. IEEE Access, 2020, 8: 20058-20066.
[9] El Ghor H, Aggoune E H M. Energy efficient scheduler of aperiodic jobs for real-time embedded systems[J]. International Journal of Automation and Computing, 2020, 17: 733-743.
[10] Teraiya J, Shah A. Analysis of dynamic and static scheduling algorithms in soft real-time system with its implementation[C]//Soft Computing: Theories and Applications: Proceedings of SoCTA 2018. Springer Singapore, 2020: 757-768.
[11] Pemasinghe S, Rajapaksha S. Comparison of CPU scheduling algorithms: FCFS, SJF, SRTF, Round Robin, priority based, and multilevel queuing[C]//2022 IEEE 10th Region 10 Humanitarian Technology Conference (R10-HTC). IEEE, 2022: 318-323.
[12] Tufegdžić M, Jevremović V, Petrović Z. Estimation of CPU Scheduling Algorithms Efficiency Using Object Oriented Programming[J]. quantum, 2022, 1: 4.
[13] Bibu G D, Nwankwo G C. Comparative analysis between first-come-first-serve (FCFS) and shortest-job-first (SJF) scheduling algorithms[J]. 2019.
[14] Putra T D. Analysis of Preemptive Shortest Job First (SJF) Algorithm in CPU Scheduling[J]. International Journal of Advanced Research in Computer and Communication Engineering, 2020, 9(4): 41-45.
[15] Benny R, Wirawan I. Comparison analysis of round robin algorithm with highest response ratio next algorithm for job scheduling problems[J]. International Journal of Open Information Technologies, 2022, 10(2): 21-26.
[16] Chen J, Banerjee S S, Kalbarczyk Z T, et al. Machine learning for load balancing in the linux kernel[C]//Proceedings of the 11th ACM SIGOPS Asia-Pacific Workshop on Systems. 2020: 67-74.
[17] Kabilesh S K, Stephensagayaraj A, Anandkumar A, et al. Resemblance of Real Time Scheduling Algorithms for Real Time Embedded Systems[J]. Journal of Optoelectronics and Communication, 2020, 2(3).
[18] Krause I, Dantas L P, Gimenez S P. Impact in the Parallel Processing of IHM-Plasma Using the Earliest-Deadline-First Algorithm for the Task-Scheduler Realized by Hardware[J]. Journal of Integrated Circuits and Systems, 2023, 18(1): 1-8.
Downloads
Published
Issue
Section
License
Copyright (c) 2024 Highlights in Science, Engineering and Technology
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
How to Cite
