Optimal online multiprocessor scheduling of sporadic real-time tasks is impossible

被引：29

作者：

Fisher, Nathan ^{[1
]}

Goossens, Joel ^{[2
]}

Baruah, Sanjoy ^{[3
]}

机构：

[1] Wayne State Univ, Detroit, MI 48202 USA

[2] Univ Libre Bruxelles, Brussels, Belgium

[3] Univ N Carolina, Chapel Hill, NC USA

来源：

REAL-TIME SYSTEMS | 2010年 / 45卷 / 1-2期

基金：

美国国家科学基金会;

关键词：

Real-time scheduling; Multiprocessor systems; Sporadic task model; Optimal scheduling algorithms;

D O I：

10.1007/s11241-010-9092-7

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Optimal online scheduling algorithms are known for sporadic task systems scheduled upon a single processor. Additionally, optimal online scheduling algorithms are also known for restricted subclasses of sporadic task systems upon an identical multiprocessor platform. The research reported in this article addresses the question of existence of optimal online multiprocessor scheduling algorithms for general sporadic task systems. Our main result is a proof of the impossibility of optimal online scheduling for sporadic task systems upon a system comprised of two or more processors. The result is shown by finding a sporadic task system that is feasible on a multiprocessor platform that cannot be correctly scheduled by any possible online, deterministic scheduling algorithm. Since the sporadic task model is a subclass of many more general real-time task models, the nonexistence of optimal scheduling algorithms for the sporadic task systems implies nonexistence for any model which generalizes the sporadic task model.

引用

页码：26 / 71

页数：46

共 23 条

[1]

ANDERSON SA, 2002, P 34 ACM S THEOR COM, P189

[2]

AUDSLEY N, 1991, P REAL TIME OPERATIN, V8, P127

[3]

Baker TP, 2007, LECT NOTES COMPUT SC, V4878, P62

[4] A necessary and sometimes sufficient condition for the feasibility of sets of sporadic hard-deadline tasks [J].