Schedulability issues for EDZL scheduling on real-time multiprocessor systems

被引：22

作者：

Chao, Yi-Hsiung ^{[1
]}

Lin, Shun-Shii ^{[1
]}

Lin, Kwei-Jay ^{[2
]}

机构：

[1] Natl Taiwan Normal Univ, Dept Comp Sci & Informat Engn, Taipei, Taiwan

[2] Univ Calif Irvine, Dept Elect Engn & Comp Sci, Irvine, CA USA

来源：

INFORMATION PROCESSING LETTERS | 2008年 / 107卷 / 05期

关键词：

scheduling; real-time scheduling; EDF; LLF; EDZL; schedulability analysis;

D O I：

10.1016/j.ipl.2008.02.014

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

EDZL (Earliest Deadline first until Zero Laxity) is an efficient and practical scheduling algorithm on multiprocessor systems. It has a comparable number Of Context switch to EDF (Earliest Deadline First) and its schedulable utilization seems to he higher than that of EDF. Previously, there was a conjecture that the utilization hound of EDZL is 3m/4 = 0.75m for m processors. In this paper, we disprove this conjecture and show that the utilization hound of EDZL is no greater than in (1 - 1/e) approximate to 0.6321 m. where e approximate to 2.718 is the Euler's number. (C) 2008 Elsevier B.V. All rights reserved.

引用

页码：158 / 164

页数：7

共 7 条

[1] Special issue: "Web retrieval and mining" [J].

Chen, H .

DECISION SUPPORT SYSTEMS, 2003, 35 (01) :1-5

[2] MULTIPROCESSOR ONLINE SCHEDULING OF HARD-REAL-TIME TASKS [J].

DERTOUZOS, ML ;

MOK, AKL .

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, 1989, 15 (12) :1497-1506

[3] REAL-TIME SCHEDULING PROBLEM [J].

DHALL, SK ;

LIU, CL .

OPERATIONS RESEARCH, 1978, 26 (01) :127-140

[4]

LEE SK, 1994, IEEE REG 10S 9 ANN I, P607

[5]

Lin KJ, 2002, FOURTH INTERNATIONAL SYMPOSIUM ON MULTIMEDIA SOFTWARE ENGINEERING, PROCEEDINGS, P17, DOI 10.1109/MMSE.2002.1181591

[6] Comparison of deadline-based scheduling algorithms for periodic real-time tasks on multiprocessor [J].

Park, M ;

Han, S ;

Kim, H ;

Cho, S ;

Cho, Y .

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2005, E88D (03) :658-661

[7] Deadline-based scheduling of periodic task systems on multiprocessors [J].

Srinivasan, A ;

Baruah, S .

INFORMATION PROCESSING LETTERS, 2002, 84 (02) :93-98

← 1 →