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

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

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

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

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

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

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

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

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

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