基于petri網(wǎng)模型的網(wǎng)格資源調(diào)度的-研究

《基于petri網(wǎng)模型的網(wǎng)格資源調(diào)度的-研究》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學術(shù)論文-天天文庫。

1、的網(wǎng)格環(huán)境支持，實現(xiàn)更方便的信息共享和互操作，從而對商業(yè)模式、人的工作方式和生活方式產(chǎn)生深遠的影響。Petri網(wǎng)是二十世紀六十年代，德國研究員CarlAdamPetri在他的博士論文《用自動機通信》中首次使用網(wǎng)絡(luò)結(jié)構(gòu)模擬通信系統(tǒng)15J，而提出的一種新的數(shù)學建模工具：Petri網(wǎng)是從實際的物理模型出發(fā)，構(gòu)造描述系統(tǒng)的模型，因而它一產(chǎn)生就受到大家的青睞，使得Petri網(wǎng)的發(fā)展非常迅速，它從最初應(yīng)用于通信系統(tǒng)，然后推廣到計算機、通信、自動控制、柔性制造(FMS)、人工智能等領(lǐng)域【6】。自1980年以來，每年一次的Petri網(wǎng)理論和應(yīng)用的國際研討會，推動、促進了Petr

2、i網(wǎng)理論和應(yīng)用技術(shù)的發(fā)展，使得Petri網(wǎng)技術(shù)日益完善和充實。國內(nèi)的各科研院校、工業(yè)界也進行了廣泛的研究，并在中國計算機學會中專門設(shè)立了Petri網(wǎng)專業(yè)委員會，每逢奇數(shù)年召開全國的Petri網(wǎng)技術(shù)研討會，對Petri網(wǎng)的發(fā)展和對外交流起了推動作用。Petri網(wǎng)既具有直觀、易懂、圖形化的特點，同時又具有數(shù)學化的分析方法，它不僅能用圖形表示系統(tǒng)的靜態(tài)結(jié)構(gòu)和動態(tài)結(jié)構(gòu)，還能用關(guān)聯(lián)矩陣、不變量和可達樹等來計算、描述推理過程I71。用Petri網(wǎng)描述系統(tǒng)具有以下優(yōu)點：1)善于表達系統(tǒng)靜態(tài)結(jié)構(gòu)和動態(tài)行為；2)可以把復(fù)雜的問題用直觀的圖形模型來表示，便于理解；3)系統(tǒng)動態(tài)過程可

3、用矩陣來描述，不需要在龐大的解空間中搜索最優(yōu)解；4)可以并行求解，同時得到多個求解路徑。因此Petri網(wǎng)是研究和模擬系統(tǒng)并行發(fā)生、次序發(fā)生或循環(huán)發(fā)生的理想工具。網(wǎng)格資源調(diào)度問題從特征上分析具有并行性和異步性，采用Petri網(wǎng)描述網(wǎng)格資源調(diào)度問題具有相當?shù)膬?yōu)勢，所以Petri網(wǎng)在網(wǎng)格資源調(diào)度的研究有相當?shù)膽?yīng)用價值。用Petri網(wǎng)描述調(diào)度問題，然后采用關(guān)聯(lián)矩陣描述各個資源的狀態(tài)，根據(jù)狀態(tài)矩陣的初始狀態(tài)采用啟發(fā)式算法優(yōu)化調(diào)度模型。上述技術(shù)的關(guān)鍵步驟在于如何解決Petri網(wǎng)節(jié)點過多的問題。1．2本課題采取的研究方法以及可行性分析Petri網(wǎng)是非常適合描述同步和異步的建模

4、工具，而網(wǎng)格資源調(diào)度問題正好具備這種特性，因而利用Petri網(wǎng)可以非常恰當?shù)拿枋稣{(diào)度問題的動態(tài)過程。參考文獻[8][9][10][11]都是利用Petri網(wǎng)給網(wǎng)格系統(tǒng)建模，然后再利用相應(yīng)的算法求解。事實上Petri網(wǎng)是一個可以擴充的系統(tǒng)，根據(jù)實際的應(yīng)用可以增加一些特殊的功能，考慮有優(yōu)先級的調(diào)度問題中，可以引進抑制弧，即可以對調(diào)度任務(wù)進行優(yōu)先級排序。在實際的情況中還可以做相應(yīng)的擴充。對于網(wǎng)格調(diào)度問題來說，它們的表述形式可以看成是將m個資源分配到n個處理機上，如何得到合理的優(yōu)化結(jié)果。在本文中擬對網(wǎng)格資源進行研究，計劃采用以下步驟：(1)對網(wǎng)格資源調(diào)度建立Petri網(wǎng)

5、模型，分析網(wǎng)格的行為過程；(2)分析Min．Min算法，引入改進的Min—Min算法；(3)把改進的Min—Min算法與Petri網(wǎng)的可達圖分析結(jié)合起來，給算法一個形象的圖形的描述；(4)利用仿真工具GridSim，把改進的算法作為GridSim中第一級broker，進行仿真實驗。1．2．1網(wǎng)格資源的建模建模的關(guān)鍵在于確定Petri網(wǎng)中的庫所(Place)和變遷(Transition)。在網(wǎng)格資源中，擬訂以調(diào)度的任務(wù)作為庫所，而把處理機作為變遷，如圖1．1描述了一組有優(yōu)先級和沒有優(yōu)先級的調(diào)度過程。P】Tnp抵o—呻如＆p我圖1．1(a)有優(yōu)先級的調(diào)度圖1．1(b

6、)無優(yōu)先級的調(diào)度實際的調(diào)度模型就是將上面的基本元素組合而來的復(fù)雜模型；由于實際的系統(tǒng)是一個復(fù)雜的模型，因而引進Petri網(wǎng)簡化技術(shù)。1．2．2簡化Petri網(wǎng)模型初始建立的Petri網(wǎng)模型由于過度注重了細節(jié)的描述，因而節(jié)點過于龐大，必須對初始模型進行化簡，否則不能體現(xiàn)Petri網(wǎng)模型的優(yōu)點。目前有很多關(guān)于Petri網(wǎng)模型簡化的技術(shù)，層次模擬和抽象是比較成熟的技術(shù)。把同一個應(yīng)用問題從使用基本網(wǎng)系統(tǒng)到使用P／T系統(tǒng)，再到使用高級網(wǎng)系統(tǒng)就是層次模擬：抽象就是忽略細節(jié)，在同一層次上忽略細節(jié)以減少節(jié)劇”。高級網(wǎng)系統(tǒng)有Pr，T-系統(tǒng)，自控網(wǎng)系統(tǒng)等，抽象技術(shù)主要是與UML相結(jié)

7、合的技術(shù)。在本文中對Petri網(wǎng)理論的應(yīng)用主要有兩個方面：第一個是描述網(wǎng)格系統(tǒng)時，為了減少節(jié)點，引進著色Petri網(wǎng)，把具有相同性質(zhì)的節(jié)點抽象成一個節(jié)點，這并不改變Petri網(wǎng)的活性，然后再利用工作流分析的方法，進一步對模型進行簡化，當然這個模型只是為了描述網(wǎng)格系統(tǒng)更為方便，根據(jù)不同的需要，我們可以做出不同的抽象模型，描述不同層次的模型；第二個應(yīng)用是在求解調(diào)度模型時，由于網(wǎng)格調(diào)度問題實際上一個NPC問題，不管如何改進算法，算法的復(fù)雜度是不會降低的，為了能加速求解過程，把問題進行分而治之的求解方法，在理論上是能加快求解的速度的。本文中采用的算法是改進的Min—Mi

8、n算法，把任務(wù)分成了有優(yōu)