資源描述：
《試論基于petri網(wǎng)的并行分布計算中的調(diào)度問題的研究》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。
1、分類號：TP302密級：公開UDC：單位代碼：10424學(xué)位論文基于Petri網(wǎng)的并行分布計算中的調(diào)度問題的研究孔德華申請學(xué)位級別：碩士學(xué)位專業(yè)名稱：計算機軟件與理論指導(dǎo)教師姓名：吳哲輝職稱：教授山東科技大學(xué)二〇〇六年五月論文題目：基于Petri網(wǎng)的并行分布計算中的調(diào)度問題的研究作者姓名：孔德華入學(xué)時間：2003年9月專業(yè)名稱：計算機軟件與理論研究方向：Petri網(wǎng)理論及應(yīng)用指導(dǎo)教師：吳哲輝職稱：教授論文提交日期：2006年5月論文答辯日期：2006年月日授予學(xué)位日期：THESTUDYABOUTSCHEDULINGQ
2、UESTIONINPARALLELANDDISTRIBUTEDCOMPUTINGBASEDONPETRINETADissertationsubmittedinfulfillmentoftherequirementsofthedegreeofMASTEROFPHILOSOPHYfromShandongUniversityofScienceandTechnologybyKongDehuaSupervisor:ProfessorWuZhehuiCollegeofInformationScienceandEngineerin
3、gMay2006聲明本人呈交給山東科技大學(xué)的這篇碩士學(xué)位論文，除了所列參考文獻(xiàn)和世所公認(rèn)的文獻(xiàn)外，全部是本人在導(dǎo)師指導(dǎo)下的研究成果。該論文資料尚沒有呈交于其它任何學(xué)術(shù)機關(guān)作鑒定。碩士生簽名：日期：AFFIRMATIONIdeclarethatthisdissertation,submittedinfulfillmentoftherequirementsfortheawardofMasterofPhilosophyinShandongUniversityofScienceandTechnology,iswhollymy
4、ownworkguidedbymysupervisorunlessreferencedofacknowledge.Thedocumenthasnotbeensubmittedforqualificationatanyotheracademicinstitute.Signature:Date:摘要本文基于Petri網(wǎng)模型對調(diào)度問題建模、分析，該方法能夠容易地考慮任務(wù)調(diào)度環(huán)境的各種實際限制條件，如共享資源的交替使用，緩沖區(qū)的申請與釋放，任務(wù)之間的先后順序等；能夠容易地監(jiān)控任務(wù)的并發(fā)執(zhí)行的情形；能夠容易地把模型和搜索算法結(jié)
5、合在一起。本文綜合考慮任務(wù)的劃分、通信的協(xié)調(diào)和同步幾個方面的問題。為了獲得低通信延遲和負(fù)載平衡的任務(wù)調(diào)度方案，我們嘗試把任務(wù)圖進行分割，分割的目標(biāo)是割邊集合的權(quán)重最?。ㄍㄐ艜r間最短），分割后各子圖的頂點權(quán)重和大體相等（負(fù)載平衡）。圖形分割問題本身也是NP問題，我們采用目前已有的啟發(fā)式的分割方法，以獲得次優(yōu)解。其具體步驟是用圖形分割算法分割任務(wù)圖，把任務(wù)聚族，使得不同族之間任務(wù)通訊量最小。根據(jù)任務(wù)族的劃分結(jié)果，把同一族任務(wù)分配到同一局部環(huán)境（同一節(jié)點，或高速局域網(wǎng)），并借此建立Petri網(wǎng)模型。對同一族內(nèi)任務(wù)建立Pet
6、ri網(wǎng)模型，求解不考慮任務(wù)間通訊的局部最優(yōu)的任務(wù)調(diào)度方案。對各任務(wù)族Petri網(wǎng)同步合成，通過網(wǎng)的合成及合成后一些性質(zhì)尋找全局較優(yōu)的任務(wù)調(diào)度解。為了緩解狀態(tài)空間的爆炸問題我們構(gòu)造同步可達(dá)圖SRG。同步可達(dá)圖SRG只是描述Petri網(wǎng)模塊間同步變遷發(fā)生時的狀態(tài)的變化，而對于模塊內(nèi)局部變遷的發(fā)生引起的狀態(tài)變化則用局部可達(dá)樹LRG來描述，由于模塊間的交互相對較少，而同一階段模塊內(nèi)的狀態(tài)變化又相對獨立，無須把它們進行組合，而是分開考慮，這樣降低了問題的組合程度。這種方法對于規(guī)模較大的任務(wù)圖Petri網(wǎng)系統(tǒng)可以分塊研究，而任意
7、兩個模塊Petri網(wǎng)的LRG所代表的狀態(tài)又可以是并發(fā)存在的，所以可以并行生成各個LRG。關(guān)鍵詞：Petri網(wǎng)，資源控制網(wǎng)，內(nèi)聯(lián)子網(wǎng)合成，資源合成網(wǎng)，LRG，SRG，并行分布式調(diào)度AbstractSchedulingquestionismodeledandanalysisedbyPetrinetinthispaper.Variousconstraintconditionssuchasshareresourcesbeingusedinturn,bufferbeingrequestedorreleased,theprece
8、denceconstraintsamongtasksbeingabidedbyinschedulingcanbeeasilyconsiderdusingPetrinet.ThesituationaboutparallelexecutionoftaskscanbeeasilysupervisedusingPetrinet.Searchingalg
