SJF is a scheduling algorithm that assigns to each process the length of its next CPU burst/execution time. CPU is then given to the process with the minimal CPU burst from the waiting queue. SJF is provably optimal, in that for a given set of processes and their CPU bursts/execution times it gives the least average waiting time for each process. The average waiting time for a process is defined by:

W_{S}=(W_{1}+W_{2}+...+W_{n})/n [1],
where W_{k}=W_{k-1}+t_{k-1} [2] is the waiting time for
a k^{th} process and t_{i} is the execution time/length of next CPU burst
of the i^{th} process; 1<= k, i <=n (actually, the execution time of the last
process in the queue, t_{n}, does not affect any waiting times), and W_{0}=0.

If we replace [2] into [1], we get:
W_{S}=((n-1)t_{1}+(n-2)t_{2}+...+(n-k)t_{k}+...
+t_{n-1})/n [3]

Now let us suppose that we have an arbitrary set of *n* CPU bursts,
{ t_{1}, t_{2}, ... , t_{n} }.

The average process waiting time in such a set is given by [3].
If we take from that set two processes, *k-j* and *k*, such that t_{k-j}>t_{k}
, *k*>*j* and switch them, the new average waiting time is:

W_{S1}=((n-1)t_{1}+...+(n-k+j)t_{k}+...
+(n-k)t_{k-j}+...+t_{n-1})/n [4]

If we subtract [4] from [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})/n =
j(t_{k-j}-t_{k})/n > 0,
therefore W_{S1} < W_{S}.

By repeating the process over and over and putting shorter jobs in front of longer ones, we will eventually completely order the starting set and achieve the minimal average waiting time:

W_{Sof ordered set}<...<W_{S1}<
W_{S}. Since we started with an arbitrary set, this completes this short and simple optimality proof of the SJF.

The main drawback of the SJF alogrithm is that, of course, in modern operating system enviroments we cannot precisely determine the length of the process' next CPU burst. We can at best approximate it, and that only by a certain degree and in certain conditions.

*Andrej Blagojevic,
Computer Science and Engineering student,
School of Electrical Engineering,
University of Belgrade, Serbia. *

Back