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

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

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

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

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

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

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

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

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