Heavy-tailed limits for medium size jobs and comparison scheduling

DOI10.1007/S10479-008-0432-0zbMATH Open1169.90366arXiv0805.1968OpenAlexW2592596173MaRDI QIDQ839865FDOQ839865

Authors: Predrag R. Jelenković, Xiaozhu Kang, Jian Tan 

Publication date: 3 September 2009

Published in: Annals of Operations Research (Search for Journal in Brave)

Abstract: We study the conditional sojourn time distributions of processor sharing (PS), foreground background processor sharing (FBPS) and shortest remaining processing time first (SRPT) scheduling disciplines on an event where the job size of a customer arriving in stationarity is smaller than exactly k>=0 out of the preceding m>=k arrivals. Then, conditioning on the preceding event, the sojourn time distribution of this newly arriving customer behaves asymptotically the same as if the customer were served in isolation with a server of rate (1- ho)/(k+1) for PS/FBPS, and (1- ho) for SRPT, respectively, where ho is the traffic intensity. Hence, the introduced notion of conditional limits allows us to distinguish the asymptotic performance of the studied schedulers by showing that SRPT exhibits considerably better asymptotic behavior for relatively smaller jobs than PS/FBPS. Inspired by the preceding results, we propose an approximation to the SRPT discipline based on a novel adaptive job grouping mechanism that uses relative size comparison of a newly arriving job to the preceding m arrivals. Specifically, if the newly arriving job is smaller than k and larger than m-k of the previous m jobs, it is routed into class k. Then, the classes of smaller jobs are served with higher priorities using the static priority scheduling. The good performance of this mechanism, even for a small number of classes m+1, is demonstrated using the asymptotic queueing analysis under the heavy-tailed job requirements. We also discuss refinements of the comparison grouping mechanism that improve the accuracy of job classification at the expense of a small additional complexity.

Full work available at URL: https://arxiv.org/abs/0805.1968

Recommendations

• Preventing Large Sojourn Times Using SMART Scheduling
• Is tail-optimal scheduling possible?
• On the average sojourn time under \(M/M/1/\)SRPT
• Heavy traffic scaling limits for shortest remaining processing time queues with heavy tailed processing time distributions
• Queues with equally heavy sojourn time and service requirement distributions

zbMATH Keywords

fairnessheavy tailsscalabilityasymptotic analysisprocessor sharingM/G/1 queueadaptive thresholdscomparison schedulingforeground background processor sharingmedium size jobsshortest remaining processing time first

Mathematics Subject Classification ID

Stochastic scheduling theory in operations research (90B36)

Cites Work

• Letter to the Editor—A Proof of the Optimality of the Shortest Remaining Processing Time Discipline
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Sojourn time asymptotics in the \(M/G/1\) processor sharing queue
• On the exact asymptotics of the busy period in GI/G/1 queues
• Reduced-load equivalence and induced burstiness in GPS queues with long-tailed traffic flows
• On the tails of waiting-time distributions
• A large-deviations analysis of the GI/GI/1 SRPT queue
• Scheduling strategies and long-range dependence
• Subexponential asymptotics of a Markov-modulated random walk with queueing applications
• The Queue M/G/1 with the Shortest Remaining Processing Time Discipline
• Largest weighted delay first scheduling: Large deviations and optimality
• Large Deviation Analysis of Subexponential Waiting Times in a Processor-Sharing Queue
• Tail probabilities for non-standard risk and queueing processes with subexponential jumps
• Asymptotic loss probability in a finite buffer fluid queue with heterogeneous heavy-tailed on-off processes
• Preventing Large Sojourn Times Using SMART Scheduling
• Grouped distributed queues, distributed queue, proportional share multiprocessor scheduling
• Handling load with less stress

Cited In (2)

• Preventing Large Sojourn Times Using SMART Scheduling
• Is tail-optimal scheduling possible?

This page was built for publication: Heavy-tailed limits for medium size jobs and comparison scheduling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q839865)