满足偏序约束的在线调度  

On-line schedule with precedence constraints satisfying

作　　者：赵明[1,2] 赵海[1] 张浩华[1] 邹勇[1] 

机构地区：[1]东北大学信息科学与工程学院,沈阳110004 [2]沈阳建筑大学信息与控制工程学院,沈阳110168

出　　处：《计算机工程与应用》2011年第12期43-45,58,共4页Computer Engineering and Applications

摘　　要：具备偏序关系的实时调度要求调度算法产生的执行序列既要满足任务的实时约束,又要满足任务间执行的偏序约束。基于并行拓扑排序,提出一种新的在线调度算法,该算法通过同时考察任务间执行的串行性和并行性来进行优先级设置,能够处理释放时间任意的任务集。给出该算法的原理和设计,并通过示例分析和比较对算法进行验证。Real-time scheduling with precedence constraints needs that scheduling sequence produced by algorithm satisfies not only real-time constraints of every task,but also precedence constraints between tasks.Based on parallel topological sort, this paper presents a new on-line scheduling algorithm wich can set priority of task considering serial property and parallel property of task execution.This algorithm can deal with tasks with random release time.The priciple and design of the algorithm are preseneted and example is shown to prove the algorithm.

关 键 词：实时调度 偏序约束 拓扑排序 

分 类 号：TP316.2[自动化与计算机技术—计算机软件与理论]