Today we will learn the Shortest Job First Program in C. So, before start learning, you should have a little bit knowledge about Shortest job first. So,
Table of Contents
What is Shortest Job First?
This is an approach which considers the next CPU burst. Each process posses its next CPU burst. When CPU is available, the process having the smallest next CPU burst is allocated CPU.
Now it may happen that two or more processes have the same next CPU burst. Then which process to allocate will be decided as per FCFS scheduling.
Advantages:
This algorithm is simple to implement.
Does not depend on any priority of the process. The smallest burst time is the higher priority consideration.
It provides good CPU utilization than FCFS (First Come First Search).
Waiting time and turn around time of each process is reduced, reducing the average waiting time and turn around the time of the system as compared to FCFS.
Disadvantages:
Waiting time of some processes still high due to the long burst time of the processes, in case of non-preemptive scheduling.
In the case of non-preemptive scheduling, it may act as a uni-processing operating system.
In the case of preemptive scheduling, context switch is required.
And in preemptive scheduling, turn around time may get increased.
There are two schemes with this type of scheduling:
Non-preemptive: Once the CPU is allocated to a process, it can not be preempted until it completes its CPU burst.
Preemptive: If a new process arrives with CPU burst length less than remaining time of current execution process, preempt the current process. This scheme is known as Shortest-Remaining-Time-First (SRTF).
Working of non-preemptive SJF:
Consider the following set of processes and the respective CPU burst times:
Initially, at time 0, only one process P1 is present in the ready queue. So will get scheduled and start execution.
As it is non-preempted scheduling, it will finish its CPU burst and then only terminate. So it gets terminated 7-time units.
Now at this time, there are P2, P3 and P4 processes present in the ready queue. After the process is finished, the next process is to be scheduled.
If FCFS would have been used, Process P2 was the next one to be scheduled. But as it is SJF, the process having least CPU burst will get scheduled i.e process P3 will get scheduled.
After it gets finished, now there are 2 processes, P2 and P4, having the same next burst time. Now to break this tie, FCFS is used.
Process P2 has arrived time 2.0 and P4 has 5.0. So P2 has arrived first so will get scheduled first and then after its completion, P4 will get scheduled.
The process is summarized in the following Gantt chart:
1. Shortest Job First Program in C (Non-preemptive)
#include<stdio.h>
int main()
{
int bt[20],p[20],wt[20],tat[20],i,j,n,total=0,pos,temp;
float avg_wt,avg_tat;
printf("Enter number of process:");
scanf("%d",&n);
printf("\nEnter Burst Time:\n");
for(i=0;i<n;i++)
{
printf("p%d:",i+1);
scanf("%d",&bt[i]);
p[i]=i+1;
}
//sorting of burst times
for(i=0;i<n;i++)
{
pos=i;
for(j=i+1;j<n;j++)
{
if(bt[j]<bt[pos])
pos=j;
}
temp=bt[i];
bt[i]=bt[pos];
bt[pos]=temp;
temp=p[i];
p[i]=p[pos];
p[pos]=temp;
}
wt[0]=0;
for(i=1;i<n;i++)
{
wt[i]=0;
for(j=0;j<i;j++)
wt[i]+=bt[j];
total+=wt[i];
}
avg_wt=(float)total/n;
total=0;
printf("\nProcess\t Burst Time \tWaiting Time\tTurnaround Time");
for(i=0;i<n;i++)
{
tat[i]=bt[i]+wt[i];
total+=tat[i];
printf("\np%d\t\t %d\t\t %d\t\t\t%d",p[i],bt[i],wt[i],tat[i]);
}
avg_tat=(float)total/n;
printf("\n\nAverage Waiting Time=%f",avg_wt);
printf("\nAverage Turnaround Time=%f\n",avg_tat);
}Output:
In the above program, we have calculated the average waiting and average turn around time. After executing this program the compiler asks the user to enter the number of processes and then store it in n. Then compiler asks the user to enter the burst time and stored it in the array bt.
After the burst time is arranged in the next section so the shortest one can be executed first. Here the selection sorting is used for sorting of burst array bt.
The waiting time of the first element is always zero. So, the remaining waiting time is calculated by using two for loops. So the inner for loop is controlled by another for loop and inside that loop, waiting time is calculated by adding burst time to waiting time.
2. Shortest Job First Program in C (Preemptive)
#include <stdio.h>
int main()
{
int arrival_time[10], burst_time[10], temp[10];
int i, smallest, count = 0, time, limit;
double wait_time = 0, turnaround_time = 0, end;
float average_waiting_time, average_turnaround_time;
printf("\nEnter the Total Number of Processes:\t");
scanf("%d", &limit);
printf("\nEnter Details of %d Processesn", limit);
for(i = 0; i < limit; i++)
{
printf("\nEnter Arrival Time:\t");
scanf("%d", &arrival_time[i]);
printf("Enter Burst Time:\t");
scanf("%d", &burst_time[i]);
temp[i] = burst_time[i];
}
burst_time[9] = 9999;
for(time = 0; count != limit; time++)
{
smallest = 9;
for(i = 0; i < limit; i++)
{
if(arrival_time[i] <= time && burst_time[i] < burst_time[smallest] && burst_time[i] > 0)
{
smallest = i;
}
}
burst_time[smallest]--;
if(burst_time[smallest] == 0)
{
count++;
end = time + 1;
wait_time = wait_time + end - arrival_time[smallest] - temp[smallest];
turnaround_time = turnaround_time + end - arrival_time[smallest];
}
}
average_waiting_time = wait_time / limit;
average_turnaround_time = turnaround_time / limit;
printf("\n\nAverage Waiting Time:\t%lf\n", average_waiting_time);
printf("Average Turnaround Time:\t%lf\n", average_turnaround_time);
return 0;
}Output:
The difference between preemptive and non-preemptive is that when the two burst times are same then the algorithm evaluates them on the basis of FCFS (First Come First Served).
Also Read:
- Bubble Sort Program in C.
- Insertion Sort Program in C.
- Merge Sort Program in C.
- Quick Sort Program in C.
- Linear Search Program in C.
- Round Robin Program in C.
- Binary Search Program in C.
