基于副版本零调整策略的实时任务主副版本容错调度

黄迎春　 邓庆绪

(1东北大学计算机科学与工程学院,沈阳 110169)(2沈阳理工大学信息科学与工程学院,沈阳 110159)

软件冗余是一种重要的实时系统容错技术.该技术对同一个任务使用多版本软件,如果一个软件版本出错,可运行其他备份版本软件继续工作.Liestman等[1]设计了截止期机制DM,采用主、副软件版本实现容错,主版本输出精度高、可靠性低,副版本输出精度低、可靠性高.Chetto等[2]提出最后机会策略LCS为副版本预留处理器时间, 完成主版本后撤销其对应的副版本,并按照最后机会策略调整其余受影响的副版本.Han等[3]遵循最后机会策略,通过检查可用时间CAT和消除空闲时间EIT来提高主版本的完成率.Liu等[4]对CAT算法进行改进,构建预测表以提高主版本的完成率.Pathan等[5]分析了基于固定优先级的容错调度的可行性.Huang等[6]提出了一种可变负载的主副版本容错调度算法.Pathan等[7-10]提出了混合关键性系统中的容错技术．

以上容错技术为提高任务的可调度性和主版本完成率,引入了优化策略,增加了调度算法的复杂性和处理器的额外开销.在主副版本容错调度中,副版本的调整时间是不能忽略的,其时间复杂度不低于副版本预分配时间复杂度和主版本调度时间复杂度.本文提出了一种主副版本容错调度算法,在主版本完成后无需进行副版本调整,并且在几乎不降低主版本完成率的基础上,省略了副版本调整操作,从而显著降低了主副版本容错调度算法的复杂性,节省了调度时间.

1　周期性任务主副版本调度模型

周期性任务τi可用五元组(ri,Ti,Di,pi,ai)表示,其中,ri为释放时间,Ti为周期,Di为相对截止期,pi为主版本的执行时间,ai为副版本的执行时间.周期性任务集合Γ={τ1,τ2,…,τn}由n个任务组成,其中τi≻τj表示任务τi的优先级高于任务τj.Γ的计划周期T=LCM(T1,T2,…,Tn)是Γ中所有任务周期的最小公倍数.为最大化任务响应时间,假设所有任务同时释放[11].由于Γ在每个计划周期开始时调度条件相同,不失一般性,仅考虑Γ在[0,T)的调度情况.τi包含主版本Pi和副版本Ai.Γ的主版本资源利用率总和UP=∑pi/Ti,副版本资源利用率总和UA=∑ai/Ti.由于τi以Ti为周期释放,将τi每次释放实例定义为τi的作业Jij,Jij的释放时间记作Rij,绝对截止期记作Dij,主、副版本作业分别记作Pij和Aij,Pij的完成时间记作Fij,Aij预分配的最早开始时间(即通知时间)记作Nij,Aij的完成时间记作Eij.

副版本的预分配算法通常采用反向策略.在预分配过程中,根据任务集Γ中任务τi的优先级,从计划周期结束时刻T到0时刻，采用单调速率RM或最早截止期优先EDF等算法[11]对任务集Γ中所有副版本Aij进行反向调度.将所有作业Jij的就绪时间Rij作为反向截止期,将截止期Dij作为反向就绪时间,从而保证所有作业均采用最后机会策略进行副版本的预分配.将反向调度的EDF算法记作BEDF(backward EDF).主版本的调度可采用RM、EDF、最早通知时间优先ENF等算法.在ENF算法中，对每个释放的任务实例,选择通知时间最早的作业执行.因此,ENF算法可以看作以作业通知时间为截止期的EDF算法.

调度模型的假设条件如下:任务是可抢占的;任务都是独立的,没有优先约束;任务的相对截止期等于其周期(隐含截止期); 任务主、副版本的执行时间均为最差情况执行时间WCET;主版本的执行时间不低于副版本的执行时间;任务的主、副版本软件是独立的;任务的主版本因复杂性在执行过程中可能出错,任务的副版本因其简单性已被充分验证,其错误概率为0;不失一般性,假设任务集中任务周期是非递减的;任务集的任务优先级是严格单调的,即不存在2个任务的优先级相同.

2　副版本预留时间调整开销

任务集在一个计划周期内的调度时间表为线性表.副版本的调整操作是指在该线性表上重新分配副版本预留时间,该操作包括查找和移动2个子操作.查找操作可由副版本平均比较次数来评价,副版本平均比较次数越少,表明副版本调整时所需的查找开销越小.移动操作可由副版本调整时间比率来评价,副版本调整时间比率越小,表明副版本移动时间片的开销越小.因此,副版本调整开销可由副版本调整平均比较次数navg和副版本调整时间比率radj来评价，其计算公式分别为

(1)

(2)

定义1若时间区间[Dij-ai,Dij]与区间[Dxy-ax,Dxy]的交集不为空,则称副版本Aij与Axy(i≠x)预留时间冲突.

定义2对于任务集Γ,定义HP(i)={τj|τiτj}为所有优先级高于任务τi的任务子集, 定义LP(i)={τj|τi≻τj}为所有优先级低于任务τi的任务子集.

定理1在一个计划周期内,副版本第1次分配时,所有副版本预留时间均冲突.

定理2若撤销任务τi的副版本引起其他任务副版本调整,则需调整的副版本集合为所有优先级低于任务τi的任务子集LP(i) .

定义3若撤销副版本Aij引起副版本Axy(i≠x)调整,则称Aij撤销影响了Axy.

定理3若作业Jij主版本成功完成时刻为Fij,撤销其对应的副版本Aij将引起副版本Amn(m≠i)调整的充分必要条件为:

1)τm∈LP(i);

2)Amn尚未完成;

3)Amn被任务τx∈LP(i) ∪{τi}的副版本Axy抢占;

4)Aij的撤销影响了Axy.

3　副版本零调整的主副版本容错调度算法

定理4若采用BEDF算法调度任务集的副版本, 采用ENF算法调度任务集主版本,则当主版本成功完成并释放对应副版本的预留时间后,其他作业副版本预留时间无需调整仍能保证按照最后机会策略分配时间.

证明在调度时刻s,不失一般性,设副版本Aij的通知时间Nij最早.下面分2种情况证明.

1) 主版本释放时刻小于等于调度时刻，即Pij的释放时间Rij≤s.

如图1所示,在时刻s,副版本Aij的通知时间Nij最早,因此执行主版本Pij.假设在时刻t成功完成Pij,需释放时间区间[Nij,Eij],进而可能引起[t,Eij]内预分配的副版本调整预留时间.下面分2种情况证明[t,Eij]内预分配的副版本作业无需调整仍能保证按照最后机会策略分配时间区间.

图1　主版本释放时刻小于等于调度时刻的情况

① 作业Jij在[Rij,Dij]内并发作业Jxy的释放时间Rxy≥t.若Rxy≥Eij,则在[t,Eij]内不存在任何副版本Axy的预留时间,因此,Aij的释放不会引起Axy的调整.若RxyRij，可知Rxy>Rij,进而可得τx≻τi.如果副版本Axy与Aij预留时间冲突,Axy会抢占Aij.因此,Aij的释放不会引起Axy的调整.

②RxyRij,Rxy

若Rxy>Rij,则τx≻τi.如果副版本Axy与Aij预留时间冲突,Axy会抢占Aij.因此,Aij的释放不会引起Axy的调整.

若RxyNij成立.二者矛盾.

若Rxy=Rij,则当Dxy≥Dij时,τi≻τx,等价于RxyRij的情况.

2) 主版本释放时刻大于调度时刻，即Rij>s.

如图2所示,由于Rij>s,因此直到Rij时刻,主版本Pij才开始执行.下面分2种情况证明[t,Eij]内预分配的副版本作业无需调整仍能保证按照最后机会策略分配时间.

图2　主版本释放时刻大于调度时刻的情况

① [t,Eij]时间区间内不存在其他副版本Axy.Pij在t时刻成功完成,仅会影响[t,Eij]时间区间内预留的副版本.由题设可知，不存在这样的副版本Axy,因此不需要调整副版本.

② [t,Eij]时间区间内存在其他副版本Axy.在时刻s,作业Jij的通知时间Nij最小,且Rij>s,因此,在时刻Rij,作业Jij的通知时间Nij仍然最小,即对于其他作业Jxy,NijRij两种情况证明.

若Rxy≤Rij,不失一般性，假设τi≻τx.若Axy与Aij发生冲突,Aij将抢占Axy,因此在[Nij,Eij]内不可能出现副版本Axy.又由于在[t,Eij]内存在其他副版本Axy,因此Axy一定出现在[t,Eij]区间内,即Nxy

若Rxy>Rij,则按照BEDF算法策略,τx≻τi.由于在[t,Eij]内存在其他副版本Axy,则副版本Axy与Aij发生冲突,Axy必然在[t,Eij]内抢占Aij,因此在t时刻,Aij的撤销不会引起Axy的调整.证毕.

依据定理4的结论,设计副版本零调整的主副版本容错调度算法BEDF-NENF,简化主副版本容错调度方案,提高调度效率.算法的具体步骤如下:

① 计算任务集副版本的处理器利用率UA.若UA>1,则任务集不可调度,算法结束;否则,采用BEDF算法为副版本预留处理器时间,设当前时刻为t=0.

② 从当前时刻t开始,循环采用ENF算法执行主版本.若时刻t已为计划周期结束时刻,则算法执行结束.若时刻t已为副版本作业预留,则执行该副版本作业,推进t至下一时刻.若时刻t无就绪的主版本作业需要执行,推进t至下一时刻.若时刻t有就绪主版本作业需要执行,则选择副版本作业通知时间最早的主版本作业执行,若该主版本作业完成,则撤销对应的副版本作业;若该主版本作业执行失败,则撤销该主版本作业,提前执行该主版本对应的副版本作业,推进t至下一时刻.

4　仿真实验

4.1　任务集的随机生成

1) 任务集中至少包含2个任务.

3) 任务集的副版本处理器利用率UA≤1.

在生成任务集时,随机生成单任务的参数如下:设定副版本的最大执行时间emax,副版本执行时间ai服从[1,emax]之间的均匀分布.设定主版本与副版本之间的最大比例rP/A,主版本执行时间pi服从[ai,airP/A]之间的均匀分布.设定周期与主版本之间的最大比例rT/P,任务周期Ti服从[pi,pirT/P]之间的均匀分布,且任务相对截止期Di=Ti.

4.2　实验结果

按照4.1节的任务集随机生成方法生成任务集. 设emax=5,rP/A=2,rT/P=6,在[0.35,1.95]区间等分设置33个点,分别作为任务集的目标主版本处理器利用率UP.然后，依据每个UP值随机生成1 000个任务集.针对这些任务集,分别采用BEDF-RM, BEDF-EDF, BEDF-ENF, BEDF-NENF算法进行调度,计算任务集的平均主版本完成率psucc、副版本调整平均比较次数navg和副版本调整时间比率radj.

图3为不同主版本错误概率下各算法的平均主版本完成率.由图可知, BEDF-EDF算法的主版本完成率最高,其次为BEDF-RM算法，BEDF-ENF算法和BEDF-NENF算法最低.各算法的平均主版本完成率约为40%.不同错误概率下,各算法的主版本完成率之差约为1%.结果表明,不同的调度算法对主版本完成率的影响较小.

图3　不同错误概率下的平均主版本完成率

图4和图5分别给出了不同主版本错误概率下各算法的副版本调整平均比较次数和副版本调整时间比率.由图可知,BEDF-RM算法和BEDF-EDF算法的副版本调整平均比较次数较多,副版本调整时间比率较高.BEDF-ENF算法的副版本调整平均比较次数和副版本调整时间比率指标明显优于BEDF-RM算法和BEDF-EDF算法,但其值不为0. BEDF-NENF算法在不同错误概率下的副版本调整平均比较次数和调整时间比率指标值均为0.

图4　不同错误概率下的副版本调整平均比较次数

图5　不同错误概率下的副版本调整时间比率

5　结论

1) BEDF-NENF算法的副版本零调整策略能够保证副版本在每个周期内按照最后机会策略分配时间.

2) 在副版本无需调整的情况下, BEDF-NENF算法的主版本完成率指标与其他调度算法无显著差异.

3) BEDF-NENF算法省略了副版本调整操作,显著降低了周期性硬实时任务主副版本容错调度的复杂性,节省了调度时间,提升了调度性能.

参考文献(References)

[1] Liestman A L, Campbell R H. A fault-tolerant scheduling problem [J].IEEETransactionsonSoftwareEngineering, 1986,12(11): 1089-1095. DOI:10.1109/tse.1986.6312999.

[2] Chetto H, Chetto M. Some results of the earliest deadline scheduling algorithm [J].IEEETransactionsonSoftwareEngineering, 1989,15(10): 1261-1269. DOI:10.1109/tse.1989.559777.

[3] Han C C, Kang G S, Wu J. A fault-tolerant scheduling algorithm for real-time periodic tasks with possible software faults [J].IEEETransactionsonComputers, 2003,52(3):362-372.

[4] Liu D, Xing W, Li R, et al. A fault-tolerant real-time scheduling algorithm in software fault-tolerant module [J].JournalofComputerResearch&Development, 2007,44(9): 961-964.DOI:10.1007/978-3-540-72590-9_145.

[5] Pathan R M, Jonsson J. Exact fault-tolerant feasibility analysis of fixed-priority real-time tasks[C]//IEEEInternationalConferenceonEmbeddedandReal-TimeComputingSystemsandApplications. Macau, China, 2010: 265-274.DOI:10.1109/rtcsa.2010.24.

[6] Huang Y, Deng Q. Fault-tolerant scheduling of primary-alternate version based on variable workload[C]//InternationalSymposiumonSystemandSoftwareReliability. Shanghai, China, 2017: 119-128.DOI:10.1109/isssr.2016.027.

[7] Pathan R M. Fault-tolerant and real-time scheduling for mixed-criticality systems [J].Real-TimeSystems, 2014,50(4): 509-547.DOI:10.1007/s11241-014-9202-z.

[8] Lin J, Cheng A M K, Steel D, et al. Scheduling mixed-criticality real-time tasks with fault tolerance[C]//TheWorkshoponMixedCriticality. Rome, Italy, 2014: 39-44.

[9] Thekkilakattil A, Dobrin R, Punnekkat S. Fault tolerant scheduling of mixed criticality real-time tasks under error bursts [J].ProcediaComputerScience, 2015,46: 1148-1155.DOI:10.1016/j.procs.2015.01.027.

[10] Huang P, Yang H, Thiele L. On the scheduling of fault-tolerant mixed-criticality systems[C]// 2014 51stACM/EDAC/IEEEDesignAutomationConference. San Francisco, USA, 2014:1-6.DOI:10.1109/dac.2014.6881458.

[11] Liu C L,Layland J W. Scheduling algorithms for multiprogramming in a hard real-time environment [J].JournaloftheAssociationforComputingMachinery, 1973:20(1): 46-61.DOI:10.1145/321738.321743.