硬實(shí)時(shí)容錯(cuò)調(diào)度算法研究.pdf

1、具有容錯(cuò)能力的硬實(shí)時(shí)系統(tǒng)要求在系統(tǒng)發(fā)生局部故障情況下所有任務(wù)仍然能在截止期限之前正確完成，否則會導(dǎo)致災(zāi)難性的后果，被廣泛地應(yīng)用到航天、軍事等關(guān)鍵領(lǐng)域。硬實(shí)時(shí)容錯(cuò)調(diào)度算法通過軟件方法構(gòu)造任務(wù)調(diào)度秩序并從理論上證明該秩序的實(shí)時(shí)性和可靠性，屬于實(shí)時(shí)系統(tǒng)的重要研究領(lǐng)域。硬實(shí)時(shí)系統(tǒng)種類繁多，新的應(yīng)用需求層出不窮，對原有的硬實(shí)時(shí)容錯(cuò)調(diào)度理論提出了新的挑戰(zhàn)。因此，需要對現(xiàn)有的硬實(shí)時(shí)容錯(cuò)調(diào)度算法進(jìn)行擴(kuò)充以適應(yīng)新的需求。
　　 主/副版本技術(shù)是分

2、布式硬實(shí)時(shí)系統(tǒng)中重要的容錯(cuò)機(jī)制。在該機(jī)制中，每個(gè)任務(wù)的主副版本分別分配到不同的處理機(jī)上。FTRMFF（Fault-Tolerant Rate-Monotonic First-Fit）算法利用主/副版本技術(shù)作為容錯(cuò)手段，通過首次適應(yīng)方式按照RMS（Rate-Monotonic Scheduling）優(yōu)先級依次將任務(wù)分配到能同時(shí)滿足實(shí)時(shí)性和可靠性的處理機(jī)上，是一種經(jīng)典的分布式容錯(cuò)調(diào)度算法。然而，以首次適應(yīng)方式來分配處理機(jī)很難充分挖掘處理機(jī)的

3、負(fù)載能力。針對這種情況，首先定義空閑因子來量化處理機(jī)中空閑資源。然后提出緊湊因子的概念來反映分配到同一個(gè)處理機(jī)上的任務(wù)之間的相容程度。最后提出的基于緊湊因子的啟發(fā)式硬實(shí)時(shí)容錯(cuò)調(diào)度算法在為任務(wù)分配處理機(jī)時(shí)遵循緊湊因子最大化的原則。該算法能增加周期任務(wù)間的相容性，從而提高分布式系統(tǒng)的調(diào)度性能。
　　 副版本根據(jù)觸發(fā)時(shí)間可分為主動副版本和被動副版本。主動副版本與其主版本同時(shí)觸發(fā)，而被動副本則在其主版本失效后才觸發(fā)，其距離截止期限的時(shí)間

4、間隔相對變小。FTRMFF算法的副版本優(yōu)先級繼承策略不利于被動副版本對處理器空閑資源的充分利用。針對這種情況，以最壞響應(yīng)時(shí)間分析為基礎(chǔ)，提出基于被動副版本優(yōu)先級提高策略的硬實(shí)時(shí)容錯(cuò)調(diào)度算法。該算法挪用高優(yōu)先級任務(wù)的空閑時(shí)間來處理低優(yōu)先級任務(wù)的容錯(cuò)，從而保證出錯(cuò)的任務(wù)滿足截止期限的要求。并且根據(jù)這種分配策略的性質(zhì)，設(shè)計(jì)了優(yōu)先級提高因子搜索算法。經(jīng)過研究分析，適當(dāng)提高被動副版本的優(yōu)先級能增加被動副版本的可調(diào)度性，從而提高處理機(jī)利用率。

5、>　　 副版本優(yōu)先級提高策略實(shí)質(zhì)上是考慮到被動副版本執(zhí)行的緊迫程度較高而提出來的。類似情況也會出現(xiàn)在處理機(jī)發(fā)生故障之后。具體來說，發(fā)生故障時(shí)刻所在的周期內(nèi)的實(shí)例相對于后續(xù)的實(shí)例的執(zhí)行窗口更小，緊迫程度更高。為實(shí)現(xiàn)緊迫實(shí)例滿足截止期限的目標(biāo)，提出啟發(fā)式非緊迫周期延遲策略。該策略盡可能推遲非緊迫實(shí)例的執(zhí)行從而合理挪動空閑資源使得低優(yōu)先級實(shí)例有更多的機(jī)會完成其緊迫周期內(nèi)的執(zhí)行。另外，具體給出了任務(wù)在緊迫周期的最壞響應(yīng)時(shí)間和非緊迫周期內(nèi)的最大

6、可延遲時(shí)間的精確計(jì)算方法。
　　 對于單處理機(jī)硬實(shí)時(shí)系統(tǒng)，在設(shè)計(jì)節(jié)能容錯(cuò)調(diào)度算法時(shí)需要考慮動態(tài)電壓調(diào)整技術(shù)對瞬時(shí)錯(cuò)誤發(fā)生概率的負(fù)面影響。將處理器空閑資源全部用于降低工作電壓不僅造成替代任務(wù)無充裕時(shí)間進(jìn)行容錯(cuò)，而且替代任務(wù)執(zhí)行本身會增加系統(tǒng)能耗開銷。為解決這些負(fù)面影響，通過定量分析電壓/頻率與錯(cuò)誤概率的關(guān)系以期望功耗最小化為目標(biāo)提出任務(wù)最優(yōu)頻率的概念。然后，根據(jù)任務(wù)在最優(yōu)頻率下的節(jié)能效率定義能耗優(yōu)先級，并提出啟發(fā)式節(jié)能容錯(cuò)調(diào)度算法

7、。該算法將處理器空閑時(shí)間優(yōu)先分配給能耗優(yōu)先級高的任務(wù)，從而最大限度地將空閑資源轉(zhuǎn)化為能耗下降。
　　 與單處理機(jī)系統(tǒng)相比，動態(tài)電壓調(diào)整技術(shù)對多處理機(jī)系統(tǒng)的影響更加復(fù)雜。低功耗技術(shù)會延長主版本的最壞響應(yīng)時(shí)間進(jìn)而破壞副版本的類型，可能造成副版本由主動方式轉(zhuǎn)為被動方式。增加的容錯(cuò)冗余不僅增加硬件代價(jià)而且產(chǎn)生更多的能耗。針對這種復(fù)雜情況，首先對容錯(cuò)和節(jié)能在消耗處理器時(shí)間方面進(jìn)行定量分析。在此基礎(chǔ)上，將FTRMFF算法中的容錯(cuò)完成時(shí)間測試