10) C program for SRTF and Round robin [VTU SS&OS]

Code:

Explanation:
Program to demonstrate round robin, SRTF algorithm for process scheduling.
Turnaround time TAT= total time taken to execute from the arrival time (Arrival is 0 in this case).
Wait time WT= wait time, the time when process is waiting. (TAT-Burst time).

Note: In this program, I don't know at what extent I have been successful in expressing what I know. If you get what I'm trying to express, kindly post a review to support this post so that Google's indexing of this page improves. Thereby supporting my work. Thanks :)

#include<stdio.h>
#include<stdlib.h>
struct proc
{
int id;
int arrival;
int burst;
int rem;
int wait;
int finish;
int turnaround;
float ratio;
}process[10];
struct proc temp;
int no;

Include all the necessary header files.
Define a structure to hold all the necessary information about a process in SRTF. Each structure members define a parameter of a process.
Create an array of process[10] to store details of 10 processes, and one temporary process (which will be used while sorting of processed in the future).

int chkprocess(int);
int nextprocess();
void roundrobin(int, int, int[], int[]);
void srtf(int);

These functions do the job as the function names say.

main()
{
int n,tq,choice;
int bt[10],st[10],i,j,k;
for(; ;)
{
printf("Enter the choice \n");
printf(" 1. Round Robin\n 2. SRT\n 3. Exit \n");
scanf("%d",&choice);

Main function. Define suitable variables.

Bt[10] is burst time for round robin algorithm.
st[10] is to backup the bt array, so that we can calculate using st array and print bt later while outputting.
tq is time quantum of RR algorithm.
i,j,k are loop variables and choice is for choice.
Coming up is the switch, where we handle menu options accordingly.

switch(choice)
{
case 1:
printf("Round Robin scheduling algorithm\n");
printf("Enter number of processes:\n");
scanf("%d",&n);
printf("Enter burst time for sequences:");
for(i=0;i<n;i++)
{
scanf("%d",&bt[i]);
st[i]=bt[i]; //service time
}
printf("Enter time quantum:");
scanf("%d",&tq);
roundrobin(n,tq,st,bt);
break;

This is Round robin algorithm input taking.

Ask for number of process, n.
scan burst time for all processes and store it in bt array. also back it up to st array for calculation purposes.
Scan time quantum
Then call roundrobin() function to calculate the stuff. This function is explained later in the program when the definition comes.

case 2:
printf("\n \n ---SHORTEST REMAINING TIME NEXT---\n \n ");
printf("\n \n Enter the number of processes: ");
scanf("%d", &n);
srtf(n);
break;

This is for SRTF.
ask for number of processes and call the srtf function. we take input in the function body itself.
Explanations are ahead.

case 3: exit(0);
}// end of switch
}// end of for
}//end of main()

Exit if choice is 3. end switch,for loop and main's body.

void roundrobin(int n,int tq,int st[],int bt[])
{
int time=0;
int tat[10],wt[10],i,count=0,swt=0,stat=0,temp1,sq=0,j,k;
float awt=0.0,atat=0.0;

This is round robin function definition.
Variables are:

time, is not actually used in this code, you may neglect it.
tat[10], wt[10] which keeps info about turnaround time of each process and wait time respectively.
count=0, indicates how many processes got executed completely. when this reaches value 'n' (count==n means all process got executed), we exit.
swt and stat are to keep the sum of TAT and WT of all processes, initially 0.
temp1 for how much time did the current process execute at a go. you will understand this later.
sq=0, for keeping track of total elapsed time of execution.
awt, atat are for average wait time and turnaround time, initially 0.0, since this is average, declare them float.

while(1)
{

infinite while loop because we dont know how many times to cycle through the processes, so we declare an infinite loop. and when count==n, that means all processes got executed, so we break the loop. Hurrah!

for(i=0,count=0;i<n;i++)
{
temp1=tq;

for loop to run through process 0 to process n and cycle again and again. count is set to 0, meaning no processes are completed now.
temp1 is the execution time given for current process, usually equals time quantum.

if(st[i]==0)
{
count++;
continue;
}

st array is nothing but bt array (burst time). remember we backed it up for calculation?
if any process's remaining time=0 we need to skip to next process. same is done.

if(st[i]>tq)
st[i]=st[i]-tq;

If remaining time of that process is greater than the time quantum, we need to execute only tq time for now, so we decrement remaining time by time quantum.

else
if(st[i]>=0)
{
temp1=st[i];
st[i]=0;
}

if remaining time is less than time quantum and greater than 0, it means the process needs to be executed for st[i] duration after which it will get completed for sure (because st[i]<tq)., so we update temp1 to be st[i], make st[i]=0 which means process got completed. then increment count.

sq=sq+temp1;
tat[i]=sq;
}
if(n==count)
break;
} //end of while

sq, total elapsed time is updated by adding current executed time temp1 to already executed time sq.
then we assign turnaround time of i'th process to be current elapsed time. (if process already is completed, its turnaround time will not get updated because it wont reach here. remember we wrote continue; above?)
so this way, until count==n, all process gets checked repeated times, and then while loop breaks.

for(i=0;i<n;i++)
{
wt[i]=tat[i]-bt[i];
swt=swt+wt[i];
stat=stat+tat[i];
}
awt=(float)swt/n;
atat=(float)stat/n;
printf("Process_no Burst time Wait time Turn around time\n");
for(i=0;i<n;i++)
printf("%d\t\t%d\t\t%d\t\t%d\n",i+1,bt[i],wt[i],tat[i]);
printf("Avg wait time is %f\n Avg turn around time is %f\n",awt,atat);
}// end of Round Robin

so now, we calculate wait time for each process, wait time = turnaround time-burst time.
we also find total TAT and WT of all processes.
Once we find Total TAT and WT, then we calculate average TAT and WT.
Then print all data.

Round robin DONE!

//This is round robin stuff.
//function to check whether there are any processes left to be executed.

int chkprocess(int s)
{
int i;
for(i = 1; i <= s; i++)
{
if(process[i].rem != 0)
return 1;
}
return 0;
}

Starting from 0, till s (the latest arrived process, you will see it ahead in the code), we check whether any process's remaining time is not 0, which means that process isnt completed.
If any found, return 1. Else return 0.

int nextprocess()
{
int min, l, i;
min = 32000; //any limit assumed
for(i = 1; i <= no; i++)
{
if( process[i].rem!=0 && process[i].rem < min)
{
min = process[i].rem;
l = i;
}
}
return l;
} // end of nextprocess

Algorithm to calculate next process to be executed. This will be useful to select "Shortest remaining job" for next execution.

We keep a variable, named minimum. This will hold a large value at the beginning. We update it when we find a even less value than this.
We check for processes Starting from 0, till no (the latest arrived process, you will see it ahead in the code) for a process having minimum remaining time.
then find its index. return it to srtf().
Note that its return l; (lowercase L) not 1(one).

void srtf(int n)
{
int i,j,k,time=0;
float tavg,wavg;
for(i = 1; i <= n; i++)
{
process[i].id = i;
printf("\n\nEnter the arrival time for process %d: ", i);
scanf("%d", &(process[i].arrival));
printf("Enter the burst time for process %d: ", i);
scanf("%d", &(process[i].burst));
process[i].rem = process[i].burst;
}

SRTF function. Declare some varibales.
For each process, assign a process id. and ask its arrival time, and burst time(time required for completing that process). Take a backup of burst time as remaining time (for calculation).

for(i = 1; i <= n; i++)
{
for(j = i + 1; j <= n; j++)
{
if(process[i].arrival > process[j].arrival)
{
temp = process[i];
process[i] = process[j];
process[j] = temp;
}
}
}

This is nothing but selection sort of all process based on their arrival time.

no = 0;
j = 1;
while(chkprocess(n) == 1)
{

While there is a process to be executed, we keep on running while loop. no and j, will be seen later.

if(process[no + 1].arrival == time)
{
no++;
if(process[j].rem==0)
process[j].finish=time;
j = nextprocess();
}

This is the code, which cant be understood easily. for now, just know the logic of this, ill tell later, where this comes useful(let me refer to this code as thug code while referring). So here it is,

Actually logic of code is simple. if somewhere we found the next process to execute and increment time. and after incrementing time, if any new process arrives, we need to check whether the newly arrived process is the next to be executed. so we call nextprocess() again to make it proper. (don't mind, read this explanation again when i refer this thug code ahead)

if(process[j].rem != 0)
{
process[j].rem--;
for(i = 1; i <= no; i++)
{
if(i != j && process[i].rem != 0)
process[i].wait++;
}
}

If the current process's remaining time is not 0, it means it needs to be executed.
decrement the remaining time by 1 unit. also you need to increase wait time of other processes(which are not completed), this is done with this condition if(i != j && process[i].rem != 0), we increment wait time by 1, of these processes.

else
{
process[j].finish = time;
j=nextprocess();
time--;
k=j;
}
time++;
}

If process has finished execution, we assign the finished time equals to current time, and find the next process to execute using nextprocess().

BUT

We found the next process to execute, but if at that point, any new process arrives, we even have to consider that. Here, previously defined "Thug code" comes to rescue, by checking whether the the no+1 process's arrival is equal to current time. (no holds the number of processes arrived till now)

If something arrived now, we need to again call the nextprocess() now, with the arrived process included. this is what is done in thug code.

Decrement current time by 1, because this process is already executed, and we did no operation here, since time is going to be updated at the end of the loop, to neutralize this, we do time--;
assign k=j, because if this was the last process remaining, we need to set finished time[k] outside loop.
Time++, because we did something in this 1 unit of time, for some process. so increment time by 1.(now i hope you got why was that time-- in previous snippet, because we that process already was executed, we did nothing in that iteration but checking)

process[k].finish = time;

to assign finished time of last process executed.

printf("\n\n\t\t\t---SHORTEST REMAINING TIME FIRST---");
printf("\n\n Process Arrival Burst Waiting Finishing turnaround Tr/Tb \n");
printf("%5s %9s %7s %10s %8s %9s\n\n", "id", "time", "time", "time", "time", "time");
for(i = 1; i <= n; i++)
{
process[i].turnaround = process[i].wait + process[i].burst;
process[i].ratio = (float)process[i].turnaround / (float)process[i].burst;

printf("%5d %8d %7d %8d %10d %9d %10.1f ", process[i].id, process[i].arrival,
process[i].burst, process[i].wait, process[i].finish, process[i].turnaround, process[i].ratio);
tavg=tavg+ process[i].turnaround;
wavg=wavg+process[i].wait;
printf("\n\n");
}
tavg=tavg/n;
wavg=wavg/n;
printf("tavg=%f\t wavg=%f\n",tavg,wavg);
}// end of srtf

Printing all values at the end.
before printing, calculate turnaround time (which is wait time+burst time in this case, not round robin's formula. because processes arrive at different times unlike round robin.
Then at the end, calculate average TAT and WT. and print both.

SRTF DONE TOO!

CHEERS! ;__;

Author : Unknown

He is a simple passionate tech freak who himself is an engineering student at Canara Engineering college. He likes App Development, Web designing, Blogging, Youtubing, Debugging and also is a CodeGeek!