Analysis of scheduling policies under correlated job sizes

作者：Gupta Varun^*; Burroughs Michelle; Harchol Balter Mor

来源：Performance Evaluation, 2010, 67(11): 996-1013.

DOI：10.1016/j.peva.2010.08.010

• Scheduling
• Correlation
• MMAP
• M/G/1
• Asymptotic analysis
• Fluid analysis

Correlations in traffic patterns are an important facet of the workloads faced by real systems and one that has far-reaching consequences on the performance and optimization of the systems involved However all the existing analytical work on understanding the effect of correlations between successive service requirements (job sizes) is limited to First-Come First-Served scheduling This leaves open fundamental questions How do various scheduling policies interact with correlated job sizes?, Can scheduling be used to mitigate the harmful effects of correlations?
In this paper we take the first step towards answering these questions Under a simple model for job size correlations we present the first asymptotic analysis of various common size-independent scheduling policies when the job size sequence exhibits high correlation Our analysis reveals that the characteristics of various scheduling policies as well as their performance relative to each other are markedly different under the assumption of job sizes versus correlated job sizes Further among the class of size-independent scheduling policies there is no single scheduling policy that is optimal for all degrees of correlations and thus any optimal policy must learn the correlations We support the asymptotic analysis with numerical algorithms for exact pe

• 出版日期2010-11