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

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

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

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

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

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

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

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