一类分布式控制系统中带有优先约束的周期性任务的容错调度

一类分布式控制系统中带有优先约束的周期性任务的容错调度刘怀,黄建新（南京师范大学，电气与自动化工程学院，南京，21004）FAULTTOLERANTSCHEDULINGALGORITHMFORPERIODICTASKSWITHPRECEDENCECONSTRAINTSINACLASSOFDISTRIBUTEDCONTROLSYSTEMLIUHUAI,HUANGJIANXINSCHOOLOFELECTRICALACCEPTED20030105ABSTRACTWITHTHEINCREASEOFTHECOMPLEXITYOFTHEDISTRIBUTEDCONTROLSYSTEMSDCS,THEYARESUBJECTTOHARDWAREFAILURESANDSOFTWAREFAILURESHOWEVER,LOOPTASKSINDCSMUSTBEFINISHEDBEFORETHEIRDEADLINESINANYCASETHEREFORE,ITISNECESSARYTOOFFERFAULTTOLERANCETODCSFORDISTRIBUTEDCONTROLSYSTEMSINWHICHTHEREAREPRECEDENCECONSTRAINTSAMONGLOOPTASKS,THESYSTEMMODEL,TASKMODELSANDFAULTTOLERANTMODELAREPRESENTEDINTHESEPAPERFIRSTLYTHENAFAULTTOLERANTSCHEDULINGALGORITHM,WHICHCANTOLERANTHARDWAREFAILURESANDSOFTWAREFAILURESSIMULTANEOUSLY,ISDESIGNEDBASEDONTASKDUPLICATIONTECHNIQUETHEPRECEDENCECONSTRAINTSAMONGLOOPTASKSANDTHEREQUIREMENTTHATTHEPRIMARYCOPYANDBACKUPCOPYOFEACHLOOPTASKMUSTBEEXECUTEDSERIALLYAREMETBYDESIGNINGASCHEDULINGSEQUENCEBECAUSEOFTHERELATIONSHIPBETWEENTHESAMPLINGPERIODANDTHECONTROLPERFORMANCE,ANIMPROVEDPARTICLESWARMOPTIMIZATIONALGORITHMISEMPLOYEDTOOPTIMIZESCHEDULINGSEQUENCESRESULTSOFCOMPUTERSIMULATIONSHOWTHATTHEALGORITHMPRESENTEDINTHISPAPERCANTOLERATEHARDWAREFAILURESANDSOFTWAREFAILURESANDOBTAINOPTIMALSCHEDULINGSEQUENCEINORDERTOACQUIRETHEOPTIMALSAMPLINGPERIODANDTHEMINIMALPROCESSORSTHATISNECESSARYFORTHESYSTEMTHISSHOWSOURALGORITHMISEFFECTIVEKEYWORDSDISTRIBUTEDCONTROLSYSTEMFAULTTOLERANTSCHEDULINGSCHEDULINGSEQUENCEPARTICLESWARMOPTIMIZATION摘要随着分布式控制系统复杂性的增加，系统出现硬件故障和软件故障的可能性增大，而系统中的任务在任何情况下都必须在其时限前完成，因此需要为分布式控制系统提供容错能力。本文针对回路任务之间具有优先约束的分布式控制系统，先给出了系统模型、任务模型和容错模型。然后基于版本复制技术设计了可同时容忍软件故障和硬件故障容错的容错调度算法。算法通过设计一个调度序列来满足回路任务之间存在的优先约束关系和主副版本之间串行执行需求。考虑到系统的采样周期与系统的控制性能有关，采用改进的粒子群算法对调度算法进行了优化。仿真实验表明本文所设计的调度算法能够同时容忍系统可能出现的硬件故障和软件故障，并能获得优化的调度序列，从而获得优化的采样周期和系统所需的最小处理器数目，这说明本算法是有效的。关键词分布式控制系统，容错调度，调度序列，粒子群优化SUPPORTEDBYTHENATIONALNATURALSCIENCEFOUNDATIONOFCHINAUNDERGRANTNO号61273114国家自然科学基金作者简介刘怀1971,男,河北承德人,博士,副教授,主要分布式控制系统,网络控制系统,数字图像处理等黄建新1965,男,博士,副教授,数字控制系统,分布式控制系统中图分类号TP316文献标识码A1引言由于分布式控制系统具有控制灵活、可靠性高、扩展方便、可获得高的控制性能等优点，因此近年来已经被广泛应用于航天控制、核电站控制、过程控制系统、加工过程自动控制系统及其他自动控制系统中。随着分布式控制系统复杂性的增加，系统出现软件故障和硬件故障的可能性增加。然而，分布式控制系统是一类强实时系统，如果系统中的实时任务不能在它们的时限前完成，会造成灾难性后果（如人员伤亡或经济损失）。因此，分布式控制系统的一个基本特性就是在任何情况实时任务必须在它们时限前完成1。为了提高分布式实时系统的可靠性，近年来出现了几种容错调度模型（1）三冗余模型（TRIPLEMODULARREDUNDANCY，TMR）3；（2）主版本/副版本模型（PRIMARYBACKUP，PB）；（3）块恢复模型（RECOVERYBLOCKMODEL）。TMR模型采用三倍的处理器运行相同任务的冗余版本，并通过输出投票来标记错误，从而实现容错。这种方法需要三倍的硬件，故其硬件投资大、比较昂贵，所以仅用于容错系统中最为关键的核心部分4。PB模型采用在两个不同的处理器上串行执行一个任务的两个版本和可接受实验检测运行结果实现容错5。块恢复技术通过为任务设计检查点，当出现故障时，从任务最后一个正确执行的检查点重新执行，从而实现容错6。在这些方法中，PB模型是一种有效的容错技术7，因而PB模型（包括PA模型PRIMARY/ALTERNATE，主部/替代部分）近年来发展迅速5,719。对周期性任务，基于PB模型针对容忍一个处理器故障和提高处理器利用率提出了很多静态容错算法8,9,10,11。这些方法通过在两个处理器上调度一个任务的两个版本实现容错，并采用可接受实验检测输出结果的正确性。PB模型有三种策略主动副版本技术9；被动副版本技术8,10；版本重叠技术11。对非周期任务，出现了动态容错调度算法，能够动态调度带有资源约束或优先约束的实时任务5,12。这些算法（静态算法和动态算法）设计为仅容错一个处理器故障，且不能容错软件故障。与硬件故障相比，软件故障出现的频率更高13。针对软件故障（暂时性故障），提出了两种容错调度策略14,15,16,17,18一种是PA技术14,15；另一种是重复执行技术16。文献14基于固定优先级抢占策略对单处理器系统提出了BCE算法，用于软件故障容错，并在保证所有替代部分时限的情况下调度尽可能多的主部分。为了提高主部分的成功率，在BCE的基础上提出了一些软件故障容错调度算法，如PKSA17、DPA和EDPA算法18、MDPCSA和ODPCSA算法19等。这些算法针对的都是单处理器系统的软件故障，它们不能应用于分布式系统，且不能容忍硬件故障。当实时性要求和计算质量要求无法同时满足时，为了满足实时性要求需要降低计算质量14。LIN等提出了非精确计算概念（IMPRECISECOMPUTATION，IC），用于有实时性要求的迭代计算问题20。后来IC用于设计容错调度算法以增加主版本或主部分的利用率21。由此可见，容错调度算法仅仅是针对某一类故障（硬件故障或软件故障），还未在现有的文献中发现能够同时容忍硬件故障和软件故障的调度算法。因此，本文针对一类分布式控制系统设计出可同时容忍软件故障和硬件故障的容错调度算法。2任务模型，系统模型与容错模型21任务模型与系统模型分布式控制系统一般是由多个通过有限带宽互联处理器构成。一个分布式控制系统往往需要运行多个控制回路。每个控制回路以固定的频率运行，且需要实现多种功能，如数据采集、控制计算、控制输出、监控、数据存储等。这些功能之间相互联系、相互影响，因此一个控制回路可以看作一个控制回路。一个分布式控制系统为了实现多种控制功能，可能需要采用多种不同类型处理器，故分布式控制系统是异构的。基于此，分布式控制系统描述如下。定义1一个分布式控制系统描述为一个处理器集合112PR,R2M其中，为处理器集；为第个处理器；为处理器数。PRI由于系统中的处理器类型不同，即一个任务在不同的处理器上的执行时间不同，因此引入执行时间向量如下2,IIIICC其中表示控制回路任务在处理器上的执行时间。为了表示处理器的处理器速度的不同，给出处理能力系数的概念。ICJIPRJ定义2处理器的处理能力系数表明一个任务在处理器的执行速度，定义如下式。PRJPRJ3PRRIJJCNO其中和分别表示任务在标准处理器上的执行时间和任务在处理器上的执行时间。标准处理器是在所有处ICNORPRIJIIPRJ理器中选择一个处理器规定其处理能力系数为1。为了要使系统具有容错能力，本文采用PB技术，即每一个任务都有主版本和副版本，它们相互独立，在不同的处理器上运行。由于系统出现故障的可能性很小（系统出现故障的可能性不超过101022，系统一般正常运行任务的主版本，因此任务的主版本的执行决定系统的控制性能，而副版本执行的情况对系统的控制性能影响不大，故这里采用IC技术。为了提高系统的控制性能，系统的主版本应实现较多的功能，如数据采集、更精确的控制计算、控制输出、显示更新、存储数据、系统优化等等。因此，任务的主版本更为复杂和执行时间更长。而任务的副版本仅仅在主版本出现故障时才执行，所以它仅实现必要和简化的功能，如数据采集、简单和必要的控制计算、控制输出等；可以不实现主版本中所实现的一些辅助功能，如显示更新、数据存储、优化等。所以任务的副版本更简单，执行时间更短。基于此，任务模型描述如下定义3分布式控制系统中的任务集为，其中N为任务数目，为第个回路任务且表示为一个四元组。1,NS2I4,PBITDT式中T为采用周期，D为任务时限，为任务主版本，为任务的副版本。和描述为三元组。PTBTPTB5,PRPCA式中，和分别为对应版本的最大执行时间、所在的处理器和到达时间。显然，和CPRAPRRPBIJIJTCTPRPIJTC分别为任务的主版本和副版本在处理器上的执行时间，这说明在同一个处理器上的同一个任务主版本的执行时间BIJTIPRJ比副版本的执行时间长。由于任务的主版本比较复杂和执行时间长，所以其更易受软件故障影响而执行失败；而副版本简单和执行时间短，故假设其在没出现硬件故障时可以正确执行。本文针对同步分布式控制系统研究软件故障和硬件故障容错调度算法，即。由于控制系统采样周期可以在一定范围内取值，将满足系统控制要求的最大采样周期记为。12NTTMAXT实际上，各控制回路之间并不是孤立的，为了实现先进的控制，提高系统的控制性能，控制回路之间可能会存在优先约束，如串级控制系统中的外回路必须在内回路开始前执行完成。引入一个优先关系矩阵，元素表示回路任务和之间的,IJNRR,IJRIJ优先约束关系。取值1和0。如果回路任务必须在回路任务开始前完成，；否则。,IJRIJ,1IJ,0IJ为了评价调度算法，处理器资源利用率定义如下。定义4处理器的平均利用率为成功执行的回路任务主版本的总时间与处理器运行时间之比的平均值。描述如下611PRQNIPICOUT本文设计的调度算法基于以下假设（1）假设系统中处理器数目和回路任务数目是固定的。实际上，分布式控制系统设计后，其处理器数目和回路任务是确定的。（2）假设回路任务的时限等于其周期。因为只要对被控对象的控制在下一个采样时刻到来之前实现控制即可，所以回路任务的时限设置为其周期。22容错调度模型系统中每个处理器都可能出现故障，同时由于软件BUG每个任务都可能执行失败。本文所研究的容错问题基于如下故障模型。A一个硬件故障和软件故障不会同时出现，即某一时刻仅出现一个处理器故障或者软件故障。另外由于每个处理器某时刻最多有一个任务的主版本执行失败，所以某个处理器在某个时刻仅出现一个软件故障。在另一个故障出现前，那些由于主版本执行失败（主版本被分配到故障处理器上或者出现软件故障）的任务通过执行它们的副版本已经顺利完成。注1事实上，硬件故障和软件故障出现的概率很低（系统故障的概率不超过1010）22，因此硬件故障和软件故障同时出现的概率更低。另外某处理器在某时刻执行一个确定的任务，所以软件故障在某时刻仅会影响一个任务的执行。因此本假设符合绝大多数实际情况。B由于硬件冗余策略可实现对永久硬件故障的容错，所以本文假设硬件故障和软件故障都是短暂的，即硬件故障和软件故障值持续一个有限的、短暂的时间间隔，它们只影响一个任务。另外，所有的故障都是独立的，即一个故障的出现与否不会影响另一个故障的出现。C处理器故障是FAILSTOP模式，即处理器处于正常运行状态或者故障状态。硬件提供故障隔离，一个故障处理器不会引起非故障处理器出现错误，即处理器是独立的。D如果一个处理器出现故障，该故障能够被其他处理器即刻检测到。对于出现的软件故障也能及时地被处理器检测出。对于处理器众多的大系统的多处理器故障，可采用如下的容错模型实现容错。将处理器划分为几个小组，前述容错模型应用到每一个小组23。从而实现对多个处理器故障容错，但是每一个组在某一时刻仅能出现一个处理器故障。3容错调度算法设计本文针对具有优先约束的分布式控制系统中的回路任务，采用PB技术设计可同时容忍硬件故障和软件故障的调度算法。每个回路任务都有两个版本主版本和副版本，它们分配在不同的处理器上。一般情况下，系统运行任务的主版本，当某任务的主版本由于软件故障或硬件故障而执行失败时，执行分配到其他处理器上该任务的副版本，从而实现容错。考虑到任务主版本的计算结果更为精确，所以尽可能执行任务的主版本。由于主动副版本技术是任务的两个版本同时运行，需要占用大量的处理器资源，所以不能采用主动副版本技术。另外，当两个任务的副版本分配到一个处理器上，而它们的主版本分配在不同的处理器上，如果这两个任务的主版本由于软件故障或硬件故障同时执行失败，需要执行它们的副版本，所以不能采用副版本重叠技术。基于此，我们采用被动副版本技术设计容错调度算法。容错调度算法设计原理首先设计一个调度序列，调度序列包含有所有任务的主版本和副版本；执行时，分配到一个处理器上的任务根据它们在调度序列中的排列顺序执行，在调度序列中先出现的先执行，在调度序列中后出现的后执行；分配到不同处理器上的任务可并行执行，以提高资源利用率，但同一个任务的主版本和副版本必须串行执行；存在优先约束关系的回路任务，根据优先关系安排它们在调度序列中的位置，需要先执行的回路任务的主版本和副版本在调度序列中出现位置均早于后执行的回路任务的两个版本。因而，本算法设计分为两个步骤（1）构造符合要求的调度序列；（2）将任务（包括主版本和副版本）分配到各个处理器上。31调度序列的构建调度序列必须包含所有的回路任务；且每个回路任务在调度序列中出现两次，第一次出现表示该回路任务的主版本，第二次出现表示该回路任务的副版本。每个处理器调度分配其上的任务根据这些任务在调度序列中出现的先后次序。显然调度序列的长度为回路任务数目的2倍，即为。N例1，假设系统中有4个回路任务，有两个处理器，构造的调度序列如图1所示。假设任务、和分配在处理2PT31BT4器上，其余的任务分配在处理器上。则这两个处理器上任务执行顺序如图2所示。PR2PRFIG1SCHEDULINGSEQUENCEANDITSCORRESPONDINGTASK图1调度序列及对应的任务FIG2EXECUTIONORDEROFTASKCOPIESASSIGNEDONEACHPROCESSOR图2各处理器上任务的执行顺序并不是所有的由回路任务构成的调度序列都满足要求，只有满足要求的调度序列才可用于调度的，基于此给出合法调度序列的定义。定义5对于第二节给出的任务模型和系统模型，当一个调度序列满足下面的两个条件，调度序列才称为合法的调度序列。（1）每个回路任务在调度序列中出现的次数必须是两次，分别代表该任务的两个独立版本（主版本和副版本）。（2）对于回路任务和，如果，在调度序列中两次出现的位置必须都早于出现的位置，以保证在开始前IJ,1IJRIJIJ完成。211342432PTPTBT3PT4T2BT43BTSCHEDULINGSEQUENCECORRESPONDINGTASKCOPY2PTBT3PT1BT1PR1PT4PT2BT3BT2R31任务的分配算法由于回路任务的主版本和副版本必须在处理器上运行，因此必须将任务的主版本和副版本分配到各个处理器上。而任务的分配问题为NP难题15，故一般采用启发式任务分配算法求取次优解。本文基于首次适应策略给出启发式任务分配策略，分配的原则是将任务分配到该任务完成最早的处理器上，且同一个回路任务的主版本和副版本分配在不同的处理器上。因此需要计算任务在各处理器上完成时间。算法1计算任务在各处理器上的完成时间，分为如下两种情况。（1）对于主版本任务，如果，其在处理器上的完成时间按式7计算。PIT,0KIR1,2ANDKIPRJ7PRRPPIJLJIJTFTC其中（为主版本或副版本）为分配到处理器上且在调度序列中位于前面的最后一个，为在处理器上的完LJPITPRLJFLPRJ成时间。如果，则其在处理器上的完成时间按式8计算。,1KIR,2ANDKIPRJ8R,MAXPR,RPPBIJIJLJKJTFTCTFT（2）对于副版本任务，在处理器上的完成时间按式9计算。PITPRJ9RPR,AXPR,RPBPIJIJLJIJTFTTFT其中（为主版本或副版本）为分配到处理器上且在调度序列中位于前面的最后一个，为在处理器上的完LPJPITLJLPRJ成时间。在此基础上，给出任务的分配算法，描述如下。算法2任务的分配算法。（1）输入回路任务数目，每个回路任务主版本和副版本在标准处理器上的执行时间，处理器数目，每个处理器处理能力系数，所设计的调度序列。（2）令。K（3）判断调度序列中第个位置上的任务是主版本还是副版本，若该位置上的任务为，根据算法1计算任务在各处KPITPIT理器上的完成时间，如果处理器满足，则任务分配到处理器；若该位置上的任务为，PRJ1PRMINPRPPIJILLMTFTFPITPRJBI根据算法1计算任务在除（任务对应的主版本任务所在的处理器）外各处理器上的完成时间，如果处理器满足BITPITBIPRM，则任务分配在处理器。PRRMNRPIBIINMTTFFITR（4）如果，令并重复（3）、（4）步；否则任务分配结束。2KN1K注2任务分配算法是静态分配算法，在系统运行前进行，在系统开始运行后，各任务所在的处理器不发生变化，从而减少算法的开销。定理1将调度序列中第一个任务的主版本开始执行与最后一个任务的副版本执行完成之间的间隔时间称为系统的响应时间，记为。如果存在一个调度序列满足，分布式控制系统中的所有回路任务都是容错可调度的。RMAXRT证明显然，如果，任务的所有版本都能在前完成，而回路任务的时限等于其周期，所以回路任务的主版本和副版MAXTMAXT本都能在其时限前完成。因此任务都是容错可调度的。注3定理1给出了判断分布式控制系统中回路任务容错可调度的充分条件。如果对于分布式控制系统能够找到一个满足定理1的调度序列，则系统是容错可调度的。但如果对于一个分布式控制系统找不到满足定理1的调度序列，就不能判断系统中的任务是否容错可调度的。根据文献24可知，控制回路的采样周期越小，系统的控制性能越高，因此可选择使系统中的回路任务容错可调度的条件下选择最小的采样周期，故对于一个调度序列可选择系统响应时间作为回路任务的采样周期，称为最佳采样周期。如果存在一个合法调度序列，其系统的响应时间在所有的调度序列中最小，则该调度序列称为最佳调度序列，此时对应的最佳采样周期称为优化采样周期，记作。OPTT4调度序列的优化对于一个分布式控制系统，采样不同的调度序列，可获得的系统最佳采样周期可能不同。例2，设有4个回路任务，2个处理器（设处理器相同），回路任务各个版本的参数如表1所示。假设，其余的。所构造的两个调度序列如图3所示。1,3R,0IJRTABLE1PARAMETERSOFLOOPTASKS表1回路任务参数TASKCOPY1PTBT2PT2BT3PT3BT4PT4BTEXECUTIONTIME8232803886358435SCHEDULINGSEQUENCE121121221PROCESSORITISASSIGNEDONSCHEDULINGSEQUENCE212122121SCHEDULINGSEQUENCE1082016611420482200STARTTIMESCHEDULINGSEQUENCE2084822021162020237SCHEDULINGSEQUENCE18211480204200239166235FINISHTIMESCHEDULINGSEQUENCE28211616224020223784272根据第2节所设计的调度算法，各回路任务的主版本和副版本所分配的处理器及开始和结束时间见表2。由表2可见，各回路任务的主版本和副版本分配在不同的处理器上，且串行执行，且具有优先约束关系的回路任务主版本和副版本的执行满足优先约束要求，调度序列1的系统响应时间为239，而调度序列2的系统响应时间为272，则采用调度序列1时可获得的最佳采样周期为239，而采用调度序列2时可获得的最佳采样周期为272。由此可见采用不同的调度序列，可获得的最佳采样周期也可能不同。在分布式控制系统中回路任务数目众多（可能多达数百个），不同调度序列的系统响应时间差别很大，因此需要构造最佳的调度序列，减少采样周期，以提高系统的控制性能。FIG3TWOSCHEDULINGSEQUENCES图3所构造的两个调度序列考虑到系统中所有回路任务的采样周期相同，减少采样周期可提高回路任务的控制性能。因此调度序列的优化为如下优化问题。9SUBJECTINMOTT其中为约束集合，包括调度序列合法性及处理器对任务的执行要求。ST系统中回路任务数目众多，所以合法调度序列的数目非常大，且调度序列和其可获得的最佳采样周期之间的关系不能用显示函数关系描述，故很难获取最佳调度序列。为了解决这类问题，出现了优化算法，如遗传算法（GA）25、粒子群算法（PSO）26,27等。与GA相比较，PSO由于不要交叉和变异操作且参数较少，因而比较简单26。本文对离散PSO（DPSO）进行改进，用于对调度序列进行优化。对于PSO，随机产生个粒子，每个粒子的一个位置表示问题解空间中一个可能解。这里每个粒子的一个位置都表示一个调M度序列，第I个粒子的第K个位置用一个维向量表示。向量中的每一个元素都为一个整数，且同一个整数在向量出现两次，2NIPK每一次表示回路任务的一个版本。第I个粒子的最佳值记为，表示第I个粒子经历的所有位置中的最佳位置。全局最佳值记作OI，表示所有粒子经历的所有位置中的最佳位置，即所有形成的调度序列中最佳的调度序列。GP由于粒子中的所有位置向量的元素都是非连续的整数，所以不能采用KENNEDY和EBERHART提出的位置更新公式28。基于离散遗传算法交叉和变异操作，给出在和基础上离散粒子群算法的位置更新算法如下。OIPG算法3位置更新算法。（1）基于的更新操作。首先从中随机选择一个片段的元素，并将它们放在的对应位置上。而将中与所IPKOIOI1IPKIPK选择片段中的相同的元素（包括整数值和出现的次数）剔除。最后将中剩余的元素放在中已放置选择片段元素的前面IPKI和后面（不改变排列顺序）。例3，假设系统中4个回路任务，2个处理器且，基于的更新操作如图4所示。在中1,3RIOIOI14213324SCHEDULINGSEQUENCE1SCHEDULINGSEQUENCE221134243从第3个位置到第5个位置上的元素选择为片段，放到的第3个位置到第5个位置；并将中与所选择的片段中相同的1IPKIPK元素剔除，见图4中第二行，剩余的元素（除掉虚线框框起来的元素）分为前2个元素和后3个元素两部分（因为只放置1IPK了第3个位置到第5个位置），放到中，见图4中第三行。1IPKFIG4RENEWINGOPERATIONS图4基于的更新操作IPKOI（2）基于的更新操作。与步骤（1）类似。首先从中随机选择一个片段的元素，并将它们放在的对应位IPKGG1IPK置上。而将中与所选择片段中的相同的元素剔除。最后将中剩余的元素放在中选择片段元素的前面和后面I1IK1IPK（不改变排列顺序）。（3）的调整。如果，必须满足表示回路任务的各个版本的整数在调度序列中的位置在表示回路任务的各个1IPK,1IJRIJ版本的整数的前面，如果不满足可通过交换它们的位置使之满足。假设且在调度序列中整数3的某次出现在整数某次出现的1,3R前面，则它们交换位置的过程如图5所示。这里和分别表示粒子第步和第步的位置，为中间向量。IPKIIPK11IPKFIG5MODIFICATIONOF1IPK图5的调整I定理2如果各个粒子初始位置是合法的，则经过更新后的位置仍然是合法的。证明各个粒子初始位置是合法的，则、和都是合法的。第（1）步中，在中随机选择一个片段的同时，在0IPOIGOIP中剔除与选择片段相同的元素（包括整数值和出现的次数），由选择的片段和中剩余的元素构成。没有引入新的整0IP0I1IPK数，也没有丢失原有的整数，故每个整数出现的次数依然为2次。第（2）步与第（1）步类似，所以中每个整数出现的次I数依然为2次。通过第（3）步保证了当时表示回路任务的各个版本的整数在中的位置在表示回路任务的各个版,1IJRI1IPKJ本的整数的前面。从而使得满足合法调度序列的所有条件，因此它是合法的。1IPK定理3如果系统中回路任务数目和处理器数目足够多，必然存在两个以上的调度序列，它们的系统响应时间相同。举例说明对于例2中的回路任务参数和处理器数目，构造如图6所示的调度序列3。FIG6SCHEDULINGSEQUENCE3图6新构造的调度序列3根据第3节的调度算法，任务的各个版本分配的处理器与调度序列1（见图3）中相同的任务的相同版本分配的处理器相同，且每个任务的各个版本开始和结束时间与调度序列1中的相同任务的相同版本的开始和结束时间相同，系统响应时间也为239，与调度序列1的系统响应时间相同。这说明了存在不同的调度序列，它们的系统响应时间相同。推论对于一个分布式控制系统，由于回路任务数目中多，最优的调度序列不是唯一的，即存在有多个调度序列，它们系统响ORIGINALSCHEDULINGSEQUENCE231324MODIFIEDSCHEDULINGSEQUENCE21332432选择的片段141324OIIPK21134243剔除的元素1IK12134324SCHEDULINGSEQUENCE321143243应时间相同且为所有调度序列中最小的。5算法仿真及分析对第2节给出的系统模型和任务模型，通过仿真实验研究调度算法和优化算法的有效性，分析处理器利用率和最佳采样周期。在仿真实验中，任务的参数选择如下。为区间60,90上均匀分布的随机数，两个回PITCNOR03BPIITCNORTNOR路任务之间存在优先约束的概率为001，如果两个回路之间存在优先约束，规定序号小的回路任务必须先于序号大的回路任务执行，而且一个回路任务至多和另外一个回路任务之间存在优先约束。与或与之间交叉片段长度是在0和调度序列长度OIPIKG1IPK之间随机选择。迭代次数为250，人口数量为100。任务调度算法和优化算法仿真程序基于VISUALC2010平台上开发的，运行在DELLINSPIRON5520计算机上。实验1，设系统中有4个处理器，10个回路任务。处理器参数如表2所示，回路任务的参数如表3所示。其中和1,9R，其余的。实验结果见表4、图7和图8所示。2,10R,0IJRTABLE2PARAMETERSOFPROCESSORS表2处理器参数PROCESSOR1234PROCESSINGCAPABILITYCOEFFICIENT1111710701352TABLE3PARAMETERSOFLOOPTASKS表3回路任务参数（执行时间为在标准处理器上）EXECUTIONTIMEEXECUTIONTIMELOOPTASKPRIMARYBACKUPLOOPTASKPRIMARYBACKUP174226872626218766193621886619461189842556820106619TABLE4STARTTIME,FINISHTIMEANDPROCESSOROFEACHCOPYOFEVERYLOOPTASK表4回路任务各版本的开始和结束时间及所分配的处理器PRIMARYCOPYBACKUPCOPYLOOPTASKPROCESSORSTARTTIMEFINISHTIMEPROCESSORSTARTTIMEFINISHTIME12067381102240463648132671234161175444692192110530641176196610874921127111017641761918212318341912069310218121832061041121613181199050100150200250210220230240250260THENUMBEROFITERATIONAVERAGEOBJECTIVEFUNCTIONFIG7THERELATIONSHIPBETWEENAVERAGEOBJECTIVEFUNCTIONANDTHENUMBEROFITERATION图7平均目标函数和进化代数之间的关系（10个任务，4个处理器）FIG8OPTIMALSCHEDULINGSEQUENCE图8优化的调度序列由图7可见，平均目标函数随进化代数的增加而减少，并最终收敛于一个最小值，说明本优化算法能够对调度序列进行优化，本例中所获得的优化的调度序列如图8所示。根据优化调度序列和容错调度算法得到任务各版本所在的处理器、开始时间和完成时间，见表4。由表4可见，系统响应时间为206，即系统最优采样周期为206；且每个任务的主版本和副版本分配在不同的处理器上，它们在不同时间执行，因而满足任务容错要求和回路任务优先约束。各个处理器对任务的主版本和副版本几乎是一个接一个的执行，即分配在同一个处理器上在调度序列中相邻的任务之间几乎没有空闲时间，因此调度序列是最优的。由定义4可得处理器的平均利用率为7444。这说明本文给出的容错调度算法和优化算法是有效的。实验2，设系统有100个回路任务，10个处理器，以验证分布式控制系统中任务数量众多的情况下，调度算法的有效性。处理器参数见表5，回路任务参数见表6。回路任务之间存在有如下约束，1,7R2,103,451R4,3R5,601R8,27R，9,14R1,7R12,9R15,9R16,0R18,4R23,684,66,29,64,93,94，和，其余。实验结果见图9和图10所示。3,4,858,7,674,823,94,7R,IJRTABLE5PARAMETERSOFPROCESSORS表5处理器参数PROCESSOR12345678910PROCESSINGCAPABILITYCOEFFICIENT1131512991119812441146412595127381477514544TABLE6PARAMETERSOFLOOPTASKSEXECUTIONTIMEIS表6回路任务参数（执行时间为在标准处理器上）EXECUTIONTIMEEXECUTIONTIMEEXECUTIONTIMELOOPTASKPRIMARYBACKUPLOOPTASKPRIMARYBACKUPLOOPTASKPRIMARYBACKUP18024264193692048425577236641977021885259692010661911692012892613752214822415611816882617641918661919792320611821812422722123651924762225862526661927832421562431641097387591082877232963183084253161183268203364193474223572213687263773213865193970214067204182244274224380244465194583244668204784254879234968205071215167205275225368205483245573215674225771215868205969206076226181246289266365196464196571216673216778236879236987267066197175227287267377237476227574227687267773217867207982248074228179238270218362188489268564198664198766198872218986259067209163189271219384259467209568209681249780249879239983241006018050100150200250760780800820840THENUMBEROFITERATIONAVERAGEOBJECTIVEFUNCTIONFIG9THERELATIONSHIPBETWEENAVERAGEOBJECTIVEFUNCTIONANDTHENUMBEROFITERATION图9平均目标函数和进化代数之间的关系（100个任务，10个处理器）732491674122386754263444273229844979439896258159394612584395577123158674838852753451129283918346858544563862882306599457472270643711438338845519147785124657618902405836135135687241171616352274880770569220151452639394979819531361215087622682100774231174910915981889846505499606327689313578779669667579306433868790674110075571732197194260922572453722936295941033616640365369891448808520FIG10THEOPTIMALSCHEDULINGSEQUENCE图10优化调度序列由图9可见，平均目标函数随着进化代数的不断增加而不断减小，最后收敛于最小值，由此得到的最佳调度序列如图10所示。根据获得的最佳调度序列和容错调度算法，可确定任务各版本所在的处理器、开始时间和结束时间，从而确定了任务的各版本什么时候在哪个处理器上执行，且一个任务的主版本和副版本在不同的处理器上不同时间执行，确保系统的容错能力，同时满足回路任务之间存在优先约束；另外，分配在一个处理器上调度序列任务相邻的任务之间基本上没有空闲的时间间隔，因而调度序列是最优的。由此得到系统的最佳采样周期为772。由定义4可得处理器的平均利用率为7587。由此可见，本算法不仅适用于回路数目较少的系统，而且适用于回路数目众多的系统。实验3，设系统有100个回路任务，分析系统的最佳采样周期、处理器的平均利用率和处理器数目的关系。由于处理器不同时，很难比较处理器数目对最佳采样周期和处理器平均利用率的影响，因此本实验中假定处理器都相同，即处理器的处理能力系数都为1。任务的参数见表6。实验结果见图11。（试验结果为实验条件相同的情况下10次实验结果的最小值）。5810121518200_500_1000_1500_2000_07072074076078最佳采样周期处理器平均利用率THENUMBEROFPROCESSORSOPTIMALPERIODAVERAGEPROCESSORUTILIZATIONFIG11THERELATIONSHIPSAMONGOPTIMALPERIOD,AVERAGEPROCESSORUTILIZATIONANDTHENUMBEROFPROCESSORS图11优化采样周期、处理器平均利用率与处理器数目之间的关系由图11可见，随着处理器数目的增加，最佳采样周期减少，这是由于随着处理器数目的增加，每个处理器需要执行的任务数目减少，且每个处理器上执行的相邻任务之间几乎没有空闲时间，因而最终完成任务的时间减少，即系统的响应时间减少，系统最佳的采样周期减少。由图可见，但这一变化基本上是反比例函数关系，但存在微小差别，这是由于对于一个调度序列，每个处理器完成最后一个任务的时间并不相同，总存在差别，这个差别随着处理器数目的变化而变化并不大，基本上与接近于一个副版本任务的执行时间，这一差别在采样周期大时表现不太明显，但随着采样周期的减小，起作用就越来越大，因此上使得优化采样周期与处理器数目之间处理器的关系与反比例函数关系存在微小差异。另外，随着处理器数目的增加，处理器的平均利用率不是固定不变的，而是稍稍下降，由图可见，但下降幅度并不大，处理器数目由5增加到20，处理器平均利用率只下降了003左右，这是由于任务不可能平均分配到各个处理器上，不同处理器完成分配到其上任务的时间是存在一定差别的，这一差别在采样周期大时对处理器的平均利用率基本上没什么影响，但随采样周期最佳采样周期的减少，其作用越来越明显，从而使处理器的平均利用率随处理器的增加略微减少。另外，由图可见，不同的处理器数目，系统得到的优化采样周期不同，因此可根据系统对采样周期的要求选择处理器数目。如本例中，如果要求系统的采样周期小于1000，处理器数目必须大于10个（标准处理器数目），此时才能满足要求。6结论分布式控制系统可能出现软件故障和硬件故障，然而系统中的任务必须在其时限前完成，因此提高系统的可靠性是系统设计和实现的关键技术之一。本文针对一类分布式控制系统设计了可同时容忍软件故障和硬件故障的容错调度算法。首先，对同步采样的分布式控制系统进行分析，给出了系统模型、任务模型和回路任务之间优先约束关系模型；同时为了能够同时容错硬件故障和软件故障，给出了容错调度模型。然后基于版本复制技术设计了可容忍硬件故障和软件故障的容错调度算法。每个回路任务有主版本和副版本，它们分配在不同的处理器上串行执行，一般情况下执行回路任务的主版本，当回路任务的主版本因硬件故障或软件故障执行失败时，执行其他处理器上的该回路任务的副版本，从而实现容错。算法分为两步，设计调度序列和任务分配算法。通过所设计调度序列控制回路任务的优先约束关系，再通过分配算法将一个任务的主版本和副版本分配在不同的处理器上，从而实现容错。考虑到系统的控制性能与系统的采样周期有关，在保证回路任务的实时性情况，选择则系统的响应时间作为系统的最佳采样周期以提高系统的控制性能。而系统的最佳采样周期与所构建的调度序列相关，基于改进离散的粒子群算法对调度序列进行优化。最后对调度算法进行了仿真，仿真结果表明所设计的优化算法能够获取优化的调度序列；所设计的调度算法能够同时实现对软件故障和硬件故障的容错；说明本文所设计的调度算法是有效的。并给出了系统所需的最小处理器数目的求取方法。REFERENCES1HCHEN,WLUO,WWANG,ETALANOVELREALTIMEFAULTTOLERANTSCHEDULINGALGORITHMBASEDONDISTRIBUTEDCONTROLSYSTEMS2011INTERNATIONALCONFERENCEONCOMPUTERSCIENCEANDSERVICESYSTEMCSSS,NANJING,CHINA,JUNE2011,80833LMANCINIMODULARREDUNDANCYINAMESSAGEPASSINGSYSTEMIEEETRANSSOFTWAREENG,1986,12179864CMKRISHNAFAULTTOLERANTSCHEDULINGINHOMOGENEOUSREALTIMESYSTEMSTECHNICALREPORTS,HTTP/WWWUNIXECSUMASSEDU/KRISHNA/REPORTS/FTSCHEDPDF5GMANIMARAN,CSIVARAMMURTHYAFAULTTOLERANTDYNAMICSCHEDULINGALGORITHMFORMULTIPROCESSORREALTIMESYSTEMSANDITSANALYSISIEEETRANSACTIONSONPARALLELANDDISTRIBUTEDSYSTEMS,1998,911113711526SWKWAK,BJCHOI,BKKIMANOPTIMALCHECKPOINTINGSTRATEGYFORREALTIMECONTROLSYSTEMSUNDERTRANSIENTFAULTSIEEETRANSACTIONSONCOMPUTERS,2001,5032933017WLUO,FMYANG,LPPANG,ETALFAULTTOLERANTSCHEDULINGBASEDONPERIODICTASKSFORHETEROGENEOUSSYSTEMSAUTONOMICANDTRUSTEDCOMPUTINGLECTURENOTESINCOMPUTERSCIENCEVOLUME4158,2006,5715808AABERTOSSI,LVMANCINI,FROSSINIFAULTTOLERANTRATEMONOTONICFIRSTFITSCHEDULINGINHARDREALTIMESYSTEMSIEEETRANSACTIONSONPARALLELANDDISTRIBUTEDSYSTEMS,1999,1099349459CHYANG,GDECONINCK,WHGUIFAULTTOLERANTSCHEDULINGFORREALTIMEEMBEDDEDCONTROLSYSTEMSJOURNALOFCOMPUTERSCIENCEANDTECHNOLOGY,2004,19219120210HLIU,SMFEIAFAULTTOLERANTSCHEDULINGALGORITHMBASEDONEDFFORDISTRI