Research On The Scheduling Technology Of Tasks In Real-Time Systems

With the development of real-time applications, new features appear in real-time systems, such as the diversity of tasks, complicated constrains of tasks and highly transient overload, In order to meet these new requirements, this thesis focuses on new scheduling theory and methods based on the analysis of the traditional ones, especially on the scheduling technology of real-time tasks.For the diversity of tasks in real-time systems, methods for computing the response time of periodic tasks are studied in order to satisfy the predictability of real-time systems. For a fixed priority preemptive scheduling periodic task, two algorithms ACRik and HCRik are proposed to compute the response time of its requests according to the load generation function and CPU usage function. For a preemptive threshold scheduling periodic task, an algorithm CRFS is put forward to compute the response time of its requests. In CRFS, the start time of executing a request is computed firstly, and then busy level period is analyzed to compute its response time. Compared with existing methods, ACRik, HCRik and CRFS have higher performance and accuracy.Since the constraints of tasks are complicated, this thesis extends and complements the schedulability analysis methods for hard real-time tasks. To estimate the maximum release jitter of the sub-task in a transaction exactly, this thesis presents corresponding methods to compute the best-case response time of periodic tasks under the EDF preemptive scheduling policy and the preemptive threshold policy. Moreover, for these two policies, methods WRPT and WREP are introduced to analyze the worst-case response time of tasks with offsets and release jitter. Experiment results show that their running time is less than that of existing methods.For the case that the number of priority levels supported by systems is limited, a static priority assignment algorithm AGP is proposed. Fundamental task sets are defined based on the characteristics of tasks. And then AGP is proved to be the optimum for these task sets.To cope with transient overload, skip-over model and (m,k) model are used. For tasks based on skip-over model, an algorithm UDB is given to determine which request should be aborted. UDB improves the schedulability of task sets by reducing the interference from the higher priority tasks to the lower priority tasks. To schedule tasks based on (m,k) model, an online scheduling algorithm SEF is given, which combines the states and deadlines of requests seamlessly. The necessary condition and the sufficient condition for SEF scheduled the tasks are presented. Compared with existing algorithms, SEF can reduce dynamic failures and improve utilization effectively.Finally, for multiprocessor systems, this thesis presents a dynamically scheduling algorithmGroup-Proper (GP). To increase the utilization of resources and processors, GP provides a grouping policy for task selection and a properly choosing policy (PCP) for processor selection respectively. If the tasks with smaller heuristic value are guaranteed to meet their deadlines, the task that accesses resources in shared mode will be selected to extend the current schedule according to the grouping policy. After analyzed the relationship of the earliest available time between the resources requested by the selected task and the processors, PCP assigns the task to the proper processor. When resource utilization is high, GP has better performance than existing algorithms.