Non-Preemptive Shortest Job First Scheduling

Shortest Job First is another type of scheduling technique in which the process with the shortest burst time is given to CPU first for execution. SJF scheduling is a non - preemptive scheduling technique.

Characteristics of SJF algorithm

• The average waiting time by using SJF is less than FCFS.
• Since processes with shorter burst time is executed first hence the turnaround time is also short by using SJF.
• SJF gives an improved output by selecting a shorter job first to execute.
• This scheduling technique is useful for batch-time processing, where waiting for jobs to complete is not critical.

Drawbacks of Non-Preemptive Shortest Job First Scheduling

One major drawback of SJF non-preemptive version is:
If all processes arrive in ready queue at different time, then there might be a chance that a process with short burst time have to wait for the current process's execution to finish. This is because when a process with shorter burst time comes then the existing job is stopped to execute and the shorter process is given to CPU.
This can lead to a serious problem also known as Starvation that a process is never getting executed because every time a process with shorter burst time comes and obstructs this process to get CPU.
To resolve this problem we have a concept of Ageing. In ageing we assign a priority to each process and this priority is increased as a process is starved more and more and then after some time interval
we check the priority of the processes and the process with highest priority is given CPU.

Numerical:

-->Given the processes below draw a gantt chart for the execution if processes using SJF and find waiting time as well as turn around time for each process.

P1 is the first process to arrive in the ready queue with arrival time of 0 so it will be executed first for complete 4ms.
Now, the process with the shortest burst time will be executed first. Since P3 has the shortest burst time thus it will be executed for 1ms.
The next process with the shortest burst time is P4 which will execute for 2ms.
The next process with the shortest burst time is P2 so it will execute for 3ms.
Now, the last process P5 will be executed for 6ms.
The gantt chart for the table is:

Waiting Time for each Process

Waiting time is computed by the formula starting execution time - arrival time of a process.
Process                                  Starting execution time - arrival time                          Waiting time
P1                                                            0 - 0                                                                  0
P2                                                            7 - 1                                                                  6
P3                                                            4 - 2                                                                  2
P4                                                            5 - 3                                                                  2
P5                                                           10 - 4                                                                 6

Turn around Time for each Process

Turn around time is computed by the formula completion time - arrival time of a process.
Process                                  Completion time - arrival time                          Waiting time
P1                                                            4 - 0                                                                  4
P2                                                          10 - 1                                                                  9
P3                                                            5 - 2                                                                  3
P4                                                            7 - 3                                                                  4
P5                                                          16 - 4                                                                 12

Implementation of SJF in C++

// C++ program to implement Shortest Job first with Arrival Time #include<iostream> using namespace std; int mat[10][6]; void swap(int *a, int *b) { int temp = *a; *a = *b; *b = temp; } void arrangeArrival(int num, int mat[][6]) { for(int i=0; i<num; i++) { for(int j=0; j<num-i-1; j++) { if(mat[j][1] > mat[j+1][1]) { for(int k=0; k<5; k++) { swap(mat[j][k], mat[j+1][k]); } } } } } void completionTime(int num, int mat[][6]) { int temp, val; mat[0][3] = mat[0][1] + mat[0][2]; mat[0][5] = mat[0][3] - mat[0][1]; mat[0][4] = mat[0][5] - mat[0][2]; for(int i=1; i<num; i++) { temp = mat[i-1][3]; int low = mat[i][2]; for(int j=i; j<num; j++) { if(temp >= mat[j][1] && low >= mat[j][2]) { low = mat[j][2]; val = j; } } mat[val][3] = temp + mat[val][2]; mat[val][5] = mat[val][3] - mat[val][1]; mat[val][4] = mat[val][5] - mat[val][2]; for(int k=0; k<6; k++) { swap(mat[val][k], mat[i][k]); } } } int main() { int num, temp; cout<<"Enter number of Process: "; cin>>num; cout<<"...Enter the process ID...\n"; for(int i=0; i<num; i++) { cout<<"...Process "<<i+1<<"...\n"; cout<<"Enter Process Id: "; cin>>mat[i][0]; cout<<"Enter Arrival Time: "; cin>>mat[i][1]; cout<<"Enter Burst Time: "; cin>>mat[i][2]; } cout<<"Before Arrange...\n"; cout<<"Process ID\tArrival Time\tBurst Time\n"; for(int i=0; i<num; i++) { cout<<mat[i][0]<<"\t\t"<<mat[i][1]<<"\t\t"<<mat[i][2]<<"\n"; } arrangeArrival(num, mat); completionTime(num, mat); cout<<"Final Result...\n"; cout<<"Process ID\tArrival Time\tBurst Time\tWaiting Time\tTurnaround Time\n"; for(int i=0; i<num; i++) { cout<<mat[i][0]<<"\t\t"<<mat[i][1]<<"\t\t"<<mat[i][2]<<"\t\t"<<mat[i][4]<<"\t\t"<<mat[i][5]<<"\n"; } }

OUTPUT:

Here you can follow me if you are interested:

https://github.com/mayank171

https://www.linkedin.com/in/mayank-mewar-586090173/