Minimizing time cost in time-shared operating systems is considered basic and essential task, and it is the most significant goal for the researchers who interested in CPU scheduling algorithms. Waiting time, turnaround time, and number of context switches are the most time cost criteria used to compare between CPU scheduling algorithms. CPU scheduling algorithms are divided into non-preemptive and preemptive. Round Robin (RR) algorithm is the most famous as it is the basis for all the algorithms used in time-sharing. In this paper, the authors proposed a novel CPU scheduling algorithm based on RR. The proposed algorithm is called Adjustable Time Slice (ATS). It reduces the time cost by taking the advantage of the low overhead of RR algorithm. In addition, ATS favors short processes allowing them to run longer time than given to long processes. The specific characteristics of each process are; its CPU execution time, weight, time slice, and number of context switches. ATS clusters the processes in groups depending on these characteristics. The traditional RR assigns fixed time slice for each process. On the other hand, dynamic variants of RR assign time slice for each process differs from other processes. The essential difference between ATS and the other methods is that it gives a set of processes a specific time based on their similarities within the same cluster. The authors compared between ATS with five popular scheduling algorithms on nine datasets of processes. The datasets used in the comparison vary in their features. The evaluation was measured in term of time cost and the experiments showed that the proposed algorithm reduces the time cost.
CPU scheduling is defined as allocating and de-allocating the CPU to a specific process/thread. CPU scheduling is the most important and most effective task in the performance of the operating system [
Different CPU scheduling algorithms have different characteristics and the choice of a specific algorithm influences the performance of the system, so the characteristics of the algorithms must be considered. For comparing between CPU scheduling algorithms, many scheduling criteria have been suggested (i.e., waiting time (WT), turnaround time (TT) and number of context switches (NCS)). WT is the sum of the periods that the processes spent waiting in the ready queue. TT is the interval from the submission time of a process to the completion time. NCS is the number of times the process is stopped, put at the tail of the queue to be resumed. The scheduler executes the process at the head of the queue. The scheduler is considered efficient if it minimizes WT, TT, and NCS.
The easiest and the simplest non-preemptive CPU scheduling algorithm is the First come First Serve (FCFS) algorithm. The policy of FCFS implementation is managed with a FIFO queue in which the process that arrives to the ready queue first is assigned to the CPU first (see
In the Shortest Job First (SJF), the CPU is assigned to the process with the smallest burst time. SJF compares between the burst times of all processes residing in the ready queue and selects the process with the smallest burst time. If two processes have the same burst times, FCFS scheduling is used (see
Round Robin scheduling (
The OS is driven by an interrupt (i.e., clock tick). Processes are chosen in a fixed sequence for execution. On each clock tick, the process running is paused and the next process starts execution. All processes wait in the queue for the slot of CPU time where all of them are treated as of equal importance. Process is not permitted to run to completion, but it is preempted. The implications of the preemptive process switching and the overhead are significant and must be taken into consideration. There is an inescapable time overhead when the process and context are switched (represented by the black bars in
For example, assume that the scheduler runs three processes {A, B, C} in the sequence A, B, C, A, B, C, A, …., until they are all completed. This sequence for these processes is shown in
Dividing the data into useful, meaningful, or both is known as clustering [
K-means is the most common of clustering algorithms, the steps of K-means are shown in algorithm 2. The simplicity of K-means comes from the use of the stopping criterion (i.e., squared error). Suppose that
Silhouette method is one of the most popular clustering evaluation techniques. It determines how well each element lies within its cluster, so it measures the clustering quality. It can be summarized as follows:
Applying the selected clustering algorithm for different values of Calculating the Within-cluster Sum of Square (WSS) for each Plotting WSS curve. The knee's position in the curve points out the suitable number of clusters.
Various forms of the RR algorithm have been proposed to minimize time cost. This section shows the most common of these forms.
Authors | Year | Technique |
Technique |
Based on | Performance Metrics | ||
---|---|---|---|---|---|---|---|
WT | TT | NCS | |||||
Aaron et al. | 2001 | VTRR | Dynamic | RR | √ | √ | √ |
Tarek et al. | 2007 | BRR | Dynamic | RR | √ | √ | √ |
Samih et al. | 2010 | CTQ | Dynamic | SRR | √ | √ | √ |
Mishra et al. | 2014 | IRRVQ | Dynamic | RR and SJF | √ | √ | -- |
Lipika Datta | 2015 | --- | Dynamic | RR and SJF | √ | √ | √ |
Christoph et al. | 2015 | Adaptive80 |
Dynamic | RR and SJF | √ | √ | √ |
Samir et al. | 2017 | SRDQ | Dynamic | RR and SJF | √ | √ | √ |
Samih | 2018 | PWRR | Dynamic | RR | √ | √ | √ |
Samih et al. | 2019 | ARR | Dynamic based on threshold | RR | √ | √ | √ |
Uferah et al. | 2020 | ADRR | Dynamic | RR and SJF | √ | √ | √ |
Samih et al. | 2020 | DRR | Dynamic based on clustering | RR and K-means | √ | √ | √ |
Samih et al. | 2020 | DTS | Dynamic based on clustering | RR and K-means | √ | √ | √ |
Before starting the proposed algorithm, the meanings of abbreviations used should be clarified as shown in
Abbreviations | Meaning |
---|---|
PW | Process weight |
PTQ | Permitted time quantum |
PTS | Proportional time slice |
BT | Burst time |
RBT | Residual burst time |
PBT | Proportional burst time |
NCS | Number of context switches |
TRR | Traditional Round Robin |
FTS | Fixed time slice |
CW | Cluster weight |
CTS | Cluster time slice |
Cavg | Average of burst times in a cluster |
ATS | Adjustable time slice |
The process features PW, PTQ, PBT, and NCS basically depend on BT. Firstly, the proposed approach rounds up similar processes in clusters and the resemblance between processes depends on these features. ATS algorithm uses k-means in the clustering process. Preparation of the data, clustering the data, and the dynamic implementation are the three stages of the proposed work, which are described in the following subsections.
PW and NCS are calculated in this stage.
The mean reason of choosing K-means clustering algorithm in this work is that K-means works properly only with the numerical features [
Process with long burst time causes more overhead resulted from numerous NCS. A threshold is predetermined to avoid this overhead. The proposed algorithm allows the process that close to finish to be completed and leave the queue.
The proposed algorithm behaved similar to the DTS algorithm [
The computer's specifications used in the experiments are shown in
Nine artificial datasets were generated to be used in the experiments. Each dataset has a number of processes varying in the BTs which have been randomly generated. To prove that the proposed algorithm is valid for diverse data, each dataset contains different number of processes varying in their burst times and accordingly the PW, NCS, PTQ, PBT, and PTS are different.
The proposed algorithm has been compared with five common algorithms VTRR, DTS, ADRR PWRR and RR. The submitted processes may be arrived in the same time or different times. The experiments were conducted taking into account the two cases.
Case 1 (same arrival time): The average turnaround times and waiting times comparisons are shown in
Hardware specifications | Software specifications |
---|---|
CPU - Intel core i5-2400 (3.10 GHz) | Gnu/Linux Fedora 28 OS |
1 TB HDD | (Python 3.7.6 (default, Jan 8 2020, 20:23:39) |
16GB RAM |
Dataset ID | #Processes | #Features | Features | ||||
PW | NCS | PTQ | PBT | PTS | |||
1 | 10 | 5 | √ | √ | √ | √ | √ |
2 | 15 | 5 | √ | √ | √ | √ | √ |
3 | 20 | 5 | √ | √ | √ | √ | √ |
4 | 25 | 5 | √ | √ | √ | √ | √ |
5 | 30 | 5 | √ | √ | √ | √ | √ |
6 | 35 | 5 | √ | √ | √ | √ | √ |
7 | 40 | 5 | √ | √ | √ | √ | √ |
8 | 45 | 5 | √ | √ | √ | √ | √ |
9 | 50 | 5 | √ | √ | √ | √ | √ |
Dataset | ATS | DTS | RR | ||||||
---|---|---|---|---|---|---|---|---|---|
WT | TT | NCS | WT | TT | NCS | WT | TT | NCS | |
1 | 1055.81 | 1202.81 | 141 | 1055.83 | 1202.83 | 142 | 1137.68 | 1284.68 | 148 |
2 | 1632.86 | 1775.46 | 205 | 1646.13 | 1788.73 | 206 | 1751.48 | 1894.08 | 210 |
3 | 2244.61 | 2388.21 | 278 | 2270.28 | 2413.88 | 279 | 2368.01 | 2511.61 | 277 |
4 | 2900.94 | 3045.9 | 346 | 2904.73 | 3049.69 | 347 | 2998.81 | 3143.77 | 346 |
5 | 3556.94 | 3702.61 | 415 | 3570.15 | 3715.82 | 416 | 3658.62 | 3804.29 | 415 |
6 | 4163.22 | 4307.91 | 487 | 4162.25 | 4306.93 | 488 | 4272.39 | 4417.08 | 481 |
7 | 4874.44 | 5021.64 | 568 | 4873.75 | 5020.95 | 569 | 4980.18 | 5127.38 | 560 |
8 | 5064.15 | 5211.59 | 641 | 5094.15 | 5241.6 | 642 | 5664.03 | 5811.47 | 631 |
9 | 5409.32 | 5557.64 | 705 | 5343.27 | 5491.59 | 706 | 6289.8 | 6438.12 | 704 |
Average | 3433.588 | 3579.308 | 3435.615556 | 3581.336 | 3680.111 | 3825.831 | |||
Improvement% | 0.194947607 | 0.180004 | 6.05453 | 5.762972 | |||||
Dataset | VTRR | RR | ADRR | ||||||
WT | TT | NCS | WT | TT | NCS | WT | TT | NCS | |
1 | 1163.1 | 1310.1 | 142 | 1163.9 | 1310.9 | 142 | 1186 | 1333 | 140 |
2 | 1786.8 | 1929.4 | 207 | 1787.33 | 1929.93 | 207 | 1828 | 1970.6 | 205 |
3 | 2424.78 | 2568.38 | 279 | 2425.15 | 2568.75 | 277 | 2490 | 2633.6 | 277 |
4 | 3069.03 | 3213.99 | 349 | 3069.24 | 3214.2 | 349 | 3144 | 3288.96 | 345 |
5 | 3734.82 | 3880.49 | 420 | 3735 | 3880.67 | 420 | 3824 | 3969.67 | 415 |
6 | 4361.7 | 4506.38 | 491 | 4361.8 | 4506.49 | 488 | 4457.71 | 4602.4 | 486 |
7 | 5073.72 | 5220.92 | 573 | 5073.8 | 5221 | 568 | 5180.5 | 5327.7 | 569 |
8 | 5760.97 | 5908.41 | 645 | 5761.04 | 5908.49 | 640 | 5877.78 | 6025.22 | 641 |
9 | 6414.06 | 6562.38 | 716 | 6414.64 | 6562.96 | 716 | 6553.2 | 6701.52 | 705 |
Average | 3754.331 | 3900.05 | 3754.656 | 3900.377 | 3837.91 | 3983.63 | |||
Improvement% | 7.972041 | 7.591376 | 7.986159 | 7.604464 | 10.00378 | 9.535625 |
DTS | PWRR | VTRR | RR | ADRR | |||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
WT | TT | NCS | WT | TT | NCS | WT | TT | NCS | WT | TT | NCS | WT | TT | NCS | |
1 | 0.002 | 0.002 | 1.399 | 7.196 | 6.373 | 4.730 | 9.224 | 8.189 | 0.704 | 9.287 | 8.245 | 0.704 | 10.977 | 9.767 | −0.714 |
2 | 0.806 | 0.742 | 1.442 | 6.773 | 6.263 | 2.381 | 8.615 | 7.979 | 0.966 | 8.643 | 8.004 | 0.966 | 10.675 | 9.903 | 0.000 |
3 | 1.131 | 1.063 | 0.714 | 5.211 | 4.913 | −0.361 | 7.430 | 7.015 | 0.358 | 7.444 | 7.028 | −0.361 | 9.855 | 9.318 | −0.361 |
4 | 0.130 | 0.124 | 1.143 | 3.264 | 3.113 | 0.000 | 5.477 | 5.230 | 0.860 | 5.483 | 5.236 | 0.860 | 7.731 | 7.390 | −0.290 |
5 | 0.370 | 0.356 | 1.425 | 2.779 | 2.673 | 0.000 | 4.763 | 4.584 | 1.190 | 4.767 | 4.588 | 1.190 | 6.984 | 6.728 | 0.000 |
6 | −0.023 | −0.023 | 1.016 | 2.555 | 2.472 | −1.247 | 4.551 | 4.404 | 0.815 | 4.553 | 4.407 | 0.205 | 6.606 | 6.399 | −0.206 |
7 | −0.014 | −0.014 | 1.045 | 2.123 | 2.062 | −1.429 | 3.928 | 3.817 | 0.873 | 3.929 | 3.818 | 0.000 | 5.908 | 5.745 | 0.176 |
8 | 0.589 | 0.573 | 0.774 | 10.591 | 10.322 | −1.585 | 12.096 | 11.794 | 0.620 | 12.097 | 11.795 | −0.156 | 13.842 | 13.504 | 0.000 |
9 | −1.236 | −1.203 | 1.674 | 13.999 | 13.676 | −0.142 | 15.665 | 15.311 | 1.536 | 15.672 | 15.318 | 1.536 | 17.455 | 17.069 | 0.000 |
Case 2 (different arrival time): Process arrival was modeled as Poisson random process. The arrival times are exponentially distributed [
Dataset | ATS | DTS | PWRR | ||||||
---|---|---|---|---|---|---|---|---|---|
WT | TT | NCS | WT | TT | NCS | WT | TT | NCS | |
1 | 1054.75 | 1201.61 | 126 | 1054.77 | 1201.63 | 127 | 1136.54 | 1136.54 | 133 |
2 | 1631.23 | 1773.69 | 184 | 1644.48 | 1786.94 | 185 | 1749.73 | 1749.73 | 189 |
3 | 2242.37 | 2385.82 | 250 | 2268.01 | 2411.47 | 251 | 2365.64 | 2365.64 | 249 |
4 | 2898.04 | 3042.85 | 311 | 2901.83 | 3046.64 | 312 | 2995.81 | 2995.81 | 311 |
5 | 3553.38 | 3698.91 | 373 | 3566.58 | 3712.1 | 374 | 3654.96 | 3654.96 | 373 |
6 | 4159.06 | 4303.6 | 438 | 4158.09 | 4302.62 | 439 | 4268.12 | 4268.12 | 432 |
7 | 4869.57 | 5016.62 | 511 | 4868.88 | 5015.93 | 512 | 4975.2 | 4975.2 | 504 |
8 | 5059.09 | 5206.38 | 576 | 5089.06 | 5236.36 | 577 | 5658.37 | 5658.37 | 567 |
9 | 5403.91 | 5552.08 | 634 | 5337.93 | 5486.1 | 635 | 6283.51 | 6283.51 | 633 |
Average | 3430.15 | 3575.73 | 3432.18 | 3577.75 | 3676.43 | 3676.43 | |||
Improvement% | 0.19 | 0.18 | 6.05 | 5.76 | |||||
1 | 1161.94 | 1308.79 | 127 | 1162.74 | 1309.59 | 127 | 1184.81 | 1331.67 | 126 |
2 | 1785.01 | 1927.47 | 186 | 1785.54 | 1928 | 186 | 1826.17 | 1968.63 | 184 |
3 | 2422.36 | 2565.81 | 251 | 2422.73 | 2566.18 | 249 | 2487.51 | 2630.97 | 249 |
4 | 3065.96 | 3210.78 | 314 | 3066.17 | 3210.99 | 314 | 3140.86 | 3285.67 | 310 |
5 | 3731.09 | 3876.61 | 378 | 3731.27 | 3876.79 | 378 | 3820.18 | 3965.7 | 373 |
6 | 4357.34 | 4501.87 | 441 | 4357.44 | 4501.98 | 439 | 4453.25 | 4597.8 | 437 |
7 | 5068.65 | 5215.7 | 515 | 5068.73 | 5215.78 | 511 | 5175.32 | 5322.37 | 512 |
8 | 5755.21 | 5902.5 | 580 | 5755.28 | 5902.58 | 576 | 5871.9 | 6019.2 | 576 |
9 | 6407.65 | 6555.82 | 644 | 6408.23 | 6556.4 | 644 | 6546.65 | 6694.82 | 634 |
Average | 3750.58 | 3896.15 | 3750.90 | 3896.48 | 3834.07 | 3979.65 | |||
Improvement% | 7.97 | 7.59 | 7.99 | 7.60 | 10.00 | 9.54 |
DTS | PWRR | VTRR | RR | ADRR | |||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
WT | TT | NCS | WT | TT | NCS | WT | TT | NCS | WT | TT | NCS | WT | TT | NCS | |
1 | 0.0019 | 0.0017 | 1.3986 | 7.1962 | 6.3728 | 4.7297 | 9.2245 | 8.19 | 0.7 | 9.2869 | 8.2455 | 0.704 | 10.9772 | 9.7667 | 0.0000 |
2 | 0.8061 | 0.7419 | 1.4423 | 6.7726 | 6.2627 | 2.3810 | 8.6154 | 7.98 | 0.97 | 8.6425 | 8.0039 | 0.966 | 10.6751 | 9.9026 | 0.0000 |
3 | 1.1307 | 1.0634 | 0.7143 | 5.2111 | 4.9132 | −0.3610 | 7.4304 | 7.02 | 0.36 | 7.4445 | 7.0283 | −0.361 | 9.8550 | 9.3177 | −0.4016 |
4 | 0.1305 | 0.1243 | 1.1429 | 3.2636 | 3.1131 | 0.0000 | 5.4770 | 5.23 | 0.86 | 5.4834 | 5.2361 | 0.86 | 7.7309 | 7.3902 | −0.3226 |
5 | 0.3700 | 0.3555 | 1.4252 | 2.7792 | 2.6728 | 0.0000 | 4.7627 | 4.584 | 1.19 | 4.7673 | 4.5884 | 1.191 | 6.9838 | 6.7275 | 0.0000 |
6 | −0.0233 | −0.0228 | 1.0163 | 2.5552 | 2.4715 | −1.2474 | 4.5505 | 4.404 | 0.82 | 4.5527 | 4.4065 | 0.21 | 6.6063 | 6.3986 | −0.2288 |
7 | −0.01 | −0.014 | 1.04 | 2.12 | 2.06 | −1.43 | 3.93 | 3.817 | 0.87 | 3.9292 | 3.8184 | 0.00 | 5.9079 | 5.7447 | 0.1953 |
8 | 0.58 | 0.57 | 0.77 | 10.6 | 10.32 | −1.59 | 12.1 | 11.79 | 0.62 | 12.097 | 11.7949 | −0.156 | 13.8425 | 13.5037 | 0.0000 |
9 | −1.24 | −1.2 | 1.67 | 13.1 | 13.68 | −0.14 | 15.67 | 15.31 | 1.54 | 15.672 | 15.3181 | 1.536 | 17.4553 | 17.0690 | 0.0000 |
This paper presented a dynamic version of RR. The proposed goal is to reduce the time cost (i.e., waiting time and turnaround time). The traditional RR uses fixed slot of time for each process in all rounds regardless the BT of the process, however, the proposed algorithm (ATS) assigns particular time slice for each process. This time slice is different from the other processes in the same cluster. If the BT of a process is longer than the assigned time slice, the process will be put at the end of the queue and assigned a new time slice in the new round. In addition, the proposed algorithm starts by grouping similar processes in a group depending on the similarity between the features. Each cluster is a signed a slot of time and every process in this cluster is assigned this time slice. In a round, some processes may finish their BT and leave the queue, and may new processes arrive. In both cases the number of the clusters and clusters’ weights will be updated and therefore the time slice assigned to a cluster and the number of the processes in the cluster will be updated. Furthermore, ATS takes into account the remaining times of the survived processes and allow short process to complete (under predetermined conditions) without interruption even if its BT longer than the assigned Time Slice, in other words, ATS grants more time to the process that is close to complete in the current and consecutive rounds. Comparison has been done between ATS and five common versions of RR from the point of view of time cost. The results showed that the proposed algorithm achieves noticeable improvements.