基于時(shí)間和費(fèi)用約束的網(wǎng)格任務(wù)調(diào)度算法研究及仿真.pdf

1、網(wǎng)格計(jì)算是繼Internet和Web之后最重要的信息技術(shù)，并且也是隨著Internet技術(shù)迅速發(fā)展起來(lái)的。集群(Cluster)、P2P(Peer-to-Peer)和網(wǎng)格是下一代并行和分布式計(jì)算的一種流行模式，其中集群和P2P中的資源是同構(gòu)的，并且大多數(shù)采用集中控制，他們的資源是很容易管理的，任務(wù)計(jì)算也是容易調(diào)度的。但是，隨著科技的發(fā)展，科學(xué)、工程和商業(yè)領(lǐng)域中大規(guī)模性的計(jì)算問(wèn)題的出現(xiàn)，使得單一的環(huán)境(P2P)、單一的技術(shù)(集群計(jì)算)變得

2、力不從心，必須尋求一種價(jià)格低廉、處理能力超強(qiáng)的高性能計(jì)算環(huán)境，網(wǎng)格計(jì)算就是這樣應(yīng)運(yùn)而生的。 網(wǎng)格是一個(gè)異構(gòu)的、分布式的、動(dòng)態(tài)的和多管理性領(lǐng)域的環(huán)境。在這樣一個(gè)環(huán)境中進(jìn)行資源管理，并且充分利用這些資源進(jìn)行任務(wù)計(jì)算，即網(wǎng)格任務(wù)調(diào)度，都是目前網(wǎng)格計(jì)算中比較熱門的研究方向。一般來(lái)說(shuō)，提交到網(wǎng)格中的任務(wù)都有一定的QoS(Quality of Service)約束條件，網(wǎng)格任務(wù)調(diào)度的核心問(wèn)題就是設(shè)計(jì)合適的調(diào)度算法去滿足網(wǎng)格任務(wù)的QoS約束條

3、件。 本文主要研究了時(shí)間和費(fèi)用兩種QoS約束條件，并提出了一種保障任務(wù)完成的最優(yōu)調(diào)度算法，該調(diào)度算法既能優(yōu)化網(wǎng)格任務(wù)執(zhí)行代價(jià)(時(shí)間和費(fèi)用)，又能保障網(wǎng)格任務(wù)完成。主要的研究工作以及創(chuàng)新性體現(xiàn)在以下幾個(gè)方面： 1) 通過(guò)模擬市場(chǎng)經(jīng)濟(jì)下的商品價(jià)值規(guī)律，提出了一個(gè)考慮子任務(wù)重要性和時(shí)間緊迫性的調(diào)度算法模型，該調(diào)度模型通過(guò)模擬市場(chǎng)經(jīng)濟(jì)下的商品價(jià)值規(guī)律，根據(jù)網(wǎng)格子任務(wù)的特點(diǎn)(重要性和時(shí)間緊迫性)有針對(duì)性的選擇資源，使得選擇的資源能

4、夠完成用戶任務(wù)。 2) 建立了一個(gè)網(wǎng)格任務(wù)調(diào)度的性能模型。該模型使任務(wù)和資源之間一一映射，并且能夠找到其最佳映射方式，使得任務(wù)處理代價(jià)最優(yōu)。 3) 改進(jìn)了一種網(wǎng)格任務(wù)代理和資源代理之間的議價(jià)算法。該改進(jìn)算法是基于決策和對(duì)策理論，通過(guò)將雙方的決策贏得函數(shù)構(gòu)造成一個(gè)零和矩陣，求其穩(wěn)定解或次穩(wěn)定解。在該解下，雙方的贏得較大而損失較小，從而達(dá)到一個(gè)平衡狀態(tài)。這種議價(jià)算法適用于大多數(shù)網(wǎng)格任務(wù)調(diào)度中的議價(jià)過(guò)程。 4) 設(shè)計(jì)了

5、一種具有保障性的時(shí)間和費(fèi)用約束的網(wǎng)格任務(wù)調(diào)度算法(DBOG)。該調(diào)度算法是建立在網(wǎng)格任務(wù)和網(wǎng)格資源之間一一映射的基礎(chǔ)上，通過(guò)代理選擇具有一定條件的資源，保障網(wǎng)格任務(wù)完成。并且該算法符合本文提出的網(wǎng)格任務(wù)調(diào)度的性能模型條件，因此它在時(shí)間和費(fèi)用上最優(yōu)。將DBOG調(diào)度算法在GridSim仿真工具上進(jìn)行了仿真研究，從實(shí)驗(yàn)研究的角度驗(yàn)證了該算法理論的正確性和可行性；并將該調(diào)度算法執(zhí)行的結(jié)果與其他的調(diào)度算法進(jìn)行了比較，結(jié)果表明該算法不但在時(shí)間和預(yù)算