Analysis of the queue service probability for the EDF scheduling algorithm

Mu Song Chen, Chi Pan 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

Publication series

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

Other

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

    Fingerprint

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. P., & 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] (Proceedings - IEEE 30th International Conference on Advanced Information Networking and Applications Workshops, WAINA 2016). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/WAINA.2016.76