实时系统容错调度算法综述资料Word文档下载推荐.docx
《实时系统容错调度算法综述资料Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《实时系统容错调度算法综述资料Word文档下载推荐.docx（14页珍藏版）》请在冰点文库上搜索。
最坏响应时间
1引言
随着实时系统的功能日益强大，应用成本的逐渐降低，实时系统在其应用领域中所处地位迅速提高。
如果实时系统无法满足设计要求的运算结果的逻辑正确性和时间正确性，将造成重大的财产损失，甚至人身伤害，导致灾难性的后果。
因此，如何保证实时系统具有一定的可靠性以避免灾难性后果的发生，是当前实时系统一个十分重要的研究领域。
相对于其它计算机系统而言，实时系统对可靠性要求十分严格。
例如，在高炉炼钢的过程中，当错误出现时，实时系统必须能够提供降级服务，以保证能够将钢水排出高炉，因为放弃对高炉的控制将造成巨大的经济损失。
因此，实时系统必须采用专门的措施以保证系统可靠性指标的实现。
对于安全关键系统中的实时系统，其可靠性的主要考虑是系统的持续工作时间，即系统尽可能连续工作而不出现失效。
在这里，失效是指实时系统丧失对安全关键系统的控制能力。
为达到可靠性目标，实时系统的设计人员通常采用容错技术。
容错技术主要用于保证系统在出现错误的情况下仍然能够继续运行。
近几年来，对容错实时系统的重视程度不断提高，取得了大量有价值的研究成果。
目前，容错实时调度算法研究主要集中在理论探讨阶段，致力于设计新颖的资源管理分配策略，在保证系统的时间特性和可靠性的前提下尽可能提高资源利用率，所获得的算法在理论上拥有较高的资源利用率，但运算复杂度较高，要投入实际应用还有待改进。
此外，在引入容错策略后，实时系统变得更加复杂，其设计和实现的工作量增加很大，不利于提高实时系统得可靠性。
针对当前容错实时系统研究中存在的问题，有必要设计实用、简单、高效的容错实时调度算法，实现容错调度功能，这对容错实时系统在安全关键系统中的应用具有很大现实意义。
2常见的容错调度算法
实时容错调度算法根据实时任务的分派和可调度性测试的时机可分为三类，即静态任务调度、动态任务调度和混合任务的调度[1]。
这里任务的分派是指选择某一个任务到某一处理机上调度的过程；
而任务的可调度性测试指的是确定任务是否可以在某一个系统上调度的过程。
文献[2]提出的一种适应性的实时容错调度算法，通过调节主/副版本间的重叠长度在系统可靠性和性能间取得折中。
文献[3]提出一种延迟调度副版本策略的技术，对主动副版本尽量延迟调度，并通过在主版本成功执行后终止副版本执行来减少系统的冗余，从而提高系统的可调度性。
文献[3]提出的技术是基于不可抢占性的非周期任务。
受到文献[3]的启发，文献[4]提出一种基于抢占的周期性任务的实时容错调度算法，提出一种基于该技术的以最小化处理机数目为优化目标的启发式任务分配算法。
表1描述了实时任务的调度分类。
其中，（a）表示所有任务的调度和分派都是离线的，在设计阶段进行的，执行严格的时间表，优点在于可预测性好。
但由于该调度基于简单的调度模型和严格的时间约束，存在脆弱和缺乏灵活性的缺点。
为了克服这种不灵活性，可以在任务进行实际分派时再检测任务的可调度性，如（c）。
（d）描述的调度方法其可调度性分析和任务分派都是在线进行的。
事实上，这样的调度分析成了一种接受测试，测试新到来的任务的截止期是否会被错过。
如果会被错过，则被拒绝调度；
否则就进入系统进行调度。
显然，这种调度方法是最具有灵活性的，但是在系统负载很重的情况下性能会很差，因此可预测性也很差。
最合理的调度方式是（b）中描述的调度方法，目前来说基于优先级的调度方式是最能被接受的。
基于以上对实时任务调度的分类，本文对实时容错的调度方法分类如下。
2.1静态实时容错调度
静态调度方法中，任务的分配离线进行的，即在实时任务正式在处理机上调度执行前，先把任务在处理机上的分配和调度时间安排好，在任务正式开始执行后按照预先的调度方案执行。
这种调度方法主要用于周期任务的调度，它的优点在于能够预先安排好调动，减少任务调度过程中的开销；
而缺点在于缺乏灵活性，在实际的调度中不能够及时地根据系统资源和任务的执行情况进行及时的调整。
文献[2-7]提出的算法都是基于静态调度算法的。
可抢占周期任务集的静态容错实时调度的实时任务集模型可以表述：
实时任务集S={t1,t2,…tn}，若采用RM作为基本调度算法，任务按周期大小以增序排列（T1
T2
⋯
Tn），且各个任务间相互独立。
每个任务ti定义为一个四元组<
Ci,Di,Ti,Pi>
，其中，Ci、Di和Ti分别为任务ti的执行时间、时限、周期，且满足Ti=Di。
该算法按周期大小定义任务的优先级，周期最短的优先级最高，周期最长的优先级最低，则任务优先级排列如下：
P1
P2
Pn。
下面我们在介绍3种单处理器可抢占周期任务集的静态容错实时调度算[8]：
PRA（PrivateReservationAlgorithm）、CRA（CommunalReservationAlgorithm）[9]和FT-RM（Fault-TolerantRM）算法[10]。
2.1.1PRA调度
时间冗余是容错重要的手段之一，利用时间冗余实现实时系统容错的研究工作开始于二十世纪九十年代初，在这一时期，最具代表性和实用价值的工作是S.Thuel提出的PRA和CRA。
PRA和CRA均以RM调度算法为基础。
对于因暂态硬件缺陷或暂态软件设计缺陷引起的实时任务运行出错，PRA和CRA调度出错任务利用冗余的处理器时间再次运行，或替代任务利用冗余的处理器时间运行。
PRA和CRA采用了不同处理器资源冗余策略，因而容错能力不同。
PRA为实时任务预留私有的处理器空闲时间，以保证任务ti在两个连续周期边界[kTi,（k+1）Ti]内能够重复运行（1+x）次，而不会导致其他任务的运行超过时限。
因此，PRA能够保证任务ti在连续出现x次错误的情况下仍能在时限到来前获得正确的运算结果。
在任务无错情况下，时间冗余使大量处理器资源处于空闲状态，PRA的资源利用率只有RM资源利用率的1／（1+x）。
因此，PRA的实际资源利用率远小于以最坏执行时间为衡量标准的最大资源利用率，即处理器资源实际能够支持的实时任务数大于可调度条件限制的实时任务数。
为改善调度条件，提高处理器资源利用率，CRA预留的处理器空闲时间由所有实时任务共同拥有，其大小为Cr=x*max（Ci），其中i∈S。
这样Cr能够满足实时任务集在[kTi,（k+1）Ti]内x次容错操作的时间需求。
若实时任务集组成简单，任务数量较少，且系统运行中不会出现新任务，PRA的可调度分析在系统运行前进行，运行时的调度策略可以通过对RM的简单改造来获得，实现简单，运行时的开销小。
因此，PRA特别适用于具有不变任务集，且资源需求较低、系统的运行环境较为恶劣、任务出错概率较高的系统。
此外，PRA具有相当大的灵活性，通过对x设置不同的数值，或对不同的任务设置不同的x，可以满足不同应用的需要。
2.1.2CRA调度
与PRA相比，CRA通过减少单位时段内的冗余时间，以降低单位时段内的容错能力为代价，提高了正常情况下实时系统的资源利用率和任务吞吐量,但是却降低了单位时段内的容错能力。
和PRA一样，CRA是在RM的基础上，利用任务的正常运行时问和容错操作时间之和代替任务的正常运行时间进行可调度分析。
PRA和CRA没有改变任务间的优先级关系，正常情况下，任务执行的顺序与RM调度时相同。
不同点在于，任务出错将被调度再次运行。
只要满足可调度条件，在被高优先级抢占的情况下，任务容错操作的次数
x，其时限要求必然满足。
CRA同样适用于具有不变任务集，且任务集组成简单、任务数量较少、资源需求较低、系统的运行环境较为恶劣、任务出错概率较高、可调度分析在系统运行前进行的静态任务系统中，运行时的调度方法可以通过对RM的简单改造来实现，具有相当大的灵活性。
PRA和CRA的最主要的缺点是：
不能适应较为复杂的动态运行环境。
在复杂的动态运行环境中，实时任务集的组成复杂，且系统的正常工作负载在不断变化，任务集是否可调度只能在系统运行时进行判断，而PRA和CRA的调度分析的运行开销较大，需要占用大量处理器资源，可能导致实时任务的运行超越时限。
2.1.3FTRM调度
在RM调度的基础上，S.Ghesh等人提出了FTRM调度。
与PRA和CRA的时间冗余策略不同，FTRM引入了备份任务的概念。
当系统在无错状态下正常运行时，备份任务拥有的处理器时间保持空闲，一旦实时任务运行出错，调度器便调度出错任务利用备份任务的处理器时间重新执行出错任务。
备份任务是一个虚拟的任务，但是具有确定的资源利用率。
FTRM将这部分资源作为预留的处理器资源，为容错操作提供保证。
在系统正常运行时，备份任务拥有的处理器时间保持空闲，当实时任务运行出错时，调度器将调度出错的任务利用备份任务的处理器时间进行容错操作。
可见，FTRM的时间冗余策略通过备份任务来体现。
在规定时段内的容错要求不同，则备份任务的资源利用率需求不同。
如果实时系统的容错要求是规定时段的单错误容错，设备份任务为tc，则其资源利用率为Uc=max（Ci/Ti），即实时任务的最高资源利用率。
系统运行过程中，FTRM要求备份任务的实例在每个周期边界就绪，在任意两个连续的周期边界内，处理器时间为lT-kTj，备份任务实例拥有的资源为Uc（lT-kTj）。
备份任务的实例在每个周期边界就绪，在所有任务中，备份任务是优先级最高的任务。
所以，根据RM算法，备份任务的实例总是在任意两个连续的周期边界内第一个被调度的任务。
为实现系统的容错要求，系统正常运行时，备份任务的实例总在调度器的管理下与处于就绪状态，且与当前优先级最高的实时任务交换运行次序，为该任务提供容错保证。
在当前任务进行容错时，如果有具有更高优先级的任务就绪，仅当该任务的时限较当前任务更接近于当前时刻时，新任务才能抢占当前任务。
2.2动态实时容错调度
与静态调度方法相对应的是动态调度。
在实时系统中，很多任务并非都以周期方式在处理机上进行调度，更多任务，特别是非周期任务都是随机到达系统并动态调度执行的。
在动态调度方法中，任务的分派和可调度性测试都是在系统运行时在线进行的。
这种情况下，可调度性测试实际上变成了一种接受测试（acceptancetest），测试动态到达任务的截止期是否会被保证，如果无法保证任务的截止期，任务将被拒绝调度。
可以看出，动态调度与静态调度相比有更好的灵活性，然后由于可调度性测试需要在线进行，它的调度算法的复杂度不能太高，并且由于无法保证是否可以被调度，算法的可预测性（predictability）很差。
文献[2,3,11,12]提出的算法都是基于动态调度算法的。
由上节可见RM可以作为静态容错实时调度算法的基础；
类似地，EDF可以作为动态容错实时调度算法的基础。
较典型的是容错EDF调度（FT-EDF）[13]。
FT-EDF通过改变EDF算法的可调度条件，在任务集设计阶段静态地预留处理器空闲时间，确保在规定时段内的单个错误容错。
基于单处理器可抢占周期任务集的动态容错实时调度，任务集的模型可表述如下：
存在任务集S={t1,t2,…tn}，若采用EDF算法作为基本调度算法，所有硬实时任务必须满足以下条件：
1）所有实时任务均为周期任务，且周期大于或等于时限；
2）所有实时任务必须在其时限到来前结束；
3）所有实时任务相互独立；
4）所有实时任务均具有恒定的运行时间。
任务按周期由小到大排列为T1
Tn。
任务ti的第k个实例在kTi时刻就绪，在（k+1）Ti时刻必须结束。
容错EDF以任务的时限与当前时刻的距离确定任务优先级，距离越近，优先级越高。
FT-EDF仅考虑暂态错误，为简化分析，当任务出错时，调度器调度出错任务再次运行。
为检测任务执行是否币确，任务结束前将进行错误检测，其开销计入任务的运行时间。
显然，任务t1的资源利用率必须满足：
U1=C1/T1
0.5，否则无法通过再次运行实现容错。
2.2.1基本EDF调度
对于满足调度条件的实时任务集，EDF算法按任务的优先级分配处理器资源，保证所有任务均满足时限要求。
若调度算法能够保证实时任务ti的第k个实例在kTi时刻就绪，在（k+1）Ti时刻必须结束，则该实例能够在不影响其他任务执行的前提下实现一次重新执行。
为此，将任务t1的资源利用率变为U1’=C1/（T1-Ci），则任务t1的第k个实例在时段[kT1,（k+1）T1-C1]内能够获得所需的运行时间Ci，[（k+1）Ti-Ci,（k+1）T1]内的时间可以用于该任务的容错操作。
该算法称为基本的FT-EDF，适用于调度资源利用率低、任务出错概率高的实时任务集。
2.2.2FT-EDF调度
与基本EDF不同，FT-EDF的冗余处理器资源由所有任务共享，适用于资源利用率高，出错概率低的实时应用[13]。
FT-EDF的设计目标是，在Tn+Tn+1时间段内，冗余的处理器资源能保证一次容错操作，且所有任务均满足时限要求。
因此，在两个连续的最大周期边界[kTn,（k+1）Tn]内，冗余的处理器资源为max（Ci），i∈S。
容错EDF仍旧按照任务的时限先后决定任务的优先级，时限近者优先级高。
系统运行时，若当前执行的任务t1出错，调度器调度该任务再次运行。
在容错处理的过程中，若新就绪的任务tj的优先级高于ti，则tj抢占ti。
若实时任务集S可由FT-EDF调度，当相邻两个错误发生的时间间隔大于Tn+Tn+1，则预留的空闲处理器资源可以满足任何任务的容错要求[13]。
FT-EDF通过调度器实现任务间空闲资源的共享和动态分配，调度算法较简单，同时保证系统正常工作时具有较高的资源利用率。
FT-EDF适用于高可靠、低故障率的实时系统。
2.3混合任务实时容错调度
在实时系统中，周期任务和非周期任务往往共同存在。
因此，响应的实时容错调度算法必须同时保证周期任务和非周期任务的容错特性，但是目前关于这方面的研究著述还不多。
文献[3]提出一种基于混合实时任务的实时容错调度算法，该算法在保证周期任务的容错能力的同时，尽量减少非周期任务的响应时间，然而该算法没有考虑非周期任务的容错特性。
文献[4]提出一种基于资源预留策略的分布式容错调度算法，该算法利用周期任务调度后的剩余时间片来调度非周期任务。
本文在BCE算法和PKSA算法基础上提出了一种调度混合型任务的算法。
2.3.1BCE算法
HanCC，ShinKG和wuJ在文献[14]中提出的BCE算法，利用最后机会原则和双版本技术实现对周期任务的容错操作。
BCE算法包括三部分：
基本算法（BasicAlgorithm），可用时间检测算法（CheckingAvailableTimeAlgorithm），消除空闲时间算法（EliminatingIdleTimeAlgorithm）。
按照任务周期值的非降顺序，确定每个任务优先权，周期短的任务具有较高的优先权值。
从时间PC到0这个反向区间内，按照优先权顺序，对每个任务实例的替代部分，采用向后速率单调算法（backward-RM）分配替代部分占用的时间间隔[STp（i,j）,EDp（i,j）]，（其中i为任务编号，j为实例编号，p为任务的第p个时间间隔），形成预分配时间表，正向调度的最早歼始时间正好是反向的最迟开始时间，使得替代部分在其截止期内尽可能地推迟执行，即具有最大的Ⅳz，。
由于计算模型中任务的可抢占性，因此每个替代部分所占用的时间片并不保证连续。
只要任务集能成功的生成预分配时问表，就可以在任务时限到来前完成任务的主部分或是替代部分。
每次执行主部分时，选择已到达但未完成的主部分中优先权值最大的主部分，任务实例的替代部分在任务执行时具有最高优先权，即在任一时刻t，t∈[STp（i,j）,EDp（i,j）]，则中断当前执行的主部分，转而执行Aij（每个任务ti包含两个相互独立的部分：
主部分（thePrimary）Pi和替代部分（theAlternate）Ai）。
Pij若在时刻t完成，则释放Aij所占用时间间隔，并调整相应受影响的其他任务替代部分所占用的时间间隔，计算新的通知时间。
虽然基本算法可以实现任务集的容错调度，但是，通过文献[40]可以看出利用基本算法时，任务主部分的完成率不高，而且早期出错的任务主部分容易对后来的任务执行造成影响，因此，有必要对基本算法进行补充。
2.3.2PKSA算法
以BCE算法为基础，李庆华等人在文献[15]中提出了新的基于软件容错的实时调度算法即PKSA算法（ProbingK-StepAlgorithm），该算法在任务执行过程中通过若干试探性检测步骤，提高了任务可执行性的预测，尽可能地避免了任务早期的失败对后续任务的影响，提高了任务的完成率，同时有效减少了浪费的CPU时间。
算法首先按照容错截止期确定每个任务的优先权（静态优先权），容错截止期较小的任务具有较高的优先权。
令P（ti）为ti的静态优先权。
然后将任务集中的任务按照优先权非升顺序，并按类似BCE方法，向后分配替代部分占用的时间间隔，并确定通知时间。
每次执行主部分时，选择已到达但未完成的主部分中具有最小通知时间（动态优先权）的主部分作为待执行主部分。
每次选择待执行主部分时，并不需要从未完成的主部分中重新选择通知时间最小的任务，因而可以节省调度成本。
在时间t，对于任一待执行主部分Pij在其执行时，由于其他任务主部分具有更小的通知时间而被抢占，但是抢占的主部分的到达时间都大于t，因此对Pij在执行间产生影响的主部分的执行时问均在t到NTij之间。
而BCE由于选择以任务周期为优先权的方法，在主部分执行期间，对其产生影响的主部分的执行时间区间不具备这个特点。
并且在任意时刻t，若Pij完成并释放Aij，不需要重新执行向后分配替代部分时间间隔的算法，仅对区间[t,EDij]之内，优先权小于ti的替代部分的时间间隔重新分配即可，这样可以降低调度成本。
PKSA算法只在有新主部分到达，或者主部分运行失败时才重新选择任务；
且对已开始执行的主部分不使用彤次试探性计算，是为了降低调度成本。
通过与BCE算法相比，PKSA算法具有更佳的调度性能[41]。
2.3.3混合型容错算法
在前面两节的基础上提出一种改进算法即混合型任务容错调度（HTFS，HybridTasksFault—tolerantScheduling）算法。
用容错截止期（Ti-ai）的大小分别确定任务集Snji和Sji中任务的优先权P（ti），容错截止期小的任务优先权大。
一般来说有容错需求的任务比无容错需求的任务要重要些，因此在分配优先权时规定Sji中的任务优先权高于Snji中的任务，即。
将Sp中的任务按P（ti）的非增排序，按照BCE算法中提出的向后速率单调算法预先分配替代部分在一个总周期内占用的时间间隔，确定每个Aij，具有最大的NTij。
当预分配的时间段到达时处理器转向执行该替代部分，此时该替代部分具有最高的优先权直到该时间段结束。
由于PKSA算法与BCE算法相比，在能够较好的预测有容错需求的周期任务主版本的执行情况，避免了早期的任务失效对后来任务的影响，因此利用PKSA算法的原理，在它的基础上进行一些调整，从而使改进后的算法能够调度混合型任务。
为了能够调度混合型任务，本文对PKSA算法进行如下改进：
，其中N为周期任务数。
该算法为实时周期任务的每个实例成功地预分配了替代任务的时间段并且处理器严格地利用预分配时间表执行相应任务的替代部分，能成功的调度周期任务和非周期任务。
对于有容错需求的任务，主部分按照通知时间进行动态的调度，若主部分在通知时间前已经顺利结束，则预留给该任务的替代部分的时间间隔被收回，并调整受影响的预分配时间段；
若通知时间到达时，主部分已经失效或者未执行完成，则放弃主部分的执行开始执行替代部分，以保证在任务满足其时间限。
可见，有容错需求的任务总有一个版本被执行且满足时间限的要求。
对于无容错需求的任务，由于他没有主版本只有副版本，而副版本的运行时问都是事先分配好的，只有当容错任务集中的任务主部分正常结束释放替代部分占用的时间间隔后，调整受影响的预分配时间段时，才会有可能改变无容错任务占用的时间间隔，但按照预分配的原理，已经保证了任务可以在时间限之前完成，当分配给无容错任务的时间段到达时，执行该副版本，Snji中的任务将在其时间限内顺利完成。
对于非周期任务集中的任务，处理器在当前没有周期任务可以之执行时，就会执行已到达的非周期任务。
按计算时间确定非周期任务的执行顺序，可以使在有限的时间内完成更多的非周期任务，同时设定任务的最大等待时间，保证任务的等待时间不至于太久，使提前到达但计算时间长的非周期任务的也有适当的响应时间。
该混合型任务的容错调度算法，通过对PKSA算法的一些改进，使新算法不仅能调度有容错需求的周期任务，而且可以调度无容错需求的周期任务和非周期任务，实现在单机实时系统中调度混合型任务的目的，扩大了算法的适用。
3其他容错调度算法
3.1基于优先级降低策略的回卷恢复容错实时调度算法
3.1.1容错调度模型
假设实时系统的任务集合T={t1,t2,…tn}，它由n个实时周期性ti任务组成。
在回卷恢复模型下，任务由5元组<
Ti,Di,Ci,mi,Oi>
表示，其中Ti是ti的周期，Di是ti的截止时限，Ci是ti的最坏执行时间，mi是ti被检查点分成的段数，Oi是系统为ti建立一个检查点的时间开销。
系统采用固定优先级可抢占调度算法对任务集进行实时调度，记为FP（T），常用的固定优先级调度算法有速率单调算法（Rate-Monotonic,RM）和时限单调算法（Deadline-Monotonic，DM）。
ti到达后，由FP（T）为其分配一个初始优先级pi∈{1,2,…,n}。
为了达到容错目的，系统还为其分配了一个容错优先级Pi，它是任务出错后使用的优先级（任务优先级越高，其优先级数值越大）。
3.1.2容错优先级降低策略[16]
容错优先级降低策略下，任务的容错优先级低于或等于初始优先级，容错响应情况与继承策略不同。
给定任务集T={ti,tj}，初始优先级pi和pj满足pi<
pj。
图1给出了任务tj的最坏响应情况：
tj执行过程中出错，且出错以后Pj参与调度，Pi<
pi<
此时ti抢占出错的tj执行，其响应时间被缩短，而tj的响应时间则被延长。
图2给出了任务ti的最坏响应情况：
ti执行过程中出错，并以Pi容错执行，Pi<
pj，期间ti被新到达的tj抢占。
可见，降低策略下的任务最坏响应时间需包含高优先级任务的周期性抢占时间及容错开销，且需排除出错的高优先级任务降低优先级后的抢占时间。
为了说明任务间的抢占关系，根据容错优先级配置P（x），可将任务集T，划分为以下几类子集：
hfp（x,i）:
P（x）下初始优先级高于Pi的任务的集合，即h
升级会员 