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

　　0引言
　　云计算作为下一代并行与分布式计算，它聚合了各种不同的离散资源。由于云计算系统所使用的计算资源具有高度的动态性和异构性，不同类型的计算资源性能差异巨大，以及资源的动态加入和退出，软硬件故障、运行维护、安全保护、系统升级等原因可能导致云环境中的资源无法继续使用，因此，云计算环境出现故障是难免的。
　　主版本/副版本（PrimaryBackup， PB技术是目前最重要的软件容错方法。目前，已有很多采用PB方法进行容错调度的文献。Manimaran等提出一种基于固定优先级调度算法的延迟主动副版本备份技术， 通过尽量向后调度主动方式的副版本， 并在主版本成功执行时终止副版本的执行来减少备份的冗余度。
　　在云计算环境下，云用户实时任务请求的类型多种多样，周期实时任务和非周期实时任务往往共同存在。当前，实时系统中周期任务和非周期任务的同时调度普遍采取的方法是建立周期性服务器，按设定的周期，在设定的服务容量内定时执行非周期任务，如文献[8]。文献[9]的空闲时间挪用（Slack Stealing， SS算法通过建立一种被动任务来窃取未被周期任务使用的有效处理机时间来执行非周期任务，然而SS是利用一种试凑的递推方法来寻找最优方案，这往往造成很大的计算时间开销。阳春华等[10]提出一种混合实时任务容错调度算法，采用主/副版本备份技术确保系统的容错能力，副版本采用主动和被动两种形式，该算法采用RM算法完成周期任务的静态调度，采用预订处理机时间方法和最早截止时间优先（Earliest Deadline First， EDF算法动态调度非周期任务，然而该算法在m个处理机上调度n个周期任务，在最坏情况下其计算复杂度高达O（nm2，这将耗费大量的检测是否满足调度条件的测试时间。
　　可见上述混合容错调度算法随着处理机数的增加需要更多的容错调度测试时间，导致调度效率不高，或难以恰当确定建立的周期性服务器的周期和服务容量，以致不能对非周期任务作出及时的响应；上述容错调度算法通常假设周期任务提前已知，可提前预处理调度周期任务，而在云环境下，周期任务也是随机到达的，提高周期任务容错调度的效率对保证任务的实时性至关重要。针对上述问题，本文提出主副版本分组的周期任务容错调度算法、非周期任务容错调度算法以及周期任务和非周期任务混合的容错调度算法。同时，本文还给出任务副版本可重叠执行的判断方法和符合本文调度模型的任务最坏响应时间的计算公式。
　　1混合任务在云环境中执行的前提假设
　　1.1云任务描述
　　周期实时任务是指按一定周期到达并请求运行，并在截止时限之前完成，每次请求称为周期任务的一个任务实例。非周期实时任务是指随机到达系统的任务，并在截止时限之前完成。周期实时任务和非周期实时任务同时并存的任务集称为混合实时任务。
　　定义1任务主版本。基于主副版本的容错技术中，系统首先运行的任务版本称为任务主版本。
　　周期任务的任务主版本τi可描述为一个四元组，τi=（Ci，Ti，Di，Ui，Ci为任务主版本τi的最大执行时间，Ti为任务主版本τi的周期，Di表示任务主版本τi的截止期限，本文假设Di等于Ti；Ui表示任务主版本τi的CPU利用率，定义为Ui=Ci/Ti。
　　非周期任务的任务主版本σi也可描述为一个四元组，σi=（ai，Ci，Di，di，ai是指非周期任务到达系统的时间；Ci为非周期任务i的最大执行时间；Di为相对截止时限；di=ai+Di为绝对截止时限。
　　定义2任务副版本。基于主副版本的容错技术中，运行任务主版本的处理机失效时，作为任务主版本备份执行的任务称为任务副版本。
　　周期任务的任务主版本τi的任务副版本αi描述为一个四元组，即αi=（Bi，Ti，Di，Ui，Bi为αi的最大执行时间，一般来说Bi≤Ci，因为副版本可以是主版本的完全备份，实现主版本需要完成的所有功能，也可以是简体版本，只保证故障状态下主版本中必不可少的功能，本文假定Bi=Ci；Ti为αi的周期，与τi的周期相同；假定主版本任务和副版本任务具有相同的Di和Ui。
　　非周期任务的任务主版本σi的任务副版本βi也描述为一个四元组，即βi=（ai，Ci，Di，di，其与任务主版本具有相同的分量。
　　副版本有三种状态：主动方式、被动方式和重叠方式。令Oi代表主版本pi和副版本bi之间的重叠长度因此副版本状态由以下公式决定：
　　status（bi=active，Oi=Ci
　　passive，Oi=0   []
　　delay，0　　对于非周期任务来说，其副版本执行方式类别及判定方法与周期任务相同。
　　为了方便后面进行形式化描述，给出以下符号表示
　　集合Primary（pj和Backup（pj分别代表分配到处理机pj上的主版本任务和副版本任务；active（pj和delay（pj分别代表分配到处理机pj上的且方式为active和delay的副版本集合；集合passiveRecover（pj，pf包含分配到pj上的方式为passive的副版本，对应的主版本被分配到pf上；集合activeRecover（pj，pf包含分配到pj上的方式为active的副版本，对应的主版本被分配到pf上；集合delayRecover（pj，pf包含分配到pj上的方式为dela y的副版本，对应的主版本被分配到pf上；Recover（pj，pf为以上3个集合的并集。
　　1.2云计算调度运行的基本假设
　　1多数情况下处理机不会失效，因此本文假设任何时刻至多存在一个处理机故障，在故障处理机被修复之前不会出现第二个处理机故障，并假定一个处理机发生故障后能及时通知其他处理机，其他实时任务不会再分配到该处理机。
　　2由于处理机之间通信所需时间与任务的执行时间相比非常短，因此忽略处理机之间消息的传递时间。
　　1.3问题描述和调度目标
　　定义3可调度的。若一个实时任务按某种调度策略调度到某处理机上，处理机上的每个实时任务都能在其对应截止时限内完成，则称该任务在该处理机上是可调度的。令Ctij表示实时任务γi在处理机pj上的完成时间，则实时任务γi可调度，就是pj∈Cloud，使得任务γi在处理机pj上的完成时间Ctij小于等于其截止时限。
　　定义4可容错的。若一个实时任务的任务主版在其可调度的处理机上执行时发生失败，其副版本任务能在其所在处理机上在实时任务的截止时限内完成，则称该实时任务是可容错的。
　　定义5可容错调度的。若存在一种调度算法将一个实时任务集的主副版本调度到一组处理机上，每个实时任务都是可容错的，则称该实时任务集可容错调度的。即对一个实时任务集Λ={γ1，γ2，…，γk}
　　，对γi∈Λ，pj，pk∈Cloud，γi的主版本和副版本分别在处理机pj、pk上可调度。
　　对周期任务的主版本集合Γ={τ1，τ2，…，τn}，副版本集合BΓ={α1，α2，…，αn}，非周期任务集的主版本集合Λ={σ1，σ2，…，σk}，副版本集合BΛ={β1，β2，…，βk}，以及处理机集合Cloud={p1，p2，…，pm}，假定处理机的类型相同，本文的调度目标可用下面的方程组来表示：
　　min mτi∈Γ，pj∈Cloud，Ctij≤Diαi∈BΓ，pk∈Cloud，Ctik≤Diσi∈Λ，pl∈Cloud，Ctil≤diβi∈BΛ，ph∈Cloud，Ctih≤di
　　2任务主副版本分组容错的调度方法
　　2.1周期任务容错调度
　　为了减少调度周期任务所需要进行可容错调度测试的处理机数量，即减少任务调度所需的时间，本文考虑将处理机分成两组，一组执行周期任务的主版本，一组执行周期任务的副版本。
　　2.1.1周期任务副版本可重叠执行的判定方法
　　在系统运行时仅有单个故障发生的假设下，通过副版本重叠技术可将同一段时间预留给来自不同处理机上的任务主版本对应的任务副版本，从而减少主/副版本容错模型中资源冗余度，提高处理机的利用率。
　　定理1任务副版本可重叠执行判定定理。若两个任务副版本αi和αk分配到同一处理机上，其对应的两个任务主版本τi和τk被分配到不同的处理机上，假定τi的周期Ti小于τk的周期Tk，令fPi表示τi的完成时间，按最短周期任务优先调度策略，如果αk的最迟开始时间大于等于max{fPi， fPk}，则任务τk的副版本αk可以与任务τi的副版本αi重叠执行。
　　证明假设αk的最迟开始时间小于max{fPi， fPk}，由于Ti　　图片
　　图1αk的可能执行情况
　　在图1（a中，αk的最迟开始时间小于fPi，从该图可以看出αi的执行方式是延迟副版本形式，若处理机p3发生故障，则要求αi与αk的重叠部分在fPi时间之前在处理机p2上同时执行，出现在同一个节点上两个不同的任务在同一时间段内执行，因此假设不成立。
　　在图1（b中，αk的最迟开始时间小于fPk，从该图可以看出αk的执行方式是延迟副版本形式，若处理机p1发生故障，则要求αi与αk的重叠部分在fPk时间之前在处理机p2上同时执行，出现在同一个节点上两个不同的任务在同一时间段内执行，因此假设不成立。证毕。
　　2.1.2任务最坏响应时间的计算
　　RM算法赋予周期最短的任务最高优先级，在任何时刻总是调度运行具有最高优先级的就绪任务，对于一个处理机上的每个周期任务来说，当所有比它具有更高优先级的任务被同时触发时，其响应时间最长。称最长响应时间出现时的情况为最坏情况，如果一个周期任务在最坏情况时的响应时间不超过其执行周期，则该任务在任何状况下都是可调度的。从响应时间的角度，文献[11]有如下最坏响应时间计算定理。
　定理2最坏响应时间计算。设一处理机上的一组周期任务S={τ1，τ2，…，τl}，各个任务按照周期递增的顺序排列，τi∈S的最坏响应时间Ri等于所有比τi具有更高优先级的任务的执行时间与任务τi本身执行时间的总和，即Ri=Ci+∑i-1j=1「Ri/TjCj。
　　定理2的证明参见文献[12]。由于上述最坏响应时间计算定理仅仅适用于标准的固定优先级调度算法，不符合本文中的任务主副版本和处理机分组的容错调度模型，下面给出符合本文容错模型的最坏响应时间计算命题。
　　命题1任务主动副版本最坏响应时间计算。设γi是周期任务τi的主动副版本，在系统无故障的情况下，γi在处理机pk的最坏响应时间Rik为：Rik=Ci+∑Status（γj=activeγj∈hepk（γi「Rik/TjCj+∑Status（γj=delayγj∈hepk（γi「Rik/TjRpj，其中hepk（γi表示处理机pk上的任务集合中优先级高于或者等于γi的所有任务集。如果Rik≤Ti，那么γi在系统无故障的情况下是可调度的；否则γi不可调度。
　　证明由于γi是active形式的副版本任务，该副版本与其对应的主版本任务τi同步执行。active形式的副版本任务γi在每个周期Ti内都执行一次，delay形式的副版本任务每个周期内其冗余部分都执行一次。同时，由于副版本只在执行副版本的处理机上执行，副版本的调度顺序也是按最小执行周期优先进行调度，因此，γi在处理机pk的最坏反应时间Rik发生在与优先级比其高的任务集hepk（γi同时触发执行。由于在系统无故障的情况下， hepk（γi中的active形式的副版本全部执行， delay形式的副版本只执行其冗余部分，passive形式的副版本不执行，因此，可通过逐步迭代的方法求出active形式的副版本任务的最坏反应时间为Rik=Ci+∑Status（γj=activeγj∈hepk（γi「Rik/TjCj+∑Status（γj=delayγj∈hepk（γi「Rik/TjRpj。证毕。
　　同理可给出以下命题：
　　命题2任务延迟副版本最坏响应时间计算。设γi是当前要进行分配的延迟副版本，在系统无故障的情况下，γi在处理机pk的最坏响应时间Rik可由下面公式计算：Rik=Rpi+∑Status（γj=activeγj∈hepk（γi「Rik/TjCj+∑Status（γj=delayγj∈hepk（γi「Rik/TjRpj。
　　如果Rik小于或者等于其主版本的最坏反应时间，那么γi在系统无故障的情况下是可调度的；否则γi不可调度。
　　命题3任务被动副版本完最坏响应时间计算：设γi是当前要进行分配的被动副版本，其主版本分配到处理机pf上， γi在处理机pk的最坏反应时间Rik可由下面公式计算：Rik=2Ci+∑γj∈hepf（τi「Rif/TjCj。
　　如果Rik小于或者等于其主版本的最坏反应时间，那么γi在pf故障的情况下是可调度的；否则γi不可调度。
　　2.1.3周期任务主副版本分组容错调度算法——PGFTS
　　按周期任务周期由小到大的优先级顺序，将周期任务的主版本或副版本分配到首次满足其实时性的处理机上，高优先级的任务可抢占低优先级的任务。根据任务类型的不同，存在4种任务分配情况。
　　1任务主版本的分配。当分配任务主版本τi给处理机pm时，只需检测该任务和已经分配到其上的其他任务主版本是否满足可调度性，若所有的处理机都不满足可调度性，则启用一个新的处理机来处理该任务。在实际执行时，如果主版本成功完成，则及时取消其对应副版本占用的处理机资源，供其他实时任务使用。   []
　　2任务主动副版本分配。当分配一个任务主动副版本αi给处理机pm时，假设其任务主版本τi已经指定到处理机pk（pk≠pm，在无处理机故障时，需检测αi和所有已经分配到pm的任务主动副版本和任务延迟副版本的冗余部分的可调度性；当某一处理机ph故障时（ph≠pm，αi和那些已经分配在pm上的任务主动副版本、任务延迟副版本的冗余部分以及Recover（pm，ph一起被检测可调度性。
　　3任务延迟副版本分配。当分配一个任务延迟副版本αi给处理机pm时，假设其任务主版本τi已经指定到处理机pk（pk≠pm，在无处理机故障时，需检测αi的冗余部分和所有已经分配到pm的任务主动副版本和任务延迟副版本的冗余部分的可调度性；当某一处理机ph故障时（ph≠pm，αi的冗余部分和那些已经分配在pm上的任务主动副版本、任务延迟副版本的冗余部分以及Recover（pm，ph一起被检测可调度性。
　　4任务被动副版本分配。当分配一个任务被动副版本αi给处理机pm时，假设其任务主版本τi已经指定到处理机pk（pk≠pm，因为任务被动副版本αi只有在pk故障时才被启动运行，只需检测αi的可调度性。下面给出周期任务主副版本分组容错调度算法（Periodic tasks FaultTolerant Scheduling algorithm based on Grouping， PGFTS。
　　算法1周期任务主副版本分组容错调度算法（PGFTS。
　　有序号的程序——————————Shift+Alt+Y
　　程序前
　　输入：周期任务的主版本集合Γ={τ1，τ2，…，τn}，副版本集合BΓ={α1，α2，…，αn}，处理机集合Cloud={p1，p2，…，pl}，接收任务主版本的处理机组G1，接收任务副版本的处理机组G2。
　　输出：周期任务处理机分配结果的集合Assign1={（τi，pk，（αi，pjpk∈G1，pj∈G2}。
　　PGFTS（
　　{
　　1
　　L←（τ1，τ2，…，τn；//到达的一组周期任务，//按照周期大小的升序依次进入准备队列L
　2
　　m←|G1|， h←|G2|；//得到处理机组G1和G2的处理机个数
　　3
　　ε←L；//任务执行队列初始化
　　4
　　do until ε=
　　5
　　{for each τi∈ε；
　　6
　　{（τi，pj←selectprocessor（τi，G1；//在G1中为τi选择满足可调度的处理机
　　7
　　if（pj≠null{Assign1←Assign1+（τi，pj；ε←ε-{τi}；}
　　8
　　else{m←m+1； Assign1←Assign1+（τi，pm；G1←G1+{pm}； ε←ε-{τi}；}
　　9
　　（αi，pj←selectprocessorbasedstatus（αi，G2，status（αi；
　　/*根据副版本αi 的status（αi，在G2中选择首次满足可容错调度的处理机*/
　　10
　　if （pj≠null{Assign1←Assign1+（αi，pj；}
　　11
　　else {h←h+1； Assign1←Assign1+（αi，ph；G1←G1+{ph}；}
　　}//end for each τi∈ε
　　}//end do until ε=
　　12
　　return Assign1；
　　}
　　程序后
　　上面5～11中的for each循环是针对一组周期任务的每个任务，所以要循环n次。内层为每个周期任务的主副版本基于首次满足的算法思想选择处理机，平均需要l/2次。所以，PGFTS算法的时间复杂性为O（nl。
　　2.2非周期任务容错调度
　　本文采用最早截止时限优先（Earliest Deadline First， EDF算法给到达的非周期任务分配优先级，高优先级的就绪任务可抢占已被调度的较低优先级的任务。分配非周期任务主版本到已分配的周期任务主版本间的空闲时间槽上执行，非周期任务副版本分配到已分配周期任务副版本的处理机上执行。
　　设有一组非周期任务主版本集合Λ={σ1，σ2，&hell ip;，σk}在某处理机上周期任务主版本间的空闲时间槽上运行，它们已经按照优先级由高到低的顺序排列，在某一时刻，一个新任务σnew到达该处理机，需检测该处理机上新任务集Λ=Λ∪{σnew}的可调度性。由于非周期任务到达的随机性，任务σi的完成时间fi随着新任务的到达会发生改变，是时间t的函数。设新任务和系统中原有任务按截止时限非递减的顺序重新排序后的新任务集为Λ={σ1，σ2，…，σj，σnew，σj+1，…，σk}，由于新任务不会抢占高优先级任务的执行，只会影响σnew之后的低优先级任务的完成时间。
　　2.2.1非周期任务σi的完成时间分析
　　设在时刻t，σi∈{σj+1，σj+2，…，σk}，σnew插入前σi的开始时间为sti，完成时间为fi，σi的剩余执行时间为Ci（t。下面分3种情况讨论任务σi∈{σj+1，σj+2，…，σk}在周期任务主版本之间的空闲时间槽上的完成时间。
　　情况1假设任务σi∈{σj+1，σj+2，…，σk}，若在σnew插入之后，σi整个执行过程仍旧在其原来的时间槽中，则σnew插入之后，σi新的开始执行时间和完成时间分别为st′i=sti+Cnew、 f′i=fi+Cnew。图2（a给出此种情况的一个实例。
　　情况2假设任务σi∈{σj+1，σj+2，…，σk}，在σnew插入之后，若σi整个执行过程分成两部分σi1，σi2，σi1仍旧在原来的时间槽（[t1，t2]中执行，σi2转移到下一个时间槽（[t3，t4]中执行，则σnew插入之后，σi新的开始执行时间和完成时间分别为st′i=sti+Cnew、 f′i=t3+Cnew-（t2-fi。图2（b给出此种情况的一个实例。
　　情况3假设任务σi∈{σj+1，σj+2，…，σk}，在σnew插入之后，σi整个执行过程由在原来的时间槽[t1，t2]中执行，转移到下一个时间槽[t3，t4]中执行，则σnew插入之后，σi新的开始执行时间和完成时间分别为st′i=t3+Cnew-（t2-sti、 f′i=st′i+Ci。图2（c给出此种情况的一个实例。
　　图片
　　图2非周期任务σi的执行情况
　　2.2.2非周期任务集可调度判定
　　定理3 非周期任务集可调度判定。新任务σnew到达处理机后，按最早截止时间优先策略EDF将新任务插入之后形成的新任务集{σ1，σ2，…，σj，σnew，σj+1，…，σk}可调度的充分必要条件为：对于所有任务σi∈{σnew，σj+1，…，σk}，其完成时间fi满足fi≤ai+Di。   []
　　证明新任务σnew到达后，按EDF策略，形成新任务集{σ1，σ2，…，σj，σnew，σj+1，…，σk}，对新任务集来说，任务所要求的截止时间早于σnew的任务的完成时间不受影响，只要σnew和截止时间晚于σnew的任务满足各自的截止时间要求，则整个新任务集就是可调度的，即对于所有任务σi∈{σnew，σj+1，…，σk}，只要其完成时间fi满足fi≤ai+Di，则新任务集是可调度的。证毕。
　　2.2.3非周期任务主副版本分组容错调度算法
　　算法2非周期任务主副版本分组容错调度算法（Aperiodic tasks FaultTolerant Scheduling algorithm based on Grouping， AGFTS。