（计算机应用技术专业论文）基于主从备份的云计算容错调度算法研究.pdf

o ， 。 基于主从备份的云计算容错调度算法研究 信延迟的依赖任务当中。 ( 3 ) 在同步调度错位技术限制备份任务所能映射的处理机基础 上，运用边界调度概念得出两个改进的算法：最小备份成本调度算法 m r c a 和备份任务最早完成时间算法b o s a 。它们分别以备份成本最 小化和备份任务最早完成为主要目标。 ( 4 ) 使用新的通信模型进行处理机之间通信，在备份成本最小 化和备份任务最早完成之间寻求平衡点，得到备份任务优化调度算 法。该算法弥补了最小备份成本调度算法和备份任务最早完成时间算 法只单方面考虑成本或时间的缺陷。 最后通过模拟实验将上述算法与传统算法a s a p 、a l a p 和e f r d 分别从任务拒绝率、备份成本、响应时间三方面进行比较。在任务拒 绝率方面，算法c a s a l 比传统算法a s a p 和a l 心都低；算法m r c a 在独立任务调度中比e f r d 和a s a p 的拒绝率更低；算法b f f a 在调 度依赖任务中比算法e f r d 和a s a p 的接受率更高：而算法b o s a 比 基于主从备份的云计算容错调度算法研究 i 己e s e a r c ho n p r i m a i 之y ，- b a c k u pb a s e df a u 工，t t o l e ra n t i i l lll ij i l l i lli ii iiiil 17 3 618 8 s c h e d u l i n ga l g o r i t h m sf o rc l o u dc o 田u t i n g a bs t r a c t w i t ht h ed e v e l o p m e n to ft h ei n t e m e t ，t h ed a t at r a n s m i s s i o ns p e e dc o n s t a n t l y c o n t i n u e st oi m p r o v ea n dt h en u m b e ro fm a c h i n e sc o n n e c t e dt ot h ei n t e r a c tb e c o m e s m o r ea n dm o r et r e m e n d o u s c u s t o m e r s d e m a n d so nt h eh i 曲- c a p a c i t ya n d l l i g h - d e n s i t yc o m p u t i n ga r er i s i n g s oc l o u dc o m p u t i n gw h i c hh a sl o w e rp r i c e sa n da s u p e r - c o m p u t i n gc a p a c i t ya n de f f i c i e n tr e s o u r c eu t i l i z a t i o nc a m ei n t ob e i n g w i t ht h e p r o d u c t i o no fc l o u dc o m p u t i n gs y s t e m s ，t h ef a u l t t o l e r a n tc a p a b i l i t yo fs y s t e mh a s b e c o m ei n c r e a s i n g l yi m p o r t a n t i nt h i s p a p e r , t h em a i ns t u d yi s f a u l t t o l e r a n t s c h e d u l i n ga l g o r i t h m so f c l o u dc o m p u t i n gb a s e do np r i m a r y - b a c k u pt e c h n i q u e t h em a i nw o r ko ft h i sa r t i c l ei n c l u d e st h ef o l l o w i n ga s p e c t s ： f i r s t l y , w ei n t r o d u c ean e wm e t h o df o rt h ed i v i s i o no f t a s k sa n de n d u ee a c ht a s k w h i c hj u s ta r r i v e dw i t hak e yd e g r e e t h e s et a s k sa r ed i v i d e di n t om i s s i o n - c r i t i c a la n d n o n e m e r g e n c yt a s k s w em a k eu s eo fa s a p ( a ss o o na sp o s s i b l e ) a l g o r i t h mt o s c h e d u l et h em i s s i o n c r i t i c a lp r i m a r yt a s ka n da l a p ( a sl a t e ra sp o s s i b l e ) a l g o r i t h m s c h e d u l et h en o n - e m e r g e n c yt a s k o nt h eb a s i so fa n a l y z i n gt h ec h a r a c t e r i s t i c so f t h e s et w oa l g o r i t h m s ，w er e c o v e ran e wa l g o r i t h mc a l l e dc a s a l ( i n t e g r a t e da s a p a n da l a p ) s c h e d u l i n ga l g o r i t h m w h e nt w oo rm o r ep r o c e s s o r sa r ef a i l u r ei nac e r t a i np e r i o dt i m e ，i no r d e rt o r e d u c et h i sc a s ei n f l u e n c i n gt h er e s u l t so ft h ei m p l e m e n t a t i o no ft h et a s k ，p u tf o r w a r d an e wb a c k u pt a s ks c h e d u l i n gt e c h n i q u ec a l l e ds y n c h r o n i z a t i o ns t a g g e r - l o c a t i o n s c h e d u l i n gt e c h n i q u e t h i st e c h n i q u et a k e si n t oa c c o u n t n o to n l ya l lp r e t a s k sb u ta l s o t h e s et a s k sw h i c ha r ei s o c h r o n o u sw i t ht h ec u r r e n tt a s kt ol i m i tw h e r et h eb a c k u po f c u r r e n tt a s kc a nb es c h e d u l e d a n da p p l yt h et e c h n i q u et oi n d e p e n d e n tt a s k s ， i i i 基于主从备份的云计算容错调度算法研究 d e p e n d e n tt a s k sa n dd e p e n d e n tt a s k sw i t hc o m m u n i c a t i o nd e l a y s a f t e rt h es y n c h r o n i z a t i o ns t a g g e r - l o c a t i o ns c h e d u l i n gt e c h n i q u eg i v e sc o n s t r a i n t s o ft h eb a c k u pt a s k sw h e r ec a l lm a p ，a p p l yt h ec o n c e p to ftb o u n d a r ys c h e d u l e st og a i n t w os c h e d u l i n ga l g o r i t h m sw h i c ha let h em i n i m u mr e p l i c a t i o nc o s ts c h e d u l i n g a l g o r i t h ma n dt h ee a r l i e s tc o m p l e t i o nt i m ea l g o r i t h mf o rb a c k u pt a s k s t h e yc o n s i d e r r e p l i c a t i o nc o s t sm i n i m i z e da n dt h eb a c k u po fc u r r e n tt a s ka tt h ee a r l i e s tc o m p l e t i o n a st h em a i no b j e c t i v e ，r e s p e c t i v e l y i nt h i sp a p e r , w eu s e an e wc o m m u n i c a t i o nm o d e lf o rc o m m u n i c a t i o nb e t w e e n t h ep r o c e s s o r s a f t e rf i n d i n gab a l a n c eb e t w e e nr e p l i c a t i o nc o s tm i n i m i z e da n dt h e e a r l i e s tc o m p l e t i o nt i m eo ft h eb a c k u pt a s k ，w eg e tt h eb a c k u pt a s k so p t i m a l s c h e d u l i n ga l g o r i t h m t h i sc o m p e n s a t e st h ed r a w b a c kf o rt h em i n i m u mr e p l i c a t i o n c o s ts c h e d u l i n ga l g o r i t h ma n dt h ee a r l i e s tc o m p l e t i o nt i m ea l g o r i t h mf o rb a c k u pt a s k s w h i c ho n l yc o n s i d e rt h ec o s to rt i m e f i n a l l ye x e r t i n gt h r o u g hs i m u l a t i o na n a l y s i so fe x p e r i m e n t a ld a t a , w ef i n dt h e a d v a n t a g e so ft h ea b o v e m e n t i o n e da l g o r i t h m st ot r a d i t i o n a la l g o r i t h m sa s a p , 入乙陋 a n de f r d t h ec o m p a r a b l ec r i t e r i o n sa r es e p a r a t e l yf r o mt h et a s kr e j e c t i o nr a t e ，t h e r e p l i c a t i o nc o s ta n dr e s p o n s et i m e i nt a s kr e j e c t i o nr a t e ，c a s - a l i sl o w e rt h a na s a p a n dk l 姣m r c ai sa l s ol o w e rt h a ne f r da n da s a po ni n d e p e n d e n tt a s k 。i nt h ea l l a l g o r i t h m s ，t h eb o s a i st h eb e s t i nt h er e p l i c a t i o nc o s t ，a l lt h r e ea l g o r i t h m sp r o p o s e d i nt h i sp a p e ra r em u c hl e s st h a ne f r da n da s a p i nt h er e s p o n s et i m e ，a l lt h r e e a l g o r i t h m sp r o p o s e di nt h i sp a p e ra r es h o r t e rt h a ne f r da n da s a po ni n d e p e n d e n t t a s k ，w h i l eo nd e p e n d e n tt a s ka l la l g o r i t h m sa r et h es a m ee x c e p te f r d k e y w o r d s ：c l o u dc o m p u t i n g ；s y n c h r o n i z a t i o n s t a g g e r - l o c a t i o ns c h e d u l i n g ； b a c k u po v e r l o a d i n g ；r e p l i c a t i o nc o s t ；r e s p o n s et i m e ；b o u n d a r y s c h e d u l e i v 基于主从备份的云计算容错调度算法研究 目录 摘要i a b s t r a c t i i i 目j i 毛1 0 r 第l 章绪论l 1 1 选题背景和意义l 1 2 国内外研究现状3 1 3 当前研究存在的问题4 1 4 本文的内容组织5 第2 章主任务调度算法6 2 1 基本定义6 2 2a s a p 调度算法7 2 3a l a p 调度算法7 2 4c a s a l 调度算法8 2 5 实例分析一1 0 第3 章备份任务调度基础1 4 3 1 任务概述1 4 3 1 1 独立任务。1 4 3 1 2 有依赖关系的任务1 5 3 1 3 通信延迟依赖任务。1 5 3 2 错误模型。1 5 3 3 任务备份技术1 7 3 3 1 备份技术。1 7 3 3 1 1 一对多备份技术1 7 3 3 1 2 一对一备份技术1 9 3 3 2 备份重载技术1 9 3 3 3 同步错位调度技术2 0 3 4 资源回收2 l 第4 章备份任务调度算法。2 2 4 1 基于独立任务调度算法。2 2 4 1 1 符号介绍2 2 4 1 2 任务响应时间2 2 4 1 3 备份成本2 2 4 1 4 备份任务调度限制条件2 3 4 1 5 边界调度2 3 4 1 6 最小备份成本调度算法( m r c a ) 2 6 4 1 7 备份任务最早完成时间算法( b f f a ) 2 8 4 2 基于依赖任务调度条件3 1 4 2 1 直接前置任务的影响3 1 v 基于主从备份的云计算容错调度算法研究 4 2 2 所有前置任务的影响3 3 4 2 3 前置任务及同步任务的影响一3 5 4 2 4 实例分析3 7 4 3 基于通信延迟要求的依赖任务调度条件3 8 4 3 1 通信模型3 8 4 3 2 主备份任务调度策略4 0 4 3 3 备份任务优化调度算法( b o s a ) 4 1 第5 章仿真实验4 4 5 1 性能指标4 4 5 2 模拟参数4 5 5 3 实验结果与分析4 5 5 3 1 拒绝率4 5 5 3 2 备份成本4 8 5 3 3 响应时间4 9 第6 章总结与展望5l 6 1 总结5 l 6 2 展望未来5 2 参考文献5 3 附录l 攻读硕士期间发表的论文5 6 附录2 攻读硕士期间参加的课题和项目5 6 致谢一5 7 独创性声明。5 8 基于主从备份的云计算容错调度算法研究 第1 章绪论 随着计算机计算能力的迅速增长，互联网络的普及和高速网络成本的大幅度 降低以及传统计算方式和计算机的使用方式的改变，云计算已经逐渐成为超级计 算发展的一个重要趋势。 1 1 选题背景和意义 什么是云计算? 云计算就是使计算作业分布在大量的分布式计算机上，通过 网络中央数据中心，企业或用户能够将资源切换到需要的不同应用上，根据需求 访问不同的计算机和存储系统。从本质上来讲，云计算是指用户终端通过远程连 接，获取存储、计算、数据库等计算资源。这就意味着计算能力也可以作为一种 商品进行流通，就像水电一样，取用方便，费用低廉。云计算的未来发展蓝图是： 在未来，只需要一台简单客户机( 手机、笔记本电脑等) ，就可以通过网络服务 来实现我们需要的一切，包括超级计算这种大型应用，从而避免了大量的硬件投 资。从这个角度而言，终端用户才是云计算的真正拥有者。云计算的主要思想是 把互联网上的各种计算资源整合在一起，例如p c 、手机、掌上电脑及其他移动 终端，实现计算的无处不在、无时不在。“云”除了具备超级计算能力外，它还是 一个超级存储仓库，可以提供无限量的存储空间。云计算的经济效用非常耐， 它将是未来发展的卓越科技之一【2 】。 当前，云计算的发展势头凶猛，应用范围广阔口, 4 1 。g o o g l e 5 1 于2 0 0 7 年1 0 月在全球宣布了云计划。i b m 6 】于2 0 0 7 年8 月推出b l u ec l o u d 计划，2 0 0 8 年8 月，i b m 宣布将斥资3 6 亿美元在美国北卡罗来纳州建立云计算数据中心。 m i c r o s o f t 7 】推出了微软云计算平台- w i n d o w sa z u r e ，它为软件提供了加速计 算服务。a m a z o n 于2 0 0 7 年向开发者开放了名为“弹性计算机云 的服务，让 中小软件公司可以按需购买亚马逊数据中心的处理能力。使用弹性计算云( e c 2 ) 1 8 1 和简单存储服务( s 3 ) 【9 1 为企业提供计算和存储服务。不到两年时间，a m a z o l l 上的注册开发人员达4 4 万人，据统计，a m a z o n 与云计算相关的业务收入已达l 亿美元。云计算是a m a z o n 增长最快的业务之一【1 0 】。 基于主从备份的云计算容错调度算法研究 云计算【1 1 , 1 2 1 是分布式计算、并行计算和网格计算的发展。作为下一代并行分 布式计算，聚合了各种不同的离散资源，解决各种在科学、工程和经济等方面的 大规模并行应用。大规模云计算系统使用的资源具有高度动态性和异构性，资源 环境所固有的不可靠状态，使得云计算平台较传统的计算平台有更大的出错机 率。云计算作为网格计算的发展，虽然它的规模更大，但是它仍存在一些网格计 算，甚至是其它所有计算系统都存在的问题应用程序处理失败。为此，研究 高效率的云计算资源调度算法，尤其是研究具有容错机制和失败容忍能力的可靠 云计算服务调度策略，对切实提高云计算服务的服务质量具有重要意义。 随着信息技术的发展，计算机系统的不断升级，网络规模呈几何级数增长， 现代信息的计算量变得越来越庞大和复杂，利用单台昂贵的超大型服务器已经不 能满足用户的需求，寻求廉价而计算功能强大的服务平台是迫在眉睫。在这样的 背景环境下，云计算系统应运而生，功能庞大的云计算系统可以解决许多以前解 决起来非常困难的科学问题。 自从计算机诞生以来，计算机硬件故障或软件错误就不可避免地伴随着，为 了解决这一问题，人们试图做各种各样的努力，希望找到一种技术能够容忍错误 的发生而不会影响程序运行结果，这就产生了容错技术( 容错技术：简而言之， 容忍故障发生技术，当处理机出现某些不可避免的硬件故障或软件错误时，系统 仍能正常执行规定的一组应用程序，或者说该程序不会因系统中的故障而被迫中 止或修改，并且执行结果也不包含系统中故障所引起的差错) 。容错技术是从系 统结构层次来提高系统的可靠性，与排错技术相互补充，构成高可信度的系统。 一个云计算服务本质上是一个分布式应用，其中大部分服务又是并行多处理 应用，也就是并行的多个子任务利用地理分散的多个计算资源或存储资源共同完 成一个功能性任务。对单独云计算服务而言，不同的资源分配策略产生不同时间 ( 或费用) 成本。在理想状态下，每一个应用程序可以分成n 个独立的任务，每 个任务运行在系统的一个处理机上，运行时间随着n 的增加而减少。对多处理机 系统而言，可靠性是衡量系统能否完成整个应用程序的重要指标。即使存在错误， 系统也能得到正确的结论，称此系统具有容错性。随着处理机数量的增加，处理 机失败的概率也会随之增加。因此，如何在云计算系统发生故障时，降低故障对 任务正常执行的影响是本文所要研究的重点。 2 基于主从备份的云计算容错调度算法研究 1 2 国内外研究现状 云计算广泛的应用于各个领域，不仅包括需要大型科学计算的国家级部门， 如航天、气象部门，而且很多大公司( 如i b m 、微软、n e c 等) 也开始追捧这 种计算模式，着手引进云计算基础设施架构。由于它的广泛应用前景，当某一个 或多个处理机发生故障或错误时，如何保证整个系统的正常运行并且得到正确的 结果，即选用适当的容错机制，特别是对有着时间、资源和容错需求的任务，如 何保证系统能够按需完成任务，是目前云计算需要研究的。 当前云计算的很多容错机制都是从传统的分布式计算、并行计算和网格计算 等容错机制继承过来的，应该说对于处理机故障，云计算与其它计算系统有许多 相通之处。单独对云计算的容错机制研究目前还很少，下面主要介绍网格计算近 几年来的容错机制研究状况。 近年来，国内外对于处理机故障时独立任务的容错机制有了大量的研究，提 出了各种有效的技术和算法。比如错误恢复中的投票技术【1 3 1 、反转恢复技术 ( r o l l b a c kr e c o v e r y ) t 1 4 1 、主备份调度技术1 5 l 等。传统的大多数容错机制都是基于主 从备份方法的，当云系统发生错误时，要保证当前执行任务的处理机能够输出正 确的结果，就必须在其他处理机上备份这个任务，如果执行主任务的处理机发生 故障，开始执行备份任务。文献 1 6 】提出了一个失效检测服务和一个灵活的错误 处理框架作为网格上的容错机制。大多数容错机制都采用主备份方法 1 5 , 1 6 , 1 7 , 1 8 , 1 9 】。 传统上许多主备份的容错机制都是为每个主任务拷贝多个备份任务，当主任务执 行发生错误，执行多个备份任务中的一个，不过这种机制会消耗大量的空间存储 备份任务及需要大量的各份成本。因此，为了减少独立任务的备份成本，文献 1 5 】 中提出了一种备份重载技术( 详见本文3 3 2 节) 。 在大型云计算系统中，有许多在地理上分散的点聚集共同运行一个作业，而 且错误的发生具有不可预知性，因此容错调度是必要的步骤。在文献 1 7 中介绍 了两种有容错需求的独立任务，一种是错误发生时尽可能短的响应时间，另外一 种是最小的备份任务备份成本。同时提出两个算法，一个是根据备份成本保证最 优化调度备份任务；另一个是以最小完成时间和尽可能低的备份成本为目的调度 备份任务。 但是任务不仅仅是独立的，还有很多具有相互依赖关系，即下一个任务的执 基予主从备份的云计算容错调度算法研究 行依赖于它前面任务的运行结果，比如像直接无环图( d a g s ) 5 2 】一样的依赖关 系任务模型由几十、成千上万的独立任务构成。文献 1 8 ，1 9 中运用优先约束策略 调度任务，考虑了“强主任务”( 假设所有的主任务都能从它们的直接前置任务那 里接受到任务结果) ，因此他们的算法e f r d ( 有效地容错可靠性驱动算法) 仅 考虑了任务的直接前置任务，而不能容忍它们的间接前置任务发生错误。为了解 决这个问题，作者q i nz h e n g 在文章 2 0 】中运用优先约束策略和备份重载方法提 出了新的算法，考虑当前任务的所有前置任务之一发生错误时如何调度任务的备 份任务。在此文中，作者区分了运用主从备份方法调度依赖任务的备份任务时的 两种不同情况及其需要满足的两个限制条件，但是这两个条件会限制依赖任务备 份任务的可靠性和重载效率，为了解决这两方面的问题，文章提出了两个策略来 改进。同时作者根据响应时间和备份成本提出两个新的算法。但是在此文中作者 没有考虑不同处理机之间任务结果通信延迟。在文章 2 1 】中，作者q i nz h e n g 重 新考虑了通信延迟，当处理机存在错误时在云系统中如何安排d a g s 以避免服务 器失败等问题。作者还介绍了通信模型以及提出了子算法，这个算法以不影响响 应时间的情况下最小化备份成本。但是文章 1 7 ，2 0 ，2 1 都是只考虑单个处理机发 生错误时如何调度备份任务，而没有考虑多个处理机在某一个时间段发生故障的 情况如何调度主任务的备份任务。传统算法一尽可能早算法 2 2 ，2 3 1 和尽可能迟算 法【2 4 j 主要是用于调度主任务的，但还不能用于允许备份重载的备份任务调度。 1 3 当前研究存在的问题 一个给定的包含许多独立的或相互依赖子任务的应用程序和一个给定的计 算机集群，如何把这些子任务调度到这些计算机资源( 不考虑容错问题) ，根据 不同的标准，很难达到所有条件都最优化，因此，调度问题对绝大多数应用来说 都是n p 完全问题，只有在少数高度简化的领域中才不是n p 完全的【2 5 】。对于一 般的调度问题而言，由于应用领域的不同而千变万化，这使得调度问题在许多情 况下难以处理，需要使用启发式方法才能在合理时间内完成，但使用了这些启发 式算法又不一定能够求得最优解，一般只能求得满意解。 在传统基于主从备份任务容错调度算法中，大多数运用备份重载技术的调度 算法都是考虑某一时刻发生故障如何调度备份任务的，特意忽略某一时刻多个处 4 基于主从备份的云计算容错调度算法研究 理机同时发生故障的情况，但在实际生活中这种情况是不能忽略的，特别是在大 规模的网格系统和云计算系统中，由成千上万的计算机组成的集群，多台计算机 同时发生故障的情况更是常有发生。在单备份任务( 被动备份) 状态下，这会影 响整个作业的运行结果。但是在多备份任务( 主动备份) 状态下，这又会浪费许 多计算机存储资源，因此，本文的重点是考虑单备份任务状态下，如何处理多个 处理机发生故障的情况。 1 4 本文的内容组织 根据研究内容，本学位论文共分为六章，其内容具体安排如下： 第1 章是绪论。主要是介绍选题背景和意义，国内外研究现状及当前云计算 容错调度研究存在的问题，最后是全文结构安排。 第2 章介绍了两个经典算法a s a p 算法和a l a p 算法，并在它们的基础上 得到新的算法c a s a l 调度算法。通过实例分析它们的具体调度情况。 第3 章介绍了备份任务调度的基础知识。包括任务的分类，错误模型，各种 备份技术，其中重点阐述备份重载技术和本文中新的同步错位调度技术。 第4 章主要介绍基于独立任务、依赖任务和通信延迟的依赖任务的备份任务 调度限制条件及在这些约束条件下的三个容错调度算法。 第5 章介绍仿真实验的各种性能指标、模拟参数和实验结果分析比较。 第6 章对本文主要内容做了总结，并介绍未来可以改进的方向。 5 基于主从备份的云计算容错调度算法研究 第2 章主任务调度算法 近几年，对主任务的调度算法研究是一个很热门的课题，经过专家学者们的 努力，涌现出各种各样以不同指标为标准的算法，比如研究独立任务为主的最大 最小算法( m a x m i n ) 、最小最小算法( r a i n - r a i n ) 、最大时间跨度算法( m a x i 蝴、快 速贪吃算法( 缸t g r e e d y ) 2 6 等。作者k a y a 等人又提出了一种文件共享独立任务的 启发式调度算法【2 7 1 ，j o n e s 等人在文献 2 8 】提出以带宽为中心的任务调度模型与启 发式算法，这些算法的选择对象大多为全体服务资源，在资源相当丰富的网格环 境下，性能受到限制，不能充分发挥其优越性。因此，缩小任务调度时资源选择 的范围、提高资源选择的精度、缩短任务资源匹配与调度的时间，有助于提高任 务调度的效率，其中，对资源的聚类预处理是一种有效的方式。资源聚类主要包 括基于处理资源性能的聚类和基于网络性能的资源聚类，现有的聚类方法有层次 式聚类算法、尽均值聚类算法及基于密度的聚类算法 3 0 , 3 1 等。f i o l e t 等人提出 了一种网格分布数据的聚类方法【3 2 1 ，杜晓丽等人针对d a g 图提出了基于模糊聚 类的任务调度启发式算法，为独立任务的聚类调度提供了借鉴【3 3 1 。 人们对任务调度算法研究有了很大进步，但是它们的研究基础都是经典算法 a s a p 调度算法和a l a p 调度算法，这两种调度算法给出了控制步的下限和资源 的上限。如果把这两种算法一起使用，还可以确定每一个操作可能调度到的最早 控制步和最迟控制步，从而确定了每一个操作可能调度的区间。在这一章将会介 绍这两种算法，以及在这两种算法的基础上提出一种新的算法_ c a s a l ( 综 合a s a p 和a l a p ) 调度算法，并将这个算法应用到后面对主任务的调度中。 2 1 基本定义 控制步：是指系统控制一个任务操作的基本时序单位，在同步系统中，通 常对应于一个或几个时钟周期。 节点入度：每个任务对应的相关的上一级任务个数。 节点出度：每个任务对应的相关的下一级任务个数。 6 基于主从备份的云计算容错调度算法研究 2 2a s a p 调度算法 a s a p 调度算法 2 2 , 2 3 , 3 4 1 对于一个刚到的任务，将它赋予尽可能早调度到的 控制步。在多处理机的云计算系统中，把所有任务到达的流图看作有向图处理( 忽 略任务流图中的传输结点，将操作结点、起始结点和终止结点作为有向图的结点， 任务相关性的边作为有向图的有向边) ，将任务流图呈正向分层排序，从有向图 起始节点开始，把每一个任务调度到能够最早执行此任务的控制步中。 算法2 1a s a p 调度算法 1 计算各个节点的入度； 2 记起始结点为当前结点，将其标识值记为0 ； 3 d o 4 删除与当前结点相连的所有有向边并计算相应结点的入度； 5 i f 结点的入度为0 6 将此节点加入队列； 7 记其标识值为当前结点标识值加1 ； 8 e l s e 9 i f 队列非空 1 0 从队列中取一个结点为当前结点； 1 1 e l s eb r e a k ： 1 2 ) w h i l e ( 结点的标识值不等于当前任务所调度到的控制步) 1 3 e n da s a p 调度算法。 2 3a l a p 调度算法 a l a p 调度算法【2 4 , 3 4 1 对于一个新到的任务，将它赋予尽可能迟调度到的控制 步。其基本思想与a s a p 调度算法类似，最大的不同点是：a l a p 调度算法是对 任务有向图进行逆向的分层排序，从有向图终止节点开始，把每一个任务调度到 能够最迟执行此任务的控制步中。 7 基于主从备份的云计算容错调度算法研究 算法2 2 a l a p 调度算法 1 计算各个节点的出度； 2 记终止节点为当前结点，将其标识值记为0 ，置层数为0 ； 3 d of 4 删除与当前结点相连的所有有向边并计算相应结点的出度； 5 i f 结点的出度为0 6 将此节点加入队列； 7 记其标识值为当前结点标识值加1 ； 8 e l s e 9 i f 队列非空 1 0 从队列中取一个结点为当前结点； 1 1 e l s eb r e a k ； 1 2 w h i l e ( 当前结点的标识值与层数之差不等于任务所调度到的控制 步) 1 3 e n da l a p 调度算法。 2 4c a s a l 调度算法 a s a p 调度算法与a l a p 调度算法是最简单、速度最快的调度算法，它们都 属于无约束调度算法，调度过程中根本不考虑用户给定的任何约束条件，是其他 调度算法的基础。在a s a p 调度算法中，任务可能过多集中于较早的控制步中； 在a l a p 调度算法中，任务可能过多集中于较迟的控制步中。因此，任务在各 控制步中的分布可能极不平衡，从而导致过量的资源需求以及过度的资源浪费， 还可能导致任务的拒绝率过高。从调度的效果考虑，这两种调度算法都不是好的 调度算法。为了能够使任务较均匀的分布在控制步中，提高任务的接受率，本文 提出了综合a s a p 和a l a p 调度算法，具体来说，根据任务紧急度，把任务分 为紧急的和非紧急的，分别用b o 为1 或0 表示，对于它们分别采用a s a p 和 a l a p 调度算法。 c a s a l ( 综合a s a p 和a l a p ) 调度算法即综合尽可能早和尽可能迟调度 算法，也可以理解为任务分级调度算法，对于每个刚到的任务，根据其紧迫程度 8 基于主从备份的云计算容错调度算法研究 不同，将它映射到尽可能早或尽可能迟调度的控制步。在云计算系统中，对紧急 程度高的任务正向的分层排序，使它能够调度到最早的控制步中；相反，紧急程 度低的任务采用逆向的分层排序，使它能够调度到最迟的控制步中。 该算法的主要调度步骤如下： 算法2 3c a s a l 调度算法 1 计算各个节点的入度与出度； 2 将各个节点的b o 值初始化为1 或0 ； 3 记起始节点为当前结点，将其标识值记为o ； 4 d o 5 i fb o = 1 6 删除与当前结点相连的所有有向边并计算相应结点入度； 7 i f 结点的入度为0 或入度节点都在队列2 中 8 将此节点加入队列l ； 9 记其标识值为当前结点标识值加1 ； 1 0 w h i l e ( 入度节点中有节点在队列2 ) f 1 1 计算此节点的出度； 1 2 腰结点的出度为0 1 3 将此节点移出队列2 ； 1 4 记其标识值为当前结点标识值减1 ； 1 5 删除与此结点相连的所有有向边并计算相应结点出度； 1 6 将此节点作为当前节点； 1 7 检查当前节点的入度节点； 1 8 1 9 2 0 2 1 2 2 ) e l s e i f 队列1 非空 从队列中取一个结点为当前结点； e l s eb r e a k ； ) e l s e 将节点加入队列2 9 基于主从备份的云计算容错调度算法研究 2 3 ) w h i l e ( 结点的标识值不等于当前任务所调度到的控制步) 2 4 i f 队列2 非空 2 5 调用a l a p 算法 2 6 e n dc a s a l 调度算法 2 5 实例分析 为了更好更形象的介绍三种算法的不同，引用文章 3 5 中的例子来阐述分析 比较上述三种算法。 例2 1 ：y 。+ 3 x y + 3 y = 0 使用迭代法解此方程，迭代步骤如下： w h i l e ( x a ) l o o p ： x l = x + d x ； u l = u 一( 3 宰x 半u 木d x ) 一( 3 木y 木d x ) ； y l = y + 宰啪； x = x 1 ； u = u l ； y = y l ； e n d ； 该迭代方法的具体流程如图2 1 所示。 1 0 基于主从备份的云计算容错调度算法研究 图2 - 1 例2 1 迭代法的流程图 图2 1 显示了本例中运用迭代法计算函数方程的整个代码运行流程，在流程 图中，我们假设任务1 、2 、3 、4 、5 、7 、l o 、1 1 为紧急任务，而6 、8 、9 为非 紧急任务。它们之间的运行流向如图箭头指向。 s t e p1 s t e p2 s t e p3 s t e p4 图2 - 2a s a p 调度算法结果 基于主从备份的云计算容错调度算法研究 s t e p1 s t e p2 s t e p3 s t e p4 s t e p1 s t e p2 s t e p3 s t e p4 图2 3a l a p 调度算法结果 图2 - 4c a s - a l 调度算法结果 图2 2 、2 3 、2 4 所显示的分别是运用算法a s a p 调度算法、a l a p 调度算 法和c a s a l 调度算法对例2 1 流程图进行主任务调度结果。当运用a s a p 调度 算法时，任务1 到1 l 都尽量往前面的控制步调度，比如任务l 、3 、4 、5 、6 映 射到控制步1 中，由于任务7 依赖于任务3 和4 的运行结果，所以它只能映射到 控制步2 中。同理，任务2 、8 、9 映射到控制步2 中，而任务1 1 只能映射到控 制步4 中，因为它所依赖的前置任务1 0 映射到任务7 的后一个控制步3 中。 当运用a l 心调度算法时，所有任务都尽量往靠后的控制步调度，根据流 程图得知任务1 1 是终止节点，将它调度到最迟控制步4 中，同理，将任务9 和 2 调度到控制步4 中，从最迟控制步开始，依次往前调度，最后结果如图2 3 所 示。 当运用c a s a l 调度算法时，根据任务的不同紧急度，紧急任务调度在尽 可能早的控制步中，而非