
Shortest Job First (SJF) Scheduling Algorithm All details that you should know!
It is a scheduling algorithm of an operating system
Shortest Job First (SJF) Criteria
- The process that requires the shortest time to complete execution, is served first.
Shortest Job First (SJF) Decision Mode
- Non-preemptive: Once a process is selected, it runs until it blocks for an I/O or some event, or it terminates.
Shortest Job First (SJF) Implementation
- This strategy can be easily implemented by using FIFO. FIFO means First In First Out.
- In this, we select the process which is less burst time from the arrival processes.
- For finding Completion time, looking in the Gantt chart from the back and complete of each process is completion time.
- Turn Around Time = Completion Time – Arrival Time.
- Waiting Time = Turn Around Time – Burst Time.
Now, see one example for a better understanding of it.
For Example:
Process | Arrival Time (A.T.) | Burst Time (B.T.) |
P0 | 0 | 10 |
P1 | 1 | 6 |
P2 | 3 | 2 |
P3 | 5 | 4 |
In this example,
- Only one process is arriving at 0 time P0.so, we have to do execution of process P0.
- After the completion of process P0. All the processes have arrived. so that we have to see for less burst time.
- After that P2 process is less burst time than others.
- Similarly, likewise, the process get executes.
Gantt Chart
Table
Process | Arrival Time | Burst Time | Completion Time | Turnaround Time | Waiting Time |
P0 | 0 | 10 | 10 | 10 | 0 |
P1 | 1 | 6 | 22 | 21 | 15 |
P2 | 3 | 2 | 12 | 9 | 7 |
P3 | 5 | 4 | 16 | 11 | 7 |
Average Turnaround Time:(10+21+9+11)/4 = 12.75
Average Waiting Time: (0+15+7+7)/4 = 7.25
Throughput: 0.181818
Advantages
- Less waiting time.
- Response time is less.
Disadvantages
- We can’t predict the completion time of the process.
- Starvation is possible for a long process.
Implementation of SJF in C language
#include <stdio.h>
int main()
{
int size;
printf("Enter the number of process : ");
scanf("%d", &size);
int at[size], bt[size], wt[size], p[size], tat[size], ct[size], i, j, gc = 0, temp1 = 0, ttat = 0, twt = 0, sbr;
float awt = 0.0, atat = 0, tp = 0;
printf("Enter Process's Arrival Time : \n");
for (i = 0; i < size; i++)
{
p[i] = i;
scanf("%d", &at[i]);
}
printf("Enter Process's Burst Time : \n");
for (i = 0; i < size; i++)
{
scanf("%d", &bt[i]);
}
//Sorting According to Arrival Time
for (i = 0; i < size; i++)
{
for (j = 0; j < size - i - 1; j++)
{
if (at[j + 1] < at[j])
{
temp1 = at[j];
at[j] = at[j + 1];
at[j + 1] = temp1;
temp1 = 0;
temp1 = bt[j];
bt[j] = bt[j + 1];
bt[j + 1] = temp1;
temp1 = 0;
temp1 = p[j];
p[j] = p[j + 1];
p[j + 1] = temp1;
}
}
}
//display After sorting 1
printf("Sorted according to Arrival Time: \n");
printf("P.No.\tAT\tBT");
for (i = 0; i < size; i++)
{
printf("\n%d\t%d\t%d", p[i], at[i], bt[i]);
}
//Applying sorting According to Burst Time
gc=at[0];
for (sbr = 0; sbr < size; sbr++)
{
printf("\nP.No.\tAT\tBT");
for (i = 0; i < size; i++)
{
printf("\n%d\t%d\t%d", p[i], at[i], bt[i]);
}
printf("\nsbr=%d",sbr);
for (i = sbr; i < size ; i++)
{
for (j = sbr; j < size - 1; j++)
{
if(at[j] <= gc && at[j+1] <= gc)
{
if (bt[j + 1] < bt[j])
{
if(gc<at[i]){
gc=at[i];
}
temp1 = at[j];
at[j] = at[j + 1];
at[j + 1] = temp1;
temp1 = 0;
temp1 = bt[j];
bt[j] = bt[j + 1];
bt[j + 1] = temp1;
temp1 = 0;
temp1 = p[j];
p[j] = p[j + 1];
p[j + 1] = temp1;
}
}
}
}
gc = gc + bt[sbr];
ct[sbr] = gc;
}
//gc = at[0];
//Computing Value of ct,wt,tat
for (i = 0; i < size; i++)
{
/*if (gc < at[i])
{
gc = at[i];
}*/
//gc = gc + bt[i];
//ct[i] = gc;
tat[i] = ct[i] - at[i];
ttat = ttat + tat[i];
wt[i] = tat[i] - bt[i];
twt = twt + wt[i];
}
atat = (float)ttat / size;
awt = (float)twt / size;
tp = (float)size / gc;
printf("\n\n");
printf("\nAfter Performing SJF:\n");
//display After sorting 2
printf("Sorted according to Bust Time: \n");
printf("P.No.\tAT\tBT\tCT\tWT\tTAT");
for (i = 0; i < size; i++)
{
printf("\n%d\t%d\t%d\t%d\t%d\t%d", p[i], at[i], bt[i], ct[i], wt[i], tat[i]);
}
//Sorting According to Arrival Time
printf("\n\n");
for (i = 0; i < size; i++)
{
for (j = 0; j < size - i - 1; j++)
{
if (p[j + 1] < p[j])
{
temp1 = at[j];
at[j] = at[j + 1];
at[j + 1] = temp1;
temp1 = 0;
temp1 = bt[j];
bt[j] = bt[j + 1];
bt[j + 1] = temp1;
temp1 = 0;
temp1 = p[j];
p[j] = p[j + 1];
p[j + 1] = temp1;
temp1 = 0;
temp1 = ct[j];
ct[j] = ct[j + 1];
ct[j + 1] = temp1;
temp1 = 0;
temp1 = wt[j];
wt[j] = wt[j + 1];
wt[j + 1] = temp1;
temp1 = 0;
temp1 = tat[j];
tat[j] = tat[j + 1];
tat[j + 1] = temp1;
}
}
}
printf("Final SJF Answer: \n");
printf("P.No.\tAT\tBT\tCT\tWT\tTAT");
for (i = 0; i < size; i++)
{
printf("\n%d\t%d\t%d\t%d\t%d\t%d", p[i], at[i], bt[i], ct[i], wt[i], tat[i]);
}
printf("\nAvg.Turn Around Time: %.2f", atat);
printf("\nAvg. Weight Time: %.2f", awt);
printf("\nThroughPut: %.2f", tp);
}
In conclusion, SJF is Non-preemptive but If we can make it preemptive it becomes SRTF.
Comment for any query.
To learn more concept about SJF go to
https://www.geeksforgeeks.org/program-shortest-job-first-sjf-scheduling-set-1-non-preemptive/
For Android projects goto the ANDROID
For Assignment Questions and Explanation of a theory topic visit:
Be the first to comment