Title :
Quantifying the properties of SRPT scheduling
Author :
Gong, Mingwei ; Williamson, Carey
Author_Institution :
Dept. of Comput. Sci., Calgary Univ., Alta., Canada
Abstract :
This paper uses a probe-based sampling approach to study the behavioural properties of Web server scheduling strategies, such as processor sharing (PS) and shortest remaining processing time (SRPT). The approach is general purpose, in that it can be used to estimate the mean and variance of the job response time, for arbitrary arrival processes, service time distributions, and scheduling policies. In the paper, we apply the approach to trace-driven simulation of Web server scheduling to compare and contrast the PS and SRPT scheduling policies. We identify two types of unfairness, called endogenous and exogenous unfairness. We quantify each, focusing on the mean and variance of slowdown, conditioned on job size, for a range of system loads. Finally, we confirm recent theoretical results regarding the asymptotic convergence of scheduling policies with respect to slowdown, and illustrate typical performance results for a practical range of job sizes from an empirical Web server workload.
Keywords :
Internet; convergence; processor scheduling; sampling methods; Web server scheduling strategies; asymptotic convergence; endogenous unfairness; exogenous unfairness; job response time; probe-based sampling approach; processor sharing; scheduling policies; service time distributions; shortest remaining processing time scheduling; Computational modeling; Computer science; Convergence; Delay systems; Performance analysis; Processor scheduling; Robustness; Sampling methods; Switches; Web server;
Conference_Titel :
Modeling, Analysis and Simulation of Computer Telecommunications Systems, 2003. MASCOTS 2003. 11th IEEE/ACM International Symposium on
Print_ISBN :
0-7695-2039-1
DOI :
10.1109/MASCOT.2003.1240650