實(shí)時(shí)異構(gòu)系統(tǒng)的集成動(dòng)態(tài)調(diào)度模型與算法研究.pdf

1、實(shí)時(shí)異構(gòu)系統(tǒng)已被廣泛應(yīng)用在航空航天、工業(yè)控制、電訊行業(yè)、圖像處理以及Internet應(yīng)用等諸多領(lǐng)域。在這些應(yīng)用中，存在大量的硬、軟實(shí)時(shí)任務(wù)共存的情況，對(duì)實(shí)時(shí)異構(gòu)系統(tǒng)的集成動(dòng)態(tài)調(diào)度模型與算法的研究具有重大理論和實(shí)際意義。本文對(duì)實(shí)時(shí)異構(gòu)系統(tǒng)的集成動(dòng)態(tài)調(diào)度問題進(jìn)行了深入的研究，提出了一種實(shí)時(shí)異構(gòu)系統(tǒng)的集成動(dòng)態(tài)調(diào)度模型，基于這種模型，提出批優(yōu)化的調(diào)度策略和批任務(wù)在處理器上運(yùn)行的目標(biāo)函數(shù)構(gòu)造原則。在此基礎(chǔ)上，提出了一種基于分批優(yōu)化的實(shí)時(shí)異構(gòu)系統(tǒng)的

2、集成動(dòng)態(tài)調(diào)度算法——GOIDSH算法。 本文針對(duì)實(shí)時(shí)異構(gòu)多任務(wù)調(diào)度的特點(diǎn)，采用集中式調(diào)度模型；提出軟、硬實(shí)時(shí)任務(wù)形式化描述非精確計(jì)算的統(tǒng)一任務(wù)模型，清晰地描述實(shí)時(shí)任務(wù)的特點(diǎn)。、系統(tǒng)任務(wù)描述簡(jiǎn)單，節(jié)省存儲(chǔ)空間，為實(shí)現(xiàn)基于批優(yōu)化的集成動(dòng)態(tài)調(diào)度打下基礎(chǔ)。 論文提出了一種新的實(shí)時(shí)異構(gòu)系統(tǒng)的集成動(dòng)態(tài)調(diào)度算法——基于分批優(yōu)化的集成動(dòng)態(tài)調(diào)度算法(GOIDSH算法)。該算法以啟發(fā)式搜索為基礎(chǔ)，主要包括任務(wù)分批、構(gòu)造目標(biāo)函數(shù)和基于批優(yōu)化的

3、調(diào)度策略三大部分，采用統(tǒng)一形式完成了實(shí)時(shí)異構(gòu)系統(tǒng)的集成動(dòng)態(tài)調(diào)度。同時(shí)，在構(gòu)造目標(biāo)函數(shù)時(shí)，算法還引入軟實(shí)時(shí)任務(wù)服務(wù)質(zhì)量(Qos)降級(jí)策略來提高調(diào)度成功率。 GOIDSH算法的核心思想是：在每次擴(kuò)充當(dāng)前局部調(diào)度時(shí)，首先按一定規(guī)則在待調(diào)度的任務(wù)集中選取一批任務(wù)組成任務(wù)子集，保證所選取的任務(wù)子集中某一任務(wù)對(duì)某個(gè)資源有訪問需求時(shí)，子集中的其它任務(wù)不能對(duì)該資源有訪問需求。然后，綜合各種因素，對(duì)該批任務(wù)中的每項(xiàng)任務(wù)在每個(gè)處理器上的運(yùn)行構(gòu)造目標(biāo)

4、函數(shù)，將問題轉(zhuǎn)化為非平衡指派問題，利用非平衡指派問題直接解法對(duì)任務(wù)進(jìn)行優(yōu)化分配，一次性為這些任務(wù)分配一個(gè)處理器或?yàn)槊總€(gè)處理器分配一項(xiàng)任務(wù)，使得這種分配具有最好的“合適性”，增大未被調(diào)度任務(wù)的被成功調(diào)度的可行性。 論文通過仿真和模擬，從調(diào)度成功率、軟實(shí)時(shí)任務(wù)的降級(jí)比率(DR)和被降級(jí)軟實(shí)時(shí)任務(wù)的服務(wù)質(zhì)量(QoS)三個(gè)方面，驗(yàn)證了GOIDSH算法的有效性及其調(diào)度性能。在仿真實(shí)驗(yàn)時(shí)，提出了一種按如下順序設(shè)定的價(jià)值最高最優(yōu)先的任務(wù)隊(duì)列排

5、序原則： ①任務(wù)的截止期越近，其價(jià)值越高； ②任務(wù)需要訪問的資源越多，其價(jià)值越高； ③任務(wù)要需訪問的資源中，互斥方式的訪問越多，其價(jià)值越高； ④任務(wù)的空閑時(shí)間越短，其價(jià)值越高； ⑤相同情形下，硬實(shí)時(shí)任務(wù)的價(jià)值高于軟實(shí)時(shí)任務(wù)的價(jià)值。 仿真實(shí)驗(yàn)結(jié)果表明，基于分批優(yōu)化的實(shí)時(shí)異構(gòu)系統(tǒng)集成動(dòng)態(tài)調(diào)度算法(GOIDSH算法)不僅成功地解決了實(shí)時(shí)異構(gòu)系統(tǒng)中硬、軟實(shí)時(shí)任務(wù)的集成動(dòng)態(tài)調(diào)度問題，而且還有效地提高