“Round Robin Algorithm”
A Project
Submitted in partial fulfillment of the requirement for the award of Diploma in
Computer Engineering Discipline
Submitted To
MAHARASHTRA STATE BOARD OF TECHNICAL EDUCATION, MUMBAI
(DTE Code:5009)
Submitted By:
Mr. Chetan Patil Roll No. 3122
Ms. Jayshree Khedkar Roll No. 3132
Ms. Shreya Wagh Roll No. 3139
Mr. Abhijeet Kulkarni Roll No. 3160
Mr. Krishna Ahire Roll No. 3164
Under the Guidance of
Prof. Mr. M. M. Goswami
DEPARTMENT OF COMPUTER ENGINEERING
GOVERNMENT POLYTECHNIC
NANDURBAR, DIST- NANDURBAR (MSBTE CODE: 1432)
YEAR 2022-23
1|Page
GOVERNMENT POLYTECHNIC, NANDURBAR, DIST - NANDURBAR (MS
CERTIFICATE
This is to certify that
Mr. Chetan Patil Roll No. 3122
Ms. Jayshree Khedkar Roll No. 3132
Ms. Shreya Wagh Roll No. 3139
Mr. Abhijeet Kulkarni Roll No. 3160
Mr. Krishna Ahire Roll No. 3164
Has satisfactorily completed project entitled
“Round Robin Algorithm”
As prescribed by Maharashtra State Board of Technical Education, Mumbai as a
part of syllabus for the partial fulfilment in Diploma in Computer Engineering for
Academic year 2022-23.
GUIDE H.O.D.
Prof. M. M. Goswami Prof. S. B. Thakre
EXAMINER PRINCIPAL
--------------- Dr. S. D. Pable
2|Page
GOVERNMENT POLYTECHNIC, NANDURBAR, DIST - NANDURBAR (M
CERTIFICATE OF APPROVAL
The Project entitled “Round Robin Algorithm” being submitted by “Chetan
Patil, Jayshree Khedkar, Shreya Wagh, Abhijeet Kulkarni and Krishna
Ahire” has been examined by us and is hereby approved for the partial award of
Diploma in Computer Engineering for which it has been submitted. It is
understood that by this approval the undersigned do not necessarily endorse or
approve any statement made, opinion expressed or conclusion drawn therein, but
approve the project only for the purpose for which it has been submitted.
(Internal Examiner) (External Examiner)
Date: Date:
3|Page
INDEX
Sr. Title Page No
1. Abstract 05
2. Introduction 06
3. FCFS 07
1. FCFS
2. Use Case Diagram of FCFS
3. Data Flow Diagram of FCFS
4. 15
ROUND ROBIN
1. RR
2. Use Case Diagram of RR
3. Data Flow Diagram of RR
5. Comparisons 24
6. Conclusion 26
4|Page
ABSTRACT
Round Robin (RR) scheduling algorithm is the widely used scheduling algorithm in multitasking.
It ensures fairness and starvation free execution of processes. Choosing the time quantum in RR
algorithm is very crucial as small time slice results in large number of context switches and large
time quantum increases the response time. To overcome these problems of RR scheduling,
instead of static time slice dynamic time slice can be used to get optimal performance. The
objective of this paper is to modify RR algorithm by adjusting time slices of different rounds
depending on the remaining CPU bursts of currently running processes and considering their
waiting times until that round in respect of the other processes waiting times. Experimental
analysis reveals that the proposed algorithm produces better average turnaround time, average
waiting time and fewer number of context switches than existing algorithms.
5|Page
INTRODUCTION
Round Robin is a CPU scheduling algorithm where each process is assigned a fixed time slot in a
cyclic way. It is simple, easy to implement, and starvation-free as all processes get fair share of
CPU. One of the most commonly used technique in CPU scheduling as a core. It is preemptive
as processes are assigned CPU only for a fixed slice of time at most. The disadvantage of it is
more overhead of context switching.
FIFO simply queues processes in the order that they arrive in the ready queue. This is commonly
used for a task queue, for example as illustrated in this section.
6|Page
First Come, First Served (FCFS)
First Come First Serve is the simplest and easiest scheduling algorithm. In this algorithm, the
CPU is allocated to the processes in the order they request it. The implementation of FCFS is
easily done with a queue (a FIFO structure). When the first process enters the system, it starts its
execution immediately and runs till it completes its execution. As other processes enter the
system, they are put at the end of the queue and wait to get the CPU. When a process finishes
executing, it releases the CPU, is removed from the queue and the CPU is allocated to next
process at the head of the queue.
First come, first served (FCFS) is an operating system process scheduling algorithm and a
network routing management mechanism that automatically executes queued requests
and processes by the order of their arrival.
With first come, first served, what comes first is handled first; the next request in line will
be executed once the one before it is complete.
FCFS is also known as first-in, first-out (FIFO) and first come, first choice (FCFC).
Example:
process Burst time
P1 25
P2 4
P3 3
The processes arrive in the order P1, P2, P3 and are served as per the FCFS algorithm. The Gantt
chart is as shown:
P1 P2 P3
0 25 29 32
7|Page
The waiting time for P1 is 0 milliseconds, for P2 it is 25 milliseconds and 29
milliseconds for P3. Thus, average waiting time is (0+25+29)/3 = 18 milliseconds.\
Advantage:
o It is easy to understand and implement.
o Simple
o Easy
o First come, First serve
Disadvantage:
It is a non-pre-emptive scheduling algorithm: Once a process has been allocated the
CPU, it will not release the CPU until it finishes executing. Thus, it is not suitable for
modern systems which work on the principle of time sharing.
The Average Waiting Time is high.
It results in convey effect i.e., many processes which require CPU for short duration have
to wait for a bigger process to finish thus resulting in low resource utilization.
Implementation:
1) Input the processes along with their burst time (bt).
2) Find waiting time (wt) for all processes.
3-) As first process that comes need not to wait so
waiting time for process 1 will be 0 i.e. wt[0] = 0.
4- Find waiting time for all other processes i.e. for
process i ->
wt[i] = bt[i-1] + wt[i-1].
8|Page
5- Find turnaround time = waiting time + burst time
for all processes.
6- Find average waiting time =
total_waiting_time / no_of_processes.
7- Similarly, find average turnaround time =
total_turn_around_time / no_of_processes.
Code
// C++ program for implementation of FCFS
// scheduling
#include<iostream>
using namespace std;
// Function to find the waiting time for all
// processes
void findWaitingTime (int processes [], int n,
int bt [], int wt [])
{
// waiting time for first process is 0
wt [0] = 0;
// calculating waiting time
for (int i = 1; i < n; i++)
wt[i] = bt[i-1] + wt[i-1];
}
// Function to calculate turnaround time
void findTurnAroundTime (int processes [], int n,
int bt [], int wt [], int that[])
9|Page
{
// calculating turnaround time by adding
// bt[i] + wt[i]
for (int i = 0; i < n ; i++)
tat[i] = bt[i] + wt[i];
}
//Function to calculate average time
void findavgTime( int processes[], int n, int bt[])
{
int wt[n], tat[n], total_wt = 0, total_tat = 0;
//Function to find waiting time of all processes
findWaitingTime(processes, n, bt, wt);
//Function to find turn around time for all processes
findTurnAroundTime(processes, n, bt, wt, tat);
//Display processes along with all details
cout << "Processes "<< " Burst time "
<< " Waiting time " << " Turn around time\n";
// Calculate total waiting time and total turn
// around time
for (int i=0; i<n; i++)
{
total_wt = total_wt + wt[i];
total_tat = total_tat + tat[i];
cout << " " << i+1 << "\t\t" << bt[i] <<"\t "
<< wt[i] <<"\t\t " << tat[i] <<endl;
}
10 | P a g e
cout << "Average waiting time = "
<< (float)total_wt / (float)n;
cout << "\nAverage turn around time = "
<< (float)total_tat / (float)n;
}
// Driver code
int main()
{
//process id's
int processes[] = { 1, 2, 3};
int n = sizeof processes / sizeof processes[0];
//Burst time of all processes
int burst_time[] = {10, 5, 8};
findavgTime(processes, n, burst_time);
return 0; }
}
Manual Output:
Processes Burst Waiting Turn around
time time
time
1 10 0 10
2 5 10 15
3 8 15 23
Average waiting time = 8.33333
Average turn around time = 16
11 | P a g e
System Output:
12 | P a g e
Use case Diagram of FCFS
Fig. Use Case Diagram for FCFS algorithm
13 | P a g e
Data Flow Diagram for FCFS
14 | P a g e
Round Robin scheduling algorithm
Round Robin is a CPU scheduling algorithm where each process is assigned a fixed time slot in a
cyclic way.
It is simple, easy to implement, and starvation-free as all processes get fair share of CPU.
One of the most commonly used technique in CPU scheduling as a core.
It is preemptive as processes are assigned CPU only for a fixed slice of time at most.
The disadvantage of it is more overhead of context switching
To schedule processes fairly, a round-robin scheduler generally employs time-sharing, giving
each job a time slot or (its allowance of CPU time), and interrupting the job if it is not completed
by then. The job is resumed next time a time slot is assigned to that process. If the process
terminates or changes its state to waiting during its attributed time quantum, the scheduler selects
the first process in the ready queue to execute. In the absence of time-sharing, or if the quanta
were large relative to the sizes of the jobs, a process that produced large jobs would be favored
over other processes.
Round-robin algorithm is a pre-emptive algorithm as the scheduler forces the process out
of the CPU once the time quota expires.
For example, if the time slot is 100 milliseconds, and job1 takes a total time of 250 ms to
complete, the round-robin scheduler will suspend the job after 100 ms and give other jobs
their time on the CPU. Once the other jobs have had their equal share (100 ms
each), job1 will get another allocation of CPU time and the cycle will repeat. This process
continues until the job finishes and needs no more time on the CPU.
1) Completion Time: Time at which process completes its execution.
2) Turn Around Time: Time Difference between completion time and arrival
time. 3)Turn Around Time = Completion Time – Arrival Time
4)Waiting Time(W.T): Time Difference between turnaround time and burst time.
5)Waiting Time = Turn Around Time – Burst Time
15 | P a g e
Steps to find waiting times of all processes:
1) Create an array rem_bt[] to keep track of remaining
burst time of processes. This array is initially a
copy of bt[] (burst times array)
2) Create another array wt[] to store waiting times
of processes. Initialize this array as 0.
3) Initialize time : t = 0
4)Keep traversing the all processes while all
processes are not done. Do following for it’s
process if it is not done yet.
a- If rem_bt[i] > quantum
(i) t = t + quantum
(ii) bt_rem[i] -= quantum;
c- Else // Last cycle for this process
(i) t = t + bt_rem[i];
(ii) wt[i] = t - bt[i]
(ii) bt_rem[i] = 0; // This process is over
Code with the example no2: -
// C++ program for implementation of RR scheduling
#include<iostream>
using namespace std;
// Function to find the waiting time for all
// processes
void findWaitingTime(int processes[], int n,
int bt[], int wt[], int quantum)
{
// Make a copy of burst times bt[] to store remaining
16 | P a g e
// burst times.
int rem_bt[n];
for (int i = 0 ; i < n ; i++)
rem_bt[i] = bt[i];
int t = 0; // Current time
// Keep traversing processes in round robin manner
// until all of them are not done.
while (1)
{
bool done = true;
// Traverse all processes one by one repeatedly
for (int i = 0 ; i < n; i++)
{
// If burst time of a process is greater than 0
// then only need to process further
if (rem_bt[i] > 0)
{
done = false; // There is a pending process
if (rem_bt[i] > quantum)
{
// Increase the value of t i.e. shows
// how much time a process has been processed
t += quantum;
// Decrease the burst_time of current process
// by quantum
rem_bt[i] -= quantum;
17 | P a g e
}
// If burst time is smaller than or equal to
// quantum. Last cycle for this process
else
{
// Increase the value of t i.e. shows
// how much time a process has been processed
t = t + rem_bt[i];
// Waiting time is current time minus time
// used by this process
wt[i] = t - bt[i];
// As the process gets fully executed
// make its remaining burst time = 0
rem_bt[i] = 0;
}
}
}
// If all processes are done
if (done == true)
break;
}
}
// Function to calculate turn around time
void findTurnAroundTime(int processes[], int n,
int bt[], int wt[], int tat[])
{
18 | P a g e
// calculating turnaround time by adding
// bt[i] + wt[i]
for (int i = 0; i < n ; i++)
tat[i] = bt[i] + wt[i];
}
// Function to calculate average time
void findavgTime(int processes[], int n, int bt[],
int quantum)
{
int wt[n], tat[n], total_wt = 0, total_tat = 0;
// Function to find waiting time of all processes
findWaitingTime(processes, n, bt, wt, quantum);
// Function to find turn around time for all processes
findTurnAroundTime(processes, n, bt, wt, tat);
// Display processes along with all details
cout << "Processes "<< " Burst time "
<< " Waiting time " << " Turn around time\n";
// Calculate total waiting time and total turn
// around time
for (int i=0; i<n; i++)
{
total_wt = total_wt + wt[i];
total_tat = total_tat + tat[i];
cout << " " << i+1 << "\t\t" << bt[i] <<"\t "
<< wt[i] <<"\t\t " << tat[i] <<endl;
}
19 | P a g e
cout << "Average waiting time = "
<< (float)total_wt / (float)n;
cout << "\nAverage turn around time = "
<< (float)total_tat / (float)n;
}
// Driver code
int main()
{
// process id's
int processes[] = { 1, 2, 3};
int n = size of processes / size of processes[0];
// Burst time of all processes
int burst_time[] = {10, 5, 8};
// Time quantum
int quantum = 2;
findavgTime(processes, n, burst_time, quantum);
return 0;
}
20 | P a g e
Manual Output
Processes Burst time Waiting time Turn around
time
1 10 13 23
2 5 10 15
3 8 13 21
Average waiting time = 12
Average turn around time = 19.6667
System output
21 | P a g e
Use case Diagram of Round Robin
22 | P a g e
Data flow diagram of Round Robin
23 | P a g e
Comparison
Priority Scheduling Round-Robin
First Come First Served Round Robin
Priority Scheduling executes the Round-Robin (RR) executes the
processes
First Come according to the
First Served priority
(FCFS) processes
Round Robinbased
(RR)upon
is thethe time
isi.e.,
the process with higher
non-preemptive priority is
scheduling quantum scheduling
preemptive defined i.e.,algorithm
each .
executed. first.
algorithm process is executed for a fixed
amount of time.
Priority Scheduling is both Round-Robin (RR) is
FCFS has theand
preemptive minimal overhead. in
non-preemptive While RR has in
preemptive small overhead as it
nature.
nature. is necessary to record the time
elapsed and then switch the process
The average waiting time and
The average waiting time for
which causes an overhead.
average response time is unknown given set of processes is quite
FCFS is inconvenient to use in
beforehand. It is mainly
small anddesigned
depends for the time
on the time-
the time-sharing system sharing system
quantum . and hence
convenient to use.
The average waiting time for given
It is quite easy to implement
set of processes is quite small and RR in any system.
dependswaiting
Average on the time
time quantum.
is generally In Round Robin Scheduling
not minimal in First Come First Algorithm average waiting time is
The problem
Served of blocking
Scheduling of a
Algorithm. Each process is executed and
minimal
process can be solved using aging. every user feels that his work is
being done as the CPU gives
The process is simply processed It is similar
equal like FCFS
amount of timeinto each
in the order of their arrival in processing
process. but uses time quantum.
FCFS.
Comparison
24 | P a g e
CONCLUSION
Thus, we have performed various scheduling algorithms such as FCFS (First Come First Serve)
and Round Robin Algorithm. We have developed a C plus program to execute these algorithms.
We have calculated waiting time, turnaround time, burst time. We have created Use case and Data
Flow Diagram for both algorithms.
25 | P a g e
Weekly Work / Progress Report
Details of Engagement Hours of the Student
Regarding Completion of the Project
Week Duration Sign of the
No. Date in hours Work or activity Performed Guide
Two hours Discussion and Finalization of
1 the Project Title
Two hours Preparation and Submission
2 of Abstracts
3 Two hours Literature Review
4 Two hours Collection of Data
5 Two hours Collection of Data
6 Two hours Discussion and Outline of Content
7 Two hours Rough Writing of the Projects Contents
Two hours Editing and Proof Reading of the
8 Contents
9 Two hours Final Completion of the Project
Two hours Seminar Presentation, viva-vice,
10 Assessment and Submission of Report
Name of Project Guide:
26 | P a g e
27 | P a g e
