The Research On The Earliest Feasible Time For A Real-time Task Based On EDF

With the continuous development of real-time systems and various new applications springing up, real-time systems demand more and more flexibility. And real-time scheduling algorithms, as the key role with the system performance, have been the focus of the real-time system research field. In order for these requirements, in2002Buttazzo et al put forward an elastic task model for real-time periodic task scheduling, a more flexible strategy. But a new problem was introduced, that is, the earliest feasible time when a new task is requested to insert in the system based on the classic EDF (Earliest Deadline First) real-time scheduling algorithm.To this issue, in that paper Buttazzo presented a concise runtime (online) formula. After that, Qian improved this formula, and put forward an earlier time point (hereinafter referred to as the Q theorem). But by a large number of experiments we have found the time from Q theorem is not the earliest time yet, so the calculating of the earliest feasible time with a new task is still an open problem.Based on the former research, this paper studies the problem with a new point of view.First, through the establishment of the simulation scheduling model, we try to solve the problem of the earliest feasible time calculation in off-line mode. In the off-line mode, starting from the request time, the earliest time can be evaluated by constantly iterating. However, there is another question, the task set convergence problem, that is, the off-line algorithm needs to be used to calculate the time to determine how the task set is schedulable and in the later time the deadline missing will not happen. After a great deal of experiments and researches, we have found and summarized three convergence modes:test to the next least common point, to the point of cycle alignment, and to the point of advance point. We prove the correctness of the three modes, and give examples to illustrate. Then we discuss the possibility for applying them as an online algorithm. On this basis, this paper puts a scheduling table based on the Q theorem. The off-line results are saved in this table and scheduling is done by querying the table. And then some problems with the practical application are discussed with some suggested solutions.Finally, our results are simulated in the real-time switch environment, the SwitchSim switch simulation platform. The simulation experiments show the valuable application significance of our solutions in pure real-time and R/B (Real-time and Best-effort) environment.