scheduling algorithms - priority pre-emptive and round robin

schedule.c

#include<stdio.h>
//#include<conio.h>
struct process
{
int pid,bt,at,priority,wt,tat,et,st,rt,rem;
int finished,count;
}p[100],fin[100];
void calc(int n)
{
int flag=0;
int i;
for(i=0;i<n;i++)
{
if(flag==0)
{
p[i].st=p[i].at;
p[i].et=p[i].st+p[i].bt;
p[i].wt=p[i].st-p[i].at;
p[i].rt=p[i].wt;
p[i].tat=p[i].et-p[i].at;
flag=1;
}
else
{
p[i].st=p[i-1].et;
if(p[i].st<p[i].at)
p[i].st=p[i].at;
p[i].et=p[i].st+p[i].bt;
p[i].wt=p[i].st-p[i].at;
p[i].rt=p[i].wt;
p[i].tat=p[i].et-p[i].at;

}
}
}
void gantt(struct process p1[100],int no)

{

     int i,j;

     printf("\nGANTT CHART : \n");
     for(i=0;i<no;i++)

     {

                      printf("%d",p1[i].pid);

                      for(j=0;j<p1[i].bt;j++)

                      printf("_");

                      printf("|");


     }
     printf("\n");
//for(i=0;i<no;i++)

  //   {

    //                  printf("%d",p1[i].tat);

      //                for(j=0;j<p1[i].bt;j++)
//printf(" ");
//}
}
void display(struct process p1[100],int n)
{
int i;
float totwt=0.0,totat=0.0;
float avgwt,avgtat;

printf("\n--------------------------------------------------------------------\n");
printf("\npid|\tat|\tpty|\tbt|\tst|\tet|\twt|\trt|\ttat\n");
printf("------------------------------------------------------------------------\n");
for(i=0;i<n;i++)
{
printf("\n%d\t%d\t%d\t%d\t%d\t%d\t%d\t%d\t%d\n",p1[i].pid,p1[i].at,p1[i].priority,p1[i].bt,p1[i].st,p1[i].et,p1[i].wt,p1[i].rt,p1[i].tat);
totwt+=p1[i].wt;
totat+=p1[i].tat;

}
printf("------------------------------------------------------------------------\n");
avgwt= totwt/n;
avgtat=totat/n;
printf("AVERAGE WAITING TIME IS : %f\n",avgwt);
printf("AVERAGE TURN AROUND TIME IS:%f\n",avgtat);

}
void sort (int n,int choice)
{
    struct process s;
  int i,j,result;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(choice==1)
{
result=(p[i].at <  p[j].at);
}
else if(choice==2)
{
if(p[i].at==p[j].at)
result=(p[i].bt <  p[j].bt);
else
result=(p[i].at<p[j].bt);
}
if(result)
{
//printf("here\n");
s=p[i];
p[i]=p[j];
p[j]=s;
}
}
}


}
void nps(int n)
{
int i,j,min;
struct process temp;
sort(n,1);
min=p[0].bt+p[0].at;
//printf("%d\n",min);
for(i=1;i<n;i++)
{
if(i!=1)
{
for(j=i-1;j<i;j++)
{
if(p[i].at <= min && p[i].priority <  p[j].priority  )
{
temp=p[i];
p[i]=p[j];
p[j]=temp;
min+=p[i].bt;
//printf("%d\n",min);
}
}
}
}
}

int small(int n,int start,int arr)
{
int index=-1,i,max=999;
for(i=0;i<n;i++)
{
if(p[i].finished!=1)
{
if(p[i].priority  < fin[start].priority && p[i].at<=arr && p[i].rem >0 )
{
index=i;
}
}
}
return index;
}
int find(int value,int n)
{
int i;
for(i=0;i<n;i++)
{
if(fin[value].pid==p[i].pid )
{
return i;
}
}
}

int load(int n,int arr,int pro)
{
int i,max=999,index=-1,flag=0;
for(i=0;i<n;i++)
{
                if(p[i].at >arr && p[i].priority < max && p[i].finished!=1&& flag==0)
                arr=p[i].at;
if(p[i].finished!=1 &&p[i].priority<max &&p[i].at<=arr )
{
max=p[i].priority;
index=i;
flag=1;
}
}
return index;
}
int find_calc(int temp,int pos)
{
    int i;
for(i=temp-1;i>=0;i--)
{
    if(fin[pos].pid==fin[i].pid)
{
    return i;
    break;
}
}
}
void pps(int n)
{
int res=0;
int i,index,pro,flag=0;;
int temp=0,pos,prev;
int max=0,value=0;
int cnt=0;
sort(n,1);
for(i=0;i<n;i++)
{
p[i].rem=p[i].bt;
value+=p[i].bt;
p[i].count=0;
p[i].finished=0;
p[i].tat=0;
}
//printf("%d\n",value);
res=temp;
max+=p[0].at+p[0].bt;
fin[0]=p[0];
while(max<=value)
{
index=small(n,temp,max);

if(index==-1)
{
res=temp;
pro=find(temp,n);
p[pro].finished=1;
if(flag==0)
{
max=0;
flag=1;
}
                         
                         max+=p[pro].rem;
                         fin[temp]=p[pro];
   if(fin[temp].at > fin[temp-1].et)
   fin[temp].st=fin[temp].at;
    else
    fin[temp].st=fin[temp-1].et;
if(p[pro].count==1)
{
 prev=find_calc(temp,temp);
 fin[temp].et=fin[temp].st+p[pro].rem;
 fin[temp].wt=fin[temp].st+fin[prev].wt-fin[prev].et;
 }
 else
{
     fin[temp].et=fin[temp].st+fin[temp].bt;
     fin[temp].wt=fin[temp].st-fin[temp].at;
}
     p[pro].count=0;
     p[pro].rem=0;  
fin[temp].rem=p[pro].rem;
fin[temp].tat=fin[temp].et-fin[temp].at;
pos=load(n,max,pro); // this is used to load the next job wit higher priority!!
if(pos==-1)
break;
else
    fin[res+1]=p[pos];
fin[res+1].st=max;
}
else
{
                      res=temp;
                  fin[res+1]=p[index];
                  pos=find(temp,n);
                  fin[temp]=p[pos];
if(flag==0)
{
           max=0;
           max=p[index].at;
           fin[temp].st=fin[temp].at;
fin[temp].et=fin[temp].st+max;
           flag=1;
}
if(fin[temp-1].et < fin[temp].at)
       fin[temp].st=fin[temp].at;
       else
       fin[temp].st=fin[temp-1].et;
       
p[pos].rem=p[pos].rem-max;
fin[temp].rem=p[pos].rem;
p[pos].count=1;

fin[temp].wt=fin[temp].st-fin[temp].at;
fin[res+1].st=fin[temp].et;

}
temp+=1;
}
gantt(fin,temp+1);
float totwt=0.0,totat=0.0;
float avgwt,avgtat;
gantt(fin,temp+1);

printf("\n---------------------------------------------------------\n");

printf("\npid|\tat|\tbt|\tpty|\tst|\tet|\twt|\tremt|\ttat\n");

printf("---------------------------------------------------------\n");

for(i=0;i<temp+1;i++)

{

printf("\n%d\t%d\t%d\t%d\t%d\t%d\t%d\t%d\t%d\n",fin[i].pid,fin[i].at,fin[i].bt,fin[i].priority,fin[i].st,fin[i].et,fin[i].wt,fin[i].rem,fin[i].tat);
if(fin[i].rem==0)
totwt+=fin[i].wt;
totat+=fin[i].tat;
}

printf("----------------------------------------------------------\n");
avgwt= totwt/n;
avgtat=totat/n;
printf("AVERAGE WAITING TIME IS : %f\n",avgwt);
printf("AVERAGE TURN AROUND TIME IS:%f\n",avgtat);
}

int findprev(int n,int pos)
{
     int i,index=-1;
for(i=n-1;i>=0;i--)
{
                 if(fin[pos].pid==fin[i].pid)
{
                 index=i;
                 return index;
                 break;
                 }
}
return index;
}
void roundrobin(int n,int time)
{
     int max=0,value=0,counter=0;
     int cycle=0;
     int temp=0,pos,flag=0,i,j,check,prev;
     sort(n,1);

printf("ROUND ROBIN\n");
for(i=0;i<n;i++)
{
                p[i].rem=p[i].bt;
                value+=p[i].bt;
                p[i].finished=0;
 }
max=p[0].at+time;
while(max<=value)
{
counter=0;
for(i=0;i<n;i++)
{
                if(p[i].rem>0 && p[i].finished!=1 && p[i].at<=max)
{
                counter++;

}
}
//printf("counter %d\n",counter);
if(counter==0)
{
break;
}
else
{
check=1;
cycle+=1;
while(check<=counter)
{
                    for(j=0;j<n;j++)
      {
                    if(p[j].rem>0 && p[j].finished!=1 && p[i].at<=max) 
               { 
                      fin[temp]=p[j];
if(temp==0)
{
max=0;
           fin[temp].st=p[j].at;
           if(p[j].rem<time)
           fin[temp].et=fin[temp].st+p[j].rem;
           else
           fin[temp].et=fin[temp].st+time;
p[j].wt=p[j].st-p[j].wt;
if(p[j].rem<time)
{max+=p[j].rem;
p[j].rem=0;}
else
{
    
p[j].rem=p[j].rem-time;
fin[temp].rem=p[j].rem;
max+=time;
}
if(fin[temp].rem==0)
{
               p[j].finished=1;
               fin[temp].tat=fin[temp].et-fin[temp].at;
                             }
}
else
{
    
                 if(fin[temp-1].et<fin[temp].at)
                     fin[temp].st=fin[temp].at;
                     else
                     fin[temp].st=fin[temp-1].et;
                     if(fin[temp].rem > time)
                 fin[temp].et=fin[temp].st+time;
                 else
                 fin[temp].et=fin[temp].st+fin[temp].rem;
prev=findprev(temp,temp);
if(prev!=-1)
fin[temp].wt=fin[temp].st+fin[prev].wt - fin[prev].et;
else
fin[temp].wt=fin[temp].st-fin[temp].at;
if(p[j].rem < time)
{
            max+=p[j].rem;
    p[j].rem=0;
    fin[temp].rem=p[j].rem;
}
    else
    {
        
p[j].rem= p[j].rem-time;
max+=time;
fin[temp].rem=p[j].rem;
}
               fin[temp].rem=p[j].rem;
                 
if(p[j].rem==0)
                 {
                 p[j].finished=1;
                 fin[temp].tat=fin[temp].et-fin[temp].at;
                 }


}
temp+=1;
check+=1;
}
}
}
}
}


gantt(fin,temp);
float totwt=0.0,totat=0.0;
float avgwt,avgtat;



printf("\n---------------------------------------------------------\n");

printf("\npid|\tat|\tbt|\tst|\tet|\twt|\tremt|\ttat\n");

printf("---------------------------------------------------------\n");

for(i=0;i<temp;i++)
{
printf("\n%d\t %d \t%d\t %d\t %d\t %d\t %d\t %d\n",fin[i].pid,fin[i].at,fin[i].bt,fin[i].st,fin[i].et,fin[i].wt,fin[i].rem,fin[i].tat);
if(fin[i].rem==0)
totwt+=fin[i].wt;
totat+=fin[i].tat;
}
avgwt= totwt/n;
avgtat=totat/n;
printf("AVERAGE WAITING TIME IS : %f\n",avgwt);
printf("AVERAGE TURN AROUND TIME IS:%f\n",avgtat);

}
int main()
{
int ch,i,n,t;
printf("enter the number of processes\n");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("enter process id\n");
scanf("%d",&p[i].pid);
printf("enter the arrival time\n");
scanf("%d",&p[i].at);
printf("enter the service time\n");
scanf("%d",&p[i].bt);
printf("enter the priority\n");
scanf("%d",&p[i].priority);
}
do
{
                           printf("\n1.priority non premptive\n2.priority premptive\n3.roundrobin\n4.exit\n");
printf("enter choice\n");
scanf("%d",&ch);
if(ch==1)
{
nps(n);
calc(n);
gantt(p,n);
display(p,n);
}
if(ch==2)
{
pps(n);
}
if(ch==3)
{
         printf("enter the time interval\n");
         scanf("%d",&t);
         roundrobin(n,t);
         }

}while(ch!=4);
//getch();
return 0;
}