Task Scheduling is the process of assigning the incoming tasks to the available systems for optimum utilization of resources (CPU, Memory, Bandwidth, etc.). Optimum, in the present context implies executing maximum number of tasks using minimum of resources. In large scale Cloud Computing, resource optimization plays a critical role as it determines the quality of service (QoS) offered to customers. Therefore, task scheduling algorithm for parallel processing directly relates to QoS and is fundamental to understanding Resource Utilization, Inter-Process Communication, Network Latency, Load Balancing, Job Migration and Fault Tolerance. In this paper, an effort is made to explore and understand some of the basic scheduling algorithms through an experimental study. Algorithms are implemented in a cloud scenario. The results are construed with respect to several performance indicators that affect the QoS.
Research Article
Improvised Dynamic Round-Robin Scheduling for Optimum Resource Utilization in Cloud Systems
https://doi.org/10.21203/rs.3.rs-2063899/v3
This work is licensed under a CC BY 4.0 License
Version 3
posted
You are reading this latest preprint version
Round-Robin (RR)
Burst Time (BT)
Time Slice (TS)
Shortest Job First (SJF)
Average Completion Time (ACT)
Average Waiting Time (AWT)
Task scheduling is about allocating CPU time (a prime resource) to the applications and optimize its usage. This is one of the critical challenges in Cloud Computing. For allocating CPU time to the processes, scheduling strategies are applied. Job scheduler or Data Centre Broker distributes the incoming tasks to the available Virtual Machines. Cloud Computing, though, appears as centralised processing from the user’s perspective, behind the scenes it works as a distributed system by splitting the work among several virtual machines.
One of the popular scheduling algorithms is Round-Robin Scheduling. It is a pre-emptive and starvation-free job-scheduling algorithm used in traditional operating systems. In pre-emptive scheduling, the running task is forced to release the CPU and its associated resources to the next task in the queue. Here, all the processes are put in a ready queue. Time-Slice (TS) or Quantum Time (QT) is a small amount of time that is allocated to each process in the queue for execution. The CPU time required to complete the execution of a process is called its Burst Time (BT). Each process is executed for the duration of one Time-Slice. If the process is completed within a Time-Slice during execution, it is terminated. Otherwise, the incomplete process with remaining burst time gets added to the end of the ready queue. CPU iterates through the tasks one after another in multiple rounds till it completes all the tasks. In this circular way, each process gets a fair chance for execution.
Two major issues related to Round-Robin Scheduling are:
- Selection of Optimum Time-Slice
- Change the Time-Slice dynamically to suit the Cloud Systems where load keeps changing in an unpredictable manner.
Firstly, if the time-slice is very small, then the increased Context Switches (CS) cause more overhead and reduces the throughput. If the time-slice is high, then the shorter jobs wait for longer time which henceforth increases the Average Completion Time (ACT) worsening the performance. Therefore, an optimum time-slice or time-quantum is the key to obtain the maximum throughput.
Secondly, the jobs keep arriving at random times in a dynamic cloud computing environment and demand a dynamic scheduling strategy to suit the changing needs.
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 all the research works under study and their respective outcomes.
Several researchers have suggested various formulae for optimum value of time-slice and tried to incorporate the dynamic nature to suit the current computing platforms (Cloud/Edge/Fog) [15] in the Round Robin Scheduling by varying the time-slice after each iteration. They have evaluated performance and compared results with algorithms proposed by earlier researchers 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 mentions the nature inspired “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 completely executed 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.
Komal Mahajan [13] suggests saving the previous allocation state of a VM to a request from a given
Userbase providing server affinity to the tasks.
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] “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] “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] “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] “A new median-average round Robin scheduling algorithm: An optimal approach for reducing turnaround and waiting time” |
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] “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] “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] “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] “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] “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. |
Load Balancing in Cloud Systems play a crucial role for improvement in speed of execution and optimization of resource utilization. Load Balancing[12][14] is required at various stages.
- While allocating a Data Centre.
- While allocating VM within a Data Centre.
- While allocating CPU time for the jobs within a VM
This third stage of Load Balancing within a VM is considered in our research work through scheduling algorithms. Enthused by the laborious research in the direction of improving the popular Round-Robin algorithm to suit the present computing systems with Edge, Fog and IoT architecture, the dynamic algorithm is explored to further advancements to prove that it performs better.
Improvised Round-Robin Algorithm that performs better as compared to earlier research under study. Proposed work combines the advantages of Shortest Job First (SJF) and Round-Robin (RR) and ably suits the present large scale and unpredictable computing requirements.
By varying time slice in a Round Robin algorithm, the best results were obtained by combining SJF (Ordering tasks in the increasing order of their burst times) and by setting the time slice to a value that would clear the queue at any point of time in one single iteration. Hence the optimum time slice is proposed as
OTS = Burst Time of the second largest job in the queue --------(9)
An algorithm is proposed based on the Optimum Time Slice in (9) as “Novel Optimum Dynamic Approach to Round robin Scheduling” (NODARR).
Proposed Algorithm (NODARR)
Sort the processes in the ascending order of their Burst Time
Insert the processes into the Ready Queue
Time Slice = OTS // Second Largest Burst Time in Ready Queue
Initialize Completion Time of each process = 0
Initialize Waiting Time of each process = 0
Initialize Context Switches = 0
Set Iteration = 1
Do
{
While ( Ready Queue is not Empty)
{ For each task in Ready Queue
{
If (BT > = Time Slice)
Execute each task for one Time Slice
Completion Time = Completion Time + Time Slice
Waiting Time = Waiting Time + Time Slice
Context Switches = Context Switches + 1
Remaining BT = BT – Time Slice
Insert the process at the end of Ready Queue
Set Burst time = Remaining Burst Time
Else
Execute each task for BT
Completion Time = Completion Time + BT
Waiting Time = Waiting Time + BT
Context Switches = Context Switches + 1
Remaining BT = 0
Remove the process from Ready Queue
End If
} End For Loop
} End While
Rearrange the tasks in the ascending order of their Burst Time // Due to new entries
Time Slice = OTS
Iteration = Iteration + 1;
}
End Do
The experimental setup is made with following entities:
- Data Center 2. Data Center Broker 3. Hosts
- Processing Elements 5. Virtual Machines 6. Cloudlets
Number of Processing Elements (CPUs) = 1
Data Center Specifications:
Architecture = "x86"
Operating System = "Linux"
Virtual Machine = "Xen"
Cloudlet Specifications: 40 cloudlets of random Burst Times (1-100).
Host Specifications: 4 Hosts with one processing element in each host, having
RAM = 4096 MB
Storage = 1000000
Bandwidth = 10000
Virtual Machine Specifications: 4 Virtual Machines are created with the following details:
Size = 10000 MB
RAM = 512 MB
MIPS = 1000
Bandwidth = 1000
Simulator: cloudsim
Dataset: Google Dataset (https://zenodo.org/record/3696775#.YxtXFHZBy3A) on
“Problem instances for scheduling jobs with time windows on unrelated parallel machines”
The experiment is conducted in two phases.
- Phase-I: Processes are subjected to run under eight different settings using the Static and Dynamic RR and/or SJF, FCFS with wide variations of Time Slice.
- Phase-II: The algorithms producing best results under the phase-I are short-listed for comparison with our proposed algorithm.
Eight different settings are chosen for phase-I as:
Case 1: Static Round-Robin with Time-Slice = 5 secs
Case 2: Static Round-Robin with Time-Slice = 10 secs
Case 3: Static Round-Robin with Time-Slice = 20 secs
Case 4: Static Round-Robin with Time-Slice = (Average BT+ Highest BT) /2
Case 5: Static First Come First Serve (Non-Pre-Emptive)
Case 6: Static SJF + Round-Robin with Time-Slice = (Average BT + Highest BT) /2
Case 7: Dynamic Round-Robin with Time-Slice = (Average BT + Highest BT) /2
Case 8: Dynamic SJF + Round-Robin using Time-Slice = (Average BT + Highest BT) /2
The random burst times chosen for 40 tasks/processes/cloudlets are listed in Table 2 below for submission to 4 virtual machines in groups of 10 each.
Table 2: Burst Time of Input Processes
|
Process No |
VM-1 |
VM-2 |
VM-3 |
VM-4 |
|
P1 |
21 |
9 |
43 |
38 |
|
P2 |
72 |
57 |
99 |
34 |
|
P3 |
15 |
81 |
23 |
65 |
|
P4 |
19 |
7 |
13 |
29 |
|
P5 |
75 |
50 |
44 |
40 |
|
P6 |
30 |
90 |
10 |
61 |
|
P7 |
88 |
22 |
44 |
39 |
|
P8 |
58 |
73 |
37 |
83 |
|
P9 |
17 |
25 |
65 |
31 |
|
P10 |
11 |
48 |
55 |
70 |
|
Average BT |
40.60 |
46.20 |
43.30 |
49.00 |
6. Results and Experimental Analysis of Phase-I
When 40 tasks of Table 2 were subjected to eight different cases under 4 VMs, the results obtained for AWT, ACT and CS are tabulated in Table 3 below.
Table 3: Results of Phase-1
|
|
VM-1 |
VM-2 |
||||
|
ACT |
AWT |
CS |
ACT |
AWT |
CS |
|
|
Case-1 |
254 |
213 |
85 |
297 |
251 |
181 |
|
Case-2 |
255 |
214 |
45 |
292 |
246 |
50 |
|
Case-3 |
240 |
199 |
24 |
304 |
257 |
29 |
|
Case-4 |
269 |
229 |
14 |
285 |
239 |
14 |
|
Case-5 |
228 |
188 |
10 |
246 |
199 |
10 |
|
Case-6 |
267 |
226 |
13 |
284 |
237 |
13 |
|
Case-7 |
167 |
126 |
14 |
194 |
148 |
14 |
|
Case-8 |
167 |
126 |
14 |
194 |
148 |
14 |
|
|
VM-3 |
VM-4 |
||||
|
Case-1 |
292 |
249 |
270 |
385 |
385 |
371 |
|
Case-2 |
294 |
251 |
48 |
378 |
378 |
53 |
|
Case-3 |
295 |
252 |
27 |
355 |
355 |
29 |
|
Case-4 |
254 |
211 |
13 |
256 |
256 |
12 |
|
Case-5 |
238 |
195 |
10 |
249 |
249 |
10 |
|
Case-6 |
245 |
202 |
11 |
257 |
257 |
12 |
|
Case-7 |
171 |
128 |
11 |
227 |
227 |
13 |
|
Case-8 |
171 |
128 |
11 |
227 |
227 |
13 |
6 a. Analysis of the Results ( Case-3 under VM-3)
Figure 2 below shows the Gantt Chart of 10 processes running under VM-3 for Case-3.
From the Gantt Chart, the completion time of 10 processes are noted in the following Table - 3.
Table 4: Completion Time of 10 processes running under VM-3 (Case-III)
|
Process |
Completion Time |
|
P1 |
326 |
|
P2 |
433 |
|
P3 |
226 |
|
P4 |
73 |
|
P5 |
350 |
|
P6 |
103 |
|
P7 |
354 |
|
P8 |
283 |
|
P9 |
414 |
|
P10 |
389 |
Average Completion Time:
(326 + 433 + 226 + 73 + 350 + 103 + 354 + 283 + 414 + 389)/10 = 2951/10 = 295
Average Waiting Time (AWT): Average Waiting Time is defined as
AWT = Sum of ((Time of Completion - Burst Time) of each job) / Number of Jobs
So, for the above example,
AWT = ( 282 + 334 + 203 + 60 + 306 + 93 + 310 + 246 + 349 + 334) /10 = 252
Context Switches: Number of Context Switches is defined as
Context Switches (CS) = Sum of (Number of Iterations of Each Process)
For the sample case considered,
CS = 3 + 5 + 2 + 1 + 3 + 1 + 3 + 2 + 4 + 3 = 27
6 b. Analysis of the Results ( Case-8 under VM1)
Table 5 below lists the tasks and related averages and time-slice values in each iteration.
Table 5: Sorted Burst Times under VM 1
|
Burst Times |
Dynamic Averages |
Time Slices |
|
11, 15, 17, 19, 21, 30, 58, 72, 75, 88 |
41, 14, 5
|
64, 19, 5 |
Iteration 1:
Av= (11+15+17+19+21+30+58+72+75+88)/10
= 41
TS = (Average BT + Highest BT)/2 = (88 + 41)/2
= 64
As time-slice is 64, first seven tasks are executed completely and remaining 3 tasks are partly executed. The remaining burst times of these three tasks are 8, 11 and 24.
Iteration 2:
Av = (8 +11+24)/3
= 14
TS = (14 +24)/2
= 19
Now only last task is left incomplete with remaining burst time as 5.
Iteration 3:
Av = 5
TS = (5+5)/2
= 5
Average Completion Time :
(11 + 26 + 43 + 62 + 83 + 113 + 171 + 371 + 382 + 406) / 10 = 167
Average Waiting Time:
(0 + 11 + 26 + 43 + 62 + 83 + 113 + 300 + 307 + 318)/10 = 126
Total number of Context Switches:
(1 + 1 + 1 + 1 + 1 + 1 + 1 + 2 + 2 + 3) = 14
The total number of context switches of 10 tasks in each VM under the above mentioned eight different cases of different time-slice with/without ordering of tasks is given in the graph of Figure 3. From the graph, it is evident that the context switching is minimum for case-5 (FCFS).
But, considering the graph for completion time and waiting time as shown in Figure 4 and Figure 5 for the same tasks and VMs, best results are obtained for the case-7 and case-8. Therefore, these cases are short-listed for phase-II, where they are compared with the proposed algorithm.
7. Results of Phase-II ( Output of the proposed algorithm)
As short-listed in phase-I, the Round-Robin with SJF (case 6 and case 8) are considered in phase-II with time slice set to different values as suggested by earlier researchers. Then, they are compared with the proposed algorithm to prove that the proposed work is better in performance.
The 40 processes run earlier under 4 VMs (Table 2) are combined to run under one single VM using the proposed algorithm and the results so obtained are compared with the other algorithms of equation [4]. The results obtained are tabulated in Table 6 below for the proposed algorithm NODARR along with other algorithms referenced in [4]. The related graphs are indicated in figures 6 and 7.
Finally, the experiment is extended to run for 1000 processes to ascertain the better performance of the proposed algorithm. The results are depicted in figure 8. Here, again the proposed algorithm out-performed the other two algorithms in terms of all the three metrics: AWT, ACT and CS.
Table 6: Results of the proposed algorithm
|
Time Slice |
Algorithm |
CS |
ACT |
AWT |
|
TS = (Av+median)/2 |
MARR (4) |
73 |
851 |
806 |
|
TS = (Av+highest)/2 |
AMRR(1) |
48 |
678 |
633 |
|
TS = Second Largest |
NODARR (9) |
40 |
627 |
582 |
The results prove that the proposed algorithm performs better as compared to the other two algorithms as suggested in reference [4].
The proposed NODARR ( Novel Optimum Dynamic Approach to Round Robin) performed better as compared to earlier suggested algorithms under all variations of task lengths and data size. Therefore, the optimum solution to dynamic time slice in round-robin is proposed as:
Optimum TS (OTS) = BT of second largest task
The proposed algorithm is a fine blend of RR and SJF. It combines the best feature of Dynamic Time-Slice of RR at one end and Minimum Waiting Time of SJF at the other. Beyond these two benefits, Optimum Time Slice set to the proposed value reduces the iterations to the minimum, providing minimum context switching.
Unpredictable incoming task lengths can have random variations where average does not lie in the middle of the data set. Hence, it is not a correct measure to use average in the calculation of time slice.
7. Future Scope
The dynamic nature of cloud can be imitated through varying configurations of VMs and different start times of jobs. Also, the same algorithm can be extended to inter-VM allocation of jobs for load balancing across VMs. But, algorithm then need to be slightly modified to incorporate the latency times involved to transmit the tasks across VMs. A generalized algorithm at the load balancer to balance loads in the intra-VM and inter-VM allocation may be devised. In addition, fault-tolerance can be integrated to exhibit the job migration due to failure of any random VM.
Ethics Approval and consent to participate
Not applicable.
Consent for Publication
I, the undersigned, give my consent for the publication of identifiable details, which can include details within the text (“Material”) and article to be published in the Journal of Grid Computing
Availability of data and material
Google Dataset (https://zenodo.org/record/3696775#.YxtXFHZBy3A) on “Problem instances for scheduling jobs with time windows on unrelated parallel machines”
Competing Interests
We, Authors hereby declare that we do not have any financial/non-financial competing interests.
Authors' contributions
Suvarna N A is the main author
Dr. Rashmi Priya is the reviewer
Funding
Not applicable
Acknowledgements
Teaching Community at Large.
- Pandaba Pradhan, Prafulla Ku. Behera, B N B Ray (2016), “Modified Round Robin Algorithm for Resource Allocation in Cloud Computing”, Procedia Computer Science 85, 878 – 890
- Saqib Ul Sabha (2018), “ A Novel and Efficient Round Robin Algorithm with Intelligent Time Slice and Shortest Remaining Time First”, Materials Today Proceedings 5, 12009-12015.
- Linz Tom. and Bindu V.R. (2021), “Dynamic Task scheduling Based on Burst Time requirement for cloud environment”, International Journal of Computer Networks & Communications (IJCNC) Vol.13, No.5, September.
- Sakshi, Chetan Sharma, Shamneesh Sharma, Sandeep Kautish, Shami A. M. Alsallami, E.M. Khalil, Ali Wagdy Mohamed (2022), “A new median-average round Robin scheduling algorithm: An optimal approach for reducing turnaround and waiting time”, Alexandria Engineering Journal 61, 10527–10538.
- Abdulaziz A. Alsulami , Qasem Abu Al-Haija, Mohammed I. Thanoon , Qian Mao (2019), “Performance Evaluation of Dynamic Round Robin Algorithms for CPU Scheduling”, DOI: https://doi.org/0.1109/SoutheastCon 42311.2019.9020439
- Uferah Shafi, Munam Shah, Abdul Wahid, Kamran Abbasi , Qaisar Javaid , Muhammad Asghar, and Muhammad Haider (2020), “A Novel Amended Dynamic Round Robin Scheduling Algorithm for Timeshared Systems”, The International Arab Journal of Information Technology, Vol. 17, No. 1, January 2020.
- Sanaj M S, Dr. Joe Prathap P M, “An Enhanced Round Robin (ERR) algorithm for Effective and Efficient Task Scheduling in cloud Environment”, https://doi.org/10.1109/ ACCTHPA49271.2020.9213198
- Shihab Ullah, “Improved Optimum Dynamic Time Slicing Round Robin Algorithm” (2017), 3rd International Conference on Electrical Information and Communication Technology (EICT), 7-9 December 2017, Khulna, Bangladesh.
- Rahul Mishra, Gaurav Mitawa, “Improved Round Robin Algorithm for effective Scheduling Process for CPU” (2021), Proceedings of the Third International Conference on Intelligent Communication Technologies and Virtual Mobile Networks (ICICV 2021). IEEE Xplore Part Number: CFP21ONG-ART; 978-0-7381-1183-4
- [10] BING HU, (Senior Member, IEEE), FUJIE FAN, (Student Member, IEEE), KWAN L. YEUNG, (Senior Member, IEEE), AND SUGIH JAMIN (2018), “Highest Rank First: A New Class of Single-iteration Scheduling Algorithms for Input-queued Switches” IEEE Access, DOI: 10.1109/ACCESS.2017
- Mohammad Oqail Ahmad and Rafiqul Zaman Khan (2019), “Cloud Computing Modeling and Simulation using CloudSim Environment”, International Journal of Recent Technology and Engineering (IJRTE) ISSN: 2277-3878, Volume-8 Issue-2, July 2019.
- Shahbaz Afzal, G. Kavitha (2019), “Load balancing in cloud computing – A hierarchical taxonomical classification”, Journal of Cloud Computing: Advances, Systems and Applications https://doi.org/10.1186/s13677-019-0146.
- Komal Mahajan, Ansuyia Makroo and Deepak Dahiya (2013) “Round Robin with Server Affinity: A VM Load Balancing Algorithm for Cloud Based Infrastructure Journal of Information Processing Systems”, DOI: 10.3745/JIPS.2013.9.3.379.
- Altaf Hussain , Muhammad Aleem , Muhammad Arshad Islam, Muhammad Azhar Iqbal (2018), “A Rigorous Evaluation of State-of-the-Art Scheduling Algorithms for Cloud Computing”, IEEE Access, DOI: 10.1109/ACCESS.2018.2884480.
- Mung Chiang, Fellow, IEEE, and Tao Zhang, Fellow, IEEE (2016), “Fog and IoT: An Overview of Research Opportunities”, IEEE Internet of Things Journal, vol. 3, no. 6, December 2016.
No competing interests reported.