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