Reproduce “Priority Scheduling in the M/G/1 with Preemption Overhead” on OpenResearch

About this paper

Shefali Ramakrishna, Edwin Peng, Ziv Scully

Researchers at Cornell University and Akuna Capital developed an analytical framework for M/G/1 queues with class-based preemptive priority, incorporating stochastic preemption overhead, to derive the response time distribution. The framework, centered on the new "job joint transform," provides recursive formulas for the Laplace-Stieltjes transform of response times, offering exact performance analysis for systems with preemption costs.

Key insights

• Preemption overhead introduces a 'two-way' dependency where a job's effective service time increases due to overheads, which in turn can lead to more arrivals and subsequent preemptions, further extending service time.
• The stability of such a system is determined by the total effective load, $ ho = extstyle\sum_{k=1}^n \lambda_k E[R_k] < 1$, where $E[R_k]$ explicitly incorporates the expected duration of all associated preemption overheads.
• The M/G/1/setup queue model provides an effective decomposition strategy for analyzing response times in preemptive priority systems with overhead by considering superjobs and extra work accumulated before a job begins service.

Summary by alphaXiv.