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

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

18 Scopus citations

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
State	Published - 2007
Externally published	Yes
Event	4296821 - Daegu, Korea, Republic of Duration: 21 08 2007 → 24 08 2007

Publication series

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

Conference

Conference	4296821
Country/Territory	Korea, Republic of
City	Daegu
Period	21/08/07 → 24/08/07

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

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{7a71af561d93482abdcc3d452d803735,

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

year = "2007",

doi = "10.1109/RTCSA.2007.34",

language = "英语",

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

note = "4296821 ; Conference date: 21-08-2007 Through 24-08-2007",

}

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, 21/08/07. 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 › peer-review

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

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 - https://www.scopus.com/pages/publications/46449118306

U2 - 10.1109/RTCSA.2007.34

DO - 10.1109/RTCSA.2007.34

M3 - 会议稿件

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 -

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

Current results on EDZL scheduling for multiprocessor real-time systems

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this