網格環(huán)境下滿足QoS控制的任務調度模型與算法研究.pdf

1、基于網絡的計算是當前國內外研究的熱點，特別是隨著網格計算的提出，許多學者對此進行了大量的研究工作，使得網格計算由最初的以協(xié)議為中心的體系架構轉變?yōu)榛诜盏捏w系架構。尤其是目前提出的服務和資源分離的面向服務的體系架構，認為服務是無狀態(tài)的，而資源是有狀態(tài)的。這樣，執(zhí)行一個服務的資源可以分布在不同的地域，亦即它們可以動態(tài)地加入和撤離網格計算環(huán)境，而呈現出分布、異構、動態(tài)的特征。因此，在網格計算環(huán)境下，保證QoS的任務調度就變得十

2、分復雜。在網格環(huán)境中，有效的任務調度是取得高性能的關鍵。由于網格用戶是獨立地向網格計算環(huán)境提交任務，因此，網格計算環(huán)境下任務的執(zhí)行呈現分布、并發(fā)的特點。如何有效安排完成任務的資源，以及如何在資源上安排任務的執(zhí)行順序是保證QoS所必需解決的問題。由于Petri網具有描述事件的并發(fā)、異步、動態(tài)等特性的能力，因此，在任務調度問題上得到越來越多的應用。本文利用Petri網(特別是高級Petri網)這一形式化工具模擬與分析網格計算環(huán)境

3、下任務的調度問題，建立了適合于網格任務調度的描述與分析模型。這對于進一步豐富Petri網的概念與模擬能力，推進網格計算，尤其是任務調度的研究具有重要的理論價值與實際意義。本文綜述了網格計算的發(fā)展與研究現狀，特別是詳細論述了現有任務調度的各種模型和算法。在此基礎上，給出了適合于網格計算，特別是以服務為中心的任務調度算法。從理論上對Petri網本身進行了研究，結合T-時間Petri網建立了適合描述網格計算環(huán)境下任務調度的一些模

4、型和算法。同時，提出并研究了用于網格計算的服務管理模型和算法，以及網格計算環(huán)境下獨立任務調度的算法，并將本文得到的結果應用于實際項目中，取得了較好的應用。本文工作的主要貢獻表現在如下幾個方面：(1)針對網格環(huán)境下實際資源是有限的特點，提出了有界Petri網同步距離的計算方法，為模擬任務調度的Petri網建模和分析提供了評價手段。(2)Petri網是一個并發(fā)模型，但是，現有的可達圖隱含了這種并發(fā)關系，而且它的狀態(tài)空間是爆炸性

5、增長，這樣不利于分析模型的性能。為此提出了Petri網并發(fā)可達圖及其構造算法，使得Petri網的分析能力進一步增強。(3)基于Petri網虹吸的網格任務(資源)調度模型與算法是實現有效調度的一種重要手段，然而，對于極小虹吸的計算還沒有一個有效的算法。本文通過研究Petri網的結構特征，提出了計算Petri網所有極小虹吸的有效計算方法。(4)針對大規(guī)模任務的穩(wěn)態(tài)調度問題，本文通過研究T-時間Petri網，提出了主從任務調度的

6、T-時間Petri網模型與算法。從我們提出的并發(fā)可達圖中得到了穩(wěn)態(tài)調度的一個優(yōu)化策略。(5)結合DS證據理論，提出了網格計算環(huán)境下服務管理的模型。該模型的最大特點在于，通過全局服務管理器實現任務在服務上的有效分配。用戶需要的服務不是在全局服務目錄中查找，而是在自己的服務目錄中查找，從而提高了服務的發(fā)現效率，有效地解決了服務發(fā)現問題。全局服務管理器管理一個虛擬的全局服務目錄，動態(tài)更新用戶服務目錄而不是針對用戶的每一次服務請求

7、，因而有效地解決服務中心的瓶頸問題。同時，全局服務管理器監(jiān)視服務的執(zhí)行情況以及資源的QoS保證情況，為保證任務的完成選擇有QoS保障的資源提供了充分的證據。(6)針對網格結點的特點(它可以是一個處理機、一個機群或一個局域網)，研究了獨立任務在同構和異構環(huán)境下的調度問題。首先，給出了同構環(huán)境下獨立任務的調度算法。對于異構環(huán)境下任務的調度問題，眾所周知，Min-min(Max-min)啟發(fā)式算法被認為是獨立任務調度性能評價的標準

8、。然而，由于Min-min算法首先映射短任務而會出現負載不平衡，這主要是因為它沒有全面地考慮處理機的性能和全局動態(tài)負載均衡。本文首先給出了評價處理機性能的一種簡易實用的評價方法，并以此給出了考慮全局負載均衡的任務調度順序，然后給出了調度在相應處理機上的兩個算法。舉例與模擬試驗表明，所給的調度算法在調度時間與調度性能方面均優(yōu)于Min-min(Max-min)算法。關鍵詞：網格計算，任務調度，調度模型與算法，全局服務管理器，Pe