面向能耗優(yōu)化的分布式實時系統(tǒng)調(diào)度算法研究.pdf

1、實時系統(tǒng)，特別是運(yùn)行在安全關(guān)鍵應(yīng)用領(lǐng)域的分布式實時系統(tǒng)，具有十分嚴(yán)格的及時性和可靠性要求。隨著當(dāng)前系統(tǒng)能耗已經(jīng)成為計算系統(tǒng)的重要設(shè)計約束，如何在實時系統(tǒng)設(shè)計中進(jìn)行能耗優(yōu)化，已經(jīng)成為實時系統(tǒng)研究中亟待解決的問題。實時調(diào)度是保障實時系統(tǒng)及時性和可靠性的重要方法。實時系統(tǒng)能耗優(yōu)化調(diào)度將能耗優(yōu)化機(jī)制與既有的實時調(diào)度策略相結(jié)合，從系統(tǒng)整體行為中挖掘其潛在的節(jié)能能力，已成為實時系統(tǒng)能耗優(yōu)化設(shè)計最有效的策略。 本論文<'1>以分布式實時系統(tǒng)的

2、能耗優(yōu)化調(diào)度算法設(shè)計為方向，分別對分布式強(qiáng)實時系統(tǒng)的可調(diào)度性驗證的形式化方法、實時任務(wù)調(diào)度、容錯實時調(diào)度等關(guān)鍵問題進(jìn)行了深入的研究，提出一系列相關(guān)方法和策略，以期進(jìn)一步完善實時系統(tǒng)能耗優(yōu)化調(diào)度方法。 實時系統(tǒng)的可調(diào)度性驗證是確保實時系統(tǒng)滿足及時性的重要手段，是實時系統(tǒng)設(shè)計中的關(guān)鍵技術(shù)。分布式實時系統(tǒng)大量復(fù)雜特征的引入，需要采用更嚴(yán)謹(jǐn)?shù)男问交炞C方法來判斷實時系統(tǒng)是否滿足定時約束。針對這一現(xiàn)狀，本論文在對當(dāng)前已有實時系統(tǒng)的形式化描

3、述模型的表達(dá)能力和建模難度進(jìn)行分析比較的基礎(chǔ)上，提出了一種與頻率相關(guān)的時間Petri網(wǎng)——FRTPN模型，以及基于該模型的可調(diào)度性驗證方法。FRTPN引入變遷頻率設(shè)置空間以及頻率相關(guān)的靜態(tài)引發(fā)時域，支持面向頻率調(diào)節(jié)的能耗優(yōu)化調(diào)度研究；同時它增加一類抑制弧支持容錯機(jī)制的建模：另外，本論文在借鑒現(xiàn)有時間Petri網(wǎng)相關(guān)驗證技術(shù)的基礎(chǔ)上，給出了FRTPN模型的基于狀態(tài)類的可調(diào)度性驗證方法，并通過對檢查點(diǎn)容錯策略進(jìn)行建模驗證了FRTPN模型的有

4、效性。 基于動態(tài)電壓調(diào)整(DVS)技術(shù)的實時能耗優(yōu)化調(diào)度方法已經(jīng)成為實時系統(tǒng)能耗優(yōu)化設(shè)計的最有效策略。針對現(xiàn)有分布式實時系統(tǒng)離線DVS調(diào)度算法采用的系統(tǒng)描述模型普遍缺乏全面準(zhǔn)確刻畫任務(wù)特征的能力，難以支持復(fù)雜分布式實時系統(tǒng)的可調(diào)度性驗證的問題。本論文以FRTPN模型上的實時系統(tǒng)可調(diào)度驗證為基礎(chǔ)，提出了一種基于能耗/時間漸變率的啟發(fā)式離線DVS調(diào)度算法，綜合考慮了頻率調(diào)整對系統(tǒng)能耗與松弛時間造成的影響，并以此為指導(dǎo)對待調(diào)頻任務(wù)進(jìn)行

5、選擇。另外，本論文還對任務(wù)分配進(jìn)行了深入研究，提出了一種以任務(wù)利用率均勻化為目標(biāo)的任務(wù)分配方法，以減少頻率切換過程導(dǎo)致的能耗開銷。在上述算法實現(xiàn)過程中，本論文根據(jù)FRTPN模型狀態(tài)空間的變化規(guī)律，優(yōu)化系統(tǒng)狀態(tài)空間的生成過程，提高了算法的實現(xiàn)效率。容錯技術(shù)是保障實時安全關(guān)鍵系統(tǒng)可靠性的重要手段，而基/副版本容錯調(diào)度是目前解決分布式實時系統(tǒng)容錯問題的有效方法。針對當(dāng)前基/副版本容錯實時調(diào)度中缺乏對能耗優(yōu)化機(jī)制考慮的問題，本論文對基/副版本容

6、錯系統(tǒng)的DVS能耗優(yōu)化調(diào)度展開研究。首先提出一種離線設(shè)置處理器執(zhí)行頻率的靜態(tài)容錯DVS調(diào)度算法，在此基礎(chǔ)上提出能夠在線收集動態(tài)松弛時間并進(jìn)行再分配的動態(tài)容錯DVS調(diào)度算法，最后提出一種以盡量推遲副版本釋放時間為目標(biāo)的基/副版本時限優(yōu)化分配算法。模擬試驗表明，上述算法能夠有效地改善容錯實時系統(tǒng)的能耗開銷。 綜上所述，本論文所做工作的主要貢獻(xiàn)與創(chuàng)新特色體現(xiàn)在以下三個方面： (1)提出了一種能夠有效對系統(tǒng)的能耗特征和容錯機(jī)制建

7、模的頻率相關(guān)時間Petri網(wǎng)模型——FRTPN及其相關(guān)可調(diào)度性驗證方法，能夠滿足復(fù)雜的分布實時系統(tǒng)的建模及面向能耗優(yōu)化的實時系統(tǒng)可調(diào)度性驗證需求。 (2)提出了一種以系統(tǒng)能耗/時間漸變率為指導(dǎo)的離線DVS調(diào)度算法(ETGBS)以及一種以任務(wù)利用率均勻化為目標(biāo)的任務(wù)分配算法(UBTA)，有效降低系統(tǒng)的能耗開銷。 (3)首次開展了基/副版本容錯系統(tǒng)的能耗優(yōu)化調(diào)度研究，提出了相應(yīng)的靜態(tài)DVS調(diào)度算法(PBSS)、動態(tài)DVS調(diào)度