云环境下周期和非周期混合实时任务双容错调度算法

1、云环境下周期和非周期混合实时任务双容错调度算法摘要 云环境中的处理机故障已成为云计算不可忽视 的问题，容错成为设计和发展云计算系统的关键需求。针对 一些容错调度算法在任务调度过程中调度效率低下以及任 务类型单一的问题，提出一种处理机和任务主副版本分组的 容错调度方法；并给出了副版本可重叠执行的判定方法，以 及任务最坏响应时间的计算公式。通过实验和分析表明，和 以前算法相比，将处理机分成两组分别执行任务主版本和任 务副版本，减少了任务调度所需进行可调度测试的时间，增 加了副版本重叠执行的机会，减少了所需的处理机个数，对 提高系统处理机的利用率和容错调度的效率具有重要的意 义。关键词 云计算；周期

2、任务；非周期任务；容错；实时 调度中图分类号0 引言云计算作为下一代并行与分布式计算，它聚合了各种不 同的离散资源。由于云计算系统所使用的计算资源具有高度 的动态性和异构性，不同类型的计算资源性能差异巨大，以 及资源的动态加入和退出，软硬件故障、运行维护、安全保 护、系统升级等原因可能导致云环境中的资源无法继续使 用，因此，云计算环境出现故障是难免的。主版本 / 副版本( PrimaryBackup ， PB 技术是目前最重 要的软件容错方法。目前，已有很多采用 PB 方法进行容错 调度的文献。 Manimaran 等1 考虑了任务之间的资源限制， 同时将处理器划分为若干组，从而保证在多个处理

3、器出错的 情况下能够实现容错。 AlOmari 等2 研究了一种 PB 重叠方 法，允许一项任务的主版本和其他任务的副版本进行重叠， 从而提高了任务的调度成功率。 Liu 等3 在假定任务的截止 时限等于其周期的情况下，在单处理机环境下引入单调速率 ( RateMonotonic ， RM 的周期任务抢占调度算法。 Dhall 等 4 将 RM 推广到多处理机系统，提出速率单调首次满足 (RateMonotonic FirstFit ，RMFF 调度算法。文献 5 对传统 的 RMFF 算法进行容错扩充为速率单调首次满足的容错 ( FaultTolerant RateMonotonic Fir

4、stFit ， FTRMF 调度算法， 根据主版本的最坏响应时间( WorstCase Response Time， WCRT 来确定副版本的执行类型， 与传统的双备份调度算法 相比，该算法有效地降低了所需要的处理机的个数。朱晓敏 等 6 考虑到任务的服务质量( Quality of Service ， QoS 需求 问题，提出异构集群系统中具有 QoS 需求的实时任务容错调 度算法。 罗威等 7 提出一种基于固定优先级调度算法的延迟 主动副版本备份技术， 通过尽量向后调度主动方式的副版 本， 并在主版本成功执行时终止副版本的执行来减少备份的冗余度。在云计算环境下，云用户实时任务请求的类型多种

5、多 样，周期实时任务和非周期实时任务往往共同存在。当前， 实时系统中周期任务和非周期任务的同时调度普遍采取的 方法是建立周期性服务器，按设定的周期，在设定的服务容 量内定时执行非周期任务， 如文献 8 。文献 9 的空闲时间挪 用（Slack Stealing , SS算法通过建立一种被动任务来窃取 未被周期任务使用的有效处理机时间来执行非周期任务，然 而 SS 是利用一种试凑的递推方法来寻找最优方案，这往往 造成很大的计算时间开销。阳春华等 10 提出一种混合实时 任务容错调度算法， 采用主 /副版本备份技术确保系统的容错 能力，副版本采用主动和被动两种形式，该算法采用 RM 算 法完成周期

6、任务的静态调度，采用预订处理机时间方法和最 早截止时间优先（ Earliest Deadline First， EDF 算法动态调 度非周期任务， 然而该算法在 m 个处理机上调度 n 个周期任 务，在最坏情况下其计算复杂度高达0 （ nm2,这将耗费大量的检测是否满足调度条件的测试时间。可见上述混合容错调度算法随着处理机数的增加需要 更多的容错调度测试时间，导致调度效率不高，或难以恰当 确定建立的周期性服务器的周期和服务容量，以致不能对非 周期任务作出及时的响应；上述容错调度算法通常假设周期 任务提前已知， 可提前预处理调度周期任务， 而在云环境下，周期任务也是随机到达的，提高周期任务容错调

7、度的效率对保证任务的实时性至关重要。针对上述问题，本文提出主副版本分组的周期任务容错调度算法、非周期任务容错调度算 法以及周期任务和非周期任务混合的容错调度算法。同时， 本文还给出任务副版本可重叠执行的判断方法和符合本文 调度模型的任务最坏响应时间的计算公式。1 混合任务在云环境中执行的前提假设1.1 云任务描述 周期实时任务是指按一定周期到达并请求运行，并在截 止时限之前完成，每次请求称为周期任务的一个任务实例。 非周期实时任务是指随机到达系统的任务，并在截止时限之 前完成。周期实时任务和非周期实时任务同时并存的任务集 称为混合实时任务。定义 1 任务主版本。基于主副版本的容错技术中，系统

8、首先运行的任务版本称为任务主版本。周期任务的任务主版本 t i可描述为一个四元组，t i=(Ci, Ti, Di, Ui, Ci为任务主版本t i的最大执行时间，Ti 为任务主版本 t i 的周期， Di 表示任务主版本 t i 的截止期 限，本文假设 Di 等于 Ti；Ui 表示任务主版本 t i 的 CPU 利 用率，定义为 Ui=Ci/Ti 。非周期任务的任务主版本a i也可描述为一个四元组，a i= (ai, Ci, Di, di, ai是指非周期任务到达系统的时间；Ci 为非周期任务 i 的最大执行时间； Di 为相对截止时限； di=ai+Di 为绝对截止时限。定义 2 任务副版本

9、。基于主副版本的容错技术中，运行 任务主版本的处理机失效时，作为任务主版本备份执行的任 务称为任务副版本。周期任务的任务主版本 t i的任务副版本a i描述为一个 四元组，即a i= (Bi , Ti, Di, Ui, Bi为a i的最大执行时间， 一般来说Bi Ci，因为副版本可以是主版本的完全备份，实 现主版本需要完成的所有功能，也可以是简体版本，只保证 故障状态下主版本中必不可少的功能，本文假定 Bi=Ci ；Ti 为a i的周期，与t i的周期相同；假定主版本任务和副版本 任务具有相同的 Di 和 Ui。非周期任务的任务主版本a i的任务副版本B i也描述为一个四元组，即B i= (a

10、i, Ci,Di, di，其与任务主版本具有相同的分量。副版本有三种状态：主动方式、被动方式和重叠方式。令 Oi 代表主版本 pi 和副版本 bi 之间的重叠长度因此副版本 状态由以下公式决定：status( bi=active ， Oi=Cipassive， Oi=0delay， 0 定理 2 最坏响应时间计算。设一处理机 上的一组周期任务 S= T 1 , T 2,，T 1，各个任务按照 周期递增的顺序排列，T i S的最坏响应时间 Ri等于所有比t i具有更高优先级的任务的执行时间与任务t i本身执行时间的总和，即 Ri=Ci+ 刀 i-1j=1 Ri/TjCj。定理 2 的证明参见文献

11、 12 。由于上述最坏响应时间计 算定理仅仅适用于标准的固定优先级调度算法，不符合本文 中的任务主副版本和处理机分组的容错调度模型，下面给出 符合本文容错模型的最坏响应时间计算命题。命题1任务主动副版本最坏响应时间计算。设丫 i是周期任务t i的主动副版本，在系统无故障的情况下，丫 i在处理机pk的最坏响应时间 Rik为：Rik=Ci+刀Status( 丫 j=active Y j hepk ( 丫 iRik/TjCj+ 刀 Status ( y j=delay y j hepk ( 丫 iRik/TjRpj ,其中hepk ( y i表示处理机pk上的任务集合 中优先级高于或者等于y i的所

12、有任务集。如果Rik Ti，那么y i在系统无故障的情况下是可调度的；否则y i不可调度。证明由于 Y i 是 active 形式的副版本任务， 该副版本与其 对应的主版本任务 t i 同步执行。 active 形式的副版本任务 Y i 在每个周期 Ti 内都执行一次， delay 形式的副版本任务每个 周期内其冗余部分都执行一次。同时，由于副版本只在执行 副版本的处理机上执行，副版本的调度顺序也是按最小执行 周期优先进行调度，因此， Y i 在处理机 pk 的最坏反应时间 Rik 发生在与优先级比其高的任务集 hepk(Y i 同时触发执 行。由于在系统无故障的情况下， hepk( Y i

13、中的 active 形式的副版本全部执行，delay形式的副版本只执行其冗余部 分， passive 形式的副版本不执行，因此，可通过逐步迭代的 方法求出 active 形式的副版本任务的最坏反应时间为Rik=Ci+ 刀 Status( y j=active y j hepk( y iRik/TjCj+ 刀 Status (y j=delay y j hepk ( y iRik/TjRpj。证毕。同理可给出以下命题：命题 2 任务延迟副版本最坏响应时间计算。设 y i 是当 前要进行分配的延迟副版本，在系统无故障的情况下， y i 在处理机 pk 的最坏响应时间 Rik 可由下面公式计算： R

14、ik=Rpi+ 刀 Status ( y j=active y j hepk ( y iRik/TjCj+ 刀 Status(y j=delayy j hepk ( y i Rik/TjRpj 。如果 Rik 小于或者等于其主版本的最坏反应时间，那么 y i 在系统无故障的情况下是可调度的；否则 y i 不可调度。命题 3 任务被动副版本完最坏响应时间计算：设 y i 是 当前要进行分配的被动副版本，其主版本分配到处理机pf上， y i 在处理机 pk 的最坏反应时间 Rik 可由下面公式计 算：Rik=2Ci+ X y j hepf ( t iRif/TjCj。如果 Rik 小于或者等于其主

15、版本的最坏反应时间，那么 y i 在 pf 故障的情况下是可调度的；否则 y i 不可调度。2.1.3周期任务主副版本分组容错调度算法一一PGFTS按周期任务周期由小到大的优先级顺序，将周期任务的 主版本或副版本分配到首次满足其实时性的处理机上，高优 先级的任务可抢占低优先级的任务。根据任务类型的不同，存在 4 种任务分配情况。1 任务主版本的分配。当分配任务主版本t i给处理机pm 时，只需检测该任务和已经分配到其上的其他任务主版 本是否满足可调度性，若所有的处理机都不满足可调度性， 则启用一个新的处理机来处理该任务。在实际执行时，如果 主版本成功完成，则及时取消其对应副版本占用的处理机资

16、源，供其他实时任务使用。2 任务主动副版本分配。当分配一个任务主动副版本 给处理机 pm 时，假设其任务主版本 t i 已经指定到处理机pk (pk工pm，在无处理机故障时，需检测a i和所有已经分配到 pm 的任务主动副版本和任务延迟副版本的冗余部分的 可调度性；当某一处理机 ph故障时(phz pm, a i和那些已 经分配在 pm 上的任务主动副版本、任务延迟副版本的冗余 部分以及 Recover (pm， ph 一起被检测可调度性。3 任务延迟副版本分配。当分配一个任务延迟副版本 a 给处理机 pm 时，假设其任务主版本 t i 已经指定到处理机pk (pk工pm，在无处理机故障时，需

17、检测a i的冗余部分和所有已经分配到 pm 的任务主动副版本和任务延迟副版本的冗余部分的可调度性；当某一处理机ph故障时(ph丰pm,a i 的冗余部分和那些已经分配在 pm 上的任务主动副版本、 任务延迟副版本的冗余部分以及 Recover( pm， ph 一起被检 测可调度性。4 任务被动副版本分配。当分配一个任务被动副版本给处理机pm时，假设其任务主版本 t i已经指定到处理机 pk (pk工pm,因为任务被动副版本 a i只有在pk故障时才被 启动运行，只需检测a i的可调度性。下面给出周期任务主 副版本分组容错调度算法( Periodic tasks FaultTolerant Sc

18、heduling algorithm based on Grouping ， PGFTS。算法 1 周期任务主副版本分组容错调度算法(PGFTS。有序号的程序 Shift+Alt+Y 程序前输入：周期任务的主版本集合 r = T 1, T 2,，T n, 副版本集合B r = a 1,a 2,，a n，处理机集合Cloud=p1 , p2,，pl，接收任务主版本的处理机组G1,接收任务副版本的处理机组 G2。输出： 周期任务处理机分配结果的集合 Assign1=(t i,pk, ( a i, pjpk G1, pj G2。PGFTS(1L T 1, T 2,，T n； /到达的一组周期任务，/

19、按照周期大小的升序依次进入准备队列 L2m |G1|, h |G2|; 得至U处理机组 G1和G2的处理机个数3L ； /任务执行队列初始化4do until =5for each t i ;6 ( t i, pjselectprocessor ( t i, G1; /在 G1 中为 t i 选择满足可调度的处理机7if (pj 丰 nullAssign1 Assign1+ ( t i, pj; - t i ;8elsem m+1 ； Assign1 Assign1+ (t i， pm；G1 G1+pm ； - t i ；9(a i, pj selectprocessorbasedstatus

20、( a i, G2, status (a i;/*根据副版本a i的status ( a i，在G2中选择首次满足 可容错调度的处理机 */10if (pj 工 nullAssign1 Assign1+ ( a i, pj; 11else h h+1 ; Assignl Assign1+ ( a i, ph; G1 G1+ph ； /end for each t i /end do until =12return Assign1 ;程序后上面511中的for each循环是针对一组周期任务的每 个任务，所以要循环 n 次。内层为每个周期任务的主副版本 基于首次满足的算法思想选择处理机，平均需要

21、 l/2 次。所 以， PGFTS 算法的时间复杂性为 O( nl。2.2 非周期任务容错调度本文采用最早截止时限优先( Earliest Deadline First ， EDF 算法给到达的非周期任务分配优先级， 高优先级的就绪 任务可抢占已被调度的较低优先级的任务。分配非周期任务 主版本到已分配的周期任务主版本间的空闲时间槽上执行， 非周期任务副版本分配到已分配周期任务副版本的处理机 上执行。设有一组非周期任务主版本集合A = a 1, a 2,，ak在某处理机上周期任务主版本间的空闲时间槽上运行，它 们已经按照优先级由高到低的顺序排列,在某一时刻,一个新任务a new到达该处理机，需检

22、测该处理机上新任务集A=AU a new的可调度性。由于非周期任务到达的随机性， 任务a i的完成时间fi随着新任务的到达会发生改变，是时 间 t 的函数。设新任务和系统中原有任务按截止时限非递减 的顺序重新排序后的新任务集为A = a 1, a 2,，a j, anew, a j+1，a k，由于新任务不会抢占高优先级任务 的执行，只会影响 a new 之后的低优先级任务的完成时间。2.2.1 非周期任务 a i 的完成时间分析设在时刻 t, a i a j+1 , a j+2，a k , a new 插 入前a i的开始时间为sti，完成时间为fi, a i的剩余执行时 间为Ci(t。下面

23、分3种情况讨论任务 a i a j+1 , a j+2， a k 在周期任务主版本之间的空闲时间槽上的完成时间。情况 1 假设任务 a i a j+1 ，a j+2 ， a k ，若在 a new 插入之后， a i 整个执行过程仍旧在其原来的时间槽中， 则a new插入之后，a i新的开始执行时间和完成时间分别为 st i=sti+Cnew、 f i=fi+Cnew。图 2 (a 给出此种情况的一 个实例。情况2假设任务a i a j+1 , a j+2，a k，在a new 插入之后，若 a i 整个执行过程分成两部分 a i1 ， a i2 ，a i1 仍旧在原来的时间槽(t1 , t2

24、中执行，a i2转移到下一个时 间槽(t3 , t4中执行，贝y a new插入之后，a i新的开始执 行时间和完成时间分别为st i=sti+Cnew 、 f i=t3+Cnew-t2-fi 。图 2(b 给出此种情况的一个实例情况3假设任务a i a j+1 , a j+2，a k，在c new 插入之后，a i整个执行过程由在原来的时间槽t1 , t2中执行，转移到下一个时间槽t3，t4中执行，则a new插入之后， a i新的开始执行时间和完成时间分别为st i=t3+Cnew-(t2-sti、 f i=st i+Ci。图2 (c给出此种情况的一个实例。图片图 2 非周期任务 a i

25、的执行情况2.2.2 非周期任务集可调度判定定理 3 非周期任务集可调度判定。 新任务 a new 到达处 理机后，按最早截止时间优先策略 EDF 将新任务插入之后形 成的新任务集 a 1, a 2,，a j, a new, a j+1，a k 可调度的充分必要条件为： 对于所有任务 a i a new，a j+1，a k，其完成时间fi满足fi ai+Di。证明新任务 a new 到达后， 按 EDF 策略，形成新任务集 a 1 , a 2,，a j , a new, a j+1，a k，对新任务 集来说，任务所要求的截止时间早于 a new 的任务的完成时 间不受影响,只要 a new 和

26、截止时间晚于 a new 的任务满足 各自的截止时间要求,则整个新任务集就是可调度的,即对 于所有任务a i a new, aj+1，a k，只要其完成时 间fi满足fi ai+Di，则新任务集是可调度的。证毕。2.2.3 非周期任务主副版本分组容错调度算法算法 2 非周期任务主副版本分组容错调度算法( Aperiodic tasks FaultTolerant Scheduling algorithm based on Grouping ， AGFTS 。程序前输入：非周期任务集的主版本集合A = a 1, a 2,，a k，副版本集合B A = B 1, B 2,，B k，处理机集合 Cl

27、oud=p1 ，p2，pn，接收周期任务主版的处理机组G1，接收周期任务副版本的处理机组G2。输出：非周期任务处理机分配结果的集合 Assign2=(ai, pk, ( B i, pjpk G1, pj G2。AGFTS( L a 1, a 2，a k; /非周期任务按最小截止时 间优先依次进入队列 Ln |G1|; l |G2|; 得到处理机组 G1和G2的处理机 个数for each a i L do find FALSE; k1; /定义标志 find 来表示是否找 到了满足可调度的处理机while ( k nA( find=FALSE 在 G1 中为 a i 选择满足可 调度的处理机

28、eftik calculatefinishtime ( a i，pk; /依据 EDF 计算 a i 在 pk 的最早完成时间if (eftik n Assign2 J Assign2 + ( a i, pk; G1 JG1+pk; n k;find J TRUE ; kJ1； lft J 0；/副版本的最迟完成时间初始化为0while (k 1以尽可能延迟的方式为副版本分配处理机 lftik Jcalculatelfinishtime ( p i, G2, status ( B i, pk, di; /*依据EDF、p i的执行方式status ( p i和di计算p i在 pk 的满足可容

29、错的最迟完成时间 */if (lftik 工 null lft=lftik ； p=pk； break； /end whileif( lft=0 Assign2 JAssign2+( p i， pk; G2JG2+pk ; lJk; /* 没找到满足可容错调度的处理机，将 p i 分配到新 处理机 pk 上 */elseAssign2 JAssign2+(p i， p; /end for eachreturn Assign2;程序后与 PGFTS 算法的时间复杂性分析类似，通过计算可知AGFTS 算法的时间复杂性为 O( nk。3 混合实时任务分组容错调度算法算法 3 混合实时任务分组容错调度

30、算法 (Hybrid tasks FaultTolerant Scheduling algorithm based on Grouping ， HGFTS 。程序前输入：到达的混合实时任务集n = Y 1, Y 2,，Y k,处理机集合Cloud=p1 , p2,，pm，接收主版本任务的 处理机组 G1 ，接收副版本任务的处理机组G2。输出：任务处理机的分配结果。HGFTS ( L J(Y 1 , Y 2，Y k ； /将到达的混合实时任务按EDF 策略依次进入队列 Ldo until L= y i L doif type ( y i periodic/判断任务的类型，并选择相应的 调度算法

31、(丫 i, pjselectppprocesso(y i, PGFTS (, G1;/*在G1中按周期任务分组容错调度算法PGFTS (为y i选择满足可调的处理机 */S Y is violate deadline instances；if (Sz null insertque ( L , S, EDF; /按 EDF 策略耳将 S 中的任务插入队列 L(a i, pkselectpbprocessor ( a i, PGFTS (, G2, status(a i; /*在G2为Y i的副版本a i按其执行方式status ( a i选择可调度的处理机*/else ( 丫 i, pj sel

32、ectapprocessor ( y i, AGFTS (, G1;/*在G1中按非周期任务分组容错调度算法AGFTS (为Y i 选择满足可调的处理机 */(B i, pkselectabprocesso( B i, AGFTS (, G2, status(B i; /* 在 G2 为 丫 i的副版本 B i 按其执行方式 status( B i 选择可调度的处 理机 */end for do until程序后与 PGFTS 算法的时间复杂性分析类似，通过计算可知HGFTS 算法的时间复杂性为 O(mk。4 模拟实验和性能分析 本文通过大量的模拟实验来验证本文所提调度算法在 提高处理机利用率

33、、减少任务可容错调度的时间和减少所需 处理机个数方面的性能。 本文用文献 13的 CloudSim 来模拟 云计算环境， CloudSim 是由澳大利亚墨尔本大学的网格实验 室和 Gridbus 项目推出的云计算仿真软件，是基于 Java 的离 散事件模拟工具包，支持云计算的资源管理和调度模拟。周期任务和非周期的参数设置如下，周期任务 i 的周期 Ti 在 1，400内均匀分布， 最大执行时间 Ci 随机分布在区间(0, n Ti内，其中 n =maxC1/T1 , C2/T2,，Cn/Tn表 示周期任务的最大 CPU 利用率。 非周期任务 i 到达系统的时 间ai和相对截止时限 Di随机取值

34、；Ci分布在区间(0,入 Di内，其中入=maxC1/D1 , C2/D2，Cn/Dn表示非周 期任务的最大 CPU 利用率。 CloudSim 模拟程序运行在 Intel 奔腾双核 E5800、3.2GHz、1GB DDR3 的戴尔台式机上。4.1 所需处理机数 m 和周期任务总 CPU 利用率的比值实验 该组实验比较本文所提周期任务分组容错调度算法PGFTS 和文献 14的 FTRMFF 、文献 2 的 ARR2 周期任务容 错调度算法在调度周期任务时所需要的处理机数目 m 和周 期任务总的 CPU 利用率的比值情况。 文献 14 采用 RMFF 策 略将周期任务分配给多处理机，在副版本只

35、采用主动运行方 式时， 获得具有容错能力的 FTRMFF 算法，所需处理机数目 一般是无容错情况下处理机数目的两倍。 ARR2 容错调度算 法的主要思想是：将处理机分成两组，一组执行主版本任务 和主动副版本的副版本任务，其他副版本任务在另一组处理 机上执行。实验的参数设置如下：周期任务数n 在200， 800内取 值；周期任务的最大 CPU利用率n分别取0.2, 0.5和0.8;同一组n和n值下实验重复10次，求得所需处理机数目m和周期任务总的 CPU利用率U=刀ni=1Ci/Ti的比值m/U的平 均值。不同n值、不同n值下各容错调度算法的比较结果如 图 3 所示。从图 3中的各子图可以看出

36、PGFTS 所得到的 m/U 值最 小，因而表现出最好的性能。在n值较小的（a、（b子图中随着任务个数的增加其节省处理机个数的优势愈加明显，这 主要是因为低 CPU 利用率的任务越多， 越多的副版本可采用 延迟或被动方式调度运行，副版本重叠使用处理机的机会就 越多，所需的处理机就越少；PGFTS 对处理机进行分组，将主副版本分别调度到不同组的处理机上，进一步增加了副版 本重叠使用处理机的机会； PGFTS 在主版本成功完成后， 及 时释放对应的副版本，将副版本剩余执行部分占用的处理机 资源分给其他任务使用，这也进一步节省了处理机资源。4.2 不同周期任数所需调度时间对比实验 为了说明本文所提出的混合任务分组容错调度算法HGFTS 在调度周期任务时的调度效率， 和文献 10所提出的 混合实时任务容错调度（ Hybrid real time task Fault Tolerant Scheduling， HFTS 算法在调度不同周期任务数时所需要的 调度时间进行对比。该算法基于周期任务的确定性知识，采 用 RM 算法完成周期任务的静态调度；采用 EDF 算法在预 留处理机时间内动态调度非周期任务。该组实验的周期任务 数n在200 , 800内取值，周期任务的最大 CPU利用率n取 0.5,随着周期任务数的增加，PGFTS和HFTS调度算法