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

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

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

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

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

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

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