SJF | |
Advantages | Disadvantages |
|
|
Solution:
OS may not know the length of the next burst time, but OS may be able to predict the burst time of processes to implement the SJF scheduling algorithm.
Prediction techniques | |
Static | Dynamic |
1. Process Size 2. Process type | 1. Simple Averaging 2. Exponential Averaging |
Static
(i) Process Size (Bytes):
Burst time of the new process can be predicted from the old process with a similar size.
(ii) Process Type:
As per the process type, the operating system can predict the burst time of the new process.
Dynamic:
(i) Simple Averaging:
This is a simple method to predict the burst time of a new process by calculating the average of all burst time of the completion process.
(ii) Exponential Average:
The next burst is generally predicted as an exponential average of CPU the measured lengths of the previous burst CPU. We can define the exponential average with the following formula. Let be the length of the nth CPU burst, and let be our predicted value for the next CPU burst. Then, for α, 0 ≤ α ≤1, define
The value of contains our most recent information, while stores the past history. The parameter α controls the relative weight of recent and past history in our prediction. If α = 0, then , and recent history has no effect (current conditions are assumed to be transient). If α = 1, then and only the most recent burst matters (history is assumed to be old and irrelevant). More commonly, α = 1/2, so recent history and past history are equally weighted. The initial can be defined as a constant or as an overall system average. In our example below, an exponential average with 1/2 and = 10. To understand the behavior of the exponential average, we can expand the formula for by substituting for to find
Example:
= processor execution time for instance of this process (total execution time for the batch process (job); processor burst time for the interactive job).
= Predicted value for the instance.
= Predicted value for the first instance; not calculate
Actual Burst Time () = (6, 4, 6, 4, 13, 13, 13)
Then = ?
Answer:
But Practically SJF is not used and the Round Robin Scheduling algorithm is the most practical.