基于副版本零調整策略的實時任務主副版本容錯調度

黃迎春　 鄧慶緒

(1東北大學計算機科學與工程學院,沈陽 110169)(2沈陽理工大學信息科學與工程學院,沈陽 110159)

軟件冗余是一種重要的實時系統(tǒng)容錯技術.該技術對同一個任務使用多版本軟件,如果一個軟件版本出錯,可運行其他備份版本軟件繼續(xù)工作.Liestman等[1]設計了截止期機制DM,采用主、副軟件版本實現(xiàn)容錯,主版本輸出精度高、可靠性低,副版本輸出精度低、可靠性高.Chetto等[2]提出最后機會策略LCS為副版本預留處理器時間, 完成主版本后撤銷其對應的副版本,并按照最后機會策略調整其余受影響的副版本.Han等[3]遵循最后機會策略,通過檢查可用時間CAT和消除空閑時間EIT來提高主版本的完成率.Liu等[4]對CAT算法進行改進,構建預測表以提高主版本的完成率.Pathan等[5]分析了基于固定優(yōu)先級的容錯調度的可行性.Huang等[6]提出了一種可變負載的主副版本容錯調度算法.Pathan等[7-10]提出了混合關鍵性系統(tǒng)中的容錯技術．

以上容錯技術為提高任務的可調度性和主版本完成率,引入了優(yōu)化策略,增加了調度算法的復雜性和處理器的額外開銷.在主副版本容錯調度中,副版本的調整時間是不能忽略的,其時間復雜度不低于副版本預分配時間復雜度和主版本調度時間復雜度.本文提出了一種主副版本容錯調度算法,在主版本完成后無需進行副版本調整,并且在幾乎不降低主版本完成率的基礎上,省略了副版本調整操作,從而顯著降低了主副版本容錯調度算法的復雜性,節(jié)省了調度時間.

1　周期性任務主副版本調度模型

周期性任務τi可用五元組(ri,Ti,Di,pi,ai)表示,其中,ri為釋放時間,Ti為周期,Di為相對截止期,pi為主版本的執(zhí)行時間,ai為副版本的執(zhí)行時間.周期性任務集合Γ={τ1,τ2,…,τn}由n個任務組成,其中τi?τj表示任務τi的優(yōu)先級高于任務τj.Γ的計劃周期T=LCM(T1,T2,…,Tn)是Γ中所有任務周期的最小公倍數(shù).為最大化任務響應時間,假設所有任務同時釋放[11].由于Γ在每個計劃周期開始時調度條件相同,不失一般性,僅考慮Γ在[0,T)的調度情況.τi包含主版本Pi和副版本Ai.Γ的主版本資源利用率總和UP=∑pi/Ti,副版本資源利用率總和UA=∑ai/Ti.由于τi以Ti為周期釋放,將τi每次釋放實例定義為τi的作業(yè)Jij,Jij的釋放時間記作Rij,絕對截止期記作Dij,主、副版本作業(yè)分別記作Pij和Aij,Pij的完成時間記作Fij,Aij預分配的最早開始時間(即通知時間)記作Nij,Aij的完成時間記作Eij.

副版本的預分配算法通常采用反向策略.在預分配過程中,根據(jù)任務集Γ中任務τi的優(yōu)先級,從計劃周期結束時刻T到0時刻，采用單調速率RM或最早截止期優(yōu)先EDF等算法[11]對任務集Γ中所有副版本Aij進行反向調度.將所有作業(yè)Jij的就緒時間Rij作為反向截止期,將截止期Dij作為反向就緒時間,從而保證所有作業(yè)均采用最后機會策略進行副版本的預分配.將反向調度的EDF算法記作BEDF(backward EDF).主版本的調度可采用RM、EDF、最早通知時間優(yōu)先ENF等算法.在ENF算法中，對每個釋放的任務實例,選擇通知時間最早的作業(yè)執(zhí)行.因此,ENF算法可以看作以作業(yè)通知時間為截止期的EDF算法.

調度模型的假設條件如下:任務是可搶占的;任務都是獨立的,沒有優(yōu)先約束;任務的相對截止期等于其周期(隱含截止期); 任務主、副版本的執(zhí)行時間均為最差情況執(zhí)行時間WCET;主版本的執(zhí)行時間不低于副版本的執(zhí)行時間;任務的主、副版本軟件是獨立的;任務的主版本因復雜性在執(zhí)行過程中可能出錯,任務的副版本因其簡單性已被充分驗證,其錯誤概率為0;不失一般性,假設任務集中任務周期是非遞減的;任務集的任務優(yōu)先級是嚴格單調的,即不存在2個任務的優(yōu)先級相同.

2　副版本預留時間調整開銷

任務集在一個計劃周期內的調度時間表為線性表.副版本的調整操作是指在該線性表上重新分配副版本預留時間,該操作包括查找和移動2個子操作.查找操作可由副版本平均比較次數(shù)來評價,副版本平均比較次數(shù)越少,表明副版本調整時所需的查找開銷越小.移動操作可由副版本調整時間比率來評價,副版本調整時間比率越小,表明副版本移動時間片的開銷越小.因此,副版本調整開銷可由副版本調整平均比較次數(shù)navg和副版本調整時間比率radj來評價，其計算公式分別為

(1)

(2)

定義1若時間區(qū)間[Dij-ai,Dij]與區(qū)間[Dxy-ax,Dxy]的交集不為空,則稱副版本Aij與Axy(i≠x)預留時間沖突.

定義2對于任務集Γ,定義HP(i)={τj|τiτj}為所有優(yōu)先級高于任務τi的任務子集, 定義LP(i)={τj|τi?τj}為所有優(yōu)先級低于任務τi的任務子集.

定理1在一個計劃周期內,副版本第1次分配時,所有副版本預留時間均沖突.

定理2若撤銷任務τi的副版本引起其他任務副版本調整,則需調整的副版本集合為所有優(yōu)先級低于任務τi的任務子集LP(i) .

定義3若撤銷副版本Aij引起副版本Axy(i≠x)調整,則稱Aij撤銷影響了Axy.

定理3若作業(yè)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算法調度任務集主版本,則當主版本成功完成并釋放對應副版本的預留時間后,其他作業(yè)副版本預留時間無需調整仍能保證按照最后機會策略分配時間.

證明在調度時刻s,不失一般性,設副版本Aij的通知時間Nij最早.下面分2種情況證明.

1) 主版本釋放時刻小于等于調度時刻，即Pij的釋放時間Rij≤s.

如圖1所示,在時刻s,副版本Aij的通知時間Nij最早,因此執(zhí)行主版本Pij.假設在時刻t成功完成Pij,需釋放時間區(qū)間[Nij,Eij],進而可能引起[t,Eij]內預分配的副版本調整預留時間.下面分2種情況證明[t,Eij]內預分配的副版本作業(yè)無需調整仍能保證按照最后機會策略分配時間區(qū)間.

圖1　主版本釋放時刻小于等于調度時刻的情況

① 作業(yè)Jij在[Rij,Dij]內并發(fā)作業(yè)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才開始執(zhí)行.下面分2種情況證明[t,Eij]內預分配的副版本作業(yè)無需調整仍能保證按照最后機會策略分配時間.

圖2　主版本釋放時刻大于調度時刻的情況

① [t,Eij]時間區(qū)間內不存在其他副版本Axy.Pij在t時刻成功完成,僅會影響[t,Eij]時間區(qū)間內預留的副版本.由題設可知，不存在這樣的副版本Axy,因此不需要調整副版本.

② [t,Eij]時間區(qū)間內存在其他副版本Axy.在時刻s,作業(yè)Jij的通知時間Nij最小,且Rij>s,因此,在時刻Rij,作業(yè)Jij的通知時間Nij仍然最小,即對于其他作業(yè)Jxy,NijRij兩種情況證明.

若Rxy≤Rij,不失一般性，假設τi?τx.若Axy與Aij發(fā)生沖突,Aij將搶占Axy,因此在[Nij,Eij]內不可能出現(xiàn)副版本Axy.又由于在[t,Eij]內存在其他副版本Axy,因此Axy一定出現(xiàn)在[t,Eij]區(qū)間內,即Nxy

若Rxy>Rij,則按照BEDF算法策略,τx?τi.由于在[t,Eij]內存在其他副版本Axy,則副版本Axy與Aij發(fā)生沖突,Axy必然在[t,Eij]內搶占Aij,因此在t時刻,Aij的撤銷不會引起Axy的調整.證畢.

依據(jù)定理4的結論,設計副版本零調整的主副版本容錯調度算法BEDF-NENF,簡化主副版本容錯調度方案,提高調度效率.算法的具體步驟如下:

① 計算任務集副版本的處理器利用率UA.若UA>1,則任務集不可調度,算法結束;否則,采用BEDF算法為副版本預留處理器時間,設當前時刻為t=0.

② 從當前時刻t開始,循環(huán)采用ENF算法執(zhí)行主版本.若時刻t已為計劃周期結束時刻,則算法執(zhí)行結束.若時刻t已為副版本作業(yè)預留,則執(zhí)行該副版本作業(yè),推進t至下一時刻.若時刻t無就緒的主版本作業(yè)需要執(zhí)行,推進t至下一時刻.若時刻t有就緒主版本作業(yè)需要執(zhí)行,則選擇副版本作業(yè)通知時間最早的主版本作業(yè)執(zhí)行,若該主版本作業(yè)完成,則撤銷對應的副版本作業(yè);若該主版本作業(yè)執(zhí)行失敗,則撤銷該主版本作業(yè),提前執(zhí)行該主版本對應的副版本作業(yè),推進t至下一時刻.

4　仿真實驗

4.1　任務集的隨機生成

1) 任務集中至少包含2個任務.

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

在生成任務集時,隨機生成單任務的參數(shù)如下:設定副版本的最大執(zhí)行時間emax,副版本執(zhí)行時間ai服從[1,emax]之間的均勻分布.設定主版本與副版本之間的最大比例rP/A,主版本執(zhí)行時間pi服從[ai,airP/A]之間的均勻分布.設定周期與主版本之間的最大比例rT/P,任務周期Ti服從[pi,pirT/P]之間的均勻分布,且任務相對截止期Di=Ti.

4.2　實驗結果

按照4.1節(jié)的任務集隨機生成方法生成任務集. 設emax=5,rP/A=2,rT/P=6,在[0.35,1.95]區(qū)間等分設置33個點,分別作為任務集的目標主版本處理器利用率UP.然后，依據(jù)每個UP值隨機生成1 000個任務集.針對這些任務集,分別采用BEDF-RM, BEDF-EDF, BEDF-ENF, BEDF-NENF算法進行調度,計算任務集的平均主版本完成率psucc、副版本調整平均比較次數(shù)navg和副版本調整時間比率radj.

圖3為不同主版本錯誤概率下各算法的平均主版本完成率.由圖可知, BEDF-EDF算法的主版本完成率最高,其次為BEDF-RM算法，BEDF-ENF算法和BEDF-NENF算法最低.各算法的平均主版本完成率約為40%.不同錯誤概率下,各算法的主版本完成率之差約為1%.結果表明,不同的調度算法對主版本完成率的影響較小.

圖3　不同錯誤概率下的平均主版本完成率

圖4和圖5分別給出了不同主版本錯誤概率下各算法的副版本調整平均比較次數(shù)和副版本調整時間比率.由圖可知,BEDF-RM算法和BEDF-EDF算法的副版本調整平均比較次數(shù)較多,副版本調整時間比率較高.BEDF-ENF算法的副版本調整平均比較次數(shù)和副版本調整時間比率指標明顯優(yōu)于BEDF-RM算法和BEDF-EDF算法,但其值不為0. BEDF-NENF算法在不同錯誤概率下的副版本調整平均比較次數(shù)和調整時間比率指標值均為0.

圖4　不同錯誤概率下的副版本調整平均比較次數(shù)

圖5　不同錯誤概率下的副版本調整時間比率

5　結論

1) BEDF-NENF算法的副版本零調整策略能夠保證副版本在每個周期內按照最后機會策略分配時間.

2) 在副版本無需調整的情況下, BEDF-NENF算法的主版本完成率指標與其他調度算法無顯著差異.

3) BEDF-NENF算法省略了副版本調整操作,顯著降低了周期性硬實時任務主副版本容錯調度的復雜性,節(jié)省了調度時間,提升了調度性能.

參考文獻(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.