EUVIMEDEUVIMED entdecken
Crossref

Strongly Tail-Optimal Scheduling in the Light-Tailed M/G/1

George Yu, Ziv Scully

Proceedings of the ACM on Measurement and Analysis of Computing Systems · 21.05.2024 · 8 (2) · 1-33

DOI: 10.1145/3656011 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the ACM on Measurement and Analysis of Computing Systems, online erschienen am 29.05.2024. Verfasst von George Yu und 1 weiteren Autor:innen. Die Arbeit wurde bisher 11-mal zitiert (Crossref) und nennt 48 Literaturangaben. Gefördert von: National Science Foundation.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We study the problem of scheduling jobs in a queueing system, specifically an M/G/1 with light-tailed job sizes, to asymptotically optimize the response time tail. This means scheduling to make \mathbfP [T > t], the chance a job's response time exceeds t, decay as quickly as possible in the t \to \infty limit. For some time, the best known policy was First-Come First-Served (FCFS), which has an asymptotically exponential tail: \mathbfP [T > t] \sim C e^-γ t . FCFS achieves the optimal *decay rate* γ, but its *tail constant* C is suboptimal. Only recently have policies that improve upon FCFS's tail constant been discovered. But it is unknown what the optimal tail constant is, let alone what policy might achieve it. In this paper, we derive a closed-form expression for the optimal tail constant C, and we introduce *γ-Boost*, a new policy that achieves this optimal tail constant. Roughly speaking, γ-Boost operates similarly to FCFS, but it pretends that small jobs arrive earlier than their true arrival times. This significantly reduces the response time of small jobs without unduly delaying large jobs, improving upon FCFS's tail constant by up to 50% with only moderate job size variability, with even larger improvements for higher variability. While these results are for systems with full job size information, we also introduce and analyze a version of γ-Boost that works in settings with partial job size information, showing it too achieves significant gains over FCFS. Finally, we show via simulation that γ-Boost has excellent practical performance.

Förderung

  • National Science Foundation

Zitieren

APA

Yu, G., & Scully, Z. (2024). Strongly Tail-Optimal Scheduling in the Light-Tailed M/G/1. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 8(2), 1-33. https://doi.org/10.1145/3656011

Vancouver

Yu G, Scully Z. Strongly Tail-Optimal Scheduling in the Light-Tailed M/G/1. Proceedings of the ACM on Measurement and Analysis of Computing Systems. 2024;8(2):1-33. doi:10.1145/3656011

BibTeX
@article{Yu2024,
  author = {Yu, George and Scully, Ziv},
  title = {Strongly Tail-Optimal Scheduling in the Light-Tailed M/G/1},
  journal = {Proceedings of the ACM on Measurement and Analysis of Computing Systems},
  year = {2024},
  volume = {8},
  number = {2},
  pages = {1--33},
  doi = {10.1145/3656011}
}
Kostenlos starten →