Multiprocessor scheduling by reduction to uniprocessor: an original optimal approach

被引：0

作者：

Paul Regnier

George Lima

Ernesto Massa

Greg Levin

Scott Brandt

机构：

[1] Federal University of Bahia,

[2] State University of Bahia,undefined

[3] University of California,undefined

来源：

Real-Time Systems | 2013年 / 49卷

关键词：

Real-time; Multiprocessor; Scheduling; Server;

D O I：

暂无

中图分类号：

学科分类号：

摘要：

Optimal multiprocessor real-time schedulers incur significant overhead for preemptions and migrations. We present RUN, an efficient scheduler that reduces the multiprocessor problem to a series of uniprocessor problems. RUN significantly outperforms existing optimal algorithms with an upper bound of O(logm) average preemptions per job on m processors (fewer than 3 per job in all of our simulated task sets) and reduces to Partitioned EDF whenever a proper partitioning is found.

引用

页码：436 / 474

页数：38

共 24 条

[1] Baruah SK(2001)Scheduling periodic tasks on uniform multiprocessors Inf Process Lett 80 97-104
[2] Baruah SK(1996)Proportionate progress: a notion of fairness in resource allocation Algorithmica 15 600-625
[3] Cohen NK(2009)Optimal virtual cluster-based multiprocessor scheduling Real-Time Syst 43 25-59
[4] Plaxton CG(2010)LRE-TL: an optimal multiprocessor algorithm for sporadic task sets with unconstrained deadlines Real-Time Syst 46 332-359
[5] Varvel DA(2011): a unifying theory for optimal hard real-time multiprocessor scheduling Real-Time Syst 47 389-429
[6] Easwaran A(1969)Scheduling algorithms for multiprogram in a hard real-time environment JPL Space Programs Summary II 37-60
[7] Shin I(1973)Scheduling algorithms for multiprogram in a hard real-time environment J ACM 20 46-61
[8] Lee I(1959)Scheduling with deadlines and loss functions Manag Sci 6 1-12
[9] Funk S(1996)Scheduling aperiodic tasks in dynamic priority systems Real-Time Syst 10 179-210
[10] Funk S(2011)An optimal boundary fair scheduling algorithm for multiprocessor real-time systems J Parallel Distrib Comput 71 1411-1425

← 1 2 3 →