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

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

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

【部分圖文】：

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

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

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

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



本文編號(hào)：3601127