Simple Near-Optimal Scheduling for the M/G/1

被引：0

作者：

Scully Z. ^{[1
]}

Harchol-Balter M. ^{[1
]}

Scheller-Wolf A. ^{[1
]}

机构：

[1] Carnegie Mellon University, Pittsburgh, PA

来源：

Performance Evaluation Review | 2020年 / 48卷 / 01期

基金：

美国国家科学基金会;

关键词：

approximation ratio; foreground-background (fb); gittins policy; latency; M/G/1; multilevel processor sharing (mlps); response time; shortest expected remaining processing time (serpt); monotonic serpt (mserpt); shortest remaining processing time (srpt); sojourn time;

D O I：

10.1145/3393691.3394216

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

We consider the problem of preemptively scheduling jobs to minimize mean response time of an M/G/1 queue. When we know each job's size, the shortest remaining processing time (SRPT) policy is optimal. Unfortunately, in many settings we do not have access to each job's size. Instead, we know only the job size distribution. In this setting the Gittins policy is known to minimize mean response time, but its complex priority structure can be computationally intractable. A much simpler alternative to Gittins is the shortest expected remaining processing time (SERPT) policy. While SERPT is a natural extension of SRPT to unknown job sizes, it is unknown whether or not SERPT is close to optimal for mean response time. © 2020 Copyright is held by the owner/author(s).

引用

页码：37 / 38

页数：1