Shortest Job First

Challenge

Shortest Job First (SJF) is an algorithm in which the process having the smallest execution time is chosen for the next execution. This scheduling method can be preemptive or non-preemptive. It significantly reduces the average waiting time for other processes awaiting execution

Create a program for Scheduling algorithm - Shortest Job First (SJF)

Solution (C)

#include<stdio.h>

struct time {

int p, art, but, wtt, tat, st;

};

int process(struct time a[], int pro, int t) {

int i, minpro, mintime = 999;

for (i = 0; i < pro; i++) {

if (a[i].art <= t && a[i].st == 0) {

if (mintime > a[i].but) {

mintime = a[i].but;

minpro = i;

}

}

}

a[minpro].st = 1;

return minpro;

}

void ganttchart(struct time a[], int gc[], int pro) {

int i, x = 0;

printf("Gantt Chart\n");

printf("0");

for (i = 0; i < pro; i++) {

x = x + a[gc[i]].but;

printf(" -> [P%d] <- %d", a[gc[i]].p, x);

}

printf("\n");

return;

}

int main() {

int i, pro, curpro, t = 0, gc[100];

struct time a[100];

float avgwt = 0, avgtt = 0;

printf("SJF (Shortest Job First) - Non Preemptive\n");

printf("Note -\n1. Arrival Time of at least on process should be 0\n2. CPU should never be idle\n");

printf("Enter Number of Processes\n");

scanf("%d", &pro);

for (i = 0; i < pro; i++) {

printf("Enter Arrival Time & Burst Time for Process P%d\n", i);

a[i].p = i;

scanf("%d%d", &a[i].art, &a[i].but);

a[i].st = 0;

}

for (i = 0; i < pro; i++) {

curpro = process(a, pro, t);

a[curpro].wtt = t - a[curpro].art;

a[curpro].tat = a[curpro].art + a[curpro].but;

t = t + a[curpro].but;

avgwt = avgwt + a[curpro].wtt;

avgtt = avgtt + a[curpro].tat;

gc[i] = curpro;

}

printf("***************************************\n");

printf("Pro\tArTi\tBuTi\tTaTi\tWtTi\n");

printf("***************************************\n");

for (i = 0; i < pro; i++) {

printf("%d\t%d\t%d\t%d\t%d\n", a[i].p, a[i].art, a[i].but, a[i].tat, a[i].wtt);

}

printf("***************************************\n");

ganttchart(a, gc, pro);

printf("***************************************\n");

avgwt = avgwt / pro;

avgtt = avgtt / pro;

printf("Average Waiting Time : %.2f\n", avgwt);

printf("Average Turn around Time : %.2f\n", avgtt);

return 0;

}

Output

/*

SJF (Shortest Job First) - Non Preemptive

Note -

1. Arrival Time of at least on process should be 0

2. CPU should never be idle

Enter Number of Processes

4

Enter Arrival Time & Burst Time for Process P0

0 4

Enter Arrival Time & Burst Time for Process P1

2 5

Enter Arrival Time & Burst Time for Process P2

3 8

Enter Arrival Time & Burst Time for Process P3

1 6

***************************************

Pro ArTi BuTi TaTi WtTi

***************************************

0 0 4 4 0

1 2 5 7 2

2 3 8 11 12

3 1 6 7 8

***************************************

Gantt Chart

0 -> [P0] <- 4 -> [P1] <- 9 -> [P3] <- 15 -> [P2] <- 23

***************************************

Average Waiting Time : 5.50

Average Turnaround Time : 7.25

*/