Tuesday, April 12, 2011

C implementation of CPU Scheduling Algorithm Shortest Remaining Time

Hello Friends, here's C implementation of CPU Scheduling Algorithms(Shortest Remaining Time).This is a .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 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 Time");
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]);
}
maxarrtime=pool[nop-1].arrival;
while(time<=maxarrtime)
{
printf("\n\nTime : %d ",time);
printf("\tpool[%d].arr : %d ",z,pool[z].arrival);
if(time==pool[z].arrival)
{
no=scanpro(time,nop);
printf("\n\nNo of Process with same arrival time : %d",no);
printf("\nMoving Arrived process from Pool of Process to Ready Queue...");
for(counter=0;counter<no;counter++)
{
ready[x]=pool[z];
printf("\npool[%d].id = P%d ",z,pool[z].id);
printf("\tready[%d].id = P%d",x,ready[x].id);
x++;
z++;
}
execute();
}
else
{
if(current.burst>0)
{
current.burst--;
incwait1();
printf("\nCurrent : P%d and Burst : %d",current.id,current.burst);
time++;
}
else
{
if(current.burst==0)
{
printf("\nProcess P%d completes.",current.id);
execute();
}
}
}
}
counter=temp.burst-current.burst;
tmp=0;
while(current.burst!=0)
{
current.burst--;
counter++;
tmp++;
}
i=1;
printf("\nIncrementing Wait Time of processes in Ready Queue by %d...",tmp);
printf("\nAfter Incrementing ...");
while(ready[i].id>0 && ready[i].burst!=0)
{
ready[i].wait=ready[i].wait+tmp;
printf("\nP%d waiting time : %d",ready[i].id,ready[i].wait);
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];
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;
printf("\nP%d Total Wait Time -->%f\tTotal Turn Around Time -->%f",i+1,at[i],(at[i]+pool[i].burst));
}
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);
return 0;
}

execute()
{
ready[0]=current;
printf("\nMoving current process to first location in Ready Queue.");
arrange();
temp.burst=temp.burst-current.burst;
exe[y++]=temp;
current=ready[0];
printf("\nCurrent :: ID = P%d Burst = %d",current.id,current.burst);
temp=ready[0];
current.burst--;
incwait1();
printf("\nDecrementing Current Burst by 1. Current burst : %d",current.burst);
time++;
}

incwait1()
{
int i=1;
printf("\n\nIncrementing wait time of processes in Ready Queue ...");
while(ready[i].id>0 && ready[i].burst!=0)
{
ready[i].wait++;
printf("\nP%d wait : %d",ready[i].id,ready[i].wait);
i++;
}
}

incwait2()
{
int i=1;
int wt=0;
printf("\n\nIncrementing wait time of processes in Ready Queue ...");
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;
printf("\nP%d wait : %d",ready[i].id,ready[i].wait);
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;
}
}
}
printf("\nReady Queue after arranging : ");
for(i=0;i<10;i++)
{
if(ready[i].id!=0 && ready[i].burst>0)
{
printf("\nP ID : P%d",ready[i].id);
printf("\tP Burst : %d",ready[i].burst);
}
}
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;
}
}


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);
}

OUTPUT:

Please enter the number of processes : 6

Please enter the ID, Burst time & Arrival Time of each process :

ID : P1
Burst Time : 7
Arrival Time : 0.000

ID : P2
Burst Time : 3
Arrival Time : 0.001

ID : P3
Burst Time : 1
Arrival Time : 5.001

ID : P4
Burst Time : 5
Arrival Time : 6.002

ID : P5
Burst Time : 4
Arrival Time : 6.020

ID : P6
Burst Time : 2
Arrival Time : 7.001

* * * * * * * PROCESS TABLE * * * * * * *

P ID Burst Time Arrival Time
P1 7 0.000000
P2 3 0.001000
P3 1 5.001000
P4 5 6.002000
P5 4 6.020000
P6 2 7.001000

Time : 0 pool[0].arr : 0

No of Process with same arrival time : 1
Moving Arrived process from Pool of Process to Ready Queue...
pool[0].id = P1 ready[1].id = P1
Moving current process to first location in Ready Queue.
Ready Queue after arranging :
P ID : P1 P Burst : 7
Current :: ID = P1 Burst = 7

Incrementing wait time of processes in Ready Queue ...
Decrementing Current Burst by 1. Current burst : 6

Time : 1 pool[1].arr : 1

No of Process with same arrival time : 1
Moving Arrived process from Pool of Process to Ready Queue...
pool[1].id = P2 ready[2].id = P2
Moving current process to first location in Ready Queue.
Ready Queue after arranging :
P ID : P2 P Burst : 3
P ID : P1 P Burst : 6
Current :: ID = P2 Burst = 3

Incrementing wait time of processes in Ready Queue ...
P1 wait : 1
Decrementing Current Burst by 1. Current burst : 2

Time : 2 pool[2].arr : 6

Incrementing wait time of processes in Ready Queue ...
P1 wait : 2
Current : P2 and Burst : 1

Time : 3 pool[2].arr : 6

Incrementing wait time of processes in Ready Queue ...
P1 wait : 3
Current : P2 and Burst : 0

Time : 4 pool[2].arr : 6
Process P2 completes.

Moving current process to first location in Ready Queue.
Ready Queue after arranging :
P ID : P1 P Burst : 6
Current :: ID = P1 Burst = 6
Incrementing wait time of processes in Ready Queue ...
Decrementing Current Burst by 1. Current burst : 5

Time : 5 pool[2].arr : 6

Incrementing wait time of processes in Ready Queue ...
Current : P1 and Burst : 4

Time : 6 pool[2].arr : 6

No of Process with same arrival time : 1
Moving Arrived process from Pool of Process to Ready Queue...
pool[2].id = P3 ready[3].id = P3
Moving current process to first location in Ready Queue.
Ready Queue after arranging :
P ID : P3 P Burst : 1
P ID : P1 P Burst : 4
Current :: ID = P3 Burst = 1

Incrementing wait time of processes in Ready Queue ...
P1 wait : 4
Decrementing Current Burst by 1. Current burst : 0

Time : 7 pool[3].arr : 7

No of Process with same arrival time : 2
Moving Arrived process from Pool of Process to Ready Queue...
pool[3].id = P4 ready[4].id = P4
pool[4].id = P5 ready[5].id = P5
Moving current process to first location in Ready Queue.
Ready Queue after arranging :
P ID : P1 P Burst : 4
P ID : P5 P Burst : 4
P ID : P4 P Burst : 5
Current :: ID = P1 Burst = 4

Incrementing wait time of processes in Ready Queue ...
P5 wait : 1
P4 wait : 1
Decrementing Current Burst by 1. Current burst : 3

Time : 8 pool[5].arr : 8

No of Process with same arrival time : 1
Moving Arrived process from Pool of Process to Ready Queue...
pool[5].id = P6 ready[6].id = P6
Moving current process to first location in Ready Queue.
Ready Queue after arranging :
P ID : P6 P Burst : 2
P ID : P1 P Burst : 3
P ID : P5 P Burst : 4
P ID : P4 P Burst : 5
Current :: ID = P6 Burst = 2

Incrementing wait time of processes in Ready Queue ...
P1 wait : 5
P5 wait : 2
P4 wait : 2
Decrementing Current Burst by 1. Current burst : 1
Incrementing Wait Time of processes in Ready Queue by 1...
After Incrementing ...
P1 waiting time : 6
P5 waiting time : 3
P4 waiting time : 3

Ready Queue after arranging :
P ID : P1 P Burst : 3
P ID : P5 P Burst : 4
P ID : P4 P Burst : 5

Incrementing wait time of processes in Ready Queue ...
P5 wait : 6
P4 wait : 10
P1 Total Wait Time -->6.000000 Total Turn Around Time -->13.000000
P2 Total Wait Time -->0.999000 Total Turn Around Time -->3.999000
P3 Total Wait Time -->0.999000 Total Turn Around Time -->1.999000
P4 Total Wait Time -->10.998000 Total Turn Around Time -->15.998000
P5 Total Wait Time -->6.980000 Total Turn Around Time -->10.980000
P6 Total Wait Time -->0.999000 Total Turn Around Time -->2.999000

Average Waiting Time : 4.495833

Average Turn Around Time : 8.162500


* * * * * * * GANTT CHART * * * * * * *

┌────┬────┬────┬────┬────┬────┬────┬────┬────┬
│ P1 │ P2 │ P1 │ P3 │ P1 │ P6 │ P1 │ P5 │ P4 │
└────┴────┴────┴────┴────┴────┴────┴────┴────┴
0 1 4 6 7 8 10 13

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

Do leave a comment if u appreciate the output style
:-)