Exponential averaging for SJF CPU scheduling

Problem Detail: 

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$.

Asked By : Utkal Sinha

Answered By : Rick Decker

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/19911