一种基于有向无环图的主路径填充调度方法

摘要

本发明提供一种基于有向无环图的主路径填充调度方法，能够充分利用主路径子任务所在的处理器，减少对其他处理器的占用。所述方法包括：针对每个任务，根据DAG图中子任务的出入度大小选取主路径；将任务划分为并行部分和串行部分，根据任务划分结果，确定任务的最大完成时间和任务的最小完成时间；判断任务的完成截止期限是否大于等于任务的最小完成时间且小于任务的最大完成时间；若是，则计算任务可填充时间，将任务可填充时间分配给每个并行部分，得到每个并行部分可使用的时间冗余；根据得到的每个并行部分可使用的时间冗余，将每个并行部分中的某并行子任务填充到主路径子任务所在的处理器执行。本发明适用于计算机多处理器调度领域。