最遲預分配容錯實時調度算法設計與分析

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

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