Appications of SRPT Scheduling with Inaccurate Information

The Shortest Remaining Processing Time (SRPT) scheduling policy was proven, in the 1960s, to yield the smallest mean response time, and recently it was proven its performance gain over Processor Sharing (PS) usu- ally does not come at the expense of large jobs. How- ever, despite the many advantages of SRPT scheduling, it is not widely applied. One important reason for the spo- radic application of SRPT scheduling is that accurate job size information is often unavailable. Our previ- ous work addressed the performance and fairness issues of SRPT scheduling when job size information is inaccu- rate. We found that SRPT (and FSP) scheduling outper- forms PS as long as there exists a (rather small) amount of correlation between the estimated job size and the ac- tual job size. In the work we summarize here, we have developed job size estimation techniques to support the ap- plication of SRPT to web server and Peer-to-Peer server side scheduling. We have evaluated our techniques with ex- tensive simulation studies and real world implementation and measurement.