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

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

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

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