分布式異構(gòu)系統(tǒng)中任務(wù)調(diào)度問題的研究.pdf

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

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