Analysis of the Queue Service Probability for the EDF Scheduling Algorithm

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.