一個(gè)網(wǎng)格服務(wù)工作流的動(dòng)態(tài)調(diào)度算法

（1.蘇州大學(xué) 計(jì)算機(jī)學(xué)院，江蘇 蘇州 215006； 2.江蘇省計(jì)算機(jī)信息處理技術(shù)重點(diǎn)實(shí)驗(yàn)室，江蘇 蘇州 215006）



摘要：針對(duì)服務(wù)網(wǎng)格環(huán)境中資源的動(dòng)態(tài)性，提出了一種并行調(diào)度算法PGSWA（parallel grid service workflow scheduling），該算法引入了性能預(yù)測模型和并行就緒隊(duì)列來預(yù)測下一段時(shí)間資源的性能并使得成員服務(wù)能夠并行執(zhí)行。實(shí)驗(yàn)證明，該算法能較好地縮短工作流的執(zhí)行時(shí)間，提高工作流的執(zhí)行性能。

關(guān)鍵詞：網(wǎng)格服務(wù)工作流； 動(dòng)態(tài)調(diào)度； 性能預(yù)測模型； 并行隊(duì)列

中圖分類號(hào)：TP3016文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695(2008)11-3285-03



Dynamic scheduling algorithm for grid service workflow



LI Chao1，2， ZHU Qiao-ming1， LI Pei-feng1，2， MA Feng-ming1，2



(1.School of Computer Science Technology， Soochow University， Suzhou Jiangsu 215006， China； 2.Key Laboratory of Computer Information Processing Technology of Jiangsu Province， Suzhou Jiangsu 215006， China)



Abstract:Considering the dynamics of resources in the service-oriented grid environment， this paper proposed a novel sche-duling algorithm PGSWA(parallel grid service workflow scheduling) to solve such problem. The algorithm introduced the performance prediction model and parallel ready queue into the scheduling to predict the resource performance and run services in parallel. The experiment results show that it can reduce the executing time of workflow， and improve its performance.

Key words：grid service workflow; dynamic scheduling; performance prediction model; parallel queue



在服務(wù)網(wǎng)格環(huán)境中，所有的資源包括計(jì)算、通信和存儲(chǔ)等都是以服務(wù)的形式存在。同時(shí)，工作流作為實(shí)現(xiàn)網(wǎng)格中資源協(xié)同工作的一項(xiàng)重要技術(shù)手段，將網(wǎng)格中的多個(gè)服務(wù)包裝成一個(gè)更大粒度的服務(wù)部署在網(wǎng)格中，供其他服務(wù)或上層的應(yīng)用訪問，來解決復(fù)雜的科學(xué)和商業(yè)應(yīng)用。

網(wǎng)格服務(wù)工作流可以看成是一組成員服務(wù)的集合，服務(wù)之間存在著時(shí)序或因果的約束條件，并最終完成一個(gè)特定的目標(biāo)。它與傳統(tǒng)的工作流之間具有很大的差別，如基于虛擬組織的工作方式；網(wǎng)格資源的動(dòng)態(tài)性導(dǎo)致網(wǎng)格的計(jì)算和處理能力隨時(shí)間變化，應(yīng)用性能估計(jì)困難；資源異構(gòu)以及跨管理域等。

調(diào)度是網(wǎng)格工作流中重要的課題，并且網(wǎng)格工作流調(diào)度不同于一般的任務(wù)調(diào)度，在調(diào)度時(shí)不僅要考慮為任務(wù)選擇一個(gè)最佳的資源，還要考慮各個(gè)任務(wù)之間的時(shí)序或因果的約束條件，以及協(xié)調(diào)各個(gè)任務(wù)的執(zhí)行來獲取最終的執(zhí)行結(jié)果^[1]。

本文提出了一種新的網(wǎng)格服務(wù)工作流調(diào)度算法。算法引入了性能預(yù)測模型能夠較好地預(yù)測下一段時(shí)間資源的性能；引入了就緒隊(duì)列和并行就緒隊(duì)列來提高任務(wù)執(zhí)行之間的并行性；考慮資源可靠性，一定程度上保證了工作流的順利執(zhí)行。

1相關(guān)工作

在已有的網(wǎng)格資源調(diào)度算法中，主要側(cè)重于解決網(wǎng)格作業(yè)與網(wǎng)格資源間的調(diào)度問題。文獻(xiàn)[2]提出了一種基于經(jīng)濟(jì)學(xué)模型的優(yōu)化調(diào)度模型，其目的是在資源提供者和使用者間建立交易，以盡可能低的費(fèi)用滿足資源使用者進(jìn)行計(jì)算任務(wù)的最低要求；文獻(xiàn)[3]采用了一種基于Class Ad匹配的集中式方案，以形成資源調(diào)度器；文獻(xiàn)[4]提供了一個(gè)高度結(jié)構(gòu)化的可擴(kuò)展的調(diào)度方案。但是這些調(diào)度方案未能從網(wǎng)格服務(wù)的角度考慮網(wǎng)格服務(wù)工作流的調(diào)度。

文獻(xiàn)[5，6]提出了一種基于遺傳算法的網(wǎng)格服務(wù)工作流調(diào)度算法，從不同側(cè)面改進(jìn)了遺傳算法，克服了傳統(tǒng)遺傳算法收斂性差和早熟收斂的缺陷，提高了資源選擇的效率。但是卻沒有考慮服務(wù)網(wǎng)格環(huán)境中資源的動(dòng)態(tài)性和可靠性，而且沒有考慮任務(wù)之間的并行性。文獻(xiàn)[7]通過對(duì)網(wǎng)格工作流中應(yīng)用程序優(yōu)先級(jí)進(jìn)行定義，可以使用優(yōu)先級(jí)調(diào)度算法來保證優(yōu)先級(jí)較高的網(wǎng)格工作流應(yīng)用程序能夠被優(yōu)先調(diào)度和運(yùn)行，但它也同樣沒有考慮到任務(wù)之間的并行執(zhí)行，導(dǎo)致執(zhí)行效率比較低。

通過具體的實(shí)驗(yàn)和模擬實(shí)驗(yàn)驗(yàn)證，本文提出的調(diào)度算法能夠有效地預(yù)測資源節(jié)點(diǎn)的性能，協(xié)助調(diào)度器獲得合理的調(diào)度方案；通過引入關(guān)鍵網(wǎng)格服務(wù)和并行就緒隊(duì)列提高了成員服務(wù)之間執(zhí)行的并行性，縮短了工作流的執(zhí)行時(shí)間，提高了工作流的執(zhí)行性能。

2網(wǎng)格服務(wù)工作流調(diào)度模型

21工作流執(zhí)行模型

工作流系統(tǒng)的核心部件是工作流引擎。它首先解析工作流描述文件，根據(jù)抽象的工作流定義，獲取包含的成員服務(wù)及成員服務(wù)之間的依賴關(guān)系，這些依賴關(guān)系不僅包括數(shù)據(jù)傳輸依賴，還包括控制依賴。

獲取了所需的成員服務(wù)和依賴關(guān)系之后，系統(tǒng)就會(huì)將滿足執(zhí)行約束的任務(wù)放到就緒隊(duì)列中，等待系統(tǒng)調(diào)度器為其選擇一個(gè)服務(wù)資源并執(zhí)行。工作流執(zhí)行模型如圖1所示。

從圖1可以看出，工作流執(zhí)行模型由有向無環(huán)圖（directed acyclic graphs，DAG）管理器和調(diào)度器組成。DAG管理器主要負(fù)責(zé)監(jiān)視任務(wù)的執(zhí)行，基于任務(wù)之間的事件及依賴關(guān)系來動(dòng)態(tài)更新就緒隊(duì)列。調(diào)度器主要為就緒隊(duì)列中的任務(wù)選擇一個(gè)最佳的服務(wù)資源，并且傳送控制信息和數(shù)據(jù)信息到服務(wù)資源所在的節(jié)點(diǎn)，并驅(qū)動(dòng)服務(wù)的執(zhí)行。

22網(wǎng)格服務(wù)工作流動(dòng)態(tài)調(diào)度模型

網(wǎng)格調(diào)度作為網(wǎng)格資源與網(wǎng)格用戶之間的橋梁，是網(wǎng)格資源管理系統(tǒng)的重要組成部分。網(wǎng)格調(diào)度系統(tǒng)一方面收集大量的可用的資源信息；另一方面根據(jù)用戶的性能需求將合適的資源分配給應(yīng)用。根據(jù)GGF網(wǎng)格調(diào)度研究小組，網(wǎng)格調(diào)度器負(fù)責(zé)：a)發(fā)現(xiàn)應(yīng)用的可用資源；b)選擇合適的資源；c)執(zhí)行作業(yè)。簡而言之，網(wǎng)格調(diào)度是由排序和映射組成，排序是根據(jù)網(wǎng)格應(yīng)用的優(yōu)先級(jí)決定網(wǎng)格作業(yè)執(zhí)行的順序，映射是一個(gè)選擇合適資源并將其分配給應(yīng)用的過程，為獲得最佳的應(yīng)用執(zhí)行性能，每次映射之前都應(yīng)該進(jìn)行性能評(píng)估。

221服務(wù)節(jié)點(diǎn)性能的預(yù)測模型

從GIS（grid information services）上獲取每個(gè)節(jié)點(diǎn)的服務(wù)資源列表，并采用每隔一段時(shí)間重新獲取的方式來保證每次都能夠較為準(zhǔn)確地獲取資源信息。

節(jié)點(diǎn)的性能是動(dòng)態(tài)變化的，通過綜合考慮CPU、CPU負(fù)載、內(nèi)存、網(wǎng)絡(luò)負(fù)載以及節(jié)點(diǎn)上等待隊(duì)列的長度這些因素來考查一個(gè)節(jié)點(diǎn)的性能。通過大量的實(shí)驗(yàn)，并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行回歸統(tǒng)計(jì)處理，得出了用來預(yù)測某個(gè)節(jié)點(diǎn)性能的預(yù)測模型。

Mp(ni)=α×ni_cload-β×ni_nload-δ×ni_c-γ×ni_m+η×ni_tnum+ε(1)

其中：α、β、δ、γ、η是性能因子，分別代表了CPU負(fù)載、網(wǎng)絡(luò)負(fù)載、CPU、內(nèi)存及節(jié)點(diǎn)上等待隊(duì)列長度影響節(jié)點(diǎn)性能所占的比重；ε為隨機(jī)誤差，均值為零的正態(tài)分布隨機(jī)變量；ni表示第i個(gè)資源節(jié)點(diǎn)，且1≤i≤n；n為所有節(jié)點(diǎn)的數(shù)目。

采用的數(shù)學(xué)模型是嶺回歸統(tǒng)計(jì)，嶺統(tǒng)計(jì)是一種理論上有較大影響并得以廣泛應(yīng)用的估計(jì)方法。對(duì)于線性回歸模型，回歸系數(shù)b的嶺估計(jì)定義為

b∧(k)=(XTX+kI)-1XTy(2)

用b的嶺統(tǒng)計(jì)建立的回歸方程稱為嶺回歸方程。其中k＞0稱為嶺系數(shù)。式(1）中的矩陣X和y都經(jīng)過中心化和標(biāo)準(zhǔn)化交換。嶺估計(jì)隨k（峰系數(shù)）值改變而改變，若記b∧i(k)為b∧(k)的第i個(gè)分量，當(dāng)k在[0，+∞)上變化時(shí)，b∧(k)的圖像稱為嶺跡。

選擇k值的嶺跡法是：將b∧1(k)，b∧2(k)，…，b∧m(k)的嶺跡畫在同一個(gè)圖上，根據(jù)嶺跡的變化趨勢選擇k值，使得各個(gè)回歸系數(shù)的嶺估計(jì)大體上穩(wěn)定，并且各個(gè)回歸嶺系數(shù)估計(jì)的符號(hào)比較合理。

通過在MATLAB中進(jìn)行回歸，發(fā)現(xiàn)在k取0.6時(shí)，各個(gè)回歸系數(shù)的嶺估計(jì)比較穩(wěn)定，因此將k設(shè)為0.6。

為了驗(yàn)證一個(gè)預(yù)測模型是否合理，是否可以進(jìn)行較為準(zhǔn)確的預(yù)測。要對(duì)其進(jìn)行檢驗(yàn)，最常用的方法是顯著性檢驗(yàn)，也稱F檢驗(yàn)。其中統(tǒng)計(jì)量計(jì)算公式如下：

F=[∑ni=1(i-y)2]/[m∑ni=1(yi-i)2/(n-m-1)](3)

在給定的顯著性水平α下，把計(jì)算出的F分布表中查得的自由度為(m，n-m-1)的Fα值相比，若F≥Fα，則可以認(rèn)為因變量y與自變量x1，x2，…，xm間線性相關(guān)關(guān)系是顯著的，所建回歸預(yù)測模型有效可用。

根據(jù)實(shí)驗(yàn)數(shù)據(jù)和式（1）（2），計(jì)算得出F的值為5.553 6。在α取0.95時(shí)，F(xiàn)0.95(6，425-6-1)=2.120 3，滿足F≥Fα，證明預(yù)測模型是有效的。

獲取了節(jié)點(diǎn)的性能值，就可根據(jù)各個(gè)節(jié)點(diǎn)的性能值生成一個(gè)按性能值非遞減排列的資源列表。

222資源的可靠性定義

利用Re(ni)代表資源節(jié)點(diǎn)ni的可靠性，只有當(dāng)資源的可靠性達(dá)到一定標(biāo)準(zhǔn)時(shí)才會(huì)有可能成為候選資源，表示為在該資源上能成功運(yùn)行某服務(wù)的概率。因此對(duì)于用戶而言，體現(xiàn)了資源安全可靠執(zhí)行服務(wù)的概率。采用式(4)計(jì)算：

Re(ni)=α×succsin-1+β×1/(n-1)∑n-1k=1succsik(4)

其中：succsik=1ni上si運(yùn)行成功0ni上si運(yùn)行失敗

表示了在資源ni上運(yùn)行服務(wù)si是否成功，α、β是權(quán)重因子且α+β=1，分別代表了最近一次執(zhí)行情況和歷史執(zhí)行情況所占的比重。

同樣，利用Re(si)來代表服務(wù)資源si的可靠性，其計(jì)算式為

Re(si)=×succsin-1+β×1/(n-1)∑n-1k=1succsik（5）

其中:succsik=1si執(zhí)行成功0si執(zhí)行失敗代表了si是否執(zhí)行成功。有了每個(gè)si的可靠性約束，調(diào)度器在選擇資源時(shí)就可以根據(jù)Re(si)的大小來篩選服務(wù)資源。

223服務(wù)估計(jì)執(zhí)行時(shí)間的定義

Test(si，ni)用來表示服務(wù)si在節(jié)點(diǎn)ni上的估計(jì)執(zhí)行時(shí)間，計(jì)算式為

Tnest(si，ni)=λTn-1est(si，ni)+(1-λ)[Tn-1exc(si，ni)+βn-1](6)

βn=1/(n-1)(∑nk=1Tkexc(si，ni)-(∑nk=1Tkexc(si，ni))2/n)（7）

λ=Texc/Test(Test＞2Texc)

1-Texc/Test(Texc＜Test≤T2Texc)

Test/Texc(Test≤Texc)（8）

其中：Tnest(si，ni)表示si在資源ni上第n次執(zhí)行時(shí)的估計(jì)執(zhí)行時(shí)間，βn是標(biāo)準(zhǔn)方差，反映了在該資源上執(zhí)行該服務(wù)實(shí)例的歷史變動(dòng)情況。λTn-1est(si，ni)代表了前一次的估計(jì)執(zhí)行時(shí)間對(duì)當(dāng)前執(zhí)行時(shí)間的影響，(1-λ)[Tn-1exc(si，ni)+βn-1]則代表了歷史執(zhí)行情況對(duì)當(dāng)前執(zhí)行時(shí)間估計(jì)的影響。λ是根據(jù)最近一次的估計(jì)時(shí)間和執(zhí)行時(shí)間動(dòng)態(tài)確定的，用于控制這兩部分對(duì)目前時(shí)間估計(jì)的影響力，并且λ的取值是動(dòng)態(tài)確定的，更加適應(yīng)了網(wǎng)格環(huán)境的動(dòng)態(tài)性。

23就緒隊(duì)列和并行就緒隊(duì)列

就緒隊(duì)列中的任務(wù)是可以執(zhí)行的活動(dòng)。在工作流執(zhí)行時(shí)，工作流中的活動(dòng)單元（即處于就緒狀態(tài)的成員服務(wù)）可能被分成n個(gè)就緒隊(duì)列，筆者用{RL1，RL2，…，RLn}代表執(zhí)行時(shí)的n個(gè)就緒隊(duì)列。n的大小和每個(gè)就緒隊(duì)列中的活動(dòng)單元是在運(yùn)行時(shí)確定的。每個(gè)就緒隊(duì)列中活動(dòng)單元之間是獨(dú)立的，并可以并行執(zhí)行，不同就緒隊(duì)列中的活動(dòng)單元根據(jù)約束條件可能并行或串行執(zhí)行，如圖2所示。

如圖2所示，RLi和RLj只能串行的執(zhí)行，因?yàn)橹挥蠷Li和RLj存在著序列約束。如果A3能夠在A2之前執(zhí)行完，則RLj和RLk可以部分并行執(zhí)行。

工作流開始執(zhí)行的時(shí)間用Ts表示，結(jié)束時(shí)間用Te表示。分析可知，工作流的執(zhí)行時(shí)間取決于就緒隊(duì)列的執(zhí)行和就緒隊(duì)列之間的并行度。并行度越高，則執(zhí)行效率越高。為了定義并行就緒隊(duì)列，首先引入關(guān)鍵成員服務(wù)CGS（critical grid ser-vice）。

231關(guān)鍵服務(wù)成員的定義

假設(shè)L代表RLk的長度，假設(shè)Si，k表示就緒隊(duì)列RLk中Si服務(wù)，若滿足如下性質(zhì)，則將其定義為關(guān)鍵網(wǎng)格服務(wù)CGS。

TCGS=max{Tsi，kest｜1≤k≤L}。其中Tsi，kest是RLk中si的估計(jì)執(zhí)行時(shí)間。

由上可知，CGS的執(zhí)行時(shí)間的快慢決定了所在就緒隊(duì)列RLk的執(zhí)行時(shí)間的快慢，在一定意義上也就決定了整個(gè)工作流的執(zhí)行時(shí)間快慢。

232并行就緒隊(duì)列的定義

通過定義并行就緒隊(duì)列，就可以確定哪些就緒隊(duì)列可以并行執(zhí)行，從而提高工作流任務(wù)的執(zhí)行效率，縮短工作流的執(zhí)行時(shí)間。

引入隊(duì)列的開始執(zhí)行時(shí)間TRLksta和執(zhí)行結(jié)束時(shí)間TRLkend，定義如下：

TRLkend=TRLksta+TCGS(9)

對(duì)開始時(shí)間和結(jié)束時(shí)間進(jìn)行了粗略的計(jì)算。其中TCGS表示關(guān)鍵服務(wù)的估計(jì)執(zhí)行時(shí)間，利用式（6）計(jì)算獲得。

如果RLi和RLj滿足下式，則表明兩個(gè)就緒隊(duì)列是可以并行執(zhí)行的。

(TRLjsta≤TRLista＜TRLjend)∨(TRLjsta＜TRLiend≤TRLjend)∨

(TRLista≤TRLjsta＜TRLiend)∨(TRLista＜TRLjend≤TRLiend)

（10）

24算法實(shí)現(xiàn)

根據(jù)上述的分析和定義，針對(duì)服務(wù)工作流調(diào)度問題，提出并行調(diào)度算法——PGSWA（parallel grid service workflow sche-duling）算法。該算法描述如下：

輸入：工作流應(yīng)用{A1，A2，…，An}，資源節(jié)點(diǎn)可靠性閾值NC，服務(wù)資源可靠性閾值SC；

輸出：成員服務(wù)與服務(wù)資源間的映射關(guān)系；

a）獲取就緒隊(duì)列{RL1，RL2，…，RLn}，并獲取每個(gè)隊(duì)列的關(guān)鍵任務(wù)；

b）通過式（11）計(jì)算來獲取并行隊(duì)列；

c）根據(jù)系統(tǒng)設(shè)定的NC來篩選篩選資源節(jié)點(diǎn)；

d）通過預(yù)測模型獲取可用資源節(jié)點(diǎn)的性能值；

e）根據(jù)需求考慮就緒隊(duì)列中成員服務(wù)的時(shí)間和成本約束，根據(jù)設(shè)定的SC，為處于就緒狀態(tài)的成員服務(wù)分配最佳的可用的服務(wù)資源。

3實(shí)驗(yàn)驗(yàn)證

在已有的網(wǎng)格調(diào)度算法中，最短作業(yè)最快資源（SJFR）^[8]和最長作業(yè)最快資源（LJFR）^[8]是兩種常用算法，前者可以獲得較短的總體作業(yè)執(zhí)行時(shí)間，但會(huì)導(dǎo)致長作業(yè)執(zhí)行時(shí)間很長；而后者雖然避免了長作業(yè)餓死，但作業(yè)執(zhí)行的總體時(shí)間也比較長。

為了驗(yàn)證PGSWA算法的性能，提交的工作流由1～20個(gè)成員服務(wù)組成，每次實(shí)驗(yàn)時(shí)提交5～10個(gè)工作流，記錄每種情況下工作流的平均執(zhí)行時(shí)間。實(shí)驗(yàn)環(huán)境為：一個(gè)主機(jī)作為調(diào)度節(jié)點(diǎn)，八個(gè)性能不同的主機(jī)作為資源節(jié)點(diǎn)，并且每個(gè)節(jié)點(diǎn)上都部署了分詞服務(wù)、人名識(shí)別服務(wù)、地名識(shí)別服務(wù)、機(jī)構(gòu)名識(shí)別服務(wù)和詞性標(biāo)注服務(wù)。實(shí)驗(yàn)結(jié)果如圖3所示。

實(shí)驗(yàn)表明，基于PGSWA算法的工作流的執(zhí)行時(shí)間低于SJFR算法和LJFR算法產(chǎn)生的執(zhí)行時(shí)間。當(dāng)工作流包含的成員服務(wù)較少時(shí)，三種算法的執(zhí)行時(shí)間相差不大，這主要是因?yàn)樘幱诰途w狀態(tài)的任務(wù)較少，任務(wù)區(qū)分度較小。隨著成員服務(wù)數(shù)量的增加，PGSWA由于考慮了任務(wù)之間的并行執(zhí)行，能獲得較好的執(zhí)行性能。

此外，為了驗(yàn)證調(diào)度算法的性能，通過在GridSim中進(jìn)行模擬實(shí)驗(yàn)與FCFS、LJFR、SJFR調(diào)度算法進(jìn)行了比較，并設(shè)置了五種不同的工作流結(jié)構(gòu)，每種工作流由5～50個(gè)成員服務(wù)組成。在實(shí)驗(yàn)中設(shè)定了10個(gè)資源節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)包含一樣的服務(wù)資源列表。兩種調(diào)度算法的實(shí)驗(yàn)結(jié)果如圖4所示。

由圖4可知，在模擬環(huán)境中，PGSWA算法表現(xiàn)出較好的性能，執(zhí)行時(shí)間均小于FCFS、LJFR和SJFR算法下的平均執(zhí)行時(shí)間。工作流的成員服務(wù)數(shù)量比較少的情況下，幾種算法下工作流的執(zhí)行時(shí)間相差不大；當(dāng)成員服務(wù)的數(shù)量超過30時(shí)，執(zhí)行時(shí)間出現(xiàn)了較大的區(qū)別，主要是由于PGSWA算法考慮了服務(wù)就緒隊(duì)列中服務(wù)之間執(zhí)行的并行性，使得滿足條件的服務(wù)能夠并行的執(zhí)行，從而提高了執(zhí)行效率。

4結(jié)束語

針對(duì)服務(wù)網(wǎng)格環(huán)境下的網(wǎng)格工作流調(diào)度，本文提出了一種新型的工作流調(diào)度模型，通過引入性能預(yù)測模型，較好地預(yù)測資源的性能；通過引入并行就緒隊(duì)列，提高了任務(wù)之間的并行執(zhí)行。通過實(shí)驗(yàn)驗(yàn)證，該調(diào)度模型能夠較好地縮短工作流的執(zhí)行時(shí)間，保證工作流的順利執(zhí)行。但該調(diào)度方法僅僅考慮了資源的性能和可靠性，沒有考慮用戶的QoS^[9]以及系統(tǒng)多層次的QoS；而且調(diào)度方法中還沒有提出一種較好的容錯(cuò)機(jī)制來保障工作流的安全執(zhí)行。這些將是下一步研究的重點(diǎn)和難點(diǎn)問題。

參考文獻(xiàn)：

［1］ZHU Qiao-ming， LI Pei-feng， GONG Zheng-xian，et al. ADJSA: An adaptable dynamic job scheduling approach based on historical information[C]//Proc of the 2nd International Conference on Scalable Information Systems. 2007:201-207.

[2]BUYYA R， ABRAMSON D， GIDDY J. An economy driven resource management architecture for a global computational power grid[C]//Proc of Int’l Conf on Parallel and Distributed Processing Techniques and Applications. 2000:259-264.

[3]FREY J， TANNENBAUM T， FOSTER I，et al. Condor-G: a computation management agent for multi-institutional grids[J].Cluster Computing，2002，5(3):237-246.

[4]CHAPIN S， KARPOVICH J， GRMSHAW A. The Legion resource mana-gement system[C]//Proc of the 5th Workshop on Job Scheduling Strategies for Parallel Processing. 2000:123-128.

[5]DONG Fang-peng， SELIM G. An adaptive double-layer workflow scheduling approach for grid computing[C]//Proc of the 21st International Symposium on High Performance Computing Systems and Applications. Washington DC:IEEE Computer Society， 2007:156-163.

[6]TRETOLA G，ZIMEO E.Activity pre-scheduling in grid workflows[C]//Proc of the 15th Euromicro International Conference on Parallel，Distributed and Network-based Processing. Washington DC:IEEE Computer Society， 2007:245-253.

[7]劉洋，桂小林，徐玉文. 網(wǎng)格工作流中基于優(yōu)先級(jí)的調(diào)度方法研究[J].西安交通大學(xué)學(xué)報(bào)， 2006，40(4):411-414.

[8]ABRAHAM A， BUYYA R. Nature’s heuristics for scheduling jobs on computational grids[C]//Proc ofthe 8th Int’l Conf on Advanced Computing and Communication. 2000:301-308.

[9]YUAN Ying-chun， LI Xiao-ping， WANG Qian. Dynamic heuristics for time and cost reduction in grid workflows[M].Berlin:Springer-Verlag， 2007:499-508.

[10]郭文彩，楊揚(yáng). 基于遺傳算法的網(wǎng)格服務(wù)工作流調(diào)度的研究[J].計(jì)算機(jī)應(yīng)用， 2006，26(1):54-56.

[11]王勇，胡春明，杜宗霞. 服務(wù)質(zhì)量感知的網(wǎng)格工作流調(diào)度[J].軟件學(xué)報(bào)， 2006，17(11):2341-2351.