Question

The SRPT scheduling policy is important because it minimizes mean response time. Runting suggests that the problem with SRPT is that it picks jobs with the shortest remaining time, whereas to minimize mean slowdown we want to choose jobs that have both short remaining time and also small original size. Runting proposes that we use the RS algorithm, which computes the product of a job's current remaining size (R) and its (original) size (S), and then runs that job whose product (RS) is smallest. Is Runting right?

(a) Explain the intuition behind the RS algorithm for minimizing mean slowdown.

(b) Prove or disprove that the RS algorithm minimizes mean slowdown on every arrival sequence. If it minimizes mean slowdown, provide a proof. If it does not minimize mean slowdown, provide a counterexample.

RS is also known as SPTP.

Answer 1

Solution: a) . The shortest remaining time algorithm will choose the process that has shortest remaining time to execute next. . The SRPT approach will results in the late execution of processes that has longer . Thus theprocess with larger reaming time will results in larger execution time plus the . The RS algorithm consider the remaining time alongwiththe real size remaining execution time waiting time that will contribute higher average time. This the process with shortest product of real size and remaining size will execute first. The mean waiting time is the mean time of process slow down Thus the RS algorithm will minimize the mean slowdown by finishing smaller process first rather than finishing lower remaining time processes first But the RS algorithm will not work on every sequence

b) RS algorithm will not work on every arrival sequence. Counter example: Let the arriving sequence be 10(5),20(4), 30(10) where numberin parenthesis is the remaining time and the other value is the real size of the processor. If the SRPT algorithm is occurred, theserving sequence will be 20(4), 10(5) and 30(10). This will results in a waiting time of "0" for process "20", "4" for process "10" and"9" for process "30", in average 13/3. If RS scheduling is taken, the serving sequence will be 10(5), 20(4), 30(10) the waiting time will be 0, 5 and 9 resulting mean slowdown of 14/3 o o o o Thus RS algorithm is not works on every arrival sequence