Research On Tasks Scheduling Algorithm In Real-time System Under Overload Conditions

The performance of real-time system under overload conditions may decrease dramatically, to solve the issue, current research mostly focus on the schedule of independent periodic tasks, but have not paid fully consideration on scheduling algorithm for other types tasks. This paper presents a new algorithm based on a summary for the shortage of current research. The algorithm can not only solve the problem of independent periodic tasks scheduling, but also solve the problem of non-periodic tasks and dependent tasks scheduling.The main work in this paper is as follows.(1) Modeling of the task set. including modeling of the task itself and the dependencies among tasks. Firstly, real-time tasks and non-real-time tasks are modeled using the same four tuple T; (TA, TC; TD; TV;) in this algorithm, where TA, represents the arrival time of the task:TC, represents the expected execution time of the task:TD, represents the deadline of the task:TV, represents the value that can be obtained by successful implementation of the task. Secondly, adjacency matrix is used to represent the dependencies among tasks.(2) According to the type of tasks and different dependencies among tasks, different scheduling algorithms are proposed to ensure the smooth degradation of system performance. For independent non-real-time tasks, due to the tasks have no deadline, the method based on greedy algorithm is used to achieve the maximized utilization rate of CPU. For independent real-time tasks, whose value will drop to zero, if the) miss deadline, the method based on dynamic programming is used to maximize expected value of tasks execution. For the situation with mixture of real-time tasks and non-real-time tasks, due to the default priority of real-time tasks is usually higher than the non-real-time tasks* in real-time system, the scheduling algorithm regards real-time tasks scheduling goal as the first target and takes the non-real-time tasks scheduling yoal into account, in this case the schedule can be decomposed into the schedule of real-time tasks and non-real-time tasks. For dependent tasks, not only the parameters of the task itself but also the dependencies among tasks need to be considered, therefore the scheduling algorithm needs to solve dependencies among tasks and then select the appropriate algorithm to get optimal solution according to the type of tasks’dependencies. This paper proposed the scheduling algorithm for all kinds of situations, a detailed simulation and analysis of algorithm is also presented.(3) In order to prove the superiority of the algorithm presented in this paper, the related scheduling algorithms about independent real-time tasks are implemented and compared with the algorithms presented in this paper.