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

^*此作品的通信作者

資訊工程學系

研究成果: 雜誌貢獻 › 期刊論文 › 同行評審

23 引文斯高帕斯（Scopus）

摘要

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.

原文	英語
頁（從 - 到）	158-164
頁數	7
期刊	Information Processing Letters
卷	107
發行號	5
DOIs	https://doi.org/10.1016/j.ipl.2008.02.014
出版狀態	已發佈 - 2008 8月 16

ASJC Scopus subject areas

理論電腦科學
訊號處理
資訊系統
電腦科學應用

存取文件

10.1016/j.ipl.2008.02.014

其它文件與鏈接

引用此

@article{e4ae09dc1e144a86b312f828b8f449c8,

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}",

note = "Funding Information: This research was supported in part by a grant NSC94-2213-E-003-004 from the National Science Council, ROC.",

year = "2008",

month = aug,

day = "16",

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

language = "English",

volume = "107",

pages = "158--164",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier",

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

N1 - Funding Information: This research was supported in part by a grant NSC94-2213-E-003-004 from the National Science Council, ROC.

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

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

U2 - 10.1016/j.ipl.2008.02.014

DO - 10.1016/j.ipl.2008.02.014

M3 - Article

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

摘要

ASJC Scopus subject areas

存取文件

其它文件與鏈接

指紋

引用此