论文部分内容阅读
近年来,随着多核平台在市场上的激增,研究热点逐渐转移到执行复杂、计算密集型的任务上,而多核处理器的复杂性往往会使任务行为不统一、不可预测,变化性极大。由于许多任务间可能存在约束性依赖关系,任务分配变得不协调,导致互相等待而错过期限超时。因此,基于独立任务的传统实时任务调度理论面临着巨大的挑战,考虑到依赖任务集合的调度算法越来越成为研究的新方向。本文在分析和研究国内外现有多核平台实时任务调度算法的基础上,在分区调度和全局调度之间找到了折中点,提出了一种基于任务拆分的多核平台实时任务调度的策略TDTD/TS (Tree Dependent Task Dispatching/Task Splitting)并且设计和实施了该策略的算法。该策略构建于多核平台上的混合实时任务(依赖和非依赖任务)之上,鉴于实时应用中严格时间保证的共性需求,综合考虑任务的动态性和依赖性对系统性能的影响。采用层次调度的方式设计本方案,具体方法分为两个阶段：TDTD (TreeDependent Task Dispatching,多叉树依赖任务分配)和TDTS (Tree Dependent Task Split,多叉树依赖任务分裂)。TDTD将依赖任务转换成一系列的连续作业,通过多叉树任务模型获取相互关联的子任务路径,以及相应的最后期限,对任务分配,建立任务表；TDTS算法中,本地调度程序会根据任务表来分配给任务处理器内核使用权,空闲等待状态的依赖任务进行分裂,所有被阻止的子任务抢占CPU立即执行保证期限。与已有算法相比,本算法具有明显优势,任务集合对处理器利用率边界可达到69.31%。通过仿真软件gem5和实验机上进行性能测试,并与已有算法进行对比,对协议进行可调度性和实时性QOS性能分析,在时间比率、调度下界比SLR (Schedule Length Ratio)和加速比Speedup方面表现优异,结果证明TDTD/TS提供了更高的效率和扩展性,具有相对的优越性。