论文研究-移动网格环境下可靠任务调度研究.pdf

所需积分/C币:10 2019-09-07 01:50:53 508KB .PDF
收藏 收藏
举报

移动网格的资源环境具有很高的动态性,在任意时刻可能发生资源加入、退出、故障、移动等。采用任务复制策略实现对资源不可靠性的容错。用weibull分布刻画资源的可靠性,建立任务复制模型;形式化描述了基于复制策略的独立任务调度问题,给出调度目标和约束条件;通过遗传算法解决调度问题。仿真结果表明,调度算法具有良好的可扩展性,调度性能与资源可靠性呈线性关系。
1442012,48(20) Computer Engineering and Applications计算机工程与应用 务T{1m1,…,T}分别分配到资源{RaR1,…,Rn}4,2适应度函数 上运行,其中响应时间最快的是T,S∈[0,d,对应资 TRS-GA调度的日标是最小化完成时间和资源 源是R,s∈[0,d],则其余资源对任务T已执行的部浪费,因而定义两个适应度函数来评价每个个体的 分造成资源浪费,设m8表示任务T在资源R上质量。时间适应度函数Fm估计每个个体的完成时 造成的浪费。用WR表示任务T成功执行后产牛的间,定义如下 资源浪费,则积=∑w。总的资源浪費是所有 time MAX (max( min 2 resp (7) 其中s4是任务T在染色体f中的起始索引;Tx 任务的WR之和,即WR=∑WR2。因此基于复制策 =1 是预设的正数,远远大于可能的调度时间。资源浪费 略的独立任务调度问题的优化目标是最小化所有任适应度函数f估计每个个体的资源浪费,定义如下 务的响应时间,最小化资源的浪费,同时要满足用户 提出的服务质量要求(用任务运行的成功概率表 FH()=WRMx-②(∑ r/min T resp )(8) esp 其中c是染色体f中第个编码对应资源的处理能 min t max T omp t≠s 力;WRMx是预设的正数,远远大于可能的资源浪费。 min wr ∑WR=∑ (6) 43遗传操作——交叉、变异和选择 l=Ik∈[0,d s..1-PF1≥S},=1,2, 在典型的两点交叉操作中,两个交叉点随机选 择,通过交换交叉点之间的部分产生两个新的个体, 4支持任务复制的任务调度遗传算法 TRS-GA在有任务复制的情况下,这种典型交叉操作会产生 基于复制策略的独立任务调度是NP难度问题,不合理调度,因为任务副本数量随着调度资源的变 本文采用遗传算法解决该问题。算法设计的关键化而变化,因而染色体的长度也是变化的。 在于编码和遗传操作要休现上述复制策略。 本文采用改进的交叉算子,称为任务有序交叉 41染色体编码和初始种群 算子,如图2所示。从位置序列中随机选取两个点, 本文采用整数编码方法,每个个休编码后得到然后从任务序列中找到相对应的位置,把两个染色 的染色体包含一个任务序列∫和一个位置序列s。体选中的部分进行交叉。交叉之后还要根据新任务 任务及其副木按自然顺序依次分配到序列f的第k序列的情况修改其对应的位置序列。 项∫,其中的整数对应着任务所映射到的资源 172272 RA。为便于遗传操作,用另外一个位置序列s,表示 染色体中每个任务的起始位置,这个序列用于在后 .2.7273.T、273 TT 面的操作中计算每个任务的副本数量。图1给出了 52 1346 S1247 IRS-GA算法的编码示例初始种群会影响到搜索算 法的质量。如果初始种群对于目标问题更恰当的 话,最后的调度就更接近最优。在建立初始种群时, h1.T.2172.1273.73,2引24,174,2 TIT2 T3IT4 对每个任务随机选取若干个资源,但要满足公式(6) f352313442 1358 中的约束条件。由于每个任务可能有不同数量的副 T1 TT T T|T2,T|7 本,因此每个染色体的基因长度有可能不同。 任务及副本 任务 图2任务有序交叉算子 .T1.272.T2.2T2.3T3,1T41T4 727374 67 变异操作在一定程度上克服了遗传算法的早熟 fl 52 f frf f f 收敛,有利于增加种群的多样性。这里变异算子实 资源索引 任务的起始索引 质上是将某个任务或其副本迁移到另一个资源上执 图1染色体编码小例 行。标准遗传算法的变异算子不能直接用于 杜丽娟,鞠宏军:移动网格环境下可靠任务调度研究 2012,48(20)145 RRS-GA调度算法,因为变异后,任务执行的可靠性出,随着资源可靠性的增加,任务副本数量减小,因 可能会因为资源的改变而不满足要求,因此进行变此有效降低了资源浪费和任务完成时间。 异的候选基因(资源)要满足任务的可靠性要求。设 300 600 任务T的原本或副本在基因对应的资源RA上 响应时间 250 资源浪费 500 运行,任务在该资源上执行的故障率为PF。该基200 400 因被选中进行变异操作则候选基因要满足条15 温100 200 件:PF<PF。PF是该任务在候选基因对应的 50 100 资源上运行的故障率。 经过交叉和变异之后,由当前种群产生新的个 00.10.20.30.40.50.60.70.80.910 资源可靠性 体。基于复制策略的任务调度是多日标优化问题, 图4完成时间和资源浪费随资源可靠性的变化 本文用向量形式评价的适应值来产生下一代,而不 是使用标量适应度值来评价染色体。对于有两个目5结论 标的给定问题,每代中的选择是一个循环,重复2次 本文针对移动网格资源数量多、性能异构、网络 每次循环依次使用一个目标,每次循环使用这个目延迟大等特点,提出基于任务复制的任务调度策 标选出下一代中的一部分个体。 略。根据资源的历史信息用 Weibull分布刻画资源的 44仿真实验及分析 可靠性,建立任务复制模型;对独立任务调度问题进 用VC艹+60仿真TRSA算法。假设10-100个行形式化描述,以最小化跨度和最小化资源浪费为 任务在5个资源上进行分配。资源的可靠性服从调度目标,以用户提出的服务质量(用任务成功执行 weibull1分布,参数β=6=2。资源性能在[20,200内的概率度量)为约束条件;通过遗传算法进行求解, 4随机产生;任务在资源上的预期执行时间在5,1001染色体编码的设计和遗传操作中体现了复制策略和4 内随机产生。此外,每个任务的执行成功率都设定调度约東条件。仿真实验表明,提出的调度算法有 为09。仿真的性能指标是任务完成时间和资源浪费良好的可扩展性,调度性能与资源的可靠性呈线性 情况,资源浪费是以资源性能乘以任务已完成部分的关系。 执行时间得到。仿真结果如图3所示,其中每个数据 点取100次实验的平均值。图3分析了任务完成时参考文献: 间和资源浪费随任务数量增加的变化趋势,近似线1 ong-Jun, u L1-Juar. IddIcware framework of mobilc 性增长,表明 TRS-GA调度算法有良好的可扩展性。 grid[C]//Proceedings of Annual Conference of China In stitute of communications 2009 600 6000 [21 Vaithiya SS, Bhanu S M SScheduling tasks in mobile 响应时间 500 资源浪费 5000 grid environment using mobility based resource predic 400 4000 tion[c]/lst International Conference on Parallel Distribut 300 ed and Grid Computing(PDGC2010 ), Solan, 2010: 89-94 雪200 2000 gy [3] Hwang S, Kesselman C Grid workflow: a flexible failure 1000 handling framework for the grid[c]//Proc of 12th IEEE 0102030405060708090100 International Symposium on High Performance Distributed 任务数量/个 Computing(HPDc-12), Los Alamitos, CA, USA. Seattle 图3完成时间和资源浪费随任务数量的变化 Washington. USA: IEEE Computer Societ ess,2003: 126-137. 图4分析了20个任务在5个资源上利用 TRS-GA 算法调度,其任务完成时间和资源浪费随资源可靠4陶永才,石磊可靠的网格作业调度机制计算机应用, 2010,30(8):2066-2069 性的变化情况。资源的可靠性用 weibul分布的参数 [5]陶永才,吴松,石磊网格环境下可靠的可分割作业调度机 β和δ调整。以任务在最大执行时间100内资源故 制[小型微型计算机系统,2011,32(3):407-411 障率小于0001为可靠性近似等于1。从结果可以看 (下转205页)

...展开详情
试读 4P 论文研究-移动网格环境下可靠任务调度研究.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    抢沙发
    一个资源只可评论一次,评论内容不能少于5个字
    weixin_38743602 如果觉得有用,不妨留言支持一下
    2019-09-07
    • 至尊王者

      成功上传501个资源即可获取
    关注 私信 TA的资源
    上传资源赚积分,得勋章
    最新推荐
    论文研究-移动网格环境下可靠任务调度研究.pdf 10积分/C币 立即下载
    1/4
    论文研究-移动网格环境下可靠任务调度研究.pdf第1页
    论文研究-移动网格环境下可靠任务调度研究.pdf第2页

    试读已结束,剩余2页未读...

    10积分/C币 立即下载 >