Size-based Scheduling Policies with Inaccurate Scheduling Information

Dong Lu, Huanyuan Sheng, Peter A Dinda

Research output: Chapter in Book/Report/Conference proceedingConference contribution

30 Scopus citations

Abstract

Size-based scheduling policies such as SRPT have been studied since 1960s and have been applied in various arenas 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. In this paper, we study the performance of SRPT and FSP as a function of the correlation coefficient between the actual job sizes and estimated job sizes. We developed a simulator that supports both M/G/1/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 will make both SRPT and FSP outperform PS in both mean response time and slowdown.

Original languageEnglish (US)
Title of host publicationProceedings - IEEE Computer Society's 12th Annual International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunications Systems, MASCOTS 2004
EditorsD. DeGroot, P. Harrison
Pages31-38
Number of pages8
DOIs
StatePublished - 2004
EventProceedings - IEEE Computer Society's 12th Annual International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunications Systems, MASCOTS 2004 - Volendam, Netherlands
Duration: Oct 4 2004Oct 8 2004

Publication series

NameProceedings - IEEE Computer Society's Annual International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunications Systems, MASCOTS
ISSN (Print)1526-7539

Other

OtherProceedings - IEEE Computer Society's 12th Annual International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunications Systems, MASCOTS 2004
CountryNetherlands
CityVolendam
Period10/4/0410/8/04

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint Dive into the research topics of 'Size-based Scheduling Policies with Inaccurate Scheduling Information'. Together they form a unique fingerprint.

Cite this