# Dynamic Round Robin CPU Scheduling Algorithm Based on K-Means Clustering Technique
## 2 Related Works  
For better CPU performance in most of the operating systems, the RR scheduling algorithm is widely implemented. Many variants of the RR algorithm have been proposed to minimize average waiting time and turnaround. This section discusses the most common versions of RR. Table 2 shows a comparison between the known versions of SRR. [PERSON] and [PERSON] [32] proposed a dynamic version of SRR named Variable Time Round-Robin scheduling (UTRR). The time slice allocated to a process depends on the time needed to all tasks, process's burst time, and number of processes in the ready queue. \begin{table}
\begin{tabular}{c c c c c c c} \hline \hline \multirow{2}{*}{**Researchers**} & \multirow{2}{*}{**Year**} & **Technique** & \multirow{2}{*}{**Technique Type**} & \multirow{2}{*}{**Based on**} & \multicolumn{2}{c}{**Performance Metrics**} \\ \cline{5-6}  & & **Name** & & & **WT** & **TT** & **NCS** \\ \hline [PERSON] and [PERSON] & 2001 & VTRR & Dynamic & SRR & ✓ & ✓ & ✓ \\ [PERSON] and [PERSON] & 2007 & BRR & Dynamic & SRR & ✓ & ✓ & ✓ \\ [PERSON] et al. & 2010 & CTQ & Dynamic & SRR & ✓ & ✓ & ✓ \\ [PERSON] & 2015 & - & Dynamic & SRR and SJF & ✓ & ✓ & ✓ \\ [PERSON] and [PERSON] & 2015 & Adaptive80 RR & Dynamic & SRR and SJF & ✓ & ✓ & ✓ \\ [PERSON] et al. & 2017 & SRDQ & Dynamic & SRR and SJF & ✓ & ✓ & ✓ \\ [PERSON] & 2018 & PWRR & Dynamic & SRR & ✓ & ✓ & ✓ \\ [PERSON] and [PERSON] & 2019 & ARR &
\begin{tabular}{c} Dynamic based \\ on threshold \\ \end{tabular} & SRR & ✓ & ✓ & ✓ \\ [PERSON] et al. & 2020 & ADRR & Dynamic & SRR and SJF & ✓ & ✓ & ✓ \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Comparison of common versions of Round Robin (RR) (WT is acronym for waiting time, TT is acronym for turnaround time). Figure 1: Organization of the paper. [PERSON] and [PERSON] [33] proposed a weighting technique for SRR. The authors classified the processes into five weight categories based on their burst times. The weight of a process is inversely proportional to the weight; process with high weight receives more time slice and vice versa. Processes with burst time less than or equal to 10 tu receive 100% of the time slice defined by SRR, Processes with burst time less than or equal to 25 tu receive 80% of the time slice defined by SRR, and so on. [PERSON] et al. [18] proposed a dynamic version of SRR named Changeable Time Quantum (CTQ). Their algorithm finds the time slice that gives the smallest average waiting time at every round. CTQ calculates the average waiting time for a specific range of time slices and picks up the time slice corresponding to smallest average waiting time. Then, the processes in this round execute for this time slice. [PERSON] [34] proposed a dynamic version of SRR by adjusting the time slice at the beginning of each round. The time slice is calculated depending on the remaining burst times in the subsequent rounds. In addition, the author also implemented SJF [35; 36; 37]. In SJF, the processes located in the ready queue are sorted in increasing order based on their burst times (i.e., the process having lowest burst time will be at the front of the ready queue and process having highest burst time will be at the end of the ready queue). [PERSON] and [PERSON] [7] presented a dynamic version of SRR named Adaptive80 RR. The reason behind this name is that the time slice is set equal to process's burst time at 80 th percentile. Like [PERSON]'s [34], Adaptive80 RR sorts processes in increasing order. The time slice in each round depends on the processes located in the ready queue and if new process arrived, it will be added to the ready queue and will be considered in the subsequent calculations. [PERSON] et al. [38] proposed a hybrid scheduling algorithm based on SRR and SJF named SJF and RR with dynamic quantum (SRDQ). Their algorithm divided the ready queue into two subqueues Q1 and Q2; Q2 for long tasks (longer than the median) and Q1 for short tasks (shorter than the median).