Analysis of the queue service probability for the EDF scheduling algorithm

Mu Song Chen, Chipan Hwang, Hsuan Fu Wang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Citation (Scopus)

Abstract

This paper is concerned with the Earliest-DeadlineFirst (EDF) policy for scheduling a constrained multi-queuesystem with a single server in the overloaded environment. Thisstudy originates from the research of the controller area network(CAN). In the CAN system, variability and constraints, e.g. heavy(or overloaded) traffic, timing constraints, limited bandwidth, etc., have crucial impacts on its scheduling performance. Violating these constrictions may lead to a lack of the ability ofmaintaining the integrity of the system communication. In thissense, this paper discusses the applicability of Earliest DeadlineFirst (EDF) technique to the scheduling of CAN messages. TheEDF scheduling algorithm permits more general applications tothe real time system under various situations and timingconstraints. It assumes implicitly that a message's urgencyincreases with the imminence of its deadline. In this regard, theEDF policy minimizes the maximum lateness and the maximumtardiness. Therefore, a software-based EDF policy uses themessage time-to-deadline as a measure of its priority is applied toschedule the message exchanges in the CAN. In this work, theclosed form of queue service probability is also derived fromsolving a set of nonlinear equations. From the simulation analysisthe concerned model, our theoretical results are well matchedwith the experimental results. Importantly, the theoretical resultsare not necessarily limited to the applications of CAN system. Instead, we hope to provide a general viewpoint of schedulingissues in the overloaded condition.

Original languageEnglish
Title of host publicationProceedings - IEEE 30th International Conference on Advanced Information Networking and Applications Workshops, WAINA 2016
EditorsAntonio J. Jara, Makoto Takizawa, Yann Bocchi, Leonard Barolli, Tomoya Enokido
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages960-963
Number of pages4
ISBN (Electronic)9781509018574
DOIs
Publication statusPublished - 2016 May 17
Event30th IEEE International Conference on Advanced Information Networking and Applications Workshops, WAINA 2016 - Crans-Montana, Switzerland
Duration: 2016 Mar 232016 Mar 25

Other

Other30th IEEE International Conference on Advanced Information Networking and Applications Workshops, WAINA 2016
CountrySwitzerland
CityCrans-Montana
Period16-03-2316-03-25

Fingerprint

Scheduling algorithms
Scheduling Algorithm
Queue
Controller
Controllers
Scheduling
Deadline
Maximum Lateness
Real-time Systems
Single Server
Real time systems
Nonlinear equations
Telecommunication traffic
Integrity
Communication Systems
Timing
Nonlinear Equations
Servers
Bandwidth
Traffic

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Computer Science Applications
  • Information Systems
  • Information Systems and Management
  • Modelling and Simulation

Cite this

Chen, M. S., Hwang, C., & Wang, H. F. (2016). Analysis of the queue service probability for the EDF scheduling algorithm. In A. J. Jara, M. Takizawa, Y. Bocchi, L. Barolli, & T. Enokido (Eds.), Proceedings - IEEE 30th International Conference on Advanced Information Networking and Applications Workshops, WAINA 2016 (pp. 960-963). [7471329] Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/WAINA.2016.76
Chen, Mu Song ; Hwang, Chipan ; Wang, Hsuan Fu. / Analysis of the queue service probability for the EDF scheduling algorithm. Proceedings - IEEE 30th International Conference on Advanced Information Networking and Applications Workshops, WAINA 2016. editor / Antonio J. Jara ; Makoto Takizawa ; Yann Bocchi ; Leonard Barolli ; Tomoya Enokido. Institute of Electrical and Electronics Engineers Inc., 2016. pp. 960-963
@inproceedings{62c89fdaaee54d4b83681974cdce28df,
title = "Analysis of the queue service probability for the EDF scheduling algorithm",
abstract = "This paper is concerned with the Earliest-DeadlineFirst (EDF) policy for scheduling a constrained multi-queuesystem with a single server in the overloaded environment. Thisstudy originates from the research of the controller area network(CAN). In the CAN system, variability and constraints, e.g. heavy(or overloaded) traffic, timing constraints, limited bandwidth, etc., have crucial impacts on its scheduling performance. Violating these constrictions may lead to a lack of the ability ofmaintaining the integrity of the system communication. In thissense, this paper discusses the applicability of Earliest DeadlineFirst (EDF) technique to the scheduling of CAN messages. TheEDF scheduling algorithm permits more general applications tothe real time system under various situations and timingconstraints. It assumes implicitly that a message's urgencyincreases with the imminence of its deadline. In this regard, theEDF policy minimizes the maximum lateness and the maximumtardiness. Therefore, a software-based EDF policy uses themessage time-to-deadline as a measure of its priority is applied toschedule the message exchanges in the CAN. In this work, theclosed form of queue service probability is also derived fromsolving a set of nonlinear equations. From the simulation analysisthe concerned model, our theoretical results are well matchedwith the experimental results. Importantly, the theoretical resultsare not necessarily limited to the applications of CAN system. Instead, we hope to provide a general viewpoint of schedulingissues in the overloaded condition.",
author = "Chen, {Mu Song} and Chipan Hwang and Wang, {Hsuan Fu}",
year = "2016",
month = "5",
day = "17",
doi = "10.1109/WAINA.2016.76",
language = "English",
pages = "960--963",
editor = "Jara, {Antonio J.} and Makoto Takizawa and Yann Bocchi and Leonard Barolli and Tomoya Enokido",
booktitle = "Proceedings - IEEE 30th International Conference on Advanced Information Networking and Applications Workshops, WAINA 2016",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
address = "United States",

}

Chen, MS, Hwang, C & Wang, HF 2016, Analysis of the queue service probability for the EDF scheduling algorithm. in AJ Jara, M Takizawa, Y Bocchi, L Barolli & T Enokido (eds), Proceedings - IEEE 30th International Conference on Advanced Information Networking and Applications Workshops, WAINA 2016., 7471329, Institute of Electrical and Electronics Engineers Inc., pp. 960-963, 30th IEEE International Conference on Advanced Information Networking and Applications Workshops, WAINA 2016, Crans-Montana, Switzerland, 16-03-23. https://doi.org/10.1109/WAINA.2016.76

Analysis of the queue service probability for the EDF scheduling algorithm. / Chen, Mu Song; Hwang, Chipan; Wang, Hsuan Fu.

Proceedings - IEEE 30th International Conference on Advanced Information Networking and Applications Workshops, WAINA 2016. ed. / Antonio J. Jara; Makoto Takizawa; Yann Bocchi; Leonard Barolli; Tomoya Enokido. Institute of Electrical and Electronics Engineers Inc., 2016. p. 960-963 7471329.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Analysis of the queue service probability for the EDF scheduling algorithm

AU - Chen, Mu Song

AU - Hwang, Chipan

AU - Wang, Hsuan Fu

PY - 2016/5/17

Y1 - 2016/5/17

N2 - This paper is concerned with the Earliest-DeadlineFirst (EDF) policy for scheduling a constrained multi-queuesystem with a single server in the overloaded environment. Thisstudy originates from the research of the controller area network(CAN). In the CAN system, variability and constraints, e.g. heavy(or overloaded) traffic, timing constraints, limited bandwidth, etc., have crucial impacts on its scheduling performance. Violating these constrictions may lead to a lack of the ability ofmaintaining the integrity of the system communication. In thissense, this paper discusses the applicability of Earliest DeadlineFirst (EDF) technique to the scheduling of CAN messages. TheEDF scheduling algorithm permits more general applications tothe real time system under various situations and timingconstraints. It assumes implicitly that a message's urgencyincreases with the imminence of its deadline. In this regard, theEDF policy minimizes the maximum lateness and the maximumtardiness. Therefore, a software-based EDF policy uses themessage time-to-deadline as a measure of its priority is applied toschedule the message exchanges in the CAN. In this work, theclosed form of queue service probability is also derived fromsolving a set of nonlinear equations. From the simulation analysisthe concerned model, our theoretical results are well matchedwith the experimental results. Importantly, the theoretical resultsare not necessarily limited to the applications of CAN system. Instead, we hope to provide a general viewpoint of schedulingissues in the overloaded condition.

AB - This paper is concerned with the Earliest-DeadlineFirst (EDF) policy for scheduling a constrained multi-queuesystem with a single server in the overloaded environment. Thisstudy originates from the research of the controller area network(CAN). In the CAN system, variability and constraints, e.g. heavy(or overloaded) traffic, timing constraints, limited bandwidth, etc., have crucial impacts on its scheduling performance. Violating these constrictions may lead to a lack of the ability ofmaintaining the integrity of the system communication. In thissense, this paper discusses the applicability of Earliest DeadlineFirst (EDF) technique to the scheduling of CAN messages. TheEDF scheduling algorithm permits more general applications tothe real time system under various situations and timingconstraints. It assumes implicitly that a message's urgencyincreases with the imminence of its deadline. In this regard, theEDF policy minimizes the maximum lateness and the maximumtardiness. Therefore, a software-based EDF policy uses themessage time-to-deadline as a measure of its priority is applied toschedule the message exchanges in the CAN. In this work, theclosed form of queue service probability is also derived fromsolving a set of nonlinear equations. From the simulation analysisthe concerned model, our theoretical results are well matchedwith the experimental results. Importantly, the theoretical resultsare not necessarily limited to the applications of CAN system. Instead, we hope to provide a general viewpoint of schedulingissues in the overloaded condition.

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

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

U2 - 10.1109/WAINA.2016.76

DO - 10.1109/WAINA.2016.76

M3 - Conference contribution

AN - SCOPUS:84983527508

SP - 960

EP - 963

BT - Proceedings - IEEE 30th International Conference on Advanced Information Networking and Applications Workshops, WAINA 2016

A2 - Jara, Antonio J.

A2 - Takizawa, Makoto

A2 - Bocchi, Yann

A2 - Barolli, Leonard

A2 - Enokido, Tomoya

PB - Institute of Electrical and Electronics Engineers Inc.

ER -

Chen MS, Hwang C, Wang HF. Analysis of the queue service probability for the EDF scheduling algorithm. In Jara AJ, Takizawa M, Bocchi Y, Barolli L, Enokido T, editors, Proceedings - IEEE 30th International Conference on Advanced Information Networking and Applications Workshops, WAINA 2016. Institute of Electrical and Electronics Engineers Inc. 2016. p. 960-963. 7471329 https://doi.org/10.1109/WAINA.2016.76