# Dynamic Round Robin CPU Scheduling Algorithm Based on K-Means Clustering Technique
## 3 The Proposed Algorithm
### Illustrative Examples
#### 3.4.2 Example 2  
Giving a short process more CPU time decreases the waiting time of this process more than it increases the waiting time of the long process. Consequently, the average waiting time decreases. To illustrate this concept, assume the following set of processes (Table 5) that arrive at the same time, each of which with its burst time, and the STS is 10 tu.  
Using SRR scheduling, we would schedule these processes according to the following Gantt chart:  
\begin{tabular}{|c|c|c|c|c|c|c|} \hline P1 & P2 & P3 & P4 & P1 & P3 & P4 & P3 \\ \hline
0 & 10 & 20 & 30 & 40 & 45 & 55 & 62 & **73** \\ \hline \end{tabular}  
The waiting time is 30 tu for process P1, 10 tu for process P2, 42 tu for process P3, and 45 for process P4. Thus the average waiting time is 31.75 tu, and the average turnaround time is 50 tu. On the other hand, suppose that each process is assigned a percentile of STS equals \(((\text{STS / BT})\times\text{STS})\) as in Table 6.  
\begin{table}
\begin{tabular}{c c c c} \hline \hline  & **BT** & **Weight** & **NCS** & **y** \\ \hline
0 & 109 & 0.077746 & 10 & 0 \\
1 & 150 & 0.10699 & 15 & 0 \\
2 & 3 & 0.00214 & 0 & 0 \\
3 & 50 & 0.035663 & 4 & 0 \\
5 & 49 & 0.03495 & 4 & 0 \\
6 & 409 & 0.291726 & 48 & 1 \\
7 & 490 & 0.349501 & 48 & 1 \\
8 & 47 & 0.033524 & 4 & 0 \\
9 & 46 & 0.03281 & 4 & 0 \\ \hline \hline \end{tabular}
\end{table}
Table 4: Clustered dataset_1.  
Figure 3: Finding optimal number of clusters.  
\begin{table}
\begin{tabular}{|c|c|} \hline
**Process ID** & **BT** \\ \hline P1 & 15 \\ P2 & 10 \\ P3 & 31 \\ P4 & 17 \\ \hline \end{tabular}
\end{table}
Table 5: Four processes with the length of the burst time.  
The results will be as shown in the following Gantt chart:  
\begin{tabular}{|c c c c c c c c c c|} \hline \hline  & \multicolumn{2}{c|}{**Round 1**} & \multicolumn{2}{c|}{**Round 2**} & \multicolumn{2}{c|}{**Round 3**} & \multicolumn{2}{c|}{**Round 4**} \\ \hline
**Process ID** & **BT** & **TS** & **RBT** & **TS** & **RBT** & **TS** & **RBT** & **TS** \\ \hline \hline \multirow{3}{*}{P1} & \multirow{3}{*}{15} & \multirow{3}{*}{7} & \multirow{3}{*}{8} & \multicolumn{2}{c|}{12.5} & \multirow{3}{*}{—} & \multirow{3}{*}{—} & \multirow{3}{*}{—} & \multirow{3}{*}{—} \\  & & & & & & & & & \\ \cline{5-8}  & & \multicolumn{2}{c|}{10} & \multicolumn{2}{c|}{} & \multicolumn{2}{c|}{—} & \multirow{3}{*}{—} & \multirow{3}{*}{—} & \multirow{3}{*}{—} \\  & & \multicolumn{2}{c|}{terminates} & \multicolumn{2}{c|}{—} & \multicolumn{2}{c|}{—} & \multirow{3}{*}{—} & \multirow{3}{*}{—} & \multirow{3}{*}{—} \\ P2 & \multirow{3}{*}{10} & \multicolumn{2}{c|}{terminates} & \multicolumn{2}{c|}{—} & \multirow{3}{*}{—} & \multirow{3}{*}{—} & \multirow{3}{*}{—} & \multirow{3}{*}{—} \\ P3 & \multirow{3}{*}{31} & \multicolumn{2}{c|}{4} & \multicolumn{2}{c|}{27} & \multirow{3}{*}{4} & \multirow{3}{*}{23} & \multirow{3}{*}{4} & \multirow{3}{*}{19} & \multirow{3}{*}{19} \\  & & & & & & & & & \\ P4 & \multirow{3}{*}{17} & \multirow{3}{*}{6} & \multirow{3}{*}{11} & \multirow{3}{*}{9} & \multirow{3}{*}{2} & \multirow{3}{*}{terminates} & \multicolumn{2}{c|}{—} & \multirow{3}{*}{—} \\  & & & & & & & after 2 tu & & \\ \hline \hline \end{tabular}  
The results will be as shown in the following Gantt chart:  
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|} \hline P1 & P2 & P3 & P4 & P1 & P3 & P4 & P3 & P4 & P3 \\ \hline
**0** & **7** & **17** & **21** & **27** & **35** & **39** & **48** & **52** & **54** & **73** \\ \hline \hline \end{tabular}  
The waiting time is 20 tu for process P1, 7 tu for process P2, 42 tu for process P3, and 37 for process P4. Thus the average waiting time is 26.5 tu, and the average turnaround time is 44.75 tu.