Shortest Job First scheduling with predicted burst time

Shortest Job First (SJF) is an optimal scheduling algorithm as it gives maximum Throughput and minimum average waiting time(WT) and turn around time (TAT) but it is not practically implementable because Burst-Time of a process can’t be predicted in advance.

We may not know the length of the next CPU burst, but we may be able to predict its value. We expect 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.

There are two methods by which we can predict the burst time of the process :

1. Static method – We can predict the Burst-Time by two factors :

§  Process size

Let say we have Process P_old having size 200 KB which is already executed and its Burst-time is 20 Units of time, now lets say we have a New Process P_new having size 201 KB which is yet to be executed.
We take Burst-Time of already executed process P_old which is almost of same size as that of New process as Burst-Time of New Process P_new.

§  Process type

We can predict Burst-Time depending on the Type of Process. Operating System process(like scheduler, dispatcher, segmentation, fragmentation) are faster than User process( Gaming, application softwares ). Burst-Time for any New O.S process can be predicted from any old O.S process of similar type and same for User process.

Note – Static method for burst time prediction is not reliable as it is always not predicted correctly.

2. Dynamic method – Let t_i be the actual Burst-Time of i^th process and Τ_n+1 be the predicted Burst-time for n+1^th process.

§  Simple average – Given n processes ( P₁, P₂… P_n)

Τ_n+1 = 1/n(Σ^{i=1 to n} t_i)

§  Exponential average (Aging) –

Τ_n+1 = αt_n + (1 - α)Τ_n

where α = is smoothing factor and 0 <= α <= 1 ,

t_n = actual burst time of n^th process,

Τ_n = predicted burst time of n^th process.

General term,

αt_n + (1 - α)αt_n-1 + (1 - α)²αt_n-2...+ (1 - α)^jαt_n-j...+ (1 - α)ⁿ⁺¹Τ₀

Τ₀ is a constant or overall system average.

Smoothening factor (α) – It controls the relative weight of recent and past history in our prediction.

§  If α = 0, Τⁿ⁺¹ = Τⁿ i.e. no change in value of initial predicted burst time.

§  If α = 1, Τⁿ⁺¹ = tⁿ i.e. predicted Burst-Time of new process will always change according to actual      Burst-time of n^th process.

§  If α = 1/2, recent and past history are equally weighted.

Example –

Calculate the exponential averaging with T1 = 10, α = 0.5 and the algorithm is SJF with previous runs as 8, 7, 4, 16.

(a) 9

(b) 8

(c) 7.5

(d) None

Explanation :

Initially T1 = 10 and α = 0.5 and the run times given are 8, 7, 4, 16 as it is shortest job first,
So the possible order in which these processes would serve will be 4, 7, 8, 16 since SJF is a non-preemptive technique.

So, using formula: T2 = α*t1 + (1-α)T1

so we have,

T2 = 0.5*4 + 0.5*10 = 7, here t1 = 4 and T1 = 10

T3 = 0.5*7 + 0.5*7 = 7, here t1 = 7 and T1 = 7

T4 = 0.5*8 + 0.5*7 = 7.5, here t1 = 8 and T1 = 7

So the future prediction for 4th process will be T4 = 7.5 which is the option(c).