Gang EDF Scheduling of Parallel Task Systems

被引：63

作者：

Kato, Shinpei ^{[1
]}

Ishikawa, Yutaka ^{[1
]}

机构：

[1] Univ Tokyo, Grad Sch Informat Sci & Technol, Tokyo 1138654, Japan

来源：

2009 30TH IEEE REAL-TIME SYSTEMS SYMPOSIUM, PROCEEDINGS | 2009年

关键词：

SCHEDULABILITY; PERFORMANCE; ALGORITHMS;

D O I：

10.1109/RTSS.2009.42

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

The preemptive real-time scheduling of sporadic parallel task systems is studied. We present an algorithm, called Gang EDF which applies the Earliest Deadline First (EDF) policy to the traditional Gang scheduling scheme. We also provide schedulability analysis of Gang EDF Specifically, the total amount of interference that is necessary to cause a deadline miss is first identified. The contribution of each task to the interference is then bounded. Finally, verifying that the total amount of contribution does not exceed the necessary interference for every task, the schedulability test is derived. Although the techniques proposed herein are based on the prior results for the sequential task model, we introduce new ideas for the parallel task model.

引用

页码：459 / 468

页数：10

共 43 条

[21] Adaptive parallel job scheduling with flexible coscheduling [J].

Frachtenberg, E ;

Feitelson, DG ;

Petrini, F ;

Fernández, J .

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2005, 16 (11) :1066-1077

[22]

Gehringer EF., 1987, PARALLEL PROCESSING

[23] 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

[24]

Han C.-C., 1989, Proceedings. Real Time Systems Symposium (Cat. No.89CH2803-5), P59, DOI 10.1109/REAL.1989.63557

[25] Performance of gang scheduling strategies in a parallel system [J].

Karatza, Helen D. .

SIMULATION MODELLING PRACTICE AND THEORY, 2009, 17 (02) :430-441

[26]

Kato S., 2009, P EUR C REAL TIM SYS

[27] Global EDF-based Scheduling with Efficient Priority Promotion [J].

Kato, Shinpei ;

Yamasaki, Nobuyuki .

RTCSA 2008: 14TH IEEE INTERNATIONAL CONFERENCE ON EMBEDDED AND REAL-TIME COMPUTING SYSTEMS AND APPLICATIONS - PROCEEDINGS, 2008, :197-206

[28] Scheduling parallel tasks with individual deadlines [J].

Kwon, OH ;

Chwa, KY .

THEORETICAL COMPUTER SCIENCE, 1999, 215 (1-2) :209-223

[29] A retargetable parallel-programming framework for MPSoC [J].

Kwon, Seongnam ;

Kim, Yongjoo ;

Jeun, Woo-Chul ;

Ha, Soonhoi ;

Paek, Yunheung .

ACM TRANSACTIONS ON DESIGN AUTOMATION OF ELECTRONIC SYSTEMS, 2008, 13 (03)

[30] Optimal scheduling for real-time parallel tasks [J].

Lee, WY ;

Lee, H .

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2006, E89D (06) :1962-1966

← 1 2 3 4 5 →