Number of algorithms are designed and experimented by researchers for task scheduling to optimize the CPU usage and minimize the execution time of each process. This paper focusses on the work related to improvising Round-Robin scheduling. Several algorithms suggested by earlier researchers are studied in detail. At the end of the section, observations are also tabulated for a quick glimpse to compare literature study and their respective outcomes.
Several researchers have suggested various formulae for optimum value of time-slice and tried to incorporate the dynamic nature in the Round Robin Scheduling by varying the time-slice after each iteration. The performance is finally evaluated and represented in comparison to earlier algorithms through several metrics such as: Average Waiting Time (AWT), Average Completion Time (ACT), Context Switches (CS), Average Response Time (ART), etc.
Pandaba Pradhan, Prafulla Ku. Behera, B N B Ray [1] suggests an improved dynamic Round-Robin algorithm. The author, in the first iteration, keeps time-slice equal to the first job in the queue and for all subsequent iterations, the time-slice is made equal to the average of the burst times of the jobs remaining in the ready queue. The results so obtained are compared with static Round-Robin algorithm.
Saqib Ul Sabha [2] arranges the jobs in the increasing order of burst time and initial time-slice is randomly chosen.The Algorithm, then compares the time-slice with the burst time of each job in the queue and execute the process completely if remaining burst time is less than or equal to half the time slice. The queue is sorted only if there is any new process entering the queue at the end of each iteration.
Linz Tom. and Bindu V.R. [3] sort the tasks and VMs in the decreasing order of their processing power and apply an improved algorithm (Dynamic Task scheduling Based on Completion Time) DTBCT. The author has suggested maintaining multiple queues and binding the tasks to VMs in the sorted order and migrate the tasks based on the completion time in the dynamic mode. Time-Slice is dynamically set based on the burst time of the task under execution.
An improvement in average response time, number of context switches, average waiting time, and average make span is established in relation to the static RR, FCFS and SJF.
Sakshi et.al [4] discusses various schemes of the dynamic round-robin scheduling with dynamic time-slice as:
- TS = (Average BT + Highest BT)/2 Average Median RR (AMRR) --- (1)
- TS = Average BT A new Round Robin (ANRR) --- (2)
- TS = Ö median * Highest BT Modified Median RR algorithm(MMRRA)--- (3)
The author then suggests the new improved algorithm by calculation of dynamic time slice as:
- TS = (Average BT + Median BT) /2 Median Average Round Robin(MARR) --- (4)
and author experimentally proves that this performs better than the earlier two schemes.
Abdulaziz A. Alsulami et.al [5] suggests four different algorithms based on the calculation of TS as:
- TS = (Max Burst Time + Min Burst Time) Optimum Round-Robin using Manhattan Distance (ORRMD) --- (5)
- TS = Ö (Median Burst Time * Highest Burst Time) Improved Round-Robin Algorithm (IRR) ---(6)
- TS = Median Burst Time Adaptive Round-Robin Algorithm (ARRA) ---(7)
- TS = (Mean + Median) of the Burst Times/2 Best Time Quantum Round-Robin CPU Scheduling Algorithm (BTQRR) ----(8)
Although author claims better results of (5) and (7) as compared to (6) and (8), the results reveal that the number of context switches is significantly higher in (5) and average response time is longer in (7) when compared with other algorithms.
Uferah Shafi et.al [6] discusses the variations of improvements to traditional Round Robin in the related literature study and uses them to compare the devised algorithm in his results. The variations of RR mentioned in the paper are:
- Improved Round Robin (IRR)
- Optimum Multilevel Dynamic Round Robin (OMDRR)
- Priority based Round Robin (PRR)
IRR: First Iteration is RR and subsequent iterations are SJF.
OMDRR: Steps followed in this algorithm are:
- Processes are ordered
- Intelligent time slice is applied
- After each iteration, time slice is doubled
- Depending on the remaining burst time, condition is applied to reduce waiting time.
PRR: In the first iteration, processes are executed in the order of priority. Subsequent iterations arrange the processes for execution based on the remaining burst time.
Uferah Shafi et.al [6] then suggests the following algorithm
TS = Lowest BT
If (TS < Threshold)
TS = Threshold
End If
Do
{ Execute first task in Ready Queue (RQ)
If (Remaining BT < TS/2)
Pre-empt the process
Else
Place the process in the end of RQ
End If
} While (RQ != NULL)
The algorithm basically reduces to the one in [2].
Sanaj M S, Dr. Joe Prathap P M [7], in their literature study mention the Ant Colony Optimization (ACO), Genetic Algorithm (GA), Multiple Pheromone Algorithm (MPA) which is a variation of ACO, FCFS, Particle Swarm Optimization (PSO). The author suggests the simple setting of time slice as mean value, which in normal distribution of data, tends to be the median itself.
Shihab Ullah [8] refers to an algorithm “Optimum Dynamic Time Slicing Round Robin Scheduling” (ODTSRR) in which time slice is set to median of the burst times in the queue. Then, after execution of each process, if the remaining burst time is less than the time slice, the process is completed to reduce waiting time.
Shihab Ullah [8], then recommends a new algorithm “Improved Optimum Dynamic Time Slicing Round Robin Scheduling Algorithm (IODTSRR)” in which the process is executed to completion if the burst time is less than or equal to twice the time slice.
Rahul Mishra, Gaurav Mitawa [9] advises the “Improved Round Robin Algorithm for effective Scheduling Process for CPU” which is about setting time slice to average burst time and executing the process to its completion if the remaining burst time is less than time slice.
In totality, the referred literature predominantly selects the time slice as mean, median, (mean+median)/2, (mean + maximum)/2, ÖMedian * Highest BT and combines Round Robin with Shortest Job First to reduce waiting time. Most of the referred literature works on a data set that is very small. Table 1 below gives the summary of the literature study.
Table 1
Comparison of previous research work on Improvisation of Round Robin Scheduling
Sl No
|
Paper Title
|
Algorithm
|
Dynamic/Static
|
Time-Slice/Algorithm
|
Sorting of Jobs
|
No. Of Processes
|
Limitations
|
[1]
|
[1] Pandaba Pradhan, Prafulla Ku. Behera, B N B Ray Modified Round Robin Algorithm for Resource Allocation in Cloud Computing
|
Modified Round-Robin
|
Dynamic
|
TS = Average BT
|
No
|
5
|
Lacks the benefits of SJF as sorting is not done. Compared with RR.
|
[2]
|
[2] Saqib Ul Sabha,A Novel and Efficient Round Robin Algorithm with Intelligent Time Slice and Shortest Remaining Time First
|
Improved Round-Robin with Intelligent Time Quantum based on remaining BT
|
Dynamic
|
TS = Random value
If (BT <= 1.5*TS)
Execute the complete process
Else
Execute for Time = TS
End If
|
Initially sorted. After each iteration only on new job entering the queue
|
4
|
No improvement in turn around time when processes arrive at different times. Compared with RR.
|
[3]
|
[3] Linz Tom. And Bindu V.R., Dynamic Task scheduling Based on Burst Time requirement for cloud environment
|
Dynamic Task Scheduling Based on Completion Time(DTBCT)
|
Dynamic
|
TS = Average Burst Time
|
Yes
|
10-1000
|
Main work revolves around managing multiple queues based on burst time. Compared with RR, SJF and FCFS.
|
[4]
|
[4] Sakshi, Chetan Sharma, Shamneesh Sharma, Sandeep Kautish, Shami A. M. Alsallami, E.M. Khalil, Ali Wagdy Mohamed,
|
Median Average Round-Robin Algorithm (MARR)
|
Dynamic
|
TS = (Average + Median)/2
|
Yes
|
4, 6
|
Turn Around Time is not improved when compared to ANRR and no change in context switching when compared with AMRR, ANRR, MMRRA
|
[5]
|
[5] Abdulaziz A. Alsulami , Qasem Abu Al-Haija, Mohammed I. Thanoon , Qian Mao, “Performance Evaluation of Dynamic Round Robin Algorithms for CPU Scheduling”
|
1. Optimum Round-Robin using Manhattan Distance
2. Improved Round-Robin Algorithm
3. Adaptive Round-Robin Algorithm
Best Time Quantum Round-Robin CPU Scheduling Algorithm
|
Dynamic
Dynamic
Dynamic
Dynamic
|
TS = (Max BT + Min BT)
(ORRMD)
TS = Ö Median * Highest BT
(IRR)
TS = Median
(ARRA)
TS = (Mean + Median)/2
(BTQRR)
|
No
Yes
Yes
Yes
|
10,000
|
Average Response Time, Average Waiting Time and Average turn Around Time is better in ORRMD. Context Switching is better in ARRA
|
[6]
|
[6] Uferah Shafi, Munam Shah, Abdul Wahid, Kamran Abbasi , Qaisar Javaid , Muhammad Asghar, and Muhammad Haider, “A Novel Amended Dynamic Round Robin Scheduling Algorithm for Timeshared Systems”
|
Amended Dynamic Round Robin
|
Dynamic
|
TS = Lowest BT
If (TS < Threshold)
TS = Threshold
End If
Do
{ Execute first task in RQ
If (Remaining BT < TS/2)
Pre-empt the process
Else
Place the process in the end of RQ
End If
} While (RQ != NULL)
|
Yes
|
5
|
The results in terms of Average Waiting Time, Average Completion Time, Context Swithing got improved in the order of RR->PRR->OMDRR->IRR->ADRR
|
7
|
[7] Sanaj M S, Dr. Joe Prathap P M, “An Enhanced Round Robin (ERR) algorithm for Effective and Efficient Task Scheduling in cloud Environment”
|
An Enhanced Round Robin (ERR) algorithm for Effective and Efficient Task Scheduling in cloud environment
|
Dynamic
|
TS = Mean BT
|
Yes
|
7
|
Compares with PSO, GA, ACO, MPA, FCFS, Min-Min. But comparison is only on makespan and energy levels. Average waiting Time comparison is made with only basic RR
|
8
|
[8] Shihab Ullah, “Improved Optimum Dynamic Time Slicing Round Robin Algorithm”
|
Improved Optimum Dynamic Time Slicing Round Robin Scheduling Algorithm (IODTSRR)
|
Dynamic
|
TS = Median BT
If (Remaining BT < TS)
Execute the complete Process
End If
|
Yes
|
5, 8
|
Compares with ODTSRR. Context Switching has increased in IODTSRR when processes (7) arrive at different times.
|
9
|
[9] Rahul Mishra, Gaurav Mitawa “Improved Round Robin Algorithm for effective Scheduling Process for CPU”
|
Improved Round Robin Algorithm for effective Scheduling Process for CPU
|
Dynamic
|
TS = Average BT
If (Remaining BT < TS)
Execute the
complete process
End If
|
Yes
|
5
|
Compared with RR and CRR.
|