The Gittins Policy is Nearly Optimal in the M/G/k under Extremely General Conditions
| Autor: | GrosofIsaac, ScullyZiv, Harchol-BalterMor |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
Computer Networks and Communications
Computer science 0211 other engineering and technologies Preemption Markov process 02 engineering and technology 01 natural sciences Scheduling (computing) Combinatorics 010104 statistics & probability symbols.namesake 0202 electrical engineering electronic engineering information engineering Computer Science (miscellaneous) Heavy traffic 0101 mathematics Safety Risk Reliability and Quality Queue Mathematics 021103 operations research Mean and predicted response 020206 networking & telecommunications Palm calculus Term (time) Distribution (mathematics) Hardware and Architecture symbols Software |
| Zdroj: | SIGMETRICS (Abstracts) |
| DOI: | 10.1145/3410220.3456281 |
| Popis: | The Gittins scheduling policy minimizes the mean response in the single-server M/G/1 queue in a wide variety of settings. Most famously, Gittins is optimal when preemption is allowed and service requirements are unknown but drawn from a known distribution. Gittins is also optimal much more generally, adapting to any amount of available information and any preemption restrictions. However, scheduling to minimize mean response time in a multiserver setting, specifically the central-queue M/G/k, is a much more difficult problem. In this work we give the first general analysis of Gittins in the M/G/k. Specifically, we show that under extremely general conditions, Gittins's mean response time in the M/G/k is at most its mean response time in the M/G/1 plus an O(log(1/(1 - ρ))) additive term, where ρ is the system load. A consequence of this result is that Gittins is heavy-traffic optimal in the M/G/k if the service requirement distribution S satisfies E[S2(log S)+] < ∞. This is the most general result on minimizing mean response time in the M/G/k to date. To prove our results, we combine properties of the Gittins policy and Palm calculus in a novel way. Notably, our technique overcomes the limitations of tagged job methods that were used in prior scheduling analyses. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|