Proof that Shortest Job First (SJF) Algorithm is Most Optimal

Shortest Job First (SJF) Algorithm is a scheduling algorithm where the idea is that the process with the shortest execution time should be processed first. SJF algorithm is the most optimal CPU scheduling algorithm and we have proved this mathematically in this article at OpenGenus.

Proof

Note the following terminologies:

• There are N processes
• t_k is the execution time of process k
• W_k is the waiting time of process k
• Let the set S of N processes be ordered {1, 2, ..., N} in increasing order of execution time.

As process k is executed just after process k-1, we can conclude:

W_k = W_k-1 + t_k-1 [Equation 1]

Note waiting time of first process is 0. W₁ = 0.

The total waiting time across N processes of set S be:

W_S = (W₁ + W₂ + ... + W_n) / N [Equation 2]

If we replace Equation 1 in Equation 2, we get:

W_S = (n-1)t₁ + (n-2)t₂ + ... + (n-k)t_k + ... + t_n-1 [Equation 3]

Now, if we select 2 processes randomly say process K-J and K such that the execution time of process K > execution time of process K-J.

If we swap these 2 processes and calculate the new waiting time, we get W_S1.

W_S1 = (n-1)t₁ + ... + (n-K+J)t_K + ... + (n-K)t_K-J + (n-k)t_k + ... + t_n-1 [Equation 3]

If we subtract Equation 4 from Equation 3, we get:

W_S - W_S1 = ((n-K+J)t_K-J + (n-K)t_K) - ((n-K+J)t_K + (n-K)t_K-J)

W_S - W_S1 = (-J) * t_K-J + (-J) t_K

So, W_S - W_S1 < 0

Therefore, W_S < W_S1

Hence, we can conclude that if we swap any two process in this ordered set required by SJF algorithm, the total / average waiting time increases.

Hence, we have mathematically proved that Shortest Job First (SJF) Algorithm is Most Optimal Scheduling algorithm.

Conclusion

Shortest Job First (SJF) Algorithm is Most Optimal Scheduling algorithm. We have presented the mathematical proof in this article at OpenGenus. You can apply the same concepts to mathematically analyze other scheduling algorithms.

Although SJF algorithm is most optimal, it presents some practical challenges to be implemented in real systems:

• The execution time of processes is not known beforehand. For specific systems, execution time can be predicted.
• Real time systems are dynamic that is the list of processes keep changing. In this case, the process that takes significantly long time to execute will keep getting delayed and may not get executed ever. Such systems are prone to attacks.

Choose your scheduling algorithm wisely.