# Exponential averaging for SJF CPU scheduling

Calculate the exponential averaging with $T_1 = 10$, $\alpha=0.5$ and the algorithm is SJF with previous runs as $8,7,4,16$.

1. 9
2. 8
3. 7.5
4. None

I am getting 4. None as the answer.

But it is given that 3. 7.5 is the correct answer. I think I am missing something here.

Because I only used the formula, $S_{n + 1}{}{}{}{} = a(T_n) + (1-a)*S_n$.

• Perhaps you could tell us why SJF is (though it seems irrelevant to the solution) and what exponential averaging is. Also, it will be interesting to know what is being calculated in this question and why. – Yuval Filmus Jan 23 '14 at 13:41
• Yes, SJF is irrelevant to this question. And here Exponential averaging is used to predict the next CPU burst. – Utkal Sinha Jan 23 '14 at 13:52
• It pains me to see evidence of educators thinking MC is a good way to evaluate student performance. – Raphael Jan 23 '14 at 15:07
• @Raphael Perhaps they have no choice, not having enough TAs to grade actual assignments, nor enough time to do that themselves. – Yuval Filmus Jan 23 '14 at 19:07
• I made a slight edit to your post (the $S_{n+1}$ subscript). Check if that matches your intent and roll back if not. – Rick Decker Jan 24 '14 at 18:40

A possible interpretation of the problem is that we initially had jobs with actual run times 8, 7, 4, and 16. Assuming no new jobs entered the queue, we'd schedule then in increasing order of their times, namely 4, 7, 8, 16 (since that's what SJF means--shortest job first). Under these assumptions we'd have time slices \begin{align} T_2&=\frac{1}{2}(4+10)=7&\text{after the first job has run}\\ T_3&=\frac{1}{2}(7+7)=7&\text{after the second job has run}\\ T_4&=\frac{1}{2}(8+7)=7.5&\text{after the third job has run}\\ \end{align} so the fourth job would be given a slice of 7.5, which is choice (3).

This isn't an entirely satisfactory answer since of course the OS might not know how much time the jobs would actually take before hand, but if the problem assumed they'd be run in that order (4, 7, 8, 16) we'd have what was mentioned as the correct answer, so it's at least a possible interpretation.

Rick is right,
Initially tau$(Γ1)=10$ and $\alpha=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: $Γ 2$= $\alpha$$\cdot$T1 + (1-$\alpha$)$Γ 1$
so we have,
$Γ 2$=$0.5*4+0.5*10$ = $7$, here $T1=4$ and $Γ 1=10$
$Γ 3=0.5*7+0.5*7$ = $7$, here $T2=7$ and $Γ 2=7$
$Γ 4=0.5*8+0.5*7$= $7.5$, here $T3=8$ and $Γ 3=7$

So the future prediction for $4th$ process will be $Γ 4=7.5$ which is the option$(3)$,
This method of exponential averaging to find predicted future service time of a process is actually not in practical use as we can’t find the history of actual burst times before doing all this.

Initially T1 = 10 and α = 0.5 and the run times given are 8, 7, 4, 16

As it is shortest job first, 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).

• Use LaTex for better format of your answer. – Thinh D. Nguyen Sep 18 '18 at 8:52