考慮緩存預(yù)熱時間的多核實時調(diào)度算法和分析.pdf

1、由于功耗和散熱的問題,處理器的設(shè)計正往多核方向發(fā)展。多核處理器不僅應(yīng)用在一般的計算機系統(tǒng)中,而且正不斷的應(yīng)用到嵌入式系統(tǒng)中。這樣的系統(tǒng)往往也是實時系統(tǒng)。在實時系統(tǒng)中,計算的正確性不僅依賴于結(jié)果的正確性而且依賴于結(jié)果產(chǎn)生時間的正確性。
　　 多核處理器帶給實時系統(tǒng)的不僅是高效的處理能力而且還有復(fù)雜的任務(wù)調(diào)度。在單處理器系統(tǒng)中,計算任務(wù)最壞情況執(zhí)行時間(WCET)時,一般認為任務(wù)的緩沖行都在緩存中,通過靜態(tài)分析用緩存延遲得到。然而在

2、多核處理器系統(tǒng)中,有的核上的緩存并沒有任務(wù)的緩沖行。當(dāng)任務(wù)運行在這樣的核上時,會增大任務(wù)的WCET,增大的這部分時間稱為緩存預(yù)熱時間。解決緩存預(yù)熱時間對多核實時調(diào)度產(chǎn)生的影響是一個重要的問題。
　　 可調(diào)度性分析是研究實時調(diào)度的重要手段,主要有兩種方法:模擬和利用率的邊界測試。模擬的方法盡管實現(xiàn)簡單,但它只檢測了系統(tǒng)運行的有限路徑,所以得到的可調(diào)度任務(wù)集數(shù)目并不可靠。利用率邊界測試往往只能推導(dǎo)出充分條件,由此獲得的可調(diào)度任務(wù)集數(shù)

3、目較為悲觀。由于這些原因,研究者提出使用模型檢測的方法,對多處理器調(diào)度算法進行可調(diào)度性分析。但他們都沒有考慮緩存預(yù)熱時間對可調(diào)度性分析的影響。針對這一問題,本論文基于模型檢測,提出一種考慮了緩存預(yù)熱時間的可調(diào)度性分析的方法,并以靜態(tài)優(yōu)先級調(diào)度算法單調(diào)速率(RM)為例,說明了這種方法的有效性。
　　 在采用多核RM算法的調(diào)度系統(tǒng)中,緩存預(yù)熱時間會導(dǎo)致一些任務(wù)集錯失截止時間。為了降低緩存預(yù)熱時間帶來的不可預(yù)測性,研究者提出新的硬件架

4、構(gòu)Push Block,預(yù)先將任務(wù)的緩沖行遷移到目的核緩存中。當(dāng)任務(wù)在目的核上運行時,就不會產(chǎn)生緩存預(yù)熱時間。然而,現(xiàn)有的調(diào)度算法并不支持這種架構(gòu)。針對這個問題,本論文以靜態(tài)優(yōu)先級調(diào)度算法RM為基礎(chǔ),結(jié)合這種新架構(gòu)所提供的功能,給出了三種策略,提出了一個新的靜態(tài)優(yōu)先級調(diào)度算法,提高了系統(tǒng)實時性,減少了錯失截止時間的任務(wù)集。
　　 在靜態(tài)優(yōu)先級調(diào)度中,系統(tǒng)運行時,任務(wù)優(yōu)先級是固定的。這可能導(dǎo)致一個高優(yōu)先級任務(wù)長時間占有CPU,而低

5、優(yōu)先級的任務(wù)必須等待。因此,產(chǎn)生了動態(tài)優(yōu)先級調(diào)度。在系統(tǒng)運行時,它可以改變?nèi)蝿?wù)的優(yōu)先級,增強了對環(huán)境的調(diào)整能力。不幸的是緩存預(yù)熱時間仍然會導(dǎo)致采用了動態(tài)優(yōu)先級調(diào)度算法的系統(tǒng)錯失截止時間。另外,目前的多核動態(tài)優(yōu)先級調(diào)度算法并沒有建立在新架構(gòu)PushBlock上,無法利用預(yù)遷移機制提高算法的性能。針對這些問題,本論文以經(jīng)典的動態(tài)優(yōu)先級調(diào)度算法最短截止時間優(yōu)先(EDF)為基礎(chǔ),提出了適應(yīng)緩存預(yù)熱時間的動態(tài)優(yōu)先級調(diào)度算法。通過實驗,展示了新算法

6、良好的性能。
　　 綜上所述,本論文研究中所做出的主要貢獻體現(xiàn)在以下三個方面:
　　 1)針對以往的可調(diào)度性分析沒有考慮緩存預(yù)熱時間的問題,提出了基于模型檢測,考慮緩存預(yù)熱時間的可調(diào)度性分析方法,并以RM算法為例,驗證了方法的有效性。
　　 2)針對緩存預(yù)熱時間導(dǎo)致經(jīng)典的靜態(tài)優(yōu)先級調(diào)度算法RM實時性降低的問題,給出了降低緩存預(yù)熱時間的三種策略,提出了適應(yīng)緩存預(yù)熱時間的靜態(tài)優(yōu)先級調(diào)度算法WM-RM,既保留了RM算法