Adaptive and scalable comparison scheduling

Abstract

The Shortest Remaining Processing Time (SRPT) scheduling disciplineis optimal and its superior performance, compared with the policies that do not use the knowledge of job sizes, can be quantified using mean-value analysis as well as our new a symptotic distribution allimits for the relatively smaller heavy-tailed jobs. However, the main difficulty in implementing SRPT in large practical systems, e.g., Web servers, is that its complexity grows with the number of jobs in the queue. Hence, in order to lower the complexity, it is natural to approximate SRPT by grouping the arrivals into a fixed (small) number of classes containing jobs of approximately equal size and then serve the classes of smaller jobs with higher priorities. In this paper, we design a novel adaptive grouping mechanism based on relative size comparison of a newly arriving job to the preceding m arrivals. Specifically, if the newly arriving job is smallerthan k and larger than m-k of the previous m jobs, it isrouted into class k. The excellent performance of this mechanism,even for a small number of classes m+1, is demonstrated using both the asymptotic queueing analysis under heavy tails and extensive simulations. We also discuss refinements of the comparison grouping mechanism that improve the accuracy of job classification at the expense of a small additional complexity.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 15 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.