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

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

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

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

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

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

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

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

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