CPU Scheduling

Question

Common data

Consider the foloowing 4 processes that arrive at time 0 with the length of CPU burst time given as follows

PROCESS| BURST TIME

P1                     5

P2                     8

P3                     3

P4                     5

QUS1.  If Ʈ₁ is 10 and the parameter that controls the relative weight of recent and past history (α)=0.5, then what is the expected burst time of process P5 if it is SJF scheduling?

a)5.1875

b)4.8132

c)5.625

d) none of these

QUS 2. if the parameter that controls the relative weight of recent and past history is unity, then what is the expected burst time of process P5?

)4

b)3

c)5

d)4.5

Answer 1

Ans of first Ques. is a

as  T2=0.5*5 + (1-0.5)10=7.5

       T3=0.5*8+0.5*T2

        T4=0.53+0.5*T3=5.375

T5=5.1875

explanation :here we have to assume what will be the next burst time from available data so process given burst time in question  is hidden to us . and by applying aging formula we have to measure the respective burst time .

and yes ans of second question is c as alpha is 1 so T5=t4.

Answer 2

#ANS1.  (D) none of these

u took P2 twice in the quesn i am considering 
 

P1                     5

P2                     8

P3                     3

P4                     5

Since  it is SJF scheduling . the process will execute in following manner
p3->p1->p4->p2

so this is the problem of exponential avearge or it is also called 'Aging" problem.

Ʈ₁= 10
so according to the formula of exponential average,
Ʈ_n=α*t_n-1 +(1-α)Ʈn-1  where t_n-1 = process burst time
Since  it is SJF scheduling . the process will execute in following manner
p3->p1->p4->p2
so the burst time will be available in following manner
t1=3,t2=5,t3=5,t4=8

Ʈ₂₌ (0.5)*3 + (1-0.5)10     [t₁₌3  because  1st p3 will execute and its burst time =3(given) ]
Ʈ_{2=6.5
similarly}
Ʈ₃=0.5*5+(0.5*6.5)
Since  it is SJF scheduling . the process will execute in following manner
Ʈ_{3=5.75
similarly}
Ʈ₄₌5.75
Ʈ₄=5.375
Ʈ₅=  6.6875
it doesnt match any options so D should be the right choice.
FOR ans 2 
alpha is 1

when α=1, then Ʈ_n=t_n-1 

So, Ʈ₅= t₄=8....... 

because If alpha is 1.0, then past history is ignored, and we assume the next burst will be the same length as the last burst.  so the options are wrong and answer should be 8.

Comments

For question 2.............

Ʈ_n=α*t_n-1 +(1-α)Ʈn-1 

when α=1, then Ʈ_n=t_n-1 

So, Ʈ₅= t₄=8....... 

because If alpha is 1.0, then past history is ignored, and we assume the next burst will be the same length as the last burst. 

Source :https://www.cs.uic.edu/~jbell/CourseNotes/OperatingSystems/5_CPU_Scheduling.html

---

thanks vasu.. updated my soln

---

I have one more doubt....it is not mentioned that P5 will execute after 4 processes only.....it is shortest job first so P5 can execute before any other process it P5 have lower BT.........so why process P5 execute after 4 processes....

Answer key given is (a) 5.1875 for question 1

                             (c) 5 for question 2

---

see its just a prediction which is based on the previous history and so using only this formula we can predict that P5 will execute after P4.. theres nothing more given in book "galvin".