黃迎春　 鄧慶緒

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

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

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

1　周期性任務主副版本調(diào)度模型

周期性任務τ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].由于Γ在每個計劃周期開始時調(diào)度條件相同,不失一般性,僅考慮Γ在[0,T)的調(diào)度情況.τ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時刻，采用單調(diào)速率RM或最早截止期優(yōu)先EDF等算法[11]對任務集Γ中所有副版本Aij進行反向調(diào)度.將所有作業(yè)Jij的就緒時間Rij作為反向截止期,將截止期Dij作為反向就緒時間,從而保證所有作業(yè)均采用最后機會策略進行副版本的預分配.將反向調(diào)度的EDF算法記作BEDF(backward EDF).主版本的調(diào)度可采用RM、EDF、最早通知時間優(yōu)先ENF等算法.在ENF算法中，對每個釋放的任務實例,選擇通知時間最早的作業(yè)執(zhí)行.因此,ENF算法可以看作以作業(yè)通知時間為截止期的EDF算法.

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

2　副版本預留時間調(diào)整開銷

任務集在一個計劃周期內(nèi)的調(diào)度時間表為線性表.副版本的調(diào)整操作是指在該線性表上重新分配副版本預留時間,該操作包括查找和移動2個子操作.查找操作可由副版本平均比較次數(shù)來評價,副版本平均比較次數(shù)越少,表明副版本調(diào)整時所需的查找開銷越小.移動操作可由副版本調(diào)整時間比率來評價,副版本調(diào)整時間比率越小,表明副版本移動時間片的開銷越小.因此,副版本調(diào)整開銷可由副版本調(diào)整平均比較次數(shù)navg和副版本調(diào)整時間比率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在一個計劃周期內(nèi),副版本第1次分配時,所有副版本預留時間均沖突.

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

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

定理3若作業(yè)Jij主版本成功完成時刻為Fij,撤銷其對應的副版本Aij將引起副版本Amn(m≠i)調(diào)整的充分必要條件為:

1)τm∈LP(i);

2)Amn尚未完成;

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

4)Aij的撤銷影響了Axy.

3　副版本零調(diào)整的主副版本容錯調(diào)度算法

定理4若采用BEDF算法調(diào)度任務集的副版本, 采用ENF算法調(diào)度任務集主版本,則當主版本成功完成并釋放對應副版本的預留時間后,其他作業(yè)副版本預留時間無需調(diào)整仍能保證按照最后機會策略分配時間.

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

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

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

圖1　主版本釋放時刻小于等于調(diào)度時刻的情況

① 作業(yè)Jij在[Rij,Dij]內(nèi)并發(fā)作業(yè)Jxy的釋放時間Rxy≥t.若Rxy≥Eij,則在[t,Eij]內(nèi)不存在任何副版本Axy的預留時間,因此,Aij的釋放不會引起Axy的調(diào)整.若RxyRij，可知Rxy>Rij,進而可得τx?τi.如果副版本Axy與Aij預留時間沖突,Axy會搶占Aij.因此,Aij的釋放不會引起Axy的調(diào)整.

②RxyRij,Rxy

若Rxy>Rij,則τx?τi.如果副版本Axy與Aij預留時間沖突,Axy會搶占Aij.因此,Aij的釋放不會引起Axy的調(diào)整.

若RxyNij成立.二者矛盾.

若Rxy=Rij,則當Dxy≥Dij時,τi?τx,等價于RxyRij的情況.

2) 主版本釋放時刻大于調(diào)度時刻，即Rij>s.

如圖2所示,由于Rij>s,因此直到Rij時刻,主版本Pij才開始執(zhí)行.下面分2種情況證明[t,Eij]內(nèi)預分配的副版本作業(yè)無需調(diào)整仍能保證按照最后機會策略分配時間.

圖2　主版本釋放時刻大于調(diào)度時刻的情況

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

② [t,Eij]時間區(qū)間內(nèi)存在其他副版本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]內(nèi)不可能出現(xiàn)副版本Axy.又由于在[t,Eij]內(nèi)存在其他副版本Axy,因此Axy一定出現(xiàn)在[t,Eij]區(qū)間內(nèi),即Nxy

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

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

① 計算任務集副版本的處理器利用率UA.若UA>1,則任務集不可調(diào)度,算法結束;否則,采用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算法進行調(diào)度,計算任務集的平均主版本完成率psucc、副版本調(diào)整平均比較次數(shù)navg和副版本調(diào)整時間比率radj.

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

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

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

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

圖5　不同錯誤概率下的副版本調(diào)整時間比率

5　結論

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

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

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

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