Question

*** ANSWER MUST RELATE TO LITTLE'S LAW AND THE TEXTBOOK (PERFORMANCE MODELING AND DESIGN OF COMPUTER SYSTEMS QUEING THEORY MOR HARCHOL BALTER) **** 6.7 More on SRPT The SRPT scheduling policy is important because it minimizes mean response time. In Exercise 2.3, we saw that SRPT does not minimize mean slowdown. 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 and is analyzed in [100].

Answer 1