Schedulability issues for EDZL scheduling on real-time multiprocessor systems

Yi Hsiung Chao; Shun Shii Lin; Kwei Jay Lin

doi:10.1016/j.ipl.2008.02.014

Schedulability issues for EDZL scheduling on real-time multiprocessor systems

Yi Hsiung Chao, Shun Shii Lin^*, Kwei Jay Lin

^*Corresponding author for this work

Research output: Contribution to journal › Journal Article › peer-review

23 Scopus citations

Abstract

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 be higher than that of EDF. Previously, there was a conjecture that the utilization bound of EDZL is 3 m / 4 = 0.75 m for m processors. In this paper, we disprove this conjecture and show that the utilization bound of EDZL is no greater than m (1 - 1 / e) ≈ 0.6321 m, where e ≈ 2.718 is the Euler's number.

Original language	English
Pages (from-to)	158-164
Number of pages	7
Journal	Information Processing Letters
Volume	107
Issue number	5
DOIs	https://doi.org/10.1016/j.ipl.2008.02.014
State	Published - 16 08 2008
Externally published	Yes

Keywords

EDF
EDZL
LLF
Real-time scheduling
Schedulability analysis
Scheduling

Access to Document

10.1016/j.ipl.2008.02.014

Cite this

@article{9bbfa5b50ebb4c80a56bfcebd31c3010,

title = "Schedulability issues for EDZL scheduling on real-time multiprocessor systems",

abstract = "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 be higher than that of EDF. Previously, there was a conjecture that the utilization bound of EDZL is 3 m / 4 = 0.75 m for m processors. In this paper, we disprove this conjecture and show that the utilization bound of EDZL is no greater than m (1 - 1 / e) ≈ 0.6321 m, where e ≈ 2.718 is the Euler's number.",

keywords = "EDF, EDZL, LLF, Real-time scheduling, Schedulability analysis, Scheduling",

author = "Chao, {Yi Hsiung} and Lin, {Shun Shii} and Lin, {Kwei Jay}",

year = "2008",

month = aug,

day = "16",

doi = "10.1016/j.ipl.2008.02.014",

language = "英语",

volume = "107",

pages = "158--164",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "5",

}

TY - JOUR

T1 - Schedulability issues for EDZL scheduling on real-time multiprocessor systems

AU - Chao, Yi Hsiung

AU - Lin, Shun Shii

AU - Lin, Kwei Jay

PY - 2008/8/16

Y1 - 2008/8/16

N2 - 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 be higher than that of EDF. Previously, there was a conjecture that the utilization bound of EDZL is 3 m / 4 = 0.75 m for m processors. In this paper, we disprove this conjecture and show that the utilization bound of EDZL is no greater than m (1 - 1 / e) ≈ 0.6321 m, where e ≈ 2.718 is the Euler's number.

AB - 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 be higher than that of EDF. Previously, there was a conjecture that the utilization bound of EDZL is 3 m / 4 = 0.75 m for m processors. In this paper, we disprove this conjecture and show that the utilization bound of EDZL is no greater than m (1 - 1 / e) ≈ 0.6321 m, where e ≈ 2.718 is the Euler's number.

KW - EDF

KW - EDZL

KW - LLF

KW - Real-time scheduling

KW - Schedulability analysis

KW - Scheduling

UR - http://www.scopus.com/inward/record.url?scp=47149114022&partnerID=8YFLogxK

U2 - 10.1016/j.ipl.2008.02.014

DO - 10.1016/j.ipl.2008.02.014

M3 - 文章

AN - SCOPUS:47149114022

SN - 0020-0190

VL - 107

SP - 158

EP - 164

JO - Information Processing Letters

JF - Information Processing Letters

IS - 5

ER -

Schedulability issues for EDZL scheduling on real-time multiprocessor systems

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this