Study Of Integrated Dynamic Scheduling Model And Algorithm For Real-time Heterogeneous Systems

Real-time heterogeneous systems are used widely in the field of flight control and avionics, processing control, telecommunication, imagine processing and Internet applications. Many of these applications involve hard and soft real-time tasks. It is very important to study of integrated dynamic scheduling model and algorithm for real-time heterogeneous systems. This paper has made the research thoroughly on the integrated dynamic scheduling issue. In this paper, a new model for integrated dynamic scheduling of real-time heterogeneous systems is presented. Basing on the model, a new integrated dynamic scheduling algorithm that is based on group optimization, called GOIDSH, is developed to schedule a set of tasks in real-time heterogeneous systems.In allusion to characteristics of real-time heterogeneous multitask scheduling, a centralized scheme is assumed in this paper and an integrated task model for real-time heterogeneous systems, called uniform form task model, is proposed. This task model uniformly characterizes hard and soft real-time tasks in real-time heterogeneous systems clearly by using imprecise computing model. The new task model saves location and provides an efficient way to achieve integrated dynamic scheduling based on group optimization.A new integrated dynamic scheduling algorithm that is based on group optimization, called GOIDSH, is developed to schedule a set of tasks in real-time heterogeneous systems. This algorithm mainly includes three parts are called selecting a group of tasks and making target function as well as a new scheduling strategy based on group optimization. GOIDSH is based on heuristic searching and implements the integrated schedule in real-time heterogeneous systems with uniform form successfully. GOIDSH improves the scheduling success ratio by introducing a new task assignment policy and a Qos (Quality of Service) degradation policy for soft real-time tasks.The kernel meaning of GOIDSH is that: Starting with an empty partial schedule, each step of the search in GOIDSH extends the current partial schedule with a group tasks selected from all pre-scheduling tasks. Each task in the group is assigned one processor before its deadline while its resource requirements can be satisfied. In GOIDSH, firstly one group tasks must be selected from all pre-scheduling tasks based on a special rule, which can ensure that a resource could not be visited by other tasks if one task in the group need to visit it. Secondly an object function matrix need to be created by synthesizing various characteristics of each task in the group which is running on each processor, then the problem is translated into the unbalanced assignment problem and solved.In order to evaluate the performance of GOIDSH, an intensive simulation is made to analyze the impact of several task parameters on its scheduling success ratio and degradation ratio of soft real-time tasks as well as QoS(quality of service) of degraded soft real-time tasks. In the simulation, new priority sort rule, called Highest Value First, is represented to sort task queue, which is defined through follow ways:①Earliest Deadline Highest Value②Most Resources Highest Value③Most Exclusive Access Highest Value④Least Slack Highest Value⑤The value of hard real time task is higher than that of soft real time task if there are no other different conditions in them.The simulation results show that GOIDSH not only has successfully solved integrated dynamic scheduling of hard and soft real-time tasks in real-time heterogeneous systems, but also can offer superior scheduling success ratio and better QoS of soft real-time tasks than that of prior algorithms, such as myopic algorithm and thrift algorithm.