一种批优化调度策略的实时异构系统的集成动态调度算法  

An Integrated Dynamic Scheduling Algorithm with Scheduling Strategy in Real-time Heterogeneous Systems

作　　者：鲁志辉[1] 李建国[2] 陈松乔[2] 王建新[2] 

机构地区：[1]湖南工业职业技术学院信息工程系,湖南长沙410007 [2]中南大学信息科学与工程学院

出　　处：《小型微型计算机系统》2008年第3期461-468,共8页Journal of Chinese Computer Systems

基　　金：国家自然科学基金资助项目(90304010)资助

摘　　要：针对实时异构多任务调度的特点,提出了软、硬实时任务形式化描述非精确计算的统一任务模型,在此基础上,提出了一种基于批优化调度策略的实时异构系统的集成动态调度算法.该算法以启发式搜索为基础,引入软实时任务服务质量降级策略,在每次扩充当前局部调度时,按制定的规则选取一批任务,计算其在各处理器上运行的目标函数,采用指派问题解法对任务优化分配.模拟实验表明,该算法与同类算法相比,提高了调度成功率.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. Basing on the model and heuristic searching, a new integrated dynamic scheduling algorithm that is based on group optimization, is developed to schedule a set of tasks in real-time heterogeneous systems. Starting with an empty partial schedule, each step of the search in our algorithm 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. This algorithm, 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. The experimental results demonstrate that our algorithm can offer superior scheduling success ratio than that of prior algorithms.

关 键 词：实时异构系统 集成动态调度 任务分配 调度优化 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]