The SJF scheduling algorithm is probably optimal, in that it provides the minimum average waiting time for a given set of processes. Moving short processes before a long one reduces the waiting time of the short process more than it creases the waiting time of the long process so consequently, the average waiting time decreases. The real problem with the SJF algorithm knows the length of the next CPU request.
- For long-term (job) scheduling in a batch system, we can use as the length the process time limit that a user specifies when he submits the job.
- Thus, users are motivated to estimate the process time limit accurately, since a lower value may mean faster response. (Too low a value will cause a time-limit-exceeded error and require resubmission.)
- SJF scheduling is used frequently in long-term scheduling.
- Although the SJF algorithm is optimal, it cannot be implemented at the level of short-term CPU scheduling.
- With short-term scheduling, there is no way to know the length of the next CPU burst.
- One approach is to try to approximate SJF scheduling.
- We may not know the length of the next CPU burst, but we may be able to predict its value.
- We expect that the next CPU burst will be similar in length to the previous ones.
- By computing an approximation of the length of the next CPU burst, we can pick the process with the shortest predicted CPU burst.
- The next CPU burst is generally predicted as an exponential average of the measured lengths of previous CPU bursts. We can define the exponential average with the following formula.
τn+1 = α*tn + (1 - α)*τ
