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

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