Determining dynamic time quantum in round-robin scheduling algorithm using machine learning

Document Type : Original Article

Authors

Information Technology Department, Faculty of Electrical and Computer Engineering, University of Sistan and Baluchestan, Zahedan, Iran

Abstract

One of the most common CPU scheduling algorithms in time-sharing systems is the round-robin algorithm. This algorithm considers a time quantum for each process, which represents the maximum amount of time that a process can have access to the processor. The processor is then allocated to ready processes in a rotating manner for the duration of the time quantum. The size of the quantum has a significant impact on the efficiency of the round-robin algorithm, such that if the quantum is too short, there will be an increase in context switches and associated overheads, which will decrease CPU utilization. Conversely, if the quantum is too large, it will increase the average response time of processes and make the use of the round-robin scheduling algorithm inefficient in interactive applications. The aim of this paper is to propose an effective method for determining the dynamic time quantum using machine learning. To this end, a training set consisting of features such as the number of processes and their maximum, minimum, average, and median burst times and the optimal time quantum as the class is constructed. Machine learning classifiers are then trained on this set to predict the optimal time quantum for new samples. The experimental results show that the proposed method outperforms other methods for determining optimal time quantum based on performance evaluation metrics of scheduling algorithms. For instance, in comparison with the genetic algorithm, which has the best performance among the available methods, the proposed method improves the average waiting time, the average number of context switches, and the average turnaround time by 12 milliseconds, 1.76 units, and about 2 milliseconds, respectively.

Keywords

References

[1] Zouaoui S., Boussaid L., and Mtibaa A., "Priority based round robin (PBRR) CPU scheduling algorithm", International Journal of Electrical and Computer Engineering, 9(1): 190-202, 2019.
[2] Mishra M. K., "An improved round robin CPU scheduling algorithm", Journal of Global Research in Computer Science, 3(6): 64-69, 2012.‏
[3] Mora H., Abdullahi S. E., and Junaidu S. B., "Modified Median Round Robin Algorithm (MMRRA)", In 13th International Conference on Electronics, Computer and Computation (ICECCO), pp. 1-7, 2017.‏
[4] Saeidi S. and Baktash H. A., "Determining the optimum time quantum value in round robin process scheduling method", International Journal of Information Technology and Computer Science, 10: 67-73, 2012.‏
[5] Ishra M. K. and Rashid F., "An improved round robin CPU scheduling algorithm with varying time quantum", International Journal of Computer Science, Engineering and Applications, 4(4): 1, 2014.‏
[6] Matarneh R. J., "Self-Adjustment Time Quantum in Round Robin Algorithm Depending on Burst Time of the Now Running Processes", American Journal of Applied Sciences, 6(10): 1831-1837, 2009.
[7] Dhumall R. A., Maktum T. A., and Ragha L., "Dynamic Quantum based Genetic Round Robin Algorithm", International Journal of Advanced Research in Computer and Communication Engineering, 3(3): 5905-5908, 2014.‏
[8] Dash A. R. and Samantra S. K., "An optimized round robin cpu scheduling algorithm with dynamic time quantum", International Journal of Computer Science, Engineering and Information Technology (IJCSEIT), 5(2): 7-26, 2016.‏
[9] Riaz R., Kazmi S. H., Kazmi Z. H., and Shah S. A.,  "Randomized Dynamic Quantum CPU Scheduling Algorithm", Journal of Information Communication Technologies and Robotic Applications, 9(2): 19-27, 2018.‏
[10] Farooq M. U., Shakoor A., and Siddique A. B., "An Efficient dynamic round robin algorithm for CPU scheduling", In 2017 International Conference on Communication, Computing and Digital Systems (C-CODE), pp. 244-248, 2017.
[11] Gull H., Iqbal S. Z., Saeed S., Alqatani M. A., and  Bamarouf Y., “Design and Evaluation of CPU Scheduling Algorithms Based on Relative Time Quantum: Variations of Round Robin Algorithm”, Journal of Computational and Theoretical Nanoscience, 15(8): 2483-2488, 2018.‏
[12] AlHeyasat O. and Herzallah R., “Estimation of Quantum Time Length for Round-robin Scheduling Algorithm using Neural Networks”, In IJCCI (ICFC-ICNC), pp. 253-257, 2010.‏
[13] Mostafa M. and Amano H., “Dynamic round robin CPU scheduling algorithm based on K-means clustering technique”, Applied Sciences, 10(15): 5134, 2020.
[14] رزاق زاده ش.، نوروزی کیوی پ.، پناهی ب.، «الگوریتم ترکیبی مبتنی بر معماری گوسیپ با استفاده از SVM برای زمانبندی وظایف در رایانش ابری»، مجله محاسبات نرم، جلد 9، شماره 2، ص. 84-93، 1399.
[15] بیرانوند ص.، زارع چاهوکی م. ع.، «مروری بر روش‌های تخمین هزینه نرم‌افزار مبتنی بر یادگیری ماشین»، مجله محاسبات نرم، جلد 5، شماره 1، ص. 36-65، 1395.
[16] وثیقی ذاکر ا.، جلیلی س.، «پیش‌بینی ژن‌های بیماری با استفاده از دسته‌بند تک کلاسی ماشین بردار پشتیبان»، مجله محاسبات نرم، جلد 4، شماره 1، ص. 74-83، 1394.
[17] ویسی ه.، قایدشرف ح.، ابراهیمی م.، «بهبود کارایی الگوریتم‌های یادگیری ماشین در تشخیص بیماری‌های قلبی با بهینه‌سازی داده‌ها و ویژگی‌ها»، مجله محاسبات نرم، جلد 8، شماره 1، ص. 70-85، 1398.
[18] سالارپور ص.، انتخاب نمونه با استفاده از اتوماتاهای یادگیر، پایان‌نامه کارشناسی ارشد، دانشگاه سیستان و بلوچستان، زاهدان، ص. 54-60، پاییز 1399.

Files

History

  • Receive Date: 10 October 2021
  • Revise Date: 13 February 2022
  • Accept Date: 10 May 2022

Share

How to cite

Statistics