Shortest Job First (SJF) Scheduling Algorithm

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.

Decision Mode:

  • Non-preemptive: Once a process is selected, it runs until it blocks for an I/O or some event, or it terminates.

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

shortest-job-first

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

Stay Connect with our app: – 

https://play.google.com/store/apps/details?id=com.edu.easyengineer

For Assignment Questions and Explanation of a theory topic visit:

http://mycandal.com/home/elementor-179/

About easyengineering 32 Articles
Easyengineering.in provides you to all subject and exam related materials online like GPSC, UPSC, IES, GATE, etc. As well as we provide daily job notification, some life-related books and other online courses which are useful too in your study.

Be the first to comment

Leave a Reply

Your email address will not be published.


*