基于DAG模型的CPS分布式任务调度算法研究

发布时间：2024-02-15 06:56

　　分布式计算环境中所处理的执行事件大多由不同信息源所产生,并具有数据量大、结构复杂和分布不均等特征。但是对于同一信息源产生的事件组,事件与事件间大多存在顺序约束的关系,使用有向无环图(Directed Acyclic Graph,DAG)可以准确模拟具有依赖关系的计算机任务在分布式环境中的处理流程。本文首先介绍了信息物理系统、CPS分布式系统和DAG模型的发展历史和研究现状,之后对现有的相关经典DAG任务调度算法和执行目标进行描述。叙述完毕后分别针对不同调度环境中的问题,提出本文的研究工作如下:(1)首先针对同构多处理器分布式环境,发现单调速率算法和最早截止时间优先算法在适用于DAG周期任务模型时,存在通信开销较高和没有涉及任务间依赖关系的问题,提出了一种允许延迟时间较短优先(ADTST)算法,该方法在考虑实时性以及DAG中工作节点间复杂依赖关系的需求上进行适配,使系统整体性能得以提升。(2)其次针对异构多处理器分布式环境,较大规模任务在该环境中调度存在处理器利用率较低问题,提出一种基于最早完成时间的拉伸调度(A-HEFT)算法,该算法既可保证在时限内对DAG任务进行有效调度,又可提高处...

【文章页数】：77 页

【学位级别】：硕士

【部分图文】：

图3.4平均任务完成率

第三章同构分布式环境中的DAG周期任务调度算法25图3.4平均任务完成率图3.5核间通信次数3.6本章小结本章提出一种具有依赖关系的任务队列(Dependenttaskqueue，DTQ)模型，然后针对该模型中的单行任务队列和周期任务的任务属性，将延迟时间较短优先(Probabl....

图3.5核间通信次数

第三章同构分布式环境中的DAG周期任务调度算法25图3.4平均任务完成率图3.5核间通信次数3.6本章小结本章提出一种具有依赖关系的任务队列(Dependenttaskqueue，DTQ)模型，然后针对该模型中的单行任务队列和周期任务的任务属性，将延迟时间较短优先(Probabl....

图5.2平均任务完成率

第五章异构分布式环境中的DAG任务容错调度算法49与MaxRe算法做对比试验。该仿真软件采用Java.Random()随机函数对工作节点执行失败损失价值量、DAG任务截止期限在合理范围区间间的随机赋值，并在仿真器中选择在3个处理器上进行仿真调度。如图5.2和图5.3给出了FT-L....

图5.3价值损失量

第五章异构分布式环境中的DAG任务容错调度算法49与MaxRe算法做对比试验。该仿真软件采用Java.Random()随机函数对工作节点执行失败损失价值量、DAG任务截止期限在合理范围区间间的随机赋值，并在仿真器中选择在3个处理器上进行仿真调度。如图5.2和图5.3给出了FT-L....

本文编号：3899411