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
:-)

9 comments:

  1. hey, how can u do that? Impressive!!! Thanks

    ReplyDelete
  2. Brillliant......mind

    ReplyDelete
  3. why does it have errors? help..

    ReplyDelete
  4. As per our knowledge there is no error in the program. For your convenience We have also posted the output along with the program...

    Please specify the error (if any) in detail

    ReplyDelete
  5. which IDE did you use to compile the program

    ReplyDelete