Automatic Control and System Engineering Journal, ISSN 1687-4811, Volume 17, Issue 2, ICGST, Delaware, USA, December 2017 Round Robin based Scheduling Algorithms, A Comparative Study Kamal ElDahshan, Afaf Abd Elkader, Nermeen Ghazy Dept. of mathematics, Computer science Division, Faculty of science, Al-Azhar University Cairo, Egypt [dahshan, afaf2azhar]@azhar.edu.eg, [nermeen_ghazy89]@yahoo.com http://www.azhar.edu.eg Abstract: 1. Introduction Scheduling is the process of allocating processes to the The Round Robin (RR) CPU scheduling algorithm CPU in order to optimize some objective function. There referred as Standard RR, it is a preemptive algorithm are many algorithms used to schedule processes. The which assigns a time slice called (time quantum TQ) [1] Round Robin (RR) CPU scheduling algorithm is one of for each process in the ready queue. When the TQ these algorithms which is effective in time sharing and finishes, the current process is preempted and added to real time operating systems. It gives reasonable response the end of the ready queue [2] [3]. RR is commonly used time. But it suffers from several disadvantages such as in time sharing and real time operating system [4] [5] high turnaround time, high waiting time and many because it gives each process a fair share of time to use context switches. There are large numbers of algorithms the CPU and produces low response time [6]. However, it proposed to enhance the standard Round Robin algorithm. is known that the Standard RR algorithm suffers from In this paper we present a survey with results analysis several disadvantages; low throughput (the number of that conclude recommendations for an Enriched Round processes that are completed per unit of time) [7], high Robin algorithm that ameliorates the performance of turnaround time (the time between starting and average waiting time and average turnaround time. completion) [7], high waiting time (the amount of time that is waiting in the ready queue) [7], and large number Keywords: Round Robin scheduling algorithm (RR), of context switches [6]. The most interesting issue with Adaptive Round Robin Scheduling algorithm, Time the Round Robin algorithm is the time quantum [8]. Quantum (TQ), Dynamic TQ, Round Robin Remaining Setting a small TQ causes too many context switches time algorithm (RRRT), (IRR) improved Round Robin which results in a low performance of the CPU [9] [10]. CPU Scheduling Algorithm, (AAAIRR) an improvement On the other hand, setting the TQ to a large value may on the improved Round Robin CPU scheduling algorithm, cause a poor response time and the RR algorithm tends to (ERR) An Enhanced Round Robin CPU Scheduling work as FCFS [8] [9] [10]. Algorithm, (MMRR) Min-Max Dispersion Measure, Many algorithms improved the RR algorithm and (IRRVQ) The improved Round Robin CPU scheduling produce better results than it. Some of these algorithms algorithm with varying time quantum, (AMRR) Average use static TQ and others use dynamic TQ. This work is a Max Round Robin Scheduling Algorithm, Average comparative study of Round Robin and its improvements. waiting time, Average turnaround time. The rest of the paper is organized as follows Section (2) Nomenclature focuses on some Static Time Quantum Algorithms RR Round Robin Section (3) focuses on some Dynamic Time Quantum TQ Time Quantum Algorithms Section (4) explains the Results and IRR Improved Round Robin ameliorations Analysis Section (5) discusses the Enriched AAAIRR An improvement on the improved Round Round Robin algorithm Section (6) concludes the paper. Robin ERR An Enhanced Round Robin CPU Scheduling RRRT Round Robin Remaining time algorithm MMRR Min-Max Dispersion Measure 2. Static Time Quantum Algorithms IRRVQ The improved Round Robin CPU scheduling Some algorithms use TQ which is fixed during the algorithm with varying time quantum execution of the algorithm. TQ may be assumed or AMRR Average Max Round Robin calculated. AWT Average waiting time The following two subsections discuss both algorithms ATT Average turnaround time. depending on assumed TQ and calculated TQ. CPU Central processing unit ERR Enriched Round Robin 29 Automatic Control and System Engineering Journal, ISSN 1687-4811, Volume 17, Issue 2, ICGST, Delaware, USA, December 2017 2.1 Description of the Round Robin from the ready queue then it selects the next shortest algorithms with assumed Time quantum process. Otherwise, the process will be added to the end of the Some researchers assumed a value for the time quantum ready queue and the next process in the ready queue will which must not exceed the maximum burst time. The be selected [12]. This algorithm reduces the waiting time following three algorithms IRR, AAIRR, ERR [11] [12] and turnaround time compared to the standard Round [13] used an assumed time quantum to schedule the Robin algorithm and Improved Round Robin algorithm. processes in the ready queue. The pseudo code of the AAIRR CPU scheduling 2.1.1 Improved Round Robin CPU Scheduling algorithm in the following: Algorithm (IRR) 1. START The improved Round Robin (IRR) algorithm is similar to 2. Make a ready queue of the Processes say Round Robin (RR) with a small improvement [11]. It REQUEST. selects the first process that arrives in the ready queue 3. Do and allocates it to the CPU for a time interval of up to 1 4. Pick the first process that arrives to the ready time quantum. After completion of process’s time queue and allocate the CPU to it for a time quantum, the remaining CPU burst time of the currently interval of up to 1 time quantum. running process is checked. If the remaining CPU burst 5. If the remaining CPU burst time of the currently time of the currently running process is less than 1 time running process is less or equal to 1 time quantum, the CPU is again allocated to the currently quantum. running process for the remaining CPU burst time. After 6. Reallocate the CPU again to the currently finishing its execution, it is removed from the ready running process for the remaining CPU burst queue and the next process will be selected. Otherwise, time. After completing the execution, remove it the process will be added to the end of the ready queue from the ready queue. and the next process will be selected [11]. It gives better 7. Otherwise, remove the currently running process performance than RR where reduces the waiting time and from the ready queue REQUEST and put it at turnaround time. the tail of the ready queue. 8. Pick the next shortest process from the ready The pseudo code of the IRR CPU scheduling algorithm queue and allocate the CPU to it for a time in the following: interval of up to 1 time quantum then go to 5. 9. WHILE queue REQUEST in not empty 1. START 10. Calculate Average Waiting Time, Average 2. Make a ready queue of the Processes say Turnaround Time and Number of Context REQUEST. Switch. 3. Do 4, 5 and 6 WHILE queue REQUEST 11. END becomes empty. 4. Pick the first process from the ready queue and allocate the CPU to it for a time interval of up to 2.1.3 An Enhanced Round Robin CPU Scheduling 1 time quantum. algorithm (ERR) 5. If the remaining CPU burst time of the currently This algorithm makes a little improvement on the IRR running process is less than 1 time quantum then algorithm. It selects the first process of the ready queue allocate CPU again to the currently running to allocate it to the CPU for a time interval of up to 1 process for remaining CPU burst time. After time quantum. Then it checks the remaining burst time of completion of execution, removed it from the the currently running process, if the remaining burst time ready queue and go to 3. is less than or equal to 1 time quantum, the current 6. Remove the currently running process from the process is again allocated to the CPU. After completing ready queue REQUEST and put it at the tail of the execution, this process is removed from the ready the ready queue. queue. If the remaining burst time of the currently 7. END running process is longer than 1 time quantum, the process will be added to the end of the ready queue [13]. 2.1.2 An Additional Improvement Round Robin CPU scheduling algorithm (AAIRR) The pseudo code of the AAIRR CPU scheduling It makes an improvement on the improved Round Robin algorithm in the following: CPU scheduling algorithm. It selects the first process that 1. Start arrives in the ready queue and allocates it to the CPU for 2. Make a ready queue of the processes a time interval of up to 1 time quantum. After completion 3. Allocate the CPU to the first process of the of process’s time quantum, the remaining CPU burst time ready queue for a time interval of up to 1 time of the currently running process is checked. If the quantum. remaining CPU burst time of the currently running 4. If the remaining burst time of the currently process is less than or equal to 1 time quantum, the CPU running process is less than or equal to 1 time is again allocated to the currently running process for the quantum then remaining CPU burst time and after execution it removed 5. Allocate CPU again to the currently running process for the remaining burst time. 30 Automatic Control and System Engineering Journal, ISSN 1687-4811, Volume 17, Issue 2, ICGST, Delaware, USA, December 2017 6. After completion of execution remove it from c) AAIRR algorithm the ready queue and go to 3 Here the processes are scheduled according to the 7. Repeat 3,4 and 5 WHILE ready queue becomes AAIRR algorithm with TQ=12 empty 8. Remove the currently running process from the Gantt chart ready queue and put it at the tail of the ready P1 P3 P4 P5 P2 P5 P2 queue. 0 24 29 41 53 65 87 115 9. END 1 Figure 3: Gantt chart for AAIRR Algorithm (Case 1) 2.1.4 Experimental data There are three cases for incoming burst time namely; Average waiting time= 36.2ms random, increasing and decreasing for randomly chosen Average turnaround time= 59.2ms TQ. Case 1: The burst time of the processes is random d) ERR algorithm Consider five processes with a random burst time shown Here the processes are scheduled according to the ERR in Table 1. Assume that TQ=12ms, we apply the algorithm with TQ=12 algorithms RR, IRR, AAIRR and ERR [11,12,13,21] to schedule these processes and the resulting Gantt charts Gantt chart for the RR, IRR, AAIRR and ERR algorithms are shown P1 P2 P3 P4 P5 P2 P5 P2 in Figures 1, 2, 3 and 4 respectively. 0 24 36 41 53 65 77 99 115 Table 1. Five processes with random burst time Figure 4: Gantt chart for ERR Algorithm (Case 1) process Burst time Average waiting time= 43.4 ms Average turnaround time= 66.4 ms P1 24 The following table compares among the four algorithms P2 40 RR, IRR, AAIRR and ERR with respect to average waiting time and average turnaround time. P3 5 Table 2. Comparison among the RR, IRR, AAIRR and ERR Algorithms P4 12 Algorithm Average Average P5 34 waiting time turnaround time RR 49.2 72.2 a) RR algorithm Enter the processes in the ready queue in the order; P1, IRR 46.8 69.8 P2, P3, P4 and P5. Each process is given a TQ= 12ms periodically. AAIRR 36.2 59.2 Gantt chart P1 P2 P3 P4 P5 P1 P2 P5 P2 P5 P2 ERR 43.4 66.4 0 12 24 29 41 53 65 77 89 101 111 115 Figures 5, 6 draw the average waiting time and the Figure 1: Gantt chart for RR Algorithm (Case 1) average turnaround time for the four algorithms RR, IRR, AAIRR and ERR algorithms. Average waiting time= 49.2 ms Average turnaround time= 72.2ms 60 e b) IRR algorithm m 50 Here the processes are scheduled according to the IRR g Ti 40 algorithm with TQ=12. n ti ai 30 W AWT Gantt chart e  20 P1 P2 P3 P4 P5 P1 P2 P5 P2 ag r 0 12 24 29 41 53 65 77 99 115 e 10 v Figure 2: Gantt chart for IRR Algorithm (Case 1) A 0 Average waiting time= 46.8 ms RR IRR AAIRR ERR Average turnaround time= 69.8 ms Figure 5: Graph for Average Waiting Time for RR, IRR, AAIRR and ERR algorithms (Case 1) 31 Automatic Control and System Engineering Journal, ISSN 1687-4811, Volume 17, Issue 2, ICGST, Delaware, USA, December 2017 ATT Gantt chart d  P1 P2 P3 P4 P5 P3 P4 P5 n u 0 7 17 27 37 47 57 73 93 o 100 r Figure 8: Gantt chart for IRR Algorithm (Case 2) a urnme 50 Average waiting time= 30.8 m s ge TTi 0 ATT Average turnaround time= 49.4 ms a r e v A c) AAIRR algorithm Figure 6: Graph for Average Turnaround Time for RR, IRR, AAIRR Here the processes are scheduled according to the and ERR algorithms (Case 1) AAIRR algorithm with TQ=10. From Figures 5, 6 it is noticed that the algorithms IRR, AAIRR and ERR give better results than the standard Gantt chart Round Robin algorithm for the average waiting time and P1 P2 P3 P4 P5 P4 P5 the average turnaround time. By comparing the results of 0 7 17 37 47 57 73 93 the three algorithms, it is noticed that the ERR algorithm Figure 9: Gantt chart for AAIRR Algorithm (Case 2) reduces the average waiting time and average turnaround time than the IRR algorithm. However the AAIRR Average waiting time= 26.8ms algorithm is the best one of them. Average turnaround time= 45.4ms Case 2: the burst time of the processes is in an increasing order d) ERR algorithm Consider five processes with a randomly increasing order Here the processes are scheduled according to the ERR of burst time shown in Table 3 assume that TQ=10ms, algorithm with TQ=10. we apply the algorithms RR, IRR, AAIRR and ERR to Gantt chart schedule these processes and the resulting Gantt charts P1 P2 P3 P4 P5 P4 P5 for the RR, IRR, AAIRR and ERR algorithms are shown 0 7 17 37 47 57 73 93 in Figures 7, 8, 9 and 10 respectively. Figure 10: Gantt chart for ERR Algorithm (Case 2) Average waiting time= 26.8 ms Table 3. Burst time in an increasing order Average turnaround time= 45.4 ms process Burst time P1 7 The following table compares among the four algorithms RR, IRR, AAIRR and ERR with respect to average P2 10 waiting time and average turnaround time. P3 20 Table 4. Comparison among the RR, IRR, AAIRR and ERR Algorithms P4 26 Algorithm Average Average P5 30 waiting time turnaround time RR 32.8 51.4 a) RR algorithm Enter the processes in the ready queue in the order; P1, IRR 30.8 49.4 P2, P3, P4 and P5. Each process is given a TQ=10ms periodically. AAIRR 26.8 45.4 Gantt chart ERR 26.8 45.4 P1 P2 P3 P4 P5 P3 P4 P5 P4 P5 0 7 17 27 37 47 57 67 77 83 93 Figures 7, 8 draw the average waiting time and the Figure 7: Gantt chart for RR Algorithm (Case 2) average turnaround time for the four algorithms RR, IRR, AAIRR and ERR. Average waiting time= 32.8 ms Average turnaround time= 51.4ms b) IRR algorithm Here the processes are scheduled according to the IRR algorithm with TQ=10. 32 Automatic Control and System Engineering Journal, ISSN 1687-4811, Volume 17, Issue 2, ICGST, Delaware, USA, December 2017 a) RR algorithm 35 Enter the processes in the ready queue in order; P1, P2, e  m 30 P3, P4 and P5. Each process is given a TQ=15ms g ti 25 periodically. n ti 20 ai Gantt chart w 15 ge  10 AWT P1 P2 P3 P4 P5 P1 P2 P3 P4 P1 P2 a ver 5 0 15 30 45 60 70 85 100 115 118 133 139 A Figure 13: Gantt chart for RR Algorithm (Case 3) 0 RR IRR AAIRR ERR Average waiting time= 87.2 ms Average turnaround time= 115ms b) IRR algorithm Figure 11: Graph for Average Waiting Time for RR, IRR, AAIRR and Here the processes are scheduled according to the IRR ERR algorithms (Case 2) algorithm with TQ=15. 52 Gantt chart e m50 P1 P2 P3 P4 P5 P1 P2 P3 P1 ge d Ti48 an46 0 15 30 45 63 73 88 109 124 139 ru Avearo44 ATT Figure 14: Gantt chart for IRR Algorithm (Case 3) n42 ur Average waiting time= 73.8 ms T Average turnaround time= 101.6 ms c) AAIRR algorithm Figure 12: Graph for Average Turnaround Time for RR, IRR, AAIRR Here the processes are scheduled according to the and ERR algorithms (Case 2) AAIRR algorithm with TQ=15. From above Figures 11, 12 it is noticed that the Gantt chart algorithms IRR, AAIRR and ERR are doing better than P1 P5 P4 P3 P2 P1 P2 standard Round Robin algorithm for the average waiting time and the average turnaround time. For the other three 0 15 25 43 73 88 118 139 algorithms, it is noticed that the ERR algorithm gives the Figure 15: Gantt chart for AAIRR Algorithm (Case 3) same results as the AAIRR algorithm because of the Average waiting time= 51.8ms increasing order of the incoming processes. But the IRR Average turnaround time= 79.6ms algorithm gives high results than both of them. The benefit of AAIRR algorithm which is selecting the next d) ERR algorithm short process to assign it to the CPU which leads to Here the processes are scheduled according to the ERR minimize the average waiting time and average algorithm with TQ=15. turnaround time is not exist. Gantt chart Case 3: The burst time of the processes is in decreasing order P1 P2 P3 P4 P5 P1 P2 Consider five processes with a randomly decreasing 0 15 30 60 78 88 118 139 order of burst time shown in Table 5. Assume that Figure 16: Gantt chart for ERR Algorithm (Case 3) TQ=15ms, we apply the algorithms RR, IRR, AAIRR Average waiting time= 68.8 ms and ERR to schedule these processes and the resulting Average turnaround time= 96.6 ms Gantt charts for the RR, IRR, AAIRR and ERR algorithms are shown in Figures 13, 14, 15 and 16 The following table compares among the four algorithms respectively. RR, IRR, AAIRR and ERR with respect to average waiting time and average turnaround time. Table 5. Burst time in decreasing order process Burst time P1 45 P2 36 P3 30 P4 18 P5 10 33 Automatic Control and System Engineering Journal, ISSN 1687-4811, Volume 17, Issue 2, ICGST, Delaware, USA, December 2017 Table 6. Comparison among the RR, IRR, AAIRR and ERR Algorithms 2.2 Description of the Round Robin algorithms with calculated time Algorithm Average Average quantum and their Experimental data waiting time Turnaround time 2.2.1 Adaptive Round Robin Scheduling Algorithm RR 87.2 115 (Adaptive RR) This algorithm improved the Round Robin algorithm. It IRR 73.8 101.6 is a “priority scheduling algorithm” based on the burst time of processes. It is composed of two phases. First, the AAIRR 51.8 79.6 processes are arranged according to the burst time. The highest priority is given to the process with smallest burst ERR 68.8 96.6 time. This approach chooses the smart time slice depending on the number of processes. If the number of processes is even, then the smart time slice will be the Figures 17, 18 draw the average waiting time and the average of the burst of all processes. If the number of average turnaround time for the RR, IRR, AAIRR and processes is odd, then the smart time slice is equal to the ERR algorithms. burst time of the mid-process [14]. 140 me 120 Adaptive Round Robin Pseudo code as follow. g ti 100 n ti 80 1. First of all check ready queue is empty ai 2. When ready queue is empty then all the w 60 AWT e  processes are assigned into the ready queue. ag 40 3. All the processes are rearranged in increasing r ve 20 order that means smaller burst time process get A higher priority and larger burst time process get 0 lower priority. RR IRR AAIRR ERR 4. While (ready queue != NULL) 5. Calculate smart Time Slice: Figure 17: Graph for Average Waiting Time for RR, IRR, AAIRR and ERR algorithms (Case 3) If (Number of process%2= = 0) STS = average CPU burst time of all processes 100 Else e m STS = mid process burst time d ti 80 6. Assign smart time slice to the ith process: un 60 Pi _ STS o r 7. If (i< Number of process) then go to step 6. a rn 40 ATT 8. If a new process is arrived update the ready u e t 20 queue, go to step 2. g 9. End of While a er 0 10. Calculate average waiting time, turnaround time, v A context switches and throughput. 11. End Figure 18: Graph for Average Turnaround Time for RR, IRR, AAIRR and ERR algorithms (Case 3) 2.2.2 Round Robin Remaining Time Algorithm (RRRT) From Figures 17, 18 it is noticed that the algorithms IRR, This algorithm improved the Adaptive Round Robin AAIRR and ERR give better results than the standard Scheduling algorithm. It assumes that all processes arrive Round Robin algorithm for the average waiting time and at the same time in the ready queue, then they are the average turnaround time. By comparing the results of arranged in an ascending order according to their burst the three algorithms, it is noticed that the ERR algorithm time. TQ is calculated by Σ pi / 2n. If the remaining CPU reduces the average waiting time and average turnaround burst time of the currently running process is less than the time than the IRR algorithm. However the AAIRR TQ, the CPU is again allocated to the currently running algorithm is the best one of them. process for the remaining CPU burst time. Otherwise, the Hence, the AAIRR algorithm is the algorithm which process will be added to the end of the ready queue [15]. gives the best results in random and decreasing cases. But in the case of increasing order it gives the same results as the ERR algorithm. 34 Automatic Control and System Engineering Journal, ISSN 1687-4811, Volume 17, Issue 2, ICGST, Delaware, USA, December 2017 The pseudo code of the Round Robin Remaining Time b) Adaptive RR algorithm Algorithm: Arrange the processes in the ready queue in an ascending 1. Assign Process to ready queue. order of their burst time; P3=6, P1=18, P5=21, P4=28 2. Rearrange all the process in increasing order of and P2=38. Since the number of processes is odd, the their burst time time quantum is set to be the burst time of the mid 3. While (ready queue! =NULL) process. Hence, TQ=21 according to Adaptive RR 4. Calculate time quantum =Σpi / 2*n algorithm. 5. if (remaining burst time < time quantum ) Allocate CPU again to the current running Gantt chart process for remaining burst time P3 P1 P5 P4 P2 P4 P2 Else 0 6 24 45 66 87 94 111 Remove the current running process from the Figure 20: Gantt chart for Adaptive RR Algorithm (Case 1) ready queue and put it at the tail of the ready queue. Average waiting time= 33.8 ms 6. If no of process > 0 Go to 5 Average turnaround time= 56 ms 7. End while 8. Calculate average waiting time, average turnaround time. c) RRRT algorithm Arrange the processes in the ready queue according to 2.1.3 Experimental data their given burst time in an ascending order; P3=6, There are three cases for incoming burst time; random, P1=18, P5=21, P4=28 and P2=38. The time quantum is increasing and decreasing. The order of the processes calculated according to the RRRT Algorithm. The affects the results of the Round Robin algorithm since the resulting TQ is 11ms. processes are executed in their given order, whereas in the other algorithms the burst time of the processes is Gantt chart arranged in an ascending order in all cases. The results of the three cases are described below. P3 P1 P5 P4 P2 P4 P2 Case 1: The burst time of the processes is random 0 6 24 45 56 67 84 111 Figure 21: Gantt chart for RRRT Algorithm (Case 1) Consider five processes with a random burst time shown in Table 7. We apply the algorithms RR, Adaptive RR Average waiting time= 31.8ms and RRRT to schedule these processes and the resulting Average turnaround time= 54ms Gantt charts for the RR, Adaptive RR and RRRT algorithms are shown in Figures 19, 20 and 21 The following table compares among the three respectively. algorithms RR, Adaptive RR and RRRT with respect to average waiting time and average turnaround time. Table 7. Five processes with random burst time process Burst time Table 8. Comparison among the RR, Adaptive RR and RRRT Algorithms P1 18 Algorithm Average Average P2 38 waiting time Turnaround time P3 6 RR 59 81.2 P4 28 Adaptive RR 33.8 56 P5 21 Round Robin 31.8 54 Remaining Time a) RR algorithm Figures 22, 23 draw the average waiting time and the Enter the processes in the ready queue in the order; P1, average turnaround time for the RR, Adaptive RR and P2, P3, P4 and P5. Each process is given a TQ= 14ms RRRT algorithms. periodically. Gantt chart P1 P2 P3 P4 P5 P1 P2 P4 P5 P2 0 14 28 34 48 62 66 80 94 101 111 Figure 19: Gantt chart for RR Algorithm (Case 1) Average waiting time= 59ms Average turnaround time= 81.2ms 35 Automatic Control and System Engineering Journal, ISSN 1687-4811, Volume 17, Issue 2, ICGST, Delaware, USA, December 2017 b) Adaptive RR algorithm 80 Arrange the processes in the ready queue in an ascending e m order of their burst time; P1=15, P2=19, P3=23, P4=47 g ti 60 and P5=56. Since the number of processes is odd, the tin 40 time quantum is set to be the burst time of the mid ai AWT process. Hence, TQ=23 according to Adaptive RR w 20 e  algorithm. g a 0 Gantt chart r ve RR Adaptive RRRT P1 P2 P3 P4 P5 P4 P5 P4 P5 A RR 0 15 34 57 80 103 126 149 150 160 Figure 25: Gantt chart for Adaptive RR Algorithm (Case 2) Figure 22: Graph for Average Waiting Time for RR, Adaptive RR and RRRT algorithms (Case 1) Average waiting time= 51.2 ms Average turnaround time= 83.2 ms 100 me 80 ge d ti 4600 cA)r RraRngReT tahleg oprriothcems ses in the ready queue according to an erou 20 ATT their given burst time in an ascending order; P1=15, Avar 0 P2=19, P3=23, P4=47 and P2=56. The time quantum is n r calculated according to the RRRT Algorithm. The TQ is u t calculated as 16ms. Gantt chart Figure 23: Graph for Average Turnaround Time for RR, Adaptive RR P1 P2 P3 P4 P5 P4 P5 and RRRT algorithms (Case 1) 0 15 34 57 73 89 120 160 Case 2: The burst time of the processes is in an Figure 26: Gantt chart for RRRT Algorithm (Case 2) increasing order Consider five processes with a randomly increasing order Average waiting time= 45.2ms of burst time shown in Table 9. We apply the algorithms Average turnaround time= 77.2ms RR, Adaptive RR and RRRT to schedule these processes The following table compares among the three and the resulting Gantt charts for the RR, Adaptive RR algorithms RR, Adaptive RR and RRRT with respect to and RRRT algorithms are shown in Figures 24, 25 and 26 average waiting time and average turnaround time. respectively. Table 10. Comparison among the RR, Adaptive RR and RRRT Algorithms Table 9. Five processes with random burst time Algorithm Average Average process Burst time waiting time Turnaround P1 15 time RR 58 90 P2 19 Adaptive RR 51.2 83.2 P3 23 Round Robin 45.2 77.2 P4 47 Remaining P5 56 Time Figures 27, 28 draw the comparison of average waiting time and average turnaround time for the RR, Adaptive a) RR algorithm RR and RRRT algorithms. Enter the processes in the ready queue in order; P1, P2, P3, P4 and P5. 80 g  Each process is given a TQ= 20ms periodically. n ti 60 ai e wme 40 Gantt chart agti 20 AWT r P1 P2 P3 P4 P5 P3 P4 P5 P4 P5 e v A 0 0 15 34 54 74 94 97 117 137 144 160 RR Adaptive RRRT Figure 24: Gantt chart for RR Algorithm (Case 2) RR Average waiting time= 58ms Average turnaround time= 90ms Figure 27: Graph for Average Waiting Time for RR, Adaptive RR and RRRT algorithms (Case 2) 36 Automatic Control and System Engineering Journal, ISSN 1687-4811, Volume 17, Issue 2, ICGST, Delaware, USA, December 2017 Gantt chart 95 P5 P4 P3 P2 P1 P2 P1 P2 P1 90 0 15 35 61 87 113 139 165 166 184 e m Figure 30: Gantt chart for Adaptive RR Algorithm (Case 3) nd ti 85 Average waiting time= 55.4 m s rou 80 ATT Average turnaround time= 92.2 ms a n ur 75 c) RRRT algorithm t e  Arrange the processes in the ready queue according to g a 70 their given burst time in an ascending order; P5=15, r ve RR Adaptive RRRT P4=20, P3=26, P2=53 and P1=70. The time quantum is A calculated according to the RRRT Algorithm. The TQ is RR calculated as 18ms. Figure 28: Graph for Average Turnaround Time for RR, Adaptive RR and RRRT algorithms (Case 2) Gantt chart P5 P4 P3 P2 P1 P2 P1 Case 3: The burst time of the processes is in decreasing order 0 15 35 61 79 97 132 184 Consider five processes with a randomly decreasing Figure 31: Gantt chart for RRRT Algorithm (Case 3) order of burst time shown in Table 11. We apply the Average waiting time= 48.6ms algorithms RR, Adaptive RR and RRRT to schedule Average turnaround time= 85.4ms these processes and the resulting Gantt charts for the RR, Adaptive RR and RRRT algorithms are shown in Figures The following table compares among the three 29, 30 and 31 respectively. algorithms RR, Adaptive RR and RRRT with respect to average waiting time and average turnaround time. Table 11. Burst time in decreasing order process Burst time Table 12. Comparison among the RR, Adaptive RR and RRRT Algorithms P1 70 Algorithm Average Average P2 53 waiting time Turnaround time P3 26 RR 109.4 146.2 P4 20 Adaptive RR 55.4 92.2 P5 15 Round Robin 48.6 85.4 Remaining Time a) RR algorithm Figures 32, 33 draw the comparison of average waiting Enter the processes in the ready queue in order; P1, P2, time and average turnaround time for the RR, Adaptive P3, P4 and P5. RR and RRRT algorithms. Each process is given a TQ= 25ms periodically. 120 Gantt chart e100 m P1 P2 P3 P4 P5 P1 P2 P3 P1 P2 g ti 6800 0 25 50 75 95 110 135 160 16 181 184 aitin 2400 AWT Figure 29: Gantt chart for RR Algorithm (Case 3) w 0 e  g Average waiting time= 109.4ms a r Average turnaround time= 146.2ms ve A b) Adaptive RR algorithm Arrange the processes in the ready queue in an ascending Figure 32: Graph for Average Waiting Time for RR, Adaptive RR and order of their burst time; P5=15, P4=20, P3=26, P2=53 RRRT algorithms (Case 3) and P1=70. Since the number of processes is odd, the time quantum is set to be the burst time of the mid process. Hence, TQ=26 according to Adaptive RR algorithm. 37 Automatic Control and System Engineering Journal, ISSN 1687-4811, Volume 17, Issue 2, ICGST, Delaware, USA, December 2017 4. //Assign TQ to (1 to n) process 200 for i = 1 to n d  150 { n u Pi → TQnew o 100 r } a urnme 50 ATT end for ge tti 0 5. C// aAlcsusliagtne TQthnee w troe malal itnhien ga vabiluarbslte ptirmocee ssoefs . the a er processes. v A 6. if ( new process is arrived and BT != 0 ) go to step 1 else if ( new process is not arrived and BT != 0 ) go to step 2 Figure 33: Graph for Average Turnaround Time for RR, Adaptive RR and else if ( new process is arrived and BT == 0) RRRT algorithms (Case 3) go to step 1 else go to step 7 3. Dynamic TQ end if The performance of RR algorithm depends on the fixed end while Time Quantum [6]. If it assumes a large TQ, then many 7. Calculate ATT, AWT and CS. processes whose burst time less than TQ will be finished //ATT = Average Turnaround Time during its TQ. Hence the RR algorithm tends to be a //AWT = Average Waiting Time FCFS algorithm. On the other hand if TQ is very small, //CS = number of Context Switches the processes will be interrupted many times. These 8. End interruptions increase the overhead of the CPU which leads to a large number of context switches. Flowchart of Min-Max Round Robin (MMRR) A dynamic TQ may changes many times during the algorithm execution of the algorithm depending on the current values of the process’s burst time [16]. Many algorithms are developed to improve the efficiency 3.2 The improved Round Robin CPU scheduling of the RR algorithm using dynamic TQ. algorithm with varying time quantum (IRRVQ) The following is a comparison among the MMRR, This algorithm associates the features of SJF and RR IRRVQ, AMRR [17] [18] [19] and RR algorithms. scheduling algorithms with varying time quantum. First, it arranges all the processes in the ready queue in an 3.1 Min-Max Dispersion Measure (MMRR) ascending order. The processes are allocated to the CPU This algorithm depends on dynamic TQ; the processes using RR scheduling with time quantum value equal to are sorted in an increasing order of their burst time. It the first process's burst time in the ready queue. After takes TQ as the range of the CPU burst time of all the each iteration the remaining processes are again arranged processes which is the difference between the maximum in an ascending order and allocated to the CPU using RR and minimum values of the processes’ burst time. If this scheduling with TQ equal to the burst time of the first range is less than 25 then the next TQ is set to 25, process in the ready queue [8]. otherwise the next TQ is set to the calculated TQ [7]. Pseudo code of the IRRVQ CPU scheduling Pseudo code for Min-Max Round Robin (MMRR) algorithm is as follow. algorithm is as follow. 1. All the processes present in the ready queue are 1. Make a ready queue RQUEUE of the sorted in ascending order. Processes submitted for execution. //n = number of processes, i = loop variable 2. DO steps 3 to 9 WHILE queue RQUEUE 2. while ( RQ != NULL ) becomes empty. //RQ = Ready Queue 3. Arrange the processes in the ready queue TQ = MAXBT – MINBT REQUEST in the ascending order of their //TQ = Time Quantum remaining burst time. //MAXBT = MAXimum Burst Time 4. Set the time quantum value equal to the burst //MINBT = MINimum Burst Time time of first process in the ready queue (Remaining burst time of the processes) RQUEUE. // If one process is there then TQ is equal to BT 5. Pick the first process from the ready queue of itself RQUEUE and allocate CPU to this process 3. if (TQ < 25) for a time interval of up to 1 time quantum. set TQnew = 25 6. Remove the currently running process from else the ready queue RQUEUE, since it has set TQnew = TQ finished execution and the remaining burst end if time is zero. 38