Preemption Control Model Of Scheduling Algorithm For Real-time Systems And Genetic Algorithm Implementation

Embedded real-time systems mostly face to the real world applications that relative to the time factor and have been extensively applied in many fields such as industry control, spaceflight and military equipments. Embedded real-time systems concern not only logical correctness but also the time requirements of the output results. Furthermore, because of the limitation of the processing ability and the storage capacity of the embedded real-time systems, usually scheduling algorithm must correctly arrange the implementation order of the tasks and at the same time guarantee the schedulability of the system using fewer resources.Basing on above reasons, in this dissertation the deficiencies and the disadvantages of the popular scheduling algorithms are studied first and then a preemption control model basing on non-preemptive time slice is presented. The preemption control model uses the condition that the worst case response time is less than or equal to the deadline of the task as the necessary and sufficient condition of the schedulability of the tasks. As the result, the model can guarantee the schedulability of the tasks and at the same time minimize the preemption times during the implementation of the tasks.Then the preemption control model is offline implemented with the genetic algorithm. To improve the efficiency of the genetic algorithm, the initial individual is constructed with the suboptimal value. Because of the illegal results which were produced during the evolution and make the tasks unscheduable, a penalty function is applied in the dissertation to solve the problem.At last, the results are verified and analyzed through real test. The software platform is Embedded real-time operation system WebitOS. The results that worked out by genetic algorithm are implemented using C language on WebitOS and at the same time are verified through producing plenty of tasks that scheduled by different scheduling algorithm. The results of the test reveal that the preemption control model basing on the non-preemptive time slice can reduce the amount of preemptions effectively and at the same time guarantee the schedulability of the tasks.