Thursday, April 1, 2010

C Implementation of Shortest Remaining Time CPU Scheduling Algorithm

Hello Friends, here's C implementation of Shortest Remaining Time CPU Scheduling Algorithm.To run this program in windows simply copy and paste the program into notepad save it with any name you want with extension ".c".To run this program under linux just remove '#include<conio.h>,getch(); and clrscr();' from the program and save it with extension ".c".Program developed and tested by Niraj.

#include<conio.h>
#include<stdio.h>

typedef struct process
{
int id;
int arrival;
int burst;
int wait;
};
struct process pool[10];
struct process ready[10];
struct process exe[20];
struct process temp,current,tmppro;

gantt(struct process pool[],int nop);
int scanpro(int time,int nop);
arrange();
execute();
incwait1();
incwait2();

int time,x,y,z;
float at[10],at1[10];
int main()
{
int tmp,nop,no;
float at_float,awt,atrt;
int j,i,maxarrtime;
int counter=0;
time=0;
x=1;
y=0;
z=0;
clrscr();
printf("Please enter the number of processes : ");
scanf("%d",&nop);
for(i=0;i<nop;i++)


at[i]=0;
printf("\nPlease enter the ID, Burst time & Arrival Time of each process : ");
printf("\n");
for(i=0;i<nop;i++)
{
printf("\nID : P%d",i+1);
pool[i].id=i+1;
printf("\nBurst Time : ");
scanf("%d",&pool[i].burst);
printf("Arrival Time : ");
scanf("%f",&at[i]);
}
for(i=0;i<nop;i++)
{
at1[i]=at[i];
at_float=at[i]+0.999;
pool[i].arrival=(int)at_float;
at[i]=(float)pool[i].arrival-at1[i];
}
printf("\n* * * * * * * PROCESS TABLE * * * * * * *\n");
printf("\nP ID Burst Time Arrival");
for(i=0;i<nop;i++)
{
if(pool[i].id==0)
break;
printf("\nP%d\t\t%d\t%f",pool[i].id,pool[i].burst,at1[i]);
}
printf("\n\n");

//SRT Logic

maxarrtime=pool[nop-1].arrival;
while(time<=maxarrtime)
{

if(time==pool[z].arrival)
{
no=scanpro(time,nop);
for(counter=0;counter<no;counter++)
{
ready[x]=pool[z];
x++;
z++;
}

execute();
}
else
{
if(current.burst>0)
{
current.burst--;
incwait1();

time++;

}
else
{
if(current.burst==0)
{
execute();
}
}
}
}
counter=temp.burst-current.burst;
tmp=0;
while(current.burst!=0)
{
current.burst--;
counter++;
tmp++;
}
i=1;

while(ready[i].id>0 && ready[i].burst!=0)
{
ready[i].wait=ready[i].wait+tmp;
i++;
}

temp.burst=counter;
exe[y++]=temp;
for(i=0;i<10;i++)
ready[i]=ready[i+1];
arrange();
incwait2();
x=0;
while(ready[x].id>0)
exe[y++]=ready[x++];
for(i=0;i<20;i++)
exe[i]=exe[i+1];

//setting wait time in pool
for(i=0;i<nop;i++)
{
for(j=0;j<20;j++)
{
if(pool[i].id==exe[j].id)
{
pool[i].wait=exe[j].wait;
}
}
at[i]=at[i]+pool[i].wait;
}

awt=0;
atrt=0;
for(i=0;i<nop;i++)
{
awt=awt+at[i];
atrt=atrt+(at[i]+pool[i].burst);
}
awt=awt/nop;
atrt=atrt/nop;
printf("\nAverage Waiting Time : %f",awt);
printf("\nAverage Turn Around Time : %f",atrt);
gantt(exe,nop);
getch();
return 0;
}

execute()
{
ready[0]=current;

arrange();
temp.burst=temp.burst-current.burst;
exe[y++]=temp;
current=ready[0];
temp=ready[0];
current.burst--;
incwait1();

time++;

}

incwait1()
{
int i=1;

while(ready[i].id>0 && ready[i].burst!=0)
{
ready[i].wait++;

i++;
}

}

incwait2()
{
int i=1;
int wt=0;

wt=ready[0].burst;
while(ready[i].id>0 && ready[i].burst!=0)
{
ready[i].wait=ready[i].wait+wt;
wt=wt+ready[i].burst;

i++;
}

}

int scanpro(int time,int nop)
{
int i;
int counter=0;
for(i=0;i<nop;i++)
if(pool[i].arrival==time)
counter++;
return counter;
}

arrange()
{
int a,i,j,counter=0;
for(i=1;i<10;i++)
{
for(j=0;j<10-i;j++)
{
if(ready[j].burst>ready[j+1].burst)
{
tmppro=ready[j];
ready[j]=ready[j+1];
ready[j+1]=tmppro;
}
}
}
i=0;
while(ready[i].burst==0)
{
counter++;
i++;
}
a=0;
for(i=counter;i<10;i++)
{
ready[a++]=ready[i];
ready[i].id=0;
ready[i].burst=0;
}
getch();
}


/*gantt chart*/
gantt(struct process pool[],int nop)
{
int t=0,i;
int procount=0;
printf("\n\n\n* * * * * * * GANTT CHART * * * * * * *\n\n");
i=0;
while(pool[i].id>0)
{
procount++;
i++;
}
printf("\n");
for(i=0;i<procount;i++)
printf("--------");
printf("\n|");
for(i=0;i<procount;i++)
printf(" P%d |",pool[i].id);
printf("\n");
for(i=0;i<procount;i++)
printf("--------");
printf("\n");
for(i=0;i<procount;i++)
{
printf("%d\t",t);
t=t+pool[i].burst;
}
printf("%d",t);
}
You would be interested in:
1. Java Implementation of Page Replacement Algorithm -FIFO, LRU, OPT
2. Java Implementation of First-Fit, Best-Fit and Worst-Fit
3. Java Implementation of Bankers Algorithm
4. C Implementation of CPU Scheduling Algorithm FCFS, SJF, Round Robin

C Implementation of CPU Sceduling Algorithm FCFS,SJF,Round Robin

Hello Friends, here's C implementation of CPU Scheduling Algorithms(First Come First Served ,Shortest Job First , Round Robin).This is a menu driven C program allowing you to select type of scheduling you want to implement .To run this program in windows simply copy and paste the program into notepad save it with any name you want with extension ".c".To run this program under linux just remove '#include,getch(); and clrscr();' from the program and save it with extension ".c".
Don't just copy ,understand it.Program developed and tested by Niraj.
For any queries,mistakes mail to rustamengg@live.com

#include<stdio.h>
typedef struct process
{
int id;
int wait;
int burst;
};
struct process pro[10];
struct process temp[20];

table(struct process pro[],int nop);
gantt(struct process pro[],int nop);
int getdata();
incwait(int tempburst,int id);
init();

int nop;

main()
{
struct process tmppro;
int choice,quantum;
int i,j,x,z,ret;
int ans,rrwt;
float rrawt,rratrt,fcfsawt,fcfsatrt,sjfatrt,sjfawt;
int procount,t,tburst[10];
do
{
printf("\t\t* * * * * * MENU * * * * * * \n");
printf("\t\t1.FCFS\n\t\t2.SJF\n\t\t3.Round Robin");
printf("\n\nPlease enter your choice : ");
scanf("%d",&choice);

switch(choice)
{
case 1:
{
init();
nop=getdata();
table(pro,nop);
gantt(pro,nop);
fcfsawt=0;
fcfsatrt=0;
for(i=nop-1;i>=0;i--)
{
pro[i].wait=0;
for(j=0;j<i;j++)
{
pro[i].wait=pro[i].wait+pro[j].burst;
}
}
for(i=0;i<nop;i++)
{
printf("\nP%d Wait Time : %d",pro[i].id,pro[i].wait);
printf("\nP%d Turn Around Time : %d",pro[i].id,(pro[i].wait+pro[i].burst));
fcfsawt=fcfsawt+pro[i].wait;
fcfsatrt=fcfsatrt+(pro[i].wait+pro[i].burst);
}
printf("\n\nAWT of FCFS : %f",fcfsawt/nop);
printf("\n\nATRT of FCFS : %f",fcfsatrt/nop);
break;
}
case 2:
{
init();
nop=getdata();
printf("\nTable before arranging ...\n");
table(pro,nop);
for(i=1;i<nop;i++)
{
for(j=0;j<nop-i;j++)
{
if(pro[j].burst>pro[j+1].burst)
{
tmppro=pro[j];
pro[j]=pro[j+1];
pro[j+1]=tmppro;
}
}
}
printf("\nTable after arranging ...\n");
table(pro,nop);
gantt(pro,nop);
sjfawt=0;
sjfatrt=0;
for(i=nop-1;i>=0;i--)
{
pro[i].wait=0;
for(j=0;j<i;j++)
{
pro[i].wait=pro[i].wait+pro[j].burst;
}
}
for(i=0;i<nop;i++)
{
printf("\nP%d Wait Time : %d",pro[i].id,pro[i].wait);
printf("\nP%d Turn Around Time : %d",pro[i].id,(pro[i].wait+pro[i].burst));
sjfawt=sjfawt+pro[i].wait;
sjfatrt=sjfatrt+(pro[i].wait+pro[i].burst);
}
printf("\n\nAWT of SJF : %f",sjfawt/nop);
printf("\n\nATRT of SJF : %f",sjfatrt/nop);
break;
}
case 3:
{
init();
j=0;
ret=0;
nop=getdata();
for(i=0;i<nop;i++)
tburst[i]=pro[i].burst;
printf("\nPlease enter the time quantum : ");
scanf("%d",&quantum);
for(i=0;i<nop;i++)
{
if(pro[i].burst>0)
{
if(pro[i].burst>quantum)
{
temp[j].id=pro[i].id;
temp[j].burst=quantum;
pro[i].burst=pro[i].burst-quantum;
j++;
incwait(quantum,pro[i].id);
}
else
{
temp[j]=pro[i];
j++;
incwait(pro[i].burst,pro[i].id);
pro[i].burst=0;
}
}
if(i==nop-1)
{
for(z=0;z<nop;z++)
{
if(pro[z].burst!=0)
{
i=-1;
break;
}
else
if(z==(nop-1)) ret=1;
}
}
if(ret==1) break;
}
table(temp,40);
gantt(temp,40);
printf("\n\nRound Robin awt and atrt : ");
rrawt=0;
rratrt=0;
for(i=0;i<nop;i++)
{
printf("\nP%d Wait Time : %d",pro[i].id,pro[i].wait);
printf("\nP%d Turn Around Time : %d",pro[i].id,(pro[i].wait+tburst[i]));
rrawt=rrawt+pro[i].wait;
rratrt=rratrt+(pro[i].wait+tburst[i]);
}
printf("\n\nAWT of RR : %f",rrawt/nop);
printf("\n\nATRT of RR : %f",rratrt/nop);
break;
}
}
printf("\n\nPress 1 to cont ...");
scanf("%d",&ans);
}
while(ans==1);
}

incwait(int tempburst,int id)
{
int i=0;
for(i=0;i<nop;i++)
{
if(pro[i].id!=id && pro[i].burst>0)
pro[i].wait=pro[i].wait+tempburst;
}
}

init()
{
int i;
nop=0;
for(i=0;i<10;i++)
{
pro[i].burst=0;
pro[i].id=0;
pro[i].wait=0;
}
for(i=0;i<20;i++)
{
temp[i].burst=0;
temp[i].id=0;
temp[i].wait=0;
}
}



table(struct process pro[],int nop)
{
int i;
printf("\n\n\n* * * * * * * PROCESS TABLE * * * * * * *\n\n");
printf("\nProcess Name Burst Time");
for(i=0;i<nop;i++)
{
if(pro[i].id==0)
break;
printf("\nP%d\t\t%d\t\t%d",pro[i].id,pro[i].burst);
}
}


gantt(struct process pro[],int nop)
{
int t=0,i;
int procount=0;
printf("\n\n\n* * * * * * * GANTT CHART * * * * * * *\n\n");
i=0;
while(pro[i].id>0)
{
procount++;
i++;
}
printf("\nÚ");
for(i=0;i<procount;i++)
printf("ÄÄÄÄÄÄÄÂ");
printf("\n³");
for(i=0;i<procount;i++)
printf(" P%d ³",pro[i].id);
printf("\nÀ");
for(i=0;i<procount;i++)
printf("ÄÄÄÄÄÄÄÁ");
printf("\n");
for(i=0;i<procount;i++)
{
printf("%d\t",t);
t=t+pro[i].burst;
}
printf("%d",t);
}


int getdata()
{
int i,nop;
printf("\n\nPlease enter the number of processes : ");
scanf("%d",&nop);
printf("\nPlease enter the ID and Burst time of each process : ");
printf("\n");
for(i=0;i<nop;i++)
{
printf("\nID : P%d",i+1);
pro[i].id=i+1;
printf("\nBurst Time : ");
scanf("%d",&pro[i].burst);
}
return nop;
}

You would be interested in:
1. Java Implementation of Page Replacement Algorithm -FIFO, LRU, OPT
2. Java Implementation of First-Fit, Best-Fit and Worst-Fit
3. Java Implementation of Bankers Algorithm
4. C implementation of CPU Scheduling Algorithm Shortest Remaining Time