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

1、隨著科學(xué)的日新月異，人們對計算機的處理能力提出更好、更快、更強的要求與挑戰(zhàn)，多處理器技術(shù)便是這個挑戰(zhàn)的有效突破口。任務(wù)調(diào)度是這個突破口中最為關(guān)鍵的技術(shù)之一。隨著科技的進一步發(fā)展，多處理技術(shù)向著不同處理器對同一個任務(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、是一個NP完全問題?，F(xiàn)有的大多數(shù)異構(gòu)多處理器實時任務(wù)調(diào)度算法采用的方式是首先初始化分簇，然后將簇進行放置，再對任務(wù)進行調(diào)度。基于復(fù)制可擴展實時任務(wù)調(diào)度算法與異構(gòu)最早時間優(yōu)先算法由于在分簇時綜合考慮任務(wù)執(zhí)行時間、處理器空閑狀態(tài)、前趨關(guān)系等多個因素從而引起算法時間復(fù)雜度過高。
　　 針對此種情況，本文研究一種改進的異構(gòu)多處理器實時任務(wù)調(diào)度算法HRTSA(Heterogeneous Real—time Task Scheduling

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

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