Current results on EDZL scheduling for multiprocessor real-time systems

Hsin Wen Wei; Yi Hsiung Chao; Shun Shii Lin; Kwei Jay Lin; Wei Kuan Shih

doi:10.1109/RTCSA.2007.34

Current results on EDZL scheduling for multiprocessor real-time systems

Hsin Wen Wei^*, Yi Hsiung Chao, Shun Shii Lin, Kwei Jay Lin, Wei Kuan Shih

^*Corresponding author for this work

Department of Computer Science and Information Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

18 Citations (Scopus)

Abstract

Many optimal uniprocessor schedulers, such as Earliest Deadline First (EDF) and Rate Monotonic (RM), do not have a good schedulability bound on multiprocessor systems. In this paper, we study an on-line algorithm Earliest Deadline First until Zero laxity (EDZL) for multiprocessor systems. A set of tasks scheduled by EDZL is scheduled using EDF until a job experiences a zero laxity. To avoid the job from missing its deadline, the priority of the job is immediately promoted to the highest priority. We derive the schedulability bound of 3/2+|u _max-1/2| for two-processor systems, where u _max is the maximum utilization of an individual task in the given task set. We also discuss the best known upper bound and lower bound on EDZL schedulability conditions.

Original language	English
Title of host publication	Proceedings - 13th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2007
Pages	120-127
Number of pages	8
DOIs	https://doi.org/10.1109/RTCSA.2007.34
Publication status	Published - 2007
Event	4296821 - Daegu, Korea, Republic of Duration: 2007 Aug 21 → 2007 Aug 24

Publication series

Name	Proceedings - 13th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2007

Other

Other	4296821
Country/Territory	Korea, Republic of
City	Daegu
Period	2007/08/21 → 2007/08/24

ASJC Scopus subject areas

Computer Science Applications
Control and Systems Engineering
Electrical and Electronic Engineering

Access to Document

10.1109/RTCSA.2007.34

Cite this

Wei, H. W., Chao, Y. H., Lin, S. S., Lin, K. J., & Shih, W. K. (2007). Current results on EDZL scheduling for multiprocessor real-time systems. In Proceedings - 13th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2007 (pp. 120-127). Article 4296844 (Proceedings - 13th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2007). https://doi.org/10.1109/RTCSA.2007.34

Current results on EDZL scheduling for multiprocessor real-time systems. / Wei, Hsin Wen; Chao, Yi Hsiung; Lin, Shun Shii et al.
Proceedings - 13th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2007. 2007. p. 120-127 4296844 (Proceedings - 13th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2007).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Wei, HW, Chao, YH, Lin, SS, Lin, KJ & Shih, WK 2007, Current results on EDZL scheduling for multiprocessor real-time systems. in Proceedings - 13th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2007., 4296844, Proceedings - 13th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2007, pp. 120-127, 4296821, Daegu, Korea, Republic of, 2007/08/21. https://doi.org/10.1109/RTCSA.2007.34

Wei HW, Chao YH, Lin SS, Lin KJ, Shih WK. Current results on EDZL scheduling for multiprocessor real-time systems. In Proceedings - 13th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2007. 2007. p. 120-127. 4296844. (Proceedings - 13th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2007). doi: 10.1109/RTCSA.2007.34

Wei, Hsin Wen ; Chao, Yi Hsiung ; Lin, Shun Shii et al. / Current results on EDZL scheduling for multiprocessor real-time systems. Proceedings - 13th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2007. 2007. pp. 120-127 (Proceedings - 13th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2007).

@inproceedings{db965857e224404bac5b605bec3eedff,

title = "Current results on EDZL scheduling for multiprocessor real-time systems",

abstract = "Many optimal uniprocessor schedulers, such as Earliest Deadline First (EDF) and Rate Monotonic (RM), do not have a good schedulability bound on multiprocessor systems. In this paper, we study an on-line algorithm Earliest Deadline First until Zero laxity (EDZL) for multiprocessor systems. A set of tasks scheduled by EDZL is scheduled using EDF until a job experiences a zero laxity. To avoid the job from missing its deadline, the priority of the job is immediately promoted to the highest priority. We derive the schedulability bound of 3/2+|u max-1/2| for two-processor systems, where u max is the maximum utilization of an individual task in the given task set. We also discuss the best known upper bound and lower bound on EDZL schedulability conditions.",

author = "Wei, {Hsin Wen} and Chao, {Yi Hsiung} and Lin, {Shun Shii} and Lin, {Kwei Jay} and Shih, {Wei Kuan}",

note = "Funding Information: This work is supported by National Key Research Program (2016YFB0302801-03), China, Republic of China.; 4296821 ; Conference date: 21-08-2007 Through 24-08-2007",

year = "2007",

doi = "10.1109/RTCSA.2007.34",

language = "English",

isbn = "0769529755",

series = "Proceedings - 13th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2007",

pages = "120--127",

booktitle = "Proceedings - 13th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2007",

}

TY - GEN

T1 - Current results on EDZL scheduling for multiprocessor real-time systems

AU - Wei, Hsin Wen

AU - Chao, Yi Hsiung

AU - Lin, Shun Shii

AU - Lin, Kwei Jay

AU - Shih, Wei Kuan

N1 - Funding Information: This work is supported by National Key Research Program (2016YFB0302801-03), China, Republic of China.

PY - 2007

Y1 - 2007

N2 - Many optimal uniprocessor schedulers, such as Earliest Deadline First (EDF) and Rate Monotonic (RM), do not have a good schedulability bound on multiprocessor systems. In this paper, we study an on-line algorithm Earliest Deadline First until Zero laxity (EDZL) for multiprocessor systems. A set of tasks scheduled by EDZL is scheduled using EDF until a job experiences a zero laxity. To avoid the job from missing its deadline, the priority of the job is immediately promoted to the highest priority. We derive the schedulability bound of 3/2+|u max-1/2| for two-processor systems, where u max is the maximum utilization of an individual task in the given task set. We also discuss the best known upper bound and lower bound on EDZL schedulability conditions.

AB - Many optimal uniprocessor schedulers, such as Earliest Deadline First (EDF) and Rate Monotonic (RM), do not have a good schedulability bound on multiprocessor systems. In this paper, we study an on-line algorithm Earliest Deadline First until Zero laxity (EDZL) for multiprocessor systems. A set of tasks scheduled by EDZL is scheduled using EDF until a job experiences a zero laxity. To avoid the job from missing its deadline, the priority of the job is immediately promoted to the highest priority. We derive the schedulability bound of 3/2+|u max-1/2| for two-processor systems, where u max is the maximum utilization of an individual task in the given task set. We also discuss the best known upper bound and lower bound on EDZL schedulability conditions.

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

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

U2 - 10.1109/RTCSA.2007.34

DO - 10.1109/RTCSA.2007.34

M3 - Conference contribution

AN - SCOPUS:46449118306

SN - 0769529755

SN - 9780769529752

T3 - Proceedings - 13th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2007

SP - 120

EP - 127

BT - Proceedings - 13th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2007

T2 - 4296821

Y2 - 21 August 2007 through 24 August 2007

ER -

Current results on EDZL scheduling for multiprocessor real-time systems

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this