Open Access

ARTICLE

An Adjustable Variant of Round Robin Algorithm Based on Clustering Technique

Samih M. Mostafa^1,*, Hirofumi Amano²
1 Faculty of Computers and Information, South Valley University, Qena, 83523, Egypt
2 Research Institute for Information Technology, Kyushu University, Fukuoka, 819-0395, Japan
* Corresponding Author: Samih M. Mostafa. Email:

Computers, Materials & Continua 2021, 66(3), 3253-3270. https://doi.org/10.32604/cmc.2021.014675

Received 08 October 2020; Accepted 25 October 2020; Issue published 28 December 2020

Abstract

CPU scheduling is the basic task within any time-shared operating system. One of the main goals of the researchers interested in CPU scheduling is minimizing time cost. Comparing between CPU scheduling algorithms is subject to some scheduling criteria (e.g., turnaround time, waiting time and number of context switches (NCS)). Scheduling policy is divided into preemptive and non-preemptive. Round Robin (RR) algorithm is the most common preemptive scheduling algorithm used in the time-shared operating systems. In this paper, the authors proposed a modified version of the RR algorithm, called dynamic time slice (DTS), to combine the advantageous of the low scheduling overhead of the RR and favor short process for the sake of minimizing time cost. Each process has a weight proportional to the weights of all processes. The process’s weight determines its time slice within the current period. The authors benefit from the clustering technique in grouping the processes that are similar in their attributes (e.g., CPU service time, weight, allowed time slice (ATS), proportional burst time (PBT) and NCS). Each process in a cluster is assigned the average of the processes’ time slices in this cluster. A comparative study of six popular scheduling algorithms and the proposed approach on nine groups of processes vary in their attributes was performed and the evaluation was measured in terms of waiting and turnaround times, and NCS. The experiments showed that the proposed algorithm gives better results.

---

Keywords

Clustering; CPU scheduling; round robin; turnaround time; waiting time

---