分布式異構系統(tǒng)中任務調度問題的研究.pdf

1、 隨著計算機應用范圍的日益擴大，分布式異構系統(tǒng)(DHS)逐漸成為解決復雜應用問題的有效工具。DHS利用一組異構的計算機來協(xié)作完成應用任務，以期獲得最好的執(zhí)行效果。DHS中的任務調度問題，對發(fā)揮系統(tǒng)的并行性能和保持負載平衡具有非常重要的意義。該問題已被證明是NP完全問題，無法在多項式時間內(nèi)找到最優(yōu)解，所以促使人們不懈地研究如何設計調度算法，用有限的代價獲得更好的解。目前常用的方法就是啟發(fā)式算法和隨機搜索的近似方法。 在本文中

2、研究了主從式DHS中的調度算法問題，對其進行數(shù)學建模，定義并分析了主從式DHS在穩(wěn)定運行階段的系統(tǒng)特性。對于樹形的主從結構，本文給出了達到穩(wěn)定運行階段的集中帶寬(bandwidth-centric)調度策略，并證明了穩(wěn)定運行階段的最優(yōu)性。 在本文中我們提出了兩種主從式DHS下的任務調度算法。首先給出了啟發(fā)式算法IMM，該算法可以解決DHS環(huán)境下，獨立的、帶優(yōu)先權和時限的任務的調度問題。隨后根據(jù)主從式DHS穩(wěn)定運行階段的特點，提出