實時系統(tǒng)中任務(wù)的超時完成可能導(dǎo)致災(zāi)難性后果,因此要求系統(tǒng)具備容錯處理能力,以保證系統(tǒng)出錯后的實時性及可靠性.主/副版本模型是提高實時系統(tǒng)容錯能力的有效技術(shù).傳統(tǒng)的容錯實時調(diào)度算法通過為副版本預(yù)留處理器時間來實現(xiàn)軟件容錯,為副版本預(yù)留的處理器時間在系統(tǒng)運行過程中需動態(tài)調(diào)整,增加了系統(tǒng)的容錯調(diào)度開銷.提出一種基于res-backwards-RM預(yù)分配子算法的容錯實時調(diào)度算法BCE*,通過限制預(yù)分配過程中高優(yōu)先級任務(wù)的搶占條件,在不影響系統(tǒng)可調(diào)度性的同時可以有效避免副版本預(yù)留時間的動態(tài)調(diào)整,降低系統(tǒng)的容錯調(diào)度開銷.仿真實驗驗證了BCE*算法的可行性及有效性,且在系統(tǒng)出錯概率及主版本負(fù)載較低的環(huán)境下,BCE*算法對系統(tǒng)容錯調(diào)度開銷的優(yōu)化效果更顯著. 

【文章來源】：計算機研究與發(fā)展. 2015,52(03)北大核心EICSCD

【文章頁數(shù)】：9 頁

【部分圖文】：

圖１ｂａｃｋｗａｒｄｓ－ＲＭ確定的Γ１的通知時間時序Ｆｉｇ．１ＴｈｅｎｏｔｉｆｉｃａｔｉｏｎｔｉｍｅｓｏｆΓ１ｃａｌｃｕｌａｔｅｄｂｙｂａｃｋｗａｒｄｓ－ＲＭ．

Ｆｉｇ．２Ｔｈｅｒｕｎ－ｔｉｍｅｓｃｈｅｄｕｌｉｎｇｏｆΓ１ｗｉｔｈｔｈｅｐｒｅ－ａｌｌｏｃａｔｉｏｎｏｆｂａｃｋｗａｒｄｓ－ＲＭ．圖２基于ｂａｃｋｗａｒｄｓ－ＲＭ預(yù)分配的Γ１的運行時調(diào)度２．２預(yù)留時間的調(diào)整開銷定義２．ＢＣＥ調(diào)度過程中，在時刻ｔ存在副版本預(yù)留時間的動態(tài)調(diào)整，當(dāng)且僅當(dāng)以下２個條件同時成立：１）存在Ｎｉｊ＞ｔ且Ｐｉｊ在時刻ｔ正確完成；２）存在Ｐｍｎ（ｐｒｉｏｍ＜ｐｒｉｏｉ）在時刻ｔ尚未完成，且Ａｍｎ與Ａｉｊ的預(yù)留時間沖突．由定義１，２可知，預(yù)留時間的動態(tài)調(diào)整僅可能發(fā)生在存在預(yù)留時間沖突的副版本上．Ｐｉｊ完成時，需從所有Ａｍｎ（ｐｒｉｏｍ＜ｐｒｉｏｉ）中查找到與Ａｉｊ沖突的副版本，此過程的時間開銷為Ｏ（ｎ）．最壞情況下，在［０，Ｔ］內(nèi)副版本預(yù)留時間的動態(tài)調(diào)整開銷為Ｏ（ｎ×Ｎ），其中Ｎ為［０，Ｔ］內(nèi)的作業(yè)總數(shù)．在［０，Ｔ］內(nèi)可能發(fā)生的最大調(diào)整次數(shù)為反向調(diào)度過程中副版本的總搶占次數(shù)，表示為Ｍｍａｘ．實際調(diào)整次數(shù)受主版本的完成情況影響，當(dāng)所有主版本均成功完成時，調(diào)整次數(shù)取最大值．隨機生成１０００組任務(wù)集，每組任務(wù)集包含的任務(wù)個數(shù)ｎ在［２，２０］內(nèi)取值，每個任務(wù)的周期Ｔｉ在［５，３００］內(nèi)隨機取值，副版本執(zhí)行時間ａｉ在［１，Ｔｉ］內(nèi)隨機取值后乘以ＵＡ∑ｎｉ＝１ａｉＴｉ，以控制任務(wù)集的副版本處理器利用率ＵＡ為（０，１］內(nèi)的指定數(shù)值，所有隨機數(shù)均服從均勻分布．對任務(wù)集

－ＲＭ調(diào)度，由于每組任務(wù)集的計劃周期不同，統(tǒng)計每組任務(wù)集在其計劃周期內(nèi)的搶占率ＭＰｍａｘ＝ＭｍａｘＴ，分別計算ＵＡ∈（０，０．１］，（０．１，０．２］，…，（０．９，１］時的平均ＭＰｍａｘ，結(jié)果如圖３所示．從圖３可看出，隨著副版本處理器利用率增大，ＭＰｍａｘ呈上升趨勢，特別是在高ＵＡ情況下，ＭＰｍａｘ加劇上升．預(yù)留時間調(diào)整次數(shù)過多將造成系統(tǒng)運行Ｆｉｇ．３ＴｈｅｉｎｆｌｕｅｎｃｅｏｆＭＰｍａｘｏｎＵＡ．圖３ＵＡ對ＭＰｍａｘ的影響時的調(diào)度開銷過大，進而影響任務(wù)的調(diào)度．根據(jù)定義２的條件２），為了減少預(yù)留時間的動態(tài)調(diào)整操作，對ｂａｃｋｗａｒｄｓ－ＲＭ算法進行改進，在副版本的反向調(diào)度過程中，設(shè)置新的任務(wù)搶占執(zhí)行規(guī)則，提出ｒｅｓ－ｂａｃｋｗａｒｄｓ－ＲＭ預(yù)分配算法，并基于ｒｅｓ－ｂａｃｋｗａｒｄｓ－ＲＭ子算法提出容錯實時調(diào)度算法ＢＣＥ＊．３ｒｅｓ－ｂａｃｋｗａｒｄｓ－ＲＭ算法預(yù)分配算法ｒｅｓ－ｂａｃｋｗａｒｄｓ－ＲＭ根據(jù)任務(wù)周期為Γ中任務(wù)τｉ分配優(yōu)先級ｐｒｉｏ＊ｉ∈｛１，２，…，ｎ｝，任務(wù)周期越短，其優(yōu)先級越高．ｒｅｓ－ｂａｃｋｗａｒｄｓ－ＲＭ從時刻Ｔ到０，對Γ中副版本進行反向調(diào)度，副版本Ａｉｊ的反向就緒時間ＢＲｉｊ＝Ｄｉｊ，反向截止時限ＢＤｉｊ＝Ｒｉｊ．反向調(diào)度過程中，若已就緒的副版本之間滿足定義１中的沖突條件，則僅當(dāng)高優(yōu)先級任務(wù)的推遲執(zhí)行將導(dǎo)致其超時完成時，高優(yōu)先級任務(wù)才可搶占低優(yōu)先級任務(wù)執(zhí)行，否則優(yōu)先執(zhí)行低優(yōu)先級任務(wù)．ｒ

【參考文獻】：
期刊論文
[1]硬實時系統(tǒng)中基于軟件容錯模型的容錯調(diào)度算法[J]. 丁萬夫,郭銳鋒,秦承剛,郭鳳釗.  計算機研究與發(fā)展. 2011(04)
[2]容錯多處理機中一種高效的實時調(diào)度算法(英文)[J]. 王健,孫建伶,王新宇,楊小虎,王申康,陳俊波.  軟件學(xué)報. 2009(10)
[3]軟件容錯模型中的容錯實時調(diào)度算法[J]. 劉東,張春元,李瑞,黃影,李毅.  計算機研究與發(fā)展. 2007(09)



本文編號：3601127