A Feedback Control Scheme Applied To Earliest Deadline First Scheduling Algorithm

Real-time scheduling algorithm is one of major design issues for embedded real-time systems. It is also an important method to guarantee time constrains and reliability for real-time systems, actively being researched in this field.Among the scheduling algorithms, RM (Rate Monotonic) and EDF (Earliest Deadline First) are two classical scheduling algorithms. RM is a good algorithm in the field of static scheduling. RM decided task scheduling order before system running, and it is easy to carry out. If preconditions are met, RM can schedule real-time task sets successfully. EDF is a good algorithm in the field of dynamic scheduling. EDF decided task scheduling order during system running. The CPU utilization of EDF scheduling algorithm can be 100% in perfect condition. Although having noticed that RM and EDF do have good performance and broadly used in embedded real-time systems, we can not ignore the shortcomings of real-time performance of the two algorithms.While some improved Earliest Deadline First and Rate Monotonic scheduling algorithms can support more sophisticated task set characteristics, they are still all open loop scheduling algorithms. Open loop means that once schedules are created they can not adjust themselves based on continuous feedback. While open-loop scheduling algorithms can perform well in static or dynamic systems where the workloads are accurately modeled, they still can perform poorly in unpredictable dynamic systems.In the consideration of system overload, a feedback control scheme is introduced in this thesis to enhance the real-time performance and stability of EDF scheduling algorithm.Firstly, the background (real-time system, embedded system, real-time operating system and embedded real-time operating system) of real-time scheduling algorithms was introduced.Secondly, real-time scheduling models, the basic theory of real-time scheduling, real-time scheduling strategies and real-time scheduling algorithms were described. RM and EDF were discussed in detail and some examples were used to explain their scheduling processes.Thirdly, the correlated theory used for our feedback scheme proposed in this paper was introduced. It is on PID(Proportional-Integral-Derivative) in auto-control theory and operation method. The theory on Single Neural Element Self-Adaptive PID method was also illustrated.Finally, it can be achieved that overload situation can be improved through using Single Neural Element Self-Adaptive PID algorithm to make feedback control on EDF scheduling. It can dynamically adjust task number in overload system and use the received deadline miss ratio for each running as the input parameter for next real-time scheduling. We simulated a EDF scheduling with a PID feedback control scheme, then compared the experiments before and after introduced such feedback control scheme. The results show that the introduced Single Neural Element Self-Adaptive PID algorithm can fast stabilize and actively improve the real-time system overloaded, and optimize the performance when system degraded. It proves the feasibility and validation of the PID feedback control scheme for EDF scheduling. The conclusions of this thesis can be referenced for theory and application of real-time scheduling algorithm.The innovating of this thesis is that introducing Single Neural Element Self-Adaptive PID scheme to make feedback control on real-time scheduling be more intelligent and implementing this algorithm applied in embedded real time scheduling.