最遲預(yù)分配容錯實時調(diào)度算法設(shè)計與分析

提出一種多類型任務(wù)集的容錯實時調(diào)度算法，詳細分析該算法的調(diào)度機制，證明了該算法的正確性，并給出了該算法的可調(diào)度條件，最后通過模擬實驗分析了算法的性能。實驗表明，調(diào)度算法的性能與系統(tǒng)負載、任務(wù)出錯概率、任務(wù)的計算時間等系統(tǒng)參數(shù)相關(guān)。
關(guān) 鍵 詞 多任務(wù); 預(yù)分配; 實時調(diào)度; 軟件容錯

容錯技術(shù)是實時安全關(guān)鍵系統(tǒng)可靠性保障的重要手段[1]。在實時系統(tǒng)中，必須將容錯和實時兩種技術(shù)相結(jié)合[1-4]。以往文獻中研究的容錯實時調(diào)度算法只能調(diào)度單一類型的實時任務(wù)，未考慮同時調(diào)度具有容錯需求的實時任務(wù)和無容錯需求的實時任務(wù)，也未能同時調(diào)度周期任務(wù)和非周期任務(wù)，而且任務(wù)優(yōu)先級不能根據(jù)需要人為指定。因此，本文建立了一種容錯實時調(diào)度模型，并在該模型基礎(chǔ)上，提出一種基于時間冗余和軟件冗余的容錯實時調(diào)度算法，對多類型的任務(wù)集合進行調(diào)度。該模型適當(dāng)放寬了對任務(wù)優(yōu)先級的限制，允許對有容錯需求的關(guān)鍵任務(wù)人為安排優(yōu)先級。
1 系統(tǒng)模型
多類型任務(wù)集容錯實時調(diào)度模型中，有周期實時任務(wù)和非周期任務(wù)兩大類。前者又分有容錯需求和無容錯需求兩類。有容錯需求的周期實時任務(wù)也稱為關(guān)鍵任務(wù)，為檢測任務(wù)執(zhí)行是否正確，任務(wù)結(jié)束前將對結(jié)果進行正確性判斷(開銷計入運行時間)。對于無容錯需求任務(wù)，假定它的每次運行都是正確的，算法只需保證在截止時間前分配所需的處理器資源而不考慮容錯相關(guān)的問題。
采用雙版本策略對關(guān)鍵任務(wù)進行容錯，每個關(guān)鍵任務(wù)都有兩個相互獨立的可執(zhí)行版本(稱為主/副版本)。主版本功能復(fù)雜、計算量大、運行結(jié)果精度高，但由于其較高的復(fù)雜度和較大的資源需求，導(dǎo)致可靠性相對較低。副版本功能相對簡單、計算量小、運行結(jié)果精度不高，因此可靠性較高。當(dāng)任務(wù)的主版本運行出錯或系統(tǒng)負載過大引起處理器資源緊張時，為保證任務(wù)的時間約束，讓副版本運行，使任務(wù)仍然能在時限內(nèi)滿足用戶的最低需求，提供基本的服務(wù)。