CSE2005 –OPERATING SYSTEM –J COMPONENT PROJECT WORK REPORT

SCHEDULING ALGORITHM
REVIEW REPORT
Submitted by

MAYANK GUPTA(15BCE0477)
AAKASH SAXENA(15BCE0963)
MILAN SANDHAYA(15BCE0828)
ANAY ANAND BHORASKAR(15BCE0966)

Prepared For

OPERATING SYSTEMS (CSE2005) – PROJECT COMPONENT

Submitted To
ARUNKUMAR G.
Assistant Professor

School of Computer Science and Engineering

1.1.1.1.1.1.1

PAGE 1
 CSE2005 –OPERATING SYSTEM –J COMPONENT PROJECT WORK REPORT

1 . ABSTRACT
This project deals with the simulation of CPU scheduling algorithms with C. The
following algorithms are simulated:
First Come First Serve (FCFS)
Shortest Job First
SRTF Algorithm
Round Robin
Our innovative algorithm

The metrics such as finishing time, waiting time, total time taken for the processes to
complete, number of rounds, etc are calculated.

2. SOFTWARE ARCHITECTURE
There are five files for the five scheduling algorithms. They are made into each functions. This function is
imported to main function which has the menu. The menu has the choice of which of the algorithm it want to get
executed. In each function the code for each algorithm is done. The code consists arrival time and burst time for
each process. The output has the waiting time and turnaround time for each process.

At the beginning any number of processes can be taken in account. The output of each process with all the
algorithms can be found.

In SRTF Algorithm, the output comes as an average value i.e avg waiting time and avg turnaround time. While
for the rest algorithms each process has its own waiting time and turnaround time shown.

3. ALGORITHM
First Come First Serve (FCFS)

 First-Come-First-Served algorithm is the simplest scheduling algorithm is the simplest

scheduling algorithm. Processes are dispatched according to their arrival time on the ready
queue. Being a nonpreemptive discipline, once a process has a CPU, it runs to completion. The
FCFS scheduling is fair in the formal sense or human sense of fairness but it is unfair in the
sense that long jobs make short jobs wait and unimportant jobs make important jobs wait.
 FCFS is more predictable than most of other schemes since it offers time. FCFS scheme is not
useful in scheduling interactive users because it cannot guarantee good response time. The code
for FCFS scheduling is simple to write and understand. One of the major drawback of this
scheme is that the average time is often quite long.
 The First-Come-First-Served algorithm is rarely used as a master scheme in modern operating
systems but it is often embedded within other schemes.

Shortest Job First

 Shortest-Job-First (SJF) is a non-preemptive discipline in which waiting job (or process) with the smallest
estimated run-time-to-completion is run next. In other words, when CPU is available, it is assigned to the
process that has smallest next CPU burst.

PAGE 2
 CSE2005 –OPERATING SYSTEM –J COMPONENT PROJECT WORK REPORT

 The SJF scheduling is especially appropriate for batch jobs for which the run times are known in
advance. Since the SJF scheduling algorithm gives the minimum average time for a given set of
processes, it is probably optimal.
 The SJF algorithm favors short jobs (or processors) at the expense of longer ones.
 The obvious problem with SJF scheme is that it requires precise knowledge of how long a job or process
will run, and this information is not usually available.
 The best SJF algorithm can do is to rely on user estimates of run times.

SRTF Algorithm
 The SRT is the preemtive counterpart of SJF and useful in time-sharing environment.
 In SRT scheduling, the process with the smallest estimated run-time to completion is run next, including
new arrivals.
 In SJF scheme, once a job begin executing, it run to completion.
 In SJF scheme, a running process may be preempted by a new arrival process with shortest estimated
run-time.
 The algorithm SRT has higher overhead than its counterpart SJF.
 The SRT must keep track of the elapsed time of the running process and must handle occasional
preemptions.
 In this scheme, arrival of small processes will run almost immediately. However, longer jobs have even
longer mean waiting time.

Round Robin
 One of the oldest, simplest, fairest and most widely used algorithm is round robin (RR).
 In the round robin scheduling, processes are dispatched in a FIFO manner but are given a limited
amount of CPU time called a time-slice or a quantum.
 If a process does not complete before its CPU-time expires, the CPU is preempted and given to
the next process waiting in a queue. The preempted process is then placed at the back of the
ready list.
 Round Robin Scheduling is preemptive (at the end of time-slice) therefore it is effective in time-
sharing environments in which the system needs to guarantee reasonable response times for
interactive users.
 The only interesting issue with round robin scheme is the length of the quantum. Setting the
quantum too short causes too many context switches and lower the CPU efficiency. On the other
hand, setting the quantum too long may cause poor response time and appoximates FCFS.
 In any event, the average waiting time under round robin scheduling is often quite long.

Our innovative algorithm

The proposed algorithm focuses on the improvement on CPU scheduling algorithm. The
algorithm reduces the waiting time and turnaround time drastically compared to the other
Scheduling algorithm and simple Round Robin scheduling algorithm. This proposed algorithm
works in a similar way as but with some modification. It executes the shortest job having
minimum burst time first instead of FCFS simple Round robin algorithm and it also uses Smart
time quantum instead of static time quantum. Instead of giving static time quantum in the CPU

PAGE 3
 CSE2005 –OPERATING SYSTEM –J COMPONENT PROJECT WORK REPORT

scheduling algorithms, our algorithm calculates the Smart time quantum itself according to the
burst time of all processes. The proposed algorithm eliminates the discrepancies of implementing
simple round robin architecture.
 In the first stage of the innovative algorithm CPU scheduling algorithms all the processes are
arranged in the increasing order of CPU burst time. It means it automatically assign the priority
to the processes. Process having low burst time has high priority to the process have high burst
time.
 Then in the second stage the algorithm calculates the mean of the CPU burst time of all the
processes. After calculating the mean, it will set the time quantum dynamically i.e. (average of
mean and highest burst time)/2.
 Then in the last stage algorithm pick the first process from the ready queue and allocate the CPU
to the process for a time interval of up to 1 Smart time quantum. If the remaining burst time of
the current running process is less than 1 Smart time quantum then algorithm again allocate the
CPU to the Current process till it execution. After execution it will remove the terminated
process from the ready queue and again go to the stage 3.
 The flowchart for proposed algorithm is shown below in figure 1:

PAGE 4
 CSE2005 –OPERATING SYSTEM –J COMPONENT PROJECT WORK REPORT

EXPERIMENTAL ANALYSIS
CPU Burst Time in Increasing Order

Algorithm Average Average Number

Waiting Turnaround of Context
Time(ms) Time (ms) Switch
FCFS 38.4 57.8 10
RR 30.4 49.8 7
SJF 26.4 45.8 6
XX 24.4 43.7 4

0 0 2 10 16 24 0 0 6 14 0 0
P1 P2 P3 P4 P5 P2 P3 P4 P5 P4 P5

0 5 15 25 35 45 47 57 67 77 83 97
Figure 2: Gantt chart representation of FCFS

0 0 0 10 16 24 0 0 0
P1 P2 P3 P4 P5 P3 P4 P5
0 5 17 27 37 47 57 73 97
Figure 3: Gantt chart representation of RR

0 0 0 0 16 24 0 0

P1 P2 P3 P5 P4P4 P5
0 5 17 37 47 57 73 97
Figure 4: Gantt chart representation of SJF

P1 P2 P3 P4 P5
0 5 17 37 63 97
Figure 5: Gantt chart representation of XX

CPU Burst Time in Decreasing Order:

Algorithm Average Average Number

Waiting Turnaround of
Time(ms) Time (ms) Context
Switch
FCFS 58 77.4 11
RR 49 68.4 8
SJF 34.4 53.8 7
XX 24.4 43.79 4

PAGE 5
 CSE2005 –OPERATING SYSTEM –J COMPONENT PROJECT WORK REPORT

0 24 16 10 2 0 14 6 0 0 4 0 0

P1 P2 P3 P4 P5 P1 P2 P3 P4 P1 P2 P1
0 10 20 30 40 45 55 65 75 77 87 93 97
Figure 7: Gantt chart representation of FCFS

0 24 16 10 0 0 14 0 0 0
P1 P2 P3 P4 P5 P1 P2 P3 P1
0 10 20 30 42 47 57 73 83 97
Figure 8: Gantt chart representation of RR

0 24 0 0 0 16 14 0 0
P1 P5 P4 P3 P2 P1 P2 P1
0 10 15 27 47 57 67 81 97
Figure 9: Gantt chart representation of SJF

0 0 0 0 0 8
P5 P4 P3 P2 P1
0 5 17 37 63 97
Gantt chart representation of XX
CPU Burst Time in Random Order:

Algorithm Average Average Number

of
Waiting Turnaround Context
Time(ms) Time (ms) Switch
FCFS 48 67.4 11
RR 40.4 59.8 8
SJF 31 50.4 6
XX 24.4 43.7 4
0 10 24 0 2 16 0 14 0 6 4 0 0
P1 P2 P3 P4 P1 P2 P5
P3 P5 P2 P5 P2
0 10 20 25 35 45 55 65 67 77 87 93 97
Figure 12: Gantt chart representation of FCFS

0 10 24 0 0 16 0 14 0 0
P1 P2 P3 P4 P1 P2 P5 P5 P1
0 10 20 30 42 47 57 73 83 97
Figure 13: Gantt chart representation of RR

0 0 0 0 16 24 0 0
P1 P3 P4 P5 P2 P5 P2

PAGE 6
 CSE2005 –OPERATING SYSTEM –J COMPONENT PROJECT WORK REPORT

0 20 25 37 47 57 73 97
Figure 14: Gantt chart representation of SJF

0 0 0 0 0 8
P3 P4 P1 P5 P2
0 5 17 37 63 97
Figure 15: Gantt chart representation of XX

4. SAMPLE CODE

#include <stdio.h>
#include <conio.h>
#include <stdio.h>
#include <conio.h>
#include<math.h>
#include<string.h>
int wt[100],bt[100],at[100],tat[100],n,p[100];
float awt[5],atat[5];
void create_file_csv(char *filename,int a[][2],int n,int m)
{
printf("\n Creating %s.csv file",filename);
FILE *fp;
int i,j;
filename=strcat(filename,".csv");
fp=fopen(filename,"w+");
fprintf(fp,"FCFS, SJF, RR, SRTF, Innovative Algo");
for(i=0;i<m;i++)
{
fprintf(fp,"\n%d",i+1);
for(j=0;j<n;j++)
fprintf(fp,",%d ",a[i][j]);
}
fclose(fp);
printf("\n %sfile created",filename);
}
void input()
{
printf("Enter Number of processes:");
scanf("%d",&n);
int i;
for(i=0;i<n;i++)
p[i]=i+1;
for(i=0;i<n;i++)
{
printf("Enter Burst Time of process %d:",i+1);
scanf("%d",&bt[i]);
printf("Enter Arrival Time of process %d:",i+1);
scanf("%d",&at[i]);
}
for(i=0;i<5;i++)
PAGE 7
 CSE2005 –OPERATING SYSTEM –J COMPONENT PROJECT WORK REPORT

{
awt[i]=0.0;
atat[i]=0.0;
}

}
void changeArrival(){
int a=at[0];
int i;
for(i=0;i<n;i++){
if(at[i]<a)
a=at[i];
}
if(a!=0){
for(i=0;i<n;i++)
at[i]=at[i]-a;
}
}
void fcfs(){
wt[0]=0;
atat[0]=tat[0]=bt[0];
int btt=bt[0];
int i;
for(i=1;i<n;i++){
wt[i]=btt-at[i];
btt+=bt[i];
awt[0]+=wt[i];
tat[i]= wt[i]+bt[i];
atat[0]+=tat[i];
}
atat[0]/=n;
awt[0]/=n;
printf("SR.\tA.T.\tB.T.\tW.T.\tT.A.T.\n");
for(i=0;i<n;i++)
{
printf("%3d\t%3d\t%3d\t%3d\t%4d\n",i+1,at[i],bt[i],wt[i],tat[i]);
}
}
void innovative()
{
int bt1[n],i,j,temp,tq;
int b[n];
float twt,ttat;
for(i=0;i<n;i++)
bt1[i]=bt[i];
for(i=0;i<n;i++)
b[i]=bt[i];
int num=n;
int time=0;
int max;
int sum,t,a,ap;
ap=0;
while(num>0){
a=0;
PAGE 8
 CSE2005 –OPERATING SYSTEM –J COMPONENT PROJECT WORK REPORT

max=0;
sum=0;
t=0;
//sorting in ascending order
for(i=0;i<n;i++){
for(j=0;j<n;j++){
if(b[i]<b[j] && at[i]<=time){
temp=p[j];
p[j]=p[i];
p[i]=temp;
temp=at[j];
at[j]=at[i];
at[i]=temp;
temp=b[j];
b[j]=b[i];
b[i]=temp;
temp=bt1[j];
bt1[j]=bt1[i];
bt1[i]=temp;
}
}
}
for(i=0;i<n;i++){
if(at[i]<=time && b[i]!=0){
a++;
if(b[i]>max)
max=b[i];
sum+=b[i];

}
}
if(a!=ap){
tq=sqrt((sum/a)*max);
ap=a;
}
for(i=0;i<n;i++){
if(at[i]<=time && b[i]!=0)
{
if(b[i]<tq)
{
t+=b[i];
b[i]=0;
}
else
{
t+=tq;
b[i]-=tq;
}
if(b[i]==0){
wt[i]=(time+t)-bt1[i];
tat[i]=time+t;
num--;
}
}
PAGE 9
 CSE2005 –OPERATING SYSTEM –J COMPONENT PROJECT WORK REPORT

}
time+=t;
}
printf("Processes\tWaitingtime\tTurnAroundTime\n");
for(j=1;j<=n;j++){
for(i=0;i<n;i++){
if(j==p[i])
printf("process %d\t%d\t\t%d\n",p[i],wt[i],tat[i]);
}
}
for(i=0;i<n;i++)
twt+=wt[i];
awt[4]=twt/n;
for(i=0;i<n;i++)
ttat+=tat[i];
atat[4]=ttat/n;
}
void rr()
{
int i, total = 0, x, counter = 0, time_quantum;
int wait_time = 0, turnaround_time = 0, temp[100];
x=n;
for(i = 0; i < n; i++)
{
temp[i] = bt[i];
}
printf("\nEnter Time Quantum:\t");
scanf("%d", &time_quantum);
printf("\nProcess ID\t\tBurst Time\t Turnaround Time\t Waiting Time\n");
for(total = 0, i = 0; x != 0;)
{
if(temp[i] <= time_quantum && temp[i] > 0)
{
total = total + temp[i];
temp[i] = 0;
counter = 1;
}
else if(temp[i] > 0)
{
temp[i] = temp[i] - time_quantum;
total = total + time_quantum;
}
if(temp[i] == 0 && counter == 1)
{
x--;
printf("Process[%d]\t\t%d\t\t %d\t\t\t %d\n", i + 1, bt[i], total - at[i], total - at[i] -
bt[i]);
wait_time = wait_time + total - at[i] - bt[i];
turnaround_time = turnaround_time + total - at[i];
counter = 0;
}
if(i == n - 1)
{
i = 0;
PAGE 10
 CSE2005 –OPERATING SYSTEM –J COMPONENT PROJECT WORK REPORT

}
else if(at[i + 1] <= total)
{
i++;
}
else
{
i = 0;
}
}
awt[2] = wait_time * 1.0 / n;
atat[2] = turnaround_time * 1.0 / n;
}
void srtf()
{
int i,x[10],b[10],count=0,time,smallest;
double avg=0,tt=0,end;
for(i=0;i<n;i++)
{
x[i]=bt[i];
}
bt[9]=9999;

for(time=0;count!=n;time++)
{
smallest=9;
for(i=0;i<n;i++)
{
if(at[i]<=time && bt[i]<b[smallest] && bt[i]>0 )
smallest=i;
}
bt[smallest]--;
if(bt[smallest]==0)
{
count++;
end=time+1;
avg=avg+end-at[smallest]-x[smallest];
tt= tt+end-at[smallest];
}
}
awt[3]=avg/n;
atat[3]=tt/n;

void display(int c)
{
int i;
printf("Average Waiting Time: %f\nAverage Turn Around Time:%f",awt[c-1],atat[c-1]);
}
void sjf()
{
float wavg=0,tavg=0,tsum=0,wsum=0;
int i,j,temp,sum=0,ta=0;
PAGE 11
 CSE2005 –OPERATING SYSTEM –J COMPONENT PROJECT WORK REPORT

for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(at[i]<at[j])
{
temp=p[j];
p[j]=p[i];
p[i]=temp;

temp=at[j];
at[j]=at[i];
at[i]=temp;

temp=bt[j];
bt[j]=bt[i];
bt[i]=temp;
}
}
}
int btime=0,min,k=1;
for(j=0;j<n;j++)
{
btime=btime+bt[j];
min=bt[k];
for(i=k;i<n;i++)
{
if (btime>=at[i] && bt[i]<min)
{
temp=p[k];
p[k]=p[i];
p[i]=temp;
temp=at[k];
at[k]=at[i];
at[i]=temp;
temp=bt[k];
bt[k]=bt[i];
bt[i]=temp;
}
}
k++;
}
wt[0]=0;
for(i=1;i<n;i++)
{
sum=sum+bt[i-1];
wt[i]=sum-at[i];
wsum=wsum+wt[i];
}

awt[1]=(wsum/n);
for(i=0;i<n;i++)
{
ta=ta+bt[i];
PAGE 12
 CSE2005 –OPERATING SYSTEM –J COMPONENT PROJECT WORK REPORT

tat[i]=ta-at[i];
tsum=tsum+tat[i];
}

atat[1]=(tsum/n);
printf("SR.\tA.T.\tB.T.\tW.T.\tT.A.T.\n");
for(i=0;i<n;i++)
{
printf("%3d\t%3d\t%3d\t%3d\t%4d\n",i+1,at[i],bt[i],wt[i],tat[i]);
}
}
int main(){
printf("Welcome to CPU Scheduling:\n\n");
input();
int c,choice;
changeArrival();
printf("Choice\tAlgorithm used\n1\tFCFS Algorithm\n2\tSJF Algorithm\n3\tRound robin\n4\tSRTF
Algorithm\n5\tOur innovative algorithm\n");
do
{
printf("Enter your choice from the above table");
scanf("%d",&c);
switch(c)
{
case 1:fcfs();break;
case 2:sjf();break;
case 3:rr();break;
case 4:srtf();break;
case 5:innovative();break;
default: printf("Please enter choice from 1 to 5 only\n");break;
}
display(c);
printf("\n\nEnter 1 to continue 0 to stop");
scanf("%d",&choice);
}while(choice==1);
getch();
int a[5][2],i;
for(i=0;i<5;i++)
{
a[i][0]=awt[i];
a[i][1]=atat[i];
}
create_file_csv("schedule",a,5,2);
}

5. SNAP SHOTS

THE FIRST FOUR ALGORITHMS:

PAGE 13
 CSE2005 –OPERATING SYSTEM –J COMPONENT PROJECT WORK REPORT

OUR INNOVATIVE ALGORITHM

PAGE 14
 CSE2005 –OPERATING SYSTEM –J COMPONENT PROJECT WORK REPORT

6. CONCLUSION

Results have shown that the proposed algorithm gives better results in terms of average
waiting time, average turnaround time and number of context switches in all cases of
process categories than the simple Round Robin CPU scheduling algorithm.
In all these proposed algorithms time quantum is static due to which in these cases the
number of context switches, average waiting time and average turnaround time will be
very high and in our proposed algorithm, time quantum is calculated dynamically
according to the burst time of all processes and it will find out a smart time quantum for
all processes which gives good performance as compared to FCFS, RR, SJF and XX.

PAGE 15
 CSE2005 –OPERATING SYSTEM –J COMPONENT PROJECT WORK REPORT

7. REFERENCES
 Abdulraza, Abdulrahim,Salisu Aliyu, Ahmad M Mustapha, Saleh E Abdullahi, “ An Additional
Improvement in Round Robin (AAIRR) CPU Scheduling Algorithm,” International Journal of
Advanced Research in Computer Science and Software Engineering Volume 4, Issue 2, February
2014 ISSN: 2277 128X.

 Manish kumar Mishra and Abdul kadir khan, “An Improved Round Robin CPU scheduling
algorithm,” Journal of Global Research in Computer Science Volume 3, No. 6, June 2012.Neetu

PAGE 16