实时多处理器系统的动态分批优化调度算法  

Dynamic Optimization Group by Group Scheduling Algorithm for Real-Time Multiprocessor Systems

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

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

出　　处：《小型微型计算机系统》2005年第1期84-89,共6页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目 (90 3 0 40 10 )资助

摘　　要：提出了一种实时多处理器系统的新的高效动态调度算法——动态分批优化调度算法 ,该算法突破了以往算法中一次只安排一项任务的做法 ,采用在每次扩充当前局部调度时 ,按一定规则在待调度的任务集中选取一批任务 ,对该批任务中的每项任务在每个处理器上运行构造目标函数 ,将问题转化为非平衡分配问题 ,一次性为这些任务都安排一个处理器或为每个处理器安排一项任务 ,使得这种安排具有最好的“合适性”,以增大未安排任务的可行性 .这种方法极大地提高了算法的调度成功率 .同时 ,为了研究该算法的有效性 ,对其进行了大量的模拟 ,分析了一些任务参数的变化对算法调度成功率的影响 ,并与节约算法的调度成功率进行了比较 .模拟结果显示 ,在节约算法的调度成功率小于 10 %的约束条件下 ,该算法的调度成功率大于 90 % ,说明新算法的优势是非常明显的 .Hard real-time systems require both functionally correct executions an d results that are produced on time. So dynamic scheduling algorithm is an impor tant component of these systems, the scheduling success ratio is the most import ant metric for these systems. In this paper, a high efficient dynamic scheduling algorithm is developed to schedule a set of tasks on real-time multiprocessor s ystems. The tasks are characterized by worst case computation times, deadlines, and resources requirements, starting with an empty partial schedule, each step o f the search extends the current partial schedule with a selected group of tasks based on a special rule from the set of the tasks yet to be scheduled. For the tasks of the group, creating a object function which synthesizes various charact eristics of each task in the group running on each processor, translating into t he unbalanced assignment problem, using a direct method of solving the unbalance d assignment problem ,a partial scheduling is found that each task of the group selected one processor in it, or each processor selected one task from the group in it. The proposed algorithm improves the scheduling success ratio very much. To evaluate the performance of the new algorithm, an intensive simulation study is made to analyze the impact of several task parameters on its scheduling succe ss ratio and compare its performance to thrift algorithm .The simulation results show that the scheduling success ratio of our new scheduling algorithm can be m ore then 90 percent while the thrift algorithm is lower then 10 percent present under the same restriction conditions, the performance of the new algorithm is better than that of the thrift algorithm.

关 键 词：多处理器 实时系统 动态调度 调度成功率 算法 优化 

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