摘要
提出了一种实时异构系统的动态分批优化调度算法,该算法采用的是在每次扩充当前局部调度时,按一定规则在待调度的任务集中选取一批任务,对该批任务中的每项任务在每个处理器上的运行综合各种因素构造目标函数,将问题转化为非平衡分配问题,一次性为这些任务都分配一个处理器或为每个处理器分配一项任务,使得这种分配具有最好的“合适性”,以增大未被调度任务的可行性.这种方法有效地提高了算法调度成功率.同时,为了评估该算法的性能,对其进行了大量的模拟,分析了一些任务参数的变化对算法调度成功率的影响,并与老算法的调度成功率进行了比较.模拟结果显示,新算法优于老算法.
A dynamic scheduling algorithm that is based on group optimization is developed to schedule a set of tasks in real-time heterogeneous systems. The tasks are characterized by worst case computation times, deadlines, resources requirements, and so on. Starting with an empty partial schedule, each step of the search in the 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, in the 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. To evaluate the performance of the algorithm, an intensive simulation is made to analyze the impact of several task parameters on its scheduling success ratio. The simulation results show that the algorithm can offer superior scheduling success ratio than that of prior algorithms.
出处
《计算机学报》
EI
CSCD
北大核心
2006年第6期976-984,共9页
Chinese Journal of Computers
基金
国家自然科学基金(90304010
60433020)资助
关键词
多处理器
实时系统
动态调度
算法
优化
multiprocessor
real-time systems
dynamic scheduling
algorithm
optimization
