Research On Key Problem Of Real-time Scheduling With Constraint

With the rapid development of embedded technology and the continuous rising of the complexity of embedded applications, embedded systems and application environments typically contain multiple types of application requirements, and to provide the service satisfying the real-time constraint to the system is not the only goal of real-time scheduling. In order to execute system function correctly, in the system scheduling process, it is needed to consider the precedence constraint among tasks, resource sharing constraint among tasks providing service satisfying task QoS requirement and so on.While traditional real-time scheduling theory and related models are still the theoretical basis for real-time scheduling, but the needs of various types of applications can not be fully met by system which only use the basic time characteristics of the task to make scheduling decision, and scheduling with a single objective often does not satisfy other constraints of real-time systems. Therefore, under the premise of ensuring to meet the real-time task schedulability, how to schedule correctly and effectively basing on the practical constraints of specific application requirements becomes the key issue of real-time scheduling research field. The problem on real-time scheduling with constraint is researched in this paper, which mainly includes real-time scheduling with precedence constraint and real-time scheduling with QoS constraint.Real-time scheduling with precedence constraint stems from the specific function design requirements of practical application. In these system, real-time applications are usually designed into interactive tasks running on the computing resource. Because these parallel tasks are designed to achieve whole computing funciton, the excuting sequence of tasks is needed to meet the precedence constraint to ensure the correctness of the whole function. In order to address on-line scheduling algorithm problem of the inefficacy to process tasks with random release time, basing on parallel topological sorting principle, an online scheduling algorithm is presented in this paper, which determines non-preemptive scheduling sequence through the analysis of parallel relation and serial relation in taskset. The algorithm is proved to be optimal when task set releases according to level of precedence constraint. Off-line scheduling is another way to solve real-time scheduling with precedence constraint. Through the anylasis of non-preemptive scheduling of real-time task set with precedence constraint, this paper concludes that there are three scheduling contstraints:real-time constraint of tasks, precedence constraint among tasks and non-preemption constraint in scheduling sequence. After convertion to the standard form in linear programming of these three kinds of constraints, this paper uses branch testing strategy which constantly modifies the scheduling sequence bound to abtain feasible scheduling sequence satisfying precedence constraint.Real-time scheduling with QoS constraint of embedded real-time system stems from the applications in control system, network communication system, industrial network systems. In such applications, missing the deadline of some tasks within limited time interval does not affect the entire performance of application, but this situation must be permitted by QoS constraint. An online scheduling algorithm satisfying QoS constraint is presented in this paper, which sets the fixed priority of task with RM scheduling policy based on task period and real-time QoS constraint. In order to reflect the pressure of the current QoS service level requirement, the algorithm switches the task between preemptive status and optional status based on the current statistical situation of the satisfying of real-time constraint. At the same time, in order to meet the adaptability to system for high loads, the algorithm can be combined with the mechanism of moderate degradation of QoS which tries to provide valid service to all tasks under the premise of ensuring the service statisfying the minimum QoS to critical tasks.The algorithm not only has the merits of static scheduling algorithm that can do schedulablity test, but also can set the executing pattern of task dynamicly according to system load just like dynamic scheduling algorithm. Aimed at the applying of real-time system with QoS constraint in the power restraint system, this paper also presents off-line optimization scheme of task executing pattern based on genetic algorithm to minimize power consumption, and targeted at the "premature" problem in using standard algorithm for solving best executiong pattern of task, a hybrid genetic algorithm is presented which imports simulated annealing algorithm during mutaion to improve the search performance of the optimal solution.During the process of discussion of two scheduling with constraint and four scheduling strategy, example analysis, simulation and other means of verification are used in this paper to test the correctness and effectiveness of proposed scheduling algorithm.