【作者】 李建国；

【导师】 陈松乔； 王建新；

【作者基本信息】 中南大学 ， 计算机应用技术， 2006， 博士

【摘要】 实时异构系统已被广泛应用在航空航天、工业控制、电讯行业、图像处理以及Internet应用等诸多领域。在这些应用中，存在大量的硬、软实时任务共存的情况，对实时异构系统的集成动态调度模型与算法的研究具有重大理论和实际意义。本文对实时异构系统的集成动态调度问题进行了深入的研究，提出了一种实时异构系统的集成动态调度模型，基于这种模型，提出批优化的调度策略和批任务在处理器上运行的目标函数构造原则。在此基础上，提出了一种基于分批优化的实时异构系统的集成动态调度算法——GOIDSH算法。本文针对实时异构多任务调度的特点，采用集中式调度模型；提出软、硬实时任务形式化描述非精确计算的统一任务模型，清晰地描述实时任务的特点。系统任务描述简单，节省存储空间，为实现基于批优化的集成动态调度打下基础。论文提出了一种新的实时异构系统的集成动态调度算法——基于分批优化的集成动态调度算法(GOIDSH算法)。该算法以启发式搜索为基础，主要包括任务分批、构造目标函数和基于批优化的调度策略三大部分，采用统一形式完成了实时异构系统的集成动态调度。同时，在构造目标函数时，算法还引入软实时任务服务质量(Ouality of Service，Qos)降级策略来提高调度成功率。GOIDSH算法的核心思想是：在每次扩充当前局部调度时，首先按一定规则在待调度的任务集中选取一批任务组成任务子集，保证所选取的任务子集中某一任务对某个资源有访问需求时，子集中的其它任务不能对该资源有访问需求。然后，综合各种因素，对该批任务中的每项任务在每个处理器上的运行构造目标函数，将问题转化为非平衡指派问题，利用非平衡指派问题直接解法对任务进行优化分配，一次性为这些任务分配一个处理器或为每个处理器分配一项任务，使得这种分配具有最好的“合适性”，增大未被调度任务的被成功调度的可行性。论文通过仿真和模拟，从调度成功率、软实时任务的降级比率(DR)和被降级软实时任务的服务质量(QoS)三个方面，验证了GOIDSH算法的有效性及其调度性能。在仿真实验时，提出了一种按如下顺序设定的价值最高最优先的任务队列排序原则：①任务的截止期越近，其价值越高；②任务需要访问的资源越多，其价值越高；③任务要需访问的资源中，互斥方式的访问越多，其价值越高；④任务的空闲时间越短，其价值越高；⑤相同情形下，硬实时任务的价值高于软实时任务的价值。仿真实验结果表明，基于分批优化的实时异构系统集成动态调度算法(GOIDSH算法)不仅成功地解决了实时异构系统中硬、软实时任务的集成动态调度问题，而且还有效地提高了调度成功率，确保了软实时任务具有良好的服务质量，与其它相关算法，如传统的近视算法和节约算法相比较，具有明显优势。更多还原

【Abstract】 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.更多还原