多處理器EPDF Pfair算法的研究.pdf

1、目前,越來越多的實(shí)時(shí)應(yīng)用需求推動(dòng)著實(shí)時(shí)系統(tǒng)的發(fā)展。同時(shí)計(jì)算機(jī)的迅猛發(fā)展和硬件價(jià)格的降低使得多處理器實(shí)時(shí)系統(tǒng)得到廣泛的應(yīng)用。多處理器系統(tǒng)的調(diào)度問題也受到更多的關(guān)注。
　　 對(duì)多處理器實(shí)時(shí)調(diào)度問題的研究大多集中在強(qiáng)實(shí)時(shí)任務(wù)系統(tǒng)。在滿足強(qiáng)定時(shí)約束的條件下,一般認(rèn)為按比例公平使用資源(Proportionate Fair,簡(jiǎn)稱Pfair)調(diào)度模型是最優(yōu)的。Pfair調(diào)度模型有多種算法,其中的最優(yōu)算法涉及處理器之間頻繁的搶占和遷移,因此而

2、帶來的開銷對(duì)于弱實(shí)時(shí)系統(tǒng)和某些強(qiáng)實(shí)時(shí)系統(tǒng)是不必要或不允許的。Pfair調(diào)度模型中的最早偽時(shí)限優(yōu)先(Earliest Pseudo-Deadlinefirst,簡(jiǎn)稱EPDF)算法在兩個(gè)以上處理器構(gòu)成的平臺(tái)上雖不是Pfair調(diào)度模型中最優(yōu)的算法,但它沒有額外的參數(shù)和規(guī)則限制。針對(duì)弱實(shí)時(shí)系統(tǒng)和任務(wù)重組頻繁的動(dòng)態(tài)任務(wù)系統(tǒng),EPDF算法與最優(yōu)的Pfair調(diào)度算法相比是較好的選擇。
　　 本文從Pfair調(diào)度模型出發(fā),分析了Plait調(diào)度的

3、最優(yōu)性和可行性,指出了最優(yōu)Pfair算法在一些實(shí)時(shí)系統(tǒng)應(yīng)用中的不足之處,為此引入了EPDF Pfair調(diào)度算法。本文對(duì)EPDF調(diào)度算法進(jìn)行了較為深入的研究。針對(duì)強(qiáng)實(shí)時(shí)系統(tǒng)中的EPDF算法,本文分析了可調(diào)度利用率約束以及現(xiàn)有的一些判定方法,對(duì)已有的可調(diào)度利用率判定作了改進(jìn),得到了一種基于利用率的可調(diào)度性判定方法和可調(diào)度性判定的一種組合方案。針對(duì)弱實(shí)時(shí)系統(tǒng),論文從權(quán)值約束角度分析了EPDF算法確保延緩的約束條件,推出了不限制任務(wù)權(quán)值情況下的