Improved Round Robin Scheduling Algorithm With

Varying Time Quantum *

1st FIAD Alaa 2rd Mekkakia Maaza Zoulikha 3nd BENDOUKHA Hayat
SIMPA LAB SIMPA LAB SIMPA LAB
USTO-MB USTO-MB USTO-MB
Oran,Algeria Oran,Algeria Oran,Algeria
alaa.fi[email protected] [email protected] [email protected]

Abstract—Cloud computing is a distributed computing model; A. Deployment models

which refers to manipulating, configuring, and accessing the
applications online. It offers online data storage, infrastructure
A deployment model defines the purpose of the cloud and
and application. Task scheduling is one of the most important the nature of how the cloud is located. The NIST definition
issues in cloud environment, such as the tasks must be affected to for the four deployment models is as follows:
the appropriate virtual machines considering different factors at • Public cloud: The public cloud infrastructure is available
the same time, which leads to considering the task scheduling
for public use alternatively for a large industry group and
problem an NP-complete problem. This article presents an
improved ROUND ROBIN (RR) CPU scheduling algorithm with is owned by an organization selling cloud services.
varying time quantum. The appropriate algorithm proven better • Private cloud: The private cloud infrastructure is operated
than traditional RR and IRRVQ algorithms. The results show for the exclusive use of an organization. The cloud may
that the waiting time and turnaround time have been reduced in be managed by that organization or a third party. Private
the proposed approach compared to traditional RR and IRRVQ
clouds may be either on- or off-premises.
• Hybrid cloud: A hybrid cloud combines multiple clouds
Index Terms—Waiting Time, Burst Time, Round Robin
Scheduling, Turnaround Time. (private, community of public) where those clouds retain
their unique identities, but are bound together as a unit. A
hybrid cloud may offer standardized or proprietary access
I. I NTRODUCTION
to data and applications, as well as application portability.
As users begin to use clouds to store or run their appli- • Community cloud: A community cloud is one where the
cations, these systems become sensitive to workload issues. cloud has been organized to serve a common function or
The optimal and fastest selection of the virtual machine for a purpose. It may be for one organization or for several
specific task becomes an important problem, because an im- organizations, but they share common concerns such as
proper scheduling of tasks can reduce the system performance. their mission, policies, security, regulatory compliance
The proposed algorithm is an improved version of ROUND needs, and so on. A community cloud may be managed
ROBIN algorithm in which we focus on reducing the waiting by the constituent organization(s) or by a third party [2].
time and turnaround time of tasks and maximizing the resource B. Service models
utilization.
The rest of the paper is organized as follows Section II presents • SaaS (Software-as-a-Service) in this service, users use
the background of cloud computing, Section III focuses on applications remotely from the cloud.
some related work. While, in Section IV the proposed tech- • Infrastructure-as-a-service (IaaS) provides virtual ma-
nique is presented with multiple examples and finally, the chines, virtual storage, virtual infrastructure and other
conclusions is presented in Section V hardware resources with guaranted processing power.
• Platform-as-a-Service (PaaS) is similar to IaaS, but also
includes operating systems and required services for a
II. BACKGROUND
particular application. In other words, PaaS is IaaS with
Cloud computing can be defined as a new style of com- a custom software stack for the given application [3].
puting in which scalable and often virtualized resources are C. SCHEDULING IN CLOUD COMPUTING
provided as services on the Internet.This cloud model is com-
posed of three service models, and four deployment models Scheduling is one of the most important activities of cloud
[1]. computing. There are various task scheduling algorithms in
the cloud environment, whose primary purpose is to attribute
correctly the tasks arrived in the system to the resources
available to obtain the minimum waiting time of tasks. Among

c
978-1-7281-7503-4/20/$31.00 2020 IEEE 33

Authorized licensed use limited to: Singapore Institute of Technology (SIT). Downloaded on January 25,2021 at 09:44:12 UTC from IEEE Xplore. Restrictions apply.
these algorithms, we finds: FCFS, Round Robin, Min-Min, task assignment begins with a strategy different from the
Max-Min, PSO, genetic algorithm... last round. Its gives better result than Max-Min and Min-
• FCFS: First come First serve basis means that task that Min algorithms. But this study is only concerned with
come first will be execute first. the number of the resources to be odd [9].
• Round-Robin algorithm (RRA): it means that each task • IRRVQ algorithm: its a combination between SJF and
will be executed a time slice calling time quantum. In this RR scheduling algorithms with varying time quantum.
Scheduling algorithm time is to be given to resources in Initially the processes are arranged in the ascending order
a time slice manner. of their burst time in the ready queue. CUP is allocated
• Min-Min Algorithm: Min-Min algorithm selects the to the first process in the ready queue and time quantum
smaller tasks to be executed first. is put equal to his burst time. Processes are arranged in
• Max-Min algorithm: Max-Min algorithm selects the big- the ascending order after each cycle, the operation are
ger tasks to be executed first [4]. repeated until the ready queue is empty. The IRRVQ
shows his superiority compared to the traditional RR [10].
III. RELATED WORKS
Several studies and researches have been carried out in this IV. PROPOSED APPROACH
field: The proposed approach is an improved version of a task
• First-Come-First-Serve: in this algorithm, the tasks are scheduling algorithm ROUND ROBIN (RR). Initially, tasks
received and queued until the resource are available; once arriving in the ready queue are arranged in the ascending
that’s the case the tasks are mapped to them depending order of their burst time, using the medium of tasks, the
on their arrival time. No other criteria are considering for ready queue is divided into two sub-queues as follow: Tasks
this technique [5]. having burst time less than the medium are stored in the first
• Round Robin (RR): its similar to FCFS, but a small time queue (light task queue). And the rest of tasks in the second
unit called the time quantum or time slice is defined. Each queue (heavy task queue). The tasks in the first queue are
task run in the processor during this time quantum [6]. executed first following these steps: The CPU is allocated
• Min-Min: In this approach the tasks are collected into to tasks using RR scheduling with a small time unit, called
a set called meta-task (MT). It has two phases. In the time quantum equal to the burst time of the medium task,
first phase the expected execution time of each task are after each cycle the tasks in the queue are organized in
calculated. In the second phase a task with the overall ascending order of the remaining burst time and the process
minimum expected completion time in MT are chosen is repeated, until the queue is empty. After all the tasks
and mapped to the corresponding resource, then the task in the first queue have been executed, the same steps are
are removed from MT and this operation are repeated un- applied to schedule the tasks of the second queue. In what
til the MT are empty. Its gives better makespan compared follows we present the algorithmic description of the approach:
to FCFS and RR, but the QOS in not consider.
• Max-Min: Its similar to Min-Min algorithm, but in phase
1.Arrange the tasks in the ascending order
2 the Max-Min chose the task with maximum expected 2.Find the medium burst time
completion time and assign it to corresponding resource. 3. For all tasks
Max-min algorithm does better than Min-min algorithm 4. If MBT burst time of the task then put in light task
in cases when the number of short task is more than the queue
longer ones [7]. 5. Else put in heavy task queue
• Improved Max-Min heuristic model for task scheduling
6. End for
in cloud: its an improved version of Max-Min algorithm. // The tasks in the first queue are executed first following
The scheduler schedule by assign tasks with maximum these steps://
execution time to the resource which produce minimum 7. Quantum time == MBT
completion time rather than original Max-min assigns 7. For all light stacks do
task with maximum completion time to the resource 8. The CPU is allocated to tasks using RR scheduling
which provides minimum execution time.it gives better (Quantum time)
makespan than Max-Min, but no criteria are consider like 9. For all heavy tasks do
: scalability, availability, stability [8]. 10. The CPU is allocated to tasks using RR scheduling
• RASA algorithm: its a combination between to known
(Quantum time)
algorithms Max-Min and Min-Min. RASA uses the ad-
vantages of the both algorithms and covers their dis-
advantages. The remaining tasks are assigned to their
V. RESULTS AND DISCUSSION
appropriate resources by one of the two strategies, al-
ternatively. For instance, if the first task is assigned to a A. Case 1
resource by the Min-min strategy, the next task will be Five processes P1, P2, P3, P4 and P5 have been considered.
assigned by the Max-min strategy. In the next round the The processes are arriving at time 0 with burst time 15, 32, 10,

34

Authorized licensed use limited to: Singapore Institute of Technology (SIT). Downloaded on January 25,2021 at 09:44:12 UTC from IEEE Xplore. Restrictions apply.
26 and 20 respectively. The processes P1, P2, P3, P4 and P5
are arranged in the ascending order of their burst time in the
ready queue which gives the sequence P3, P1, P5, P4 and P2.
The ready queue is divided into two sub-queues using medium
burst time . The first sub-queue contains the processes P3, P1
and P5, the second one contains P4 and P2.
Initially the processes of the first sub-queue are executed: The
time quantum value is set equal to the burst time of the process
medium i.e. 15. CPU is allocated to the processes P3, P1 and
P5 for a time quantum of 15 milliseconds (ms). After the first
cycle, the burst time of processes P3, P1 and P5 are equal to Fig. 1. Comparison of RR, IRRVQ and proposed algorithm (Case1).
0, 0 and 5 respectively. The processes P3 and P1 are finished
execution so they are removed from the ready queue. The
time quantum value is set to the burst time of P5 i.e. 5. The
CPU is allocated to process P5 for a time quantum of 5 ms.
After second cycle; the burst time of P5 is 0 so the process is
removed from the ready queue.
The first sub-queue is empty so the second sub-queue begins
execution: The time quantum value is set equal to the burst Fig. 2. Gantt chart representation of RR with TQ=10 (Case1).
time of medium process, in this case we have two processes
P4 and P2 so we calculate the average of their burst time so
its equal to 29. CPU is allocated to the processes P4 and P2
from the ready queue for a time quantum of 29 ms. After
third cycle, the burst time of P4 and P2 are 0, 3 respectively.
The process P4 has finished execution, so its removed from
the ready queue. Now only P2 in the ready queue, so CPU
is allocated to P2 for a time quantum of 3 ms. The waiting
time of P1 is 10 ms, for P2 is 71 ms, 0 ms for P3, 45 ms for Fig. 3. Gantt chart representation of IRRVQ (Case1).
P4, 25 ms for P5. The average waiting time is 30.2 ms. With
same number of processes with same arrival and CPU burst
times, the average waiting time is 54.2 ms for time quantum
10 in RR, and 46.2 ms for time quantum 10, 5, 5, 6, 6 in
IRRVQ. The average turnaround time is 50.8 ms in proposed
algorithm while average turnaround time is equal to 74.8 for

Fig. 4. Gantt chart representation of proposed algorithm (Case1).

TABLE I
P ROCESSES WITH THEIR ARRIVAL AND BURST TIME (C ASE 1).
time quantum 10 in RR, and 66.8 for time quantum 10, 5, 5,
Arrival Burst
Processes 6, 6 in IRRVQ.
time time The comparison result of RR, IRRVQ and proposed algorithm
P1 0 15 is shown in Table 2 and Fig. 1.
P2 0 32 Fig. 2 show the Gantt chart representation of RR with time
P3 0 10 quantum 10.
P4 0 26
Fig. 3 show the Gantt chart representation of IRRVQ with time
quantum 10, 5, 5, 6, 6 respectively.
P5 0 20
Fig. 4 show the Gantt chart representation of proposed algo-
rithm.
TABLE II
C OMPARISON OF RR, IRRVQ AND PROPOSED ALGORITHM (C ASE 1). B. Case 2
Algorithm Time Quantum Average Waiting Time (ms) Average Turnaround Time (ms)
In this case processes are arriving at different time. Five
RR 10 54.2 74.8 processes P1, P2, P3, P4 and P5 arriving at time 0, 4, 10,
10, 5, 15, 17 respectively with burst time 7, 25, 5, 36, 18. The time
IRRVQ 46.2 66.8
5, 6, 6 quantum value is set equal to the burst time of the first process
Proposed 15, 5,
30.2 50.8 in the ready queue i.e. 7. CPU is allocated to the process P1
approach 29, 3
from the ready queue for a time quantum of 7 ms. After first

35

Authorized licensed use limited to: Singapore Institute of Technology (SIT). Downloaded on January 25,2021 at 09:44:12 UTC from IEEE Xplore. Restrictions apply.
TABLE III cycle, the burst time of P1 is 0 and P2 has arriving in the ready
P ROCESSES WITH THEIR ARRIVAL AND BURST TIME ( CASE 2). queue. The process P1 has finished execution, so its removed
from the ready queue. The time quantum value is set equal
Arrival Burst
Process to the burst time of P2 i.e. 25. CPU is allocated to P2 for a
Time Time time quantum of 25 ms. After second cycle, the burst time
P1 0 7 of P2 is 0 and P3, P4, P5 have arriving in the ready queue.
P2 4 25 The process P2 has finished execution so its removed from
P3 10 5 the ready queue. The processes P3, P4 and P5 are arranged in
P4 15 36
the ascending order of their remaining burst time in the ready
queue. The ready queue is divided into two sub-queues using
P5 17 18
medium burst time. The first sub-queue contains P3 and P5,
and the second sub-queue contains P4.
TABLE IV Initially the processes of the first sub-queue are executed: The
C OMPARISON OF RR, IRRVQ AND PROPOSED APPROACH (C ASE 2).
time quantum value is set equal to the burst time of the process
Algorithm Time Quantum (TQ) Average Waiting Time (ms) Average Turnaround Time (ms) medium i.e. 11.5. CPU is allocated to the processes P3 and
RR 7 25.6 43.8 P5 for a time quantum of 11.5 ms. After third cycle, the
IRRVQ
7, 11,
19.4 37.6
remaining burst time for P3 and P5 are 0 and 6.5 respectively.
7, 11
The process P3 has finished execution, so its removed from
Proposed 7, 25,
approach 11.5, 6.5, 36
17 35.2 the ready queue. The time quantum value is set equal of the
burst time of P5 i.e. 6.5. CPU is allocated to the process P5
for a time quantum of 6.5 ms.
The first sub-queue is empty so the second sub-queue begins
execution: The time quantum value is set equal to the burst
time of the only process in the queue P4 i.e. 36. CPU is
allocated to the process P4 for a time quantum of 36 ms.
The waiting time of P1 is 0 ms, 3 ms for P2, 22 ms for P3,
for P4 is 40 ms and 20 ms for P5. The average waiting time
is 17 ms. With the same example, the average waiting time
is 25.6 ms for time quantum 7 in RR, and 19.4 ms for time
quantum 7, 11, 7, 11 in IRRVQ. The average turnaround time
Fig. 5. Comparison of RR, IRRVQ and proposed algorithm (Case2). is 35.2 in proposed algorithm while its equal to 43.8 for time
quantum 7 in RR and 37.6 for time quantum 7, 11, 7, 11 in
IRRVQ.
The comparison result of RR, IRRVQ and our algorithm is
shown in Table 4 and Fig. 5.
Fig. 6 show the Gantt chart representation of RR with Time
Quantum 7. Fig. 7 show the Gantt chart representation of
IRRVQ with time quantum 7, 11 7, 11 respectively. Fig. 8
Fig. 6. Gantt chart representation of RR with TQ = 7 (Case2). show the Gantt chart representation of proposed algorithm.

VI. C ONCLUSION A ND F UTURE W ORK

The paper presents an improved version of Round Robin
task scheduling algorithm with varying time quantum. The
results show that the proposed algorithm gives better per-
formance than conventional RR and IRRVQ algorithms. The
Fig. 7. Gantt chart representation of IRRVQ (Case2). waiting time and turnaround time have been reduced in our
algorithm. This will help to improve the performance of the
system.

R EFERENCES
[1] Mell, Peter, & Tim. (2011, September 28). The NIST Defi-
nition of Cloud Computing. Retrieved January 8, 2020, from
https://csrc.nist.gov/publications/detail/sp/800-145/final.
[2] Sosinsky, B. (2011). Cloud computing bible. Indianapolis, IN: Wiley
Publishing.
[3] Escalante, A. (2010). Handbook of Cloud Computing. Berlin: Springer
Fig. 8. Gantt chart representation of proposed algorithm (Case2). US. doi: https://doi.org/10.1007/978-1-4419-6524-0

36

Authorized licensed use limited to: Singapore Institute of Technology (SIT). Downloaded on January 25,2021 at 09:44:12 UTC from IEEE Xplore. Restrictions apply.
[4] Sharma, Shimpy. (2014). Different Scheduling Algorithms in Different
Cloud Environment. IJARCCE. 3.
[5] Rahul,M. (2015). A Brief Review of Scheduling Algorithms in Cloud
Computing. Asian Journal of Technology & Management Research.
[6] Arya, G. P., Nilay, K., & Prasad, D. (2018). An Improved Round
Robin CPU Scheduling Algorithm based on Priority of Process. In-
ternational Journal of Engineering & Technology, 7(4.5), 238-241.
doi:10.14419/ijet.v7i4.5.20077
[7] Etminani, K., & Naghibzadeh, M. (2007). A Min-Min Max-Min selec-
tive algorihtm for grid task scheduling. 2007 3rd IEEE/IFIP International
Conference in Central Asia on Internet. doi:10.1109/canet.2007.4401694
[8] Devipriya, S., & Ramesh, C. (2013). Improved Max-min heuristic model
for task scheduling in cloud. 2013 International Conference on Green
Computing, Communication and Conservation of Energy (ICGCE).
doi:10.1109/icgce.2013.6823559
[9] Parsa (2009). RASA: A New Grid Task Scheduling Algorithm. Interna-
tional Journal of Digital Content Technology and its Applications.
[10] Kumar Mishra, M. and Rashid, F. (2014). An Improved Round Robin
CPU Scheduling Algorithm with Varying Time Quantum. International
Journal of Computer Science, Engineering and Applications, 4(4), pp.1-
8.

37

Authorized licensed use limited to: Singapore Institute of Technology (SIT). Downloaded on January 25,2021 at 09:44:12 UTC from IEEE Xplore. Restrictions apply.