一種改進(jìn)的異構(gòu)多處理器實(shí)時(shí)任務(wù)調(diào)度算法研究.pdf

1、隨著科學(xué)的日新月異，人們對(duì)計(jì)算機(jī)的處理能力提出更好、更快、更強(qiáng)的要求與挑戰(zhàn)，多處理器技術(shù)便是這個(gè)挑戰(zhàn)的有效突破口。任務(wù)調(diào)度是這個(gè)突破口中最為關(guān)鍵的技術(shù)之一。隨著科技的進(jìn)一步發(fā)展，多處理技術(shù)向著不同處理器對(duì)同一個(gè)任務(wù)有不同的處理速度的異構(gòu)方向發(fā)展，這種異構(gòu)性也讓異構(gòu)多處理器的任務(wù)的調(diào)度問題變得更加復(fù)雜。
　　 調(diào)度算法研究中，任務(wù)模型大多數(shù)采用有向無環(huán)圖DAG(Directed AcyclicGraph)。任務(wù)的調(diào)度問題，已被證明

2、是一個(gè)NP完全問題?，F(xiàn)有的大多數(shù)異構(gòu)多處理器實(shí)時(shí)任務(wù)調(diào)度算法采用的方式是首先初始化分簇，然后將簇進(jìn)行放置，再對(duì)任務(wù)進(jìn)行調(diào)度。基于復(fù)制可擴(kuò)展實(shí)時(shí)任務(wù)調(diào)度算法與異構(gòu)最早時(shí)間優(yōu)先算法由于在分簇時(shí)綜合考慮任務(wù)執(zhí)行時(shí)間、處理器空閑狀態(tài)、前趨關(guān)系等多個(gè)因素從而引起算法時(shí)間復(fù)雜度過高。
　　 針對(duì)此種情況，本文研究一種改進(jìn)的異構(gòu)多處理器實(shí)時(shí)任務(wù)調(diào)度算法HRTSA(Heterogeneous Real—time Task Scheduling

3、Algorithm for multiprocessors)。本文在初始化分簇時(shí)提出一種基于前趨約束的最小執(zhí)行時(shí)間分簇策略以降低時(shí)間復(fù)雜度，為了保證調(diào)度成功率，在放置策略和調(diào)度策略都進(jìn)行改進(jìn)。論文的具體改進(jìn)工作如下：
　　 根據(jù)異構(gòu)多處理器實(shí)時(shí)任務(wù)中同一子任務(wù)在不同處理器上執(zhí)行時(shí)間各不相同的特點(diǎn)，本文提出一種基于前趨約束的最小執(zhí)行時(shí)間分簇策略。這種策略將在某一處理器上具有最小執(zhí)行時(shí)間的節(jié)點(diǎn)分配至同一處理器上執(zhí)行，僅考慮節(jié)點(diǎn)的執(zhí)行

4、時(shí)間與前趨關(guān)系，以降低分簇算法的時(shí)間復(fù)雜度。當(dāng)存在個(gè)別性能較優(yōu)的處理器時(shí)，采用基于前趨約束的最小執(zhí)行時(shí)間分策略會(huì)將大量節(jié)點(diǎn)分至較優(yōu)的處理器上執(zhí)行。這種情況將引起個(gè)別處理器過載，其它處理器空閑的問題。針對(duì)此問題，在放置各簇任務(wù)至各處理器時(shí)，采用負(fù)載均衡的放置策略。這種放置方式在保證處理器負(fù)載均衡的同時(shí)，能有效地提高任務(wù)的處理效率。
　　 為了減少任務(wù)通信時(shí)延，提高處理器的利用率，本文對(duì)現(xiàn)有的任務(wù)調(diào)度算法進(jìn)行了改進(jìn)，通過采用三種復(fù)制