Title :
Size-based scheduling policies with inaccurate scheduling information
Author :
Lu, Dong ; Sheng, Huanyuan ; Dinda, Peter
Author_Institution :
Dept. of Comput. Sci., Northwestern Univ., Evanston, IL, USA
Abstract :
Size-based scheduling policies, such as shortest remaining processing time (SRPT), have been studied since the 1960s and have been applied in various areas, including packet networks and Web server scheduling. SRPT has been proven to be optimal in the sense that it yields - compared to any other conceivable strategy - the smallest mean value of occupancy and therefore also of waiting and delay time. One important prerequisite to applying size-based scheduling is to know the sizes of all jobs in advance, which are unfortunately not always available. No work has been done to study the performance of size-based scheduling policies when only inaccurate scheduling information is available. We study the performance of SRPT and fair sojourn protocol (FSP) as a function of the correlation coefficient between the actual job sizes and estimated job sizes. We have developed a simulator that supports both M/G/l/m and G/G/n/m queuing models. The simulator can be driven by trace data or synthetic data produced by a workload generator we have developed that allows us to control the correlation. The simulations show that the degree of correlation has a dramatic effect on the performance of SRPT and FSP, and that a reasonably good job size estimator makes both SRPT and FSP outperform processor sharing (PS) in both mean response time and slowdown.
Keywords :
delays; parameter estimation; queueing theory; scheduling; Web server scheduling; correlation coefficient; delay time; fair sojourn protocol; inaccurate scheduling information; packet networks; processor sharing; queuing models; queuing system; shortest remaining processing time; size-based scheduling policies; waiting time; workload generator; Computer network management; Computer science; Delay; Engineering management; Global Positioning System; Industrial engineering; Job shop scheduling; Processor scheduling; Time factors; Web server;
Conference_Titel :
Modeling, Analysis, and Simulation of Computer and Telecommunications Systems, 2004. (MASCOTS 2004). Proceedings. The IEEE Computer Society's 12th Annual International Symposium on
Print_ISBN :
0-7695-2251-3
DOI :
10.1109/MASCOT.2004.1348179