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

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

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

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

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

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

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

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