Optimization Of Earliest Deadline First Scheduling Algorithm Based On DNA-GA

Real-time scheduling algorithm is one of key problems for the design and realization of embedded real-time system. It is also an important method that ensures time restriction and reliability of real-time system. Real-time scheduling is an important and active research field.Among the scheduling algorithms, RM (Rate Monotonic) and EDF (Earliest Deadline First) are two kinds of 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 RM and EDF have many excellent performances and are used very broadly in embedded real-time system, we can not ignore their shortcomings for real-time performance.Considering scheduling spending, real-time performance of EDF scheduling algorithm was improved by optimizing release time of tasks in this thesis.Firstly, the background (real-time system, embedded system, real-time operating system and embedded real-time operating system) of real-time scheduling algorithms were introduced.Secondly, real-time scheduling models, real-time scheduling basic theory, real-time scheduling strategies and real-time scheduling algorithms were analyzed. RM and EDF were researched in details. Some examples were used to explain the scheduling process of RM and EDF.Thirdly, the theory of DNA-GA (Deoxyribonucleic acid Genetic Algorithm) was introduced. And, the biology foundation of DNA algorithm and the theory of Genetic Algorithm were illustrated.Finally, the release time of tasks by EDF scheduling was optimized off-line based on DNA-GA. And then, the optimized release time was used for scheduling real time task sets. The optimized scheduling process of EDF scheduling algorithm based on DNA-GA was simulated by software in this thesis. Compared with the scheduling spending for preemption before optimized by simulating experiment, the scheduling spending for preemption after optimized was reduced. The experiment results show that the release time can be optimizing by DNA-GA. It showed the feasibility and validity of method that optimize release time by DNA-GA. The conclusions of this thesis can be reference for theory and application of real-time scheduling algorithm.The innovating of this thesis is that optimize the release time by DNA-GA. This thesis achieved the combination of the DNA-GA and embedded real time scheduling algorithm.