網(wǎng)格任務調度算法研究及其有色Petri網(wǎng)的建模與仿真.pdf

1、網(wǎng)格計算環(huán)境下，由于資源的異構性、動態(tài)性、自治性以及網(wǎng)格任務的多樣性，任務調度一直就是網(wǎng)格計算的重要環(huán)節(jié)。因此，任務調度算法的效率決定著網(wǎng)格計算的效率，調度算法的設計就更應該精益求精。采用圖形化的數(shù)學工具來完成包括系統(tǒng)和算法的形式化描述、正確性檢驗、性能評價、測試等是對算法設計精益求精的重要工作方法。論文建立了任務調度算法模型，在運行系統(tǒng)模型中仿真實際任務調度算法的運行，通過分析模型的性質和性能來研究實際算法的性能，從而對實際調度算法進

2、行了改進設計。本文的主要內容如下：
　　（1）本文對兩種經(jīng)典的網(wǎng)格任務調度算法Min-Min和Max-Min算法進行了分析，然后使用有色Petri網(wǎng)的建模工具CPN Tools進行了仿真實驗，通過舉例模擬發(fā)現(xiàn)：Min-Min算法中任務的最大完成時間（makespan）相對較長，但是更主要的缺點是負載不均衡，Max-Min算法具有較小的最大完成時間。
　?。?）基于以上研究，需要對網(wǎng)格任務調度算法進行改進，使得任務調度算法具有

3、較小的最大完成時間，并且要考慮到整個系統(tǒng)機器間的負載平衡問題。因此，本文設計出了一種基于優(yōu)先級的網(wǎng)格任務調度算法P-M-M。為了解決機器間的負載平衡問題，該算法采用根據(jù)任務的平均預期執(zhí)行時間進行分組的方法；為了使算法具有較小的最大完成時間，每組按照Max-Min算法執(zhí)行。該算法首先分配具有優(yōu)先權的任務，把任務分配到執(zhí)行時間最快的機器上；對于無優(yōu)先權的任務，計算每個任務在網(wǎng)格系統(tǒng)中的計算機上的平均預期執(zhí)行時間，然后根據(jù)這個平均值對要調度的