EDZL scheduling analysis

被引：40

作者：

Baker, Theodore P. ^{[1
]}

Cirinei, Michele ^{[2
]}

Bertogna, Marko ^{[2
]}

机构：

[1] Florida State Univ, Dept Comp Sci, Tallahassee, FL 32306 USA

[2] Scuola Super Sant Anna, ReTIS Lab, Pisa, Italy

来源：

REAL-TIME SYSTEMS | 2008年 / 40卷 / 03期

基金：

美国国家科学基金会;

关键词：

EDF; Earliest deadline first; EDZL; Earliest deadline zero laxity; Multiprocessor; Real time; Scheduling; Symmetric multiprocessing; Schedulability;

D O I：

10.1007/s11241-008-9061-6

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

A schedulability test is derived for the global Earliest Deadline Zero Laxity (EDZL) scheduling algorithm on a platform with multiple identical processors. The test is sufficient, but not necessary, to guarantee that a system of independent sporadic tasks with arbitrary deadlines will be successfully scheduled, with no missed deadlines, by the multiprocessor EDZL algorithm. Global EDZL is known to be at least as effective as global Earliest-Deadline-First (EDF) in scheduling task sets to meet deadlines. It is shown, by testing on large numbers of pseudo-randomly generated task sets, that the combination of EDZL and the new schedulability test is able to guarantee that far more task sets meet deadlines than the combination of EDF and known EDF schedulability tests. In the second part of the paper, an improved version of the EDZL-schedulability test is presented. This new algorithm is able to efficiently exploit information on the slack values of interfering tasks, to iteratively refine the estimation of the interference a task can be subjected to. This iterative algorithm is shown to have better performance than the initial test, in terms of schedulable task sets detected.

引用

页码：264 / 289

页数：26

共 14 条

[1]

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

[2] Multiprocessor EDF and deadline monotonic schedulability analysis [J].

Baker, TP .

RTSS 2003: 24TH IEEE INTERNATIONAL REAL-TIME SYSTEMS SYMPOSIUM, PROCEEDINGS, 2003, :120-129

[3]

BAKER TP, 2006, INT C REAL TIM NETW, P119

[4]

BAKER TP, 2006, P 27 IEEE REAL TIM S

[5] Improved schedulability analysis of EDF on multiprocessor platforms [J].

Bertogna, M ;

Cirinei, M ;

Lipari, G .

17TH EUROMICRO CONFERENCE ON REAL-TIME SYSTEMS, PROCEEDINGS, 2005, :209-218

[6]

Cho S, 2002, IEICE T COMMUN, VE85B, P2859

[7]

CIRINEI M, 2007, P EUROMICRO C REAL T

[8]

CIRINEI M, 2007, THESIS SCUOLA SUPERI

[9] Priority-driven scheduling of periodic task systems on multiprocessors [J].

Goossens, J ;

Funk, S ;

Baruah, S .

REAL-TIME SYSTEMS, 2003, 25 (2-3) :187-205

[10]

HA R, 1994, INT CON DISTR COMP S, P162

← 1 2 →