Shortest Job First [SJF] Process Scheduling Program with Gantt Chart

Another type of process scheduling algorithm is the Shortest Job First [SJF] process scheduling algorithm, In SJF the CPU is allocated to the process which has the smallest CPU burst time out of all the processes and so on. If two or more than two processes share the same CPU burst time then First Come First Serve [FCFS] scheduling is used to solve the conflict between those processes.

SJF scheduling can be done in both ways,

• Nonpreemptive -
  In Nonpreemptive SJF scheduling algorithm, Once the CPU has been allocated to a process It cannot jump from current process to another. Firstly it must completely finish the execution of the current process then only it can be allocated to some other processes.
• Preemptive -
  In Preemptive SJF, Even if the CPU is allocated to a process say "A", It can jump from "A" to some other process "B" if the CPU burst time of "B" is smaller than that of the process "A".

Shortest Job First [SJF] process scheduling algorithm is much more Optimal and gives the Minimum Average Waiting Time as compared to FCFS and other process scheduling algorithms. Because executing a smaller process before the larger one decreases the waiting time for smaller process much more than it increases the waiting time of larger process. Hence, the average waiting time decreases.

In this article we will be only sharing Nonpreemptive SJF program.

Shortest Job First Process Scheduling Program

Below is the program for SJF process scheduling with Gantt Chart in C,

//This is a Program for Shortest Job First Process Scheduling by [C] Lectures.
#include<stdio.h>
#include<graphics.h>
#include<dos.h>
#include<conio.h>
void main()
{
    int no,i,j,sum=0,position,temp,temp1=0,temp2=0,temp_tat=0,temp_wt=0;
    int cpuburst[10],process[10],avg_waiting_time=0,avg_turnaround_time=0;
    int gdriver = DETECT, gmode;
    initgraph(&gdriver,&gmode,"C:\\TC\\BGI ");
    clrscr();
    printf("\nShortest Job First Process Scheduling : ");
    printf("\nEnter the number of Processes : ");
    scanf("%d",&no);
    for(i=1;i<=no;i++)
    {
        process[i]=i;
        printf("\nEnter CPU Burst time for process P%d : ",i);
        scanf("%d",&cpuburst[i]);
    }
    cpuburst[0]=0;
    for(i=1;i<=no;i++)
    {
        position=i;
        for(j=i+1;j<=no;j++)
        {
            if(cpuburst[j]<cpuburst[position])
                position=j;
        }
        temp=cpuburst[i];
        cpuburst[i]=cpuburst[position];
        cpuburst[position]=temp;
        temp=process[i];
        process[i]=process[position];
        process[position]=temp;
    }
    for(i=1;i<=no;i++)
    {
        sum += cpuburst[i];
        avg_waiting_time += cpuburst[i-1];
        avg_turnaround_time += cpuburst[i];
        temp_wt=0;
        temp_tat=0;
        for(j=1;j<i;j++)
        {
            temp_tat += cpuburst[j];
            temp_wt += cpuburst[j-1];
        }
        printf("\nWaiting time for process P%d : %d",process[i],cpuburst[i-1]+temp_wt);
        printf("\nTurn around time for process P%d : %d \n",process[i],cpuburst[i]+temp_tat);
        avg_turnaround_time += temp_tat;
        avg_waiting_time += temp_wt;
    }
    printf("\n\nAverage waiting time : %d",avg_waiting_time/no);
    printf("\nAverage turn around time : %d",avg_turnaround_time/no);
    outtextxy(80,460,"Do Not Press Any Key! This screen will be cleared automatically in 10s.");
    delay(10000);
    cleardevice();
    line(100,100,100,150);
    line(100,100,100+(sum*10),100);
    line(100+(sum*10),100,100+(sum*10),150);
    line(100,150,100+(sum*10),150);
    for(i=1;i<no;i++)
    {
        temp1 = cpuburst[i];
        temp2 += temp1;
        line(100+(temp2*10),100,100+(temp2*10),150);
    }
    getch();
    closegraph();
}

Output of the Program

There will be two output screens for our program, In first screen we will give our inputs to the program and it will print out the waiting time & turn around time for all the process individually and also the average waiting time and average turnaround time of the processes. And in the second output screen we will get the Gantt chart of our inputs.

Now let us check the validity of our program to see if the output calculated by our program is same as the manually calculated output,
Suppose there are 4 processes P1, P2, P3 and P4.
Assuming that all the four process arrived at 0ms, So the Arrival time for all the process is 0ms.

The CPU burst time for process P1 is 9ms,
The CPU burst time for process P2 is 3ms,

The CPU burst time for process P3 is 6ms,

The CPU burst time for process P4 is 5ms.

As the CPU burst time of process P2 is smaller than that of all the other processes, the CPU will be allocated to P2. Hence, the Waiting time for process P2 will be 0ms

After the process P2 has been completely executed then the CPU will be allocated to the next smallest process P4 which has CPU burst time of 5ms. Hence, the Waiting time for process P4 will be 3ms

After executing process P2 and P4 the CPU will be then allocated to the next smallest process P3 which has the CPU burst time of 6ms. Hence, the Waiting time for process P3 will be equals to 3ms + 5ms = 8ms

Now at last the CPU will be allocated to process P1 which has the largest CPU burst time of all the other process. The Waiting time for process P1 will be 3ms + 5ms + 6ms = 14ms

The Average Waiting Time = (0ms + 3ms + 8ms + 14ms)/4 = 6ms

Now for Turn around time, As we know that the process P2 has the smallest CPU burst time i.e 3ms so the CPU will be allocated to process P2. Hence, the Turn around time for P2 = 3ms

After the process P2 as been executed completely, the CPU will be then allocated to process P4 which has the CPU burst time of 5ms. So, the Turn around time for process P4 = 3ms + 5ms = 8ms

Now the CPU will be allocated to process P3 as it has the smallest CPU burst time i.e 6ms as compared to P1. So, the Turn around time for P3 = 3ms + 5ms + 6ms = 14ms

At last the CPU will be allocated to process P1 which has the largest CPU burst time of all the process i.e 9ms. So, the Turn around time for process P1 = 3ms + 5ms + 6ms + 9ms = 23ms

The Average Turn Around Time = (3ms + 8ms + 14ms + 23ms)/4 = 12ms

Download Source Code from Here.