基于多DAG模型的异构分布式系统任务调度策略研究

发布时间：2021-02-04 04:12

　　近年来,随着通讯与计算机技术的飞速发展,由大规模分布式计算环境搭建的大数据中心平台在电子商务、工业控制、科学计算等领域都有着广泛的应用。其中任务调度策略的优良直接影响着系统的计算效率与质量。近年来针对单个DAG任务（有向无环图）在多个计算资源上的调度问题研究已基本趋于成熟。随着计算机技术的发展与用户需求的不断提升,多DAG共享一组异构计算资源的问题逐渐受到广泛的关注。其中调度公平性与可靠性等相关问题也成为研究的热点。因此本文针对异构分布式计算环境下的多DAG任务调度相关问题进行研究,主要工作与创新点如下:（1）针对多DAG任务调度时的公平性问题进行研究。提出一种针对已有经典公平调度算法Fairness算法进行改进的启发式公平调度算法IFairness算法（Improved Fairness）,该算法在原算法基础上在选择待调度DAG阶段采用一种新的评判指标DAG完成度（Completion Degree）代替原有算法中的剩余Makespan作为DAG选择依据,此外,在计算每个DAG的滞后程度阶段,采用“向后看”一步的原则,解决了某些DAG在前期得不到调度的问题。仿真实验表明,该算法有效提... 

【文章来源】：南京理工大学江苏省 211工程院校

【文章页数】：71 页

【学位级别】：硕士

【部分图文】：

图1.1分布式计算示例图

硕士学位论文基于多DAG模型的异构分布式系统任务调度策略研究391/(1)/2(1)sin(/2)=1()22（4-6）通过1000次对式（4-5）进行计算可得1000个点，这1000个点连成一条曲线，其图如图4.1所示，由图可见，大部分点在0的附近，只有很少量的点远离0。这和Lévyflight的特性是相符合的。图4.1Lévyflight曲线图[91]综合式（4-2）～（4-6），可知在Lévyflight随机游走中，采用以下的更新公式：1,,01/,,()||titititbestuXXXXv（4-7）在变异阶段，在按发现概率ap丢弃差的位置以后，采用式（4-7）产生相同数量的位置代替丢弃的位置。1,,,,()tititjtkXXrXX（4-8）其中，r是缩放因子，是区间(0,1)的均匀分布的随机数，t,jX和t,kX表示第t代的两个随机解。从以上的描述可以看出，选择阶段实际上是一个变异的过程，即在搜索阶段结束后，随机的选择三个布谷鸟个体，然后由这三个个体按照式（4-8）形成一个新的布谷鸟个体，如果按发现概率ap需要丢弃k个布谷鸟，则需要按照式（4-8）形成k个新的布谷鸟个体


本文编号：3017701