面向網(wǎng)格工作流的松弛預(yù)留策略

肖鵬，胡志剛，閻朝坤，屈喜龍

（1. 湖南工程學(xué)院 計(jì)算機(jī)與通信系，湖南 湘潭 411104；2. 中南大學(xué) 信息科學(xué)與工程學(xué)院，湖南 長(zhǎng)沙 410083）

1 引言

網(wǎng)格環(huán)境[1]中的預(yù)留服務(wù)主要用于保證資源分配時(shí)刻的可獲得性，從而為資源協(xié)同分配提供QoS保證[2]。近期網(wǎng)格性能測(cè)評(píng)報(bào)告顯示，過(guò)度使用預(yù)留機(jī)制會(huì)對(duì)性能造成嚴(yán)重負(fù)面影響，例如資源有效利用率下降[2～4]、系統(tǒng)負(fù)載不均衡[5,6]、服務(wù)請(qǐng)求拒絕率升高[7,8]、調(diào)度性能低下[9]。解決預(yù)留機(jī)制的負(fù)面影響成為改進(jìn)網(wǎng)格系統(tǒng)性能的一個(gè)重要的課題。由于資源異構(gòu)性和負(fù)載動(dòng)態(tài)性，任務(wù)難以準(zhǔn)確估計(jì)其預(yù)留數(shù)量和時(shí)間，導(dǎo)致的結(jié)果是：①任務(wù)傾向于高估其預(yù)留時(shí)間，以此確保足夠的時(shí)間彈性[3,7,8]；②任務(wù)傾向重復(fù)提交預(yù)留請(qǐng)求，以此降低資源故障對(duì)任務(wù)執(zhí)行的影響[2,3,10]。Dun等人[11]對(duì)大量工作流的性能測(cè)評(píng)顯示，任務(wù)實(shí)際執(zhí)行效率往往因?yàn)椴粶?zhǔn)確的預(yù)留估計(jì)而極不確定；Prodan等人[12]在分析導(dǎo)致工作流延遲的因素時(shí)發(fā)現(xiàn)，預(yù)留協(xié)商延遲是影響工作流執(zhí)行效率的關(guān)鍵因素。基于預(yù)留機(jī)制存在的問(wèn)題，本文提出一種支持時(shí)空二維松弛的預(yù)留策略，允許系統(tǒng)在一定條件下接納存在疊交的預(yù)留請(qǐng)求，目標(biāo)是降低傳統(tǒng)預(yù)留機(jī)制對(duì)系統(tǒng)性能的負(fù)面影響。

2 相關(guān)研究

Smith等人[2]從等待時(shí)間、預(yù)留延遲、拒絕率等方面分析了預(yù)留機(jī)制對(duì)任務(wù)調(diào)度的影響，其實(shí)驗(yàn)數(shù)據(jù)顯示：預(yù)留機(jī)制能有效降低任務(wù)平均等待時(shí)間，但面對(duì)較高的預(yù)留請(qǐng)求率時(shí)，以上性能指標(biāo)都會(huì)顯著惡化。為降低預(yù)留機(jī)制對(duì)資源利用率的負(fù)面影響，回填技術(shù)[6]被廣泛應(yīng)用，例如文獻(xiàn)[3]中提出了基于回填技術(shù)的多資源協(xié)同預(yù)留算法，其實(shí)驗(yàn)數(shù)據(jù)顯示，回填技術(shù)能有效減輕預(yù)留機(jī)制給系統(tǒng)性能帶來(lái)的負(fù)面影響；Sulistio等人[4]則針對(duì)用戶頻繁取消預(yù)留請(qǐng)求的問(wèn)題提出一種超額預(yù)留機(jī)制，以此降低頻繁取消預(yù)留請(qǐng)求所導(dǎo)致的資源效率損失。

傳統(tǒng)預(yù)留機(jī)制的另一個(gè)主要缺陷是容易產(chǎn)生大量“資源能力碎片”。針對(duì)這一問(wèn)題，胡春明等人[13]提出一種基于彈性時(shí)間的預(yù)留策略，通過(guò)引入時(shí)間彈性因子，以此提高資源調(diào)度的自主性和資源綜合利用率；Farooq等人[7]則提出一種“關(guān)鍵任務(wù)重調(diào)度”機(jī)制，用于降低關(guān)鍵路徑上的任務(wù)預(yù)留請(qǐng)求被拒絕的概率；Jawad等人[14]則提出了一種基于“動(dòng)態(tài)關(guān)鍵路徑”的協(xié)同預(yù)留機(jī)制，其核心思想是將通信關(guān)聯(lián)度強(qiáng)的父子節(jié)點(diǎn)聚合，從而重構(gòu)工作流的關(guān)鍵節(jié)點(diǎn)和路徑；與本文研究最為接近的是Sulistio等人在文獻(xiàn)[4]中提出“超額預(yù)留”機(jī)制，但該研究只給出“超額預(yù)留”的概念，而對(duì)其將導(dǎo)致的違約風(fēng)險(xiǎn)缺乏量化分析和解決策略。而本文則明確給出了量化分析松弛策略的預(yù)留違約風(fēng)險(xiǎn)的方法。

3 定義與問(wèn)題描述

設(shè)網(wǎng)格系統(tǒng)由N個(gè)資源站點(diǎn)組成，表示為集合{R1,R2,…,RN}；工作流表示為有向無(wú)環(huán)圖 G = ＜T,E＞，其中，T = [t1, t2, …, tn]為工作流的子任務(wù)集合，E = {＜ ti, tj＞|if ＜ ti, tj＞∈T×T}為工作流的有向邊集合；子任務(wù)ti的預(yù)留請(qǐng)求表示為三元組＜si,ei,ri＞，si為預(yù)留起始時(shí)間，ei為預(yù)留截止時(shí)間，ri為資源預(yù)留量；資源時(shí)間槽 Sk表示為三元組＜λk, μk, πk＞，λk為時(shí)間槽起始時(shí)間，μk為結(jié)束時(shí)間，πk為空閑資源量

定義 1 若 Sk對(duì) ti的預(yù)留請(qǐng)求＜si,ei,ri＞以概率Pk,i滿足(si≥λk)∩(ei≤μk) ∩ (fk≥ri)，則稱(chēng)時(shí)間槽 Sk松弛滿足ti的預(yù)留請(qǐng)求。

定義 2 與子任務(wù)ti的預(yù)留起始時(shí)間和截止時(shí)間疊交的預(yù)留請(qǐng)求集合記分別記為S-(ti)和S+(ti)：

定義3 設(shè)隨機(jī)事件Ei表示子任務(wù)ti沒(méi)有發(fā)生預(yù)留違約，隨機(jī)事件表示集合(ti)沒(méi)有導(dǎo)致 ti發(fā)生預(yù)留違約，隨機(jī)事件表示集合S+(ti)沒(méi)有導(dǎo)致ti發(fā)生預(yù)留違約。

圖1 資源預(yù)留時(shí)間槽示例

以圖1為例，當(dāng)ti的預(yù)留請(qǐng)求ri到達(dá)時(shí)，時(shí)間槽上已經(jīng)存在7個(gè)預(yù)留請(qǐng)求，按照傳統(tǒng)預(yù)留的定義，則不存在能滿足ri的空閑時(shí)間槽。(ti)={r2, r3, r4}且S+(ti)={r5, r7}，若其中的預(yù)留請(qǐng)求提前釋放資源，則ri實(shí)際并不會(huì)發(fā)生預(yù)留違約。由定義3可知， ti不發(fā)生預(yù)留違約的概率計(jì)算公式為

工作流G = ＜T, E＞的協(xié)同預(yù)留方案可以表示為從資源需求集合到資源站點(diǎn)集合的映射 M:{r1,r2,…, rn}× {R1,R2,…,RN}→{0,1}。顯然協(xié)同預(yù)留方案M為n×N矩陣，Mi,j=1表示在Cj上預(yù)留資源給子任務(wù) ti。綜合上述定義和分析，面向工作流的松弛預(yù)留策略可以歸結(jié)為以下優(yōu)化問(wèn)題：

其中，Pr{E|M}≥V*則表示協(xié)同預(yù)留方案M不發(fā)生預(yù)留違約的概率大于等于V*。V*為松弛預(yù)留閾值，其數(shù)值越大則表示松弛接納策略越保守，當(dāng) V*=1時(shí)松弛預(yù)留策略退化為傳統(tǒng)預(yù)留策略。由于預(yù)留方案 M 的解空間為 2n×N，上述優(yōu)化問(wèn)題顯然屬于NP-Complete。對(duì)此，第 4節(jié)的預(yù)留接納策略將采用進(jìn)化算法[15]來(lái)求取近似最優(yōu)解。

4 策略分析與求解

4.1 違約概率分析

由式(3)可知，工作流中子任務(wù)ti的預(yù)留違約概率由Pr{}和Pr{}合成。

其中，Tk為隨機(jī)變量表示子任務(wù)tk的實(shí)際完成時(shí)間，集合是(ti)子集中滿足如下條件的子集：

①若ti的資源預(yù)留量ri滿足

則 ti需要中所有預(yù)留請(qǐng)求都在 si之前完成，才能保證不發(fā)生預(yù)留違約，Pr{}的計(jì)算公式為

②若資源預(yù)留量ri滿足

綜合以上2種情況的分析可知，ti不出現(xiàn)預(yù)留違約的概率Pr{}具有嚴(yán)格的上界和下界，其計(jì)算式分別由式(8)和式(10)給出，證畢。

其中，rk的預(yù)留起始時(shí)間滿足以下條件

證明 若 ti的實(shí)際完成時(shí)間提前并釋放其資源，則S+(ti)中部分預(yù)留請(qǐng)求將不會(huì)產(chǎn)生預(yù)留違約。關(guān)鍵問(wèn)題是：ti的實(shí)際完成時(shí)間提前到何種程度才能保證 S+(ti)的預(yù)留請(qǐng)求都不會(huì)產(chǎn)生預(yù)留違約。為此，可以將S+(ti)中的預(yù)留請(qǐng)求按起始時(shí)間升序排列為＜r1,r2,…,rm＞，并從中找到一個(gè)滿足式(13)所示條件的rk。顯然，如果ti的實(shí)際完成時(shí)間早于rk，S+(ti)中預(yù)留請(qǐng)求＜r1,r2,…,rk＞都不會(huì)和ti的預(yù)留請(qǐng)求發(fā)生任何交疊；另一方面，ti提前釋放的資源能夠保證S+(ti)中＜rk+1,rk+2,…,rm＞都不發(fā)生會(huì)由于空閑資源不夠而導(dǎo)致的預(yù)留違約。綜上所述，得證。

4.2 預(yù)留接納算法

本文主要考慮網(wǎng)格工作流，由于子任務(wù)之間存在相互依賴(lài)關(guān)系，因此必須首先計(jì)算出子任務(wù)之間的關(guān)聯(lián)強(qiáng)度。本文采用了PMCC[17]公式來(lái)計(jì)算工作流子任務(wù)之間的關(guān)聯(lián)強(qiáng)度。工作流中任意兩子任務(wù)ti和tj(i ≠ j)之間的關(guān)聯(lián)強(qiáng)度計(jì)算公式如下：

其中，Ti和Tj為隨機(jī)變量，分別表示任務(wù)ti和tj的實(shí)際完成時(shí)間。針對(duì)網(wǎng)格工作流的基于松弛預(yù)留策略的協(xié)同預(yù)留接納算法實(shí)現(xiàn)如下所示。

End.

算法采用進(jìn)化策略來(lái)獲得調(diào)度長(zhǎng)度最優(yōu)化的協(xié)同預(yù)留方案。step 4 ～ step 15是采用松弛策略的分析結(jié)論來(lái)計(jì)算工作流中每個(gè)子任務(wù)不發(fā)生預(yù)留違約的概率，step 16則求取整個(gè)協(xié)同預(yù)留方案不出現(xiàn)預(yù)留違約的概率。算法的整體復(fù)雜度為O(Wn2N)，W為進(jìn)化迭代數(shù)目，n為工作流中的任務(wù)節(jié)點(diǎn)數(shù)，N為網(wǎng)格系統(tǒng)的資源站點(diǎn)數(shù)目。

5 實(shí)驗(yàn)與性能分析

實(shí)驗(yàn)構(gòu)建了一個(gè)異構(gòu)多集群計(jì)算網(wǎng)格，包括了12個(gè)高性能計(jì)算集群作為資源站點(diǎn)，各集群節(jié)點(diǎn)的性能指標(biāo)參考 DAS-2[18]的配置。實(shí)驗(yàn)首先以隨機(jī)DAG作為工作負(fù)載，然后采用 WIEN2K[19]工作流進(jìn)行實(shí)驗(yàn)分析。

5.1 隨機(jī)DAG實(shí)驗(yàn)分析

REXR是本文提出的松弛預(yù)留策略；CONR[2]為傳統(tǒng)的嚴(yán)格預(yù)留策略，主要作為實(shí)驗(yàn)分析的基線；CBFR[6]為保守回填預(yù)留策略；MALR[20]為可塑預(yù)留策略；OVBR[4]為超額預(yù)留策略。實(shí)驗(yàn)分5組進(jìn)行，預(yù)留請(qǐng)求率從 5%逐步增加到 25%。實(shí)驗(yàn)設(shè)定OVBR的超額接納率為20%，REXR的接納閾值 V*為 0.8。圖 2為不同預(yù)留請(qǐng)求率的資源平均利用率。實(shí)驗(yàn)數(shù)據(jù)顯示，當(dāng)預(yù)留請(qǐng)求率較低時(shí)(5%和10%)，CBFR、MALR、OVBR和REXR 4種策略的資源利用率差別很小，且相對(duì) CONR策略而言大約能提高 13%；當(dāng)預(yù)留請(qǐng)求率超過(guò)15%時(shí)，這 4種策略的性能表現(xiàn)出現(xiàn)明顯分化，其中OVBR策略的性能下降最為顯著，而CBFR策略和 MALR的性能差異只在預(yù)留請(qǐng)求率到達(dá)20%以上時(shí)才比較明顯。為了分析各種策略之間的性能差異，統(tǒng)計(jì)了各個(gè)資源站點(diǎn)的平均資源率，如圖3所示。

圖2 不同預(yù)留請(qǐng)求率下的資源平均利用率

圖3 各個(gè)資源站點(diǎn)的平均利用率

CONR策略偏向于將預(yù)留請(qǐng)求均衡地分配到各個(gè)站點(diǎn)，由于資源站點(diǎn)的靜態(tài)性能和動(dòng)態(tài)負(fù)載壓力差異很大，因此CONR策略在面對(duì)較高的預(yù)留請(qǐng)求率時(shí)其性能表現(xiàn)顯著惡化；CBFR和MALR則偏向于向靜態(tài)性能指標(biāo)較高的站點(diǎn)預(yù)留資源，因而導(dǎo)致這些站點(diǎn)面臨更高負(fù)載；OVBR在實(shí)現(xiàn)層面上類(lèi)似CONR，由于實(shí)驗(yàn)設(shè)定了20%的超額接納率，在預(yù)留請(qǐng)求率不高時(shí)，20%的超額預(yù)留沒(méi)有對(duì)系統(tǒng)造成任何負(fù)面影響，因此OVBR策略的表現(xiàn)是5種策略中最優(yōu)的，但隨著預(yù)留請(qǐng)求率的上升，OVBR不僅不能提高資源利用率，反而頻繁導(dǎo)致預(yù)留違約，從而使得有效資源利用率顯著下降。REXR策略的主要特點(diǎn)是隨預(yù)留請(qǐng)求率的增大而相對(duì)保持平穩(wěn)，例如當(dāng)預(yù)留請(qǐng)求率從5%增大到25%時(shí)，REXR只損失了約24%的資源利用率。

圖4為5種策略在拒絕率方面的性能比較。實(shí)驗(yàn)數(shù)據(jù)顯示：當(dāng)預(yù)留請(qǐng)求率較低時(shí)，5種策略的拒絕率差別不大，原因是為整個(gè)網(wǎng)格系統(tǒng)處于低負(fù)載狀態(tài)，此時(shí)預(yù)留機(jī)制的負(fù)面效果尚為突出；當(dāng)預(yù)留請(qǐng)求率升高時(shí)，CBFR的拒絕率增加最快，其次是CONR策略和MALR策略，而OVBR策略的拒絕率幾乎和REXR相同。OVBR策略和REXR策略的拒絕率相似的原因是兩者都放寬了預(yù)留接納的標(biāo)準(zhǔn)。為進(jìn)一步分析這2種策略在不同參數(shù)下的性能表現(xiàn)，用不同的參數(shù) V*和 O*重復(fù)本次實(shí)驗(yàn)，其中V*為 REXR策略的松弛接納閾值，而 O*為 OVBR的超額接納率，實(shí)驗(yàn)結(jié)果如圖5所示。

圖4 不同預(yù)留請(qǐng)求率下的預(yù)留請(qǐng)求拒絕率

圖5 不同參數(shù)下的預(yù)留違約率比較

實(shí)驗(yàn)結(jié)果顯示，OVBR在較低的預(yù)留請(qǐng)求率時(shí)幾乎沒(méi)有任何預(yù)留違約，而當(dāng)預(yù)留請(qǐng)求率達(dá)到并超過(guò)15%時(shí)，其預(yù)留違約率顯著增加。當(dāng)OVBR策略采用40%的超額預(yù)留率時(shí)，其違約率高達(dá)74%。即使預(yù)留請(qǐng)求率為20%，OVBR的違約率也高達(dá)55%相對(duì)而言，REXR的V*參數(shù)也會(huì)對(duì)其違約率產(chǎn)生一定影響，具體表現(xiàn)為：V*的值越小，違約率隨之增加得越快，但總體幅度明顯小于OVBR，而且只要V*值不小于0.8，其預(yù)留違約率就能控制在7%以內(nèi)。

REXR算法的時(shí)間開(kāi)銷(xiāo)由進(jìn)化策略的迭代參數(shù)W和任務(wù)規(guī)模決定，本次實(shí)驗(yàn)統(tǒng)計(jì)了REXR算法不同參數(shù)取值下的算法的平均執(zhí)行時(shí)間，實(shí)驗(yàn)結(jié)果如表1所示。任務(wù)規(guī)模對(duì)算法執(zhí)行效率的影響明顯大于參數(shù)W的影響。當(dāng)任務(wù)規(guī)模較小時(shí)，REXR算法收斂速度很快，此時(shí)的W參數(shù)幾乎不影響算法執(zhí)行效率；當(dāng)任務(wù)規(guī)模達(dá)到200以上時(shí)，進(jìn)化迭代參數(shù)至少要達(dá)到500以上，算法才能獲得有效收斂。

表1 不同參數(shù)下的算法執(zhí)行時(shí)間/s

綜合以上實(shí)驗(yàn)數(shù)據(jù)和分析，本次實(shí)驗(yàn)的主要結(jié)論是：①當(dāng)預(yù)留請(qǐng)求率低于10%時(shí)，CBFR策略和OVBR策略能有效提高資源利用率；②當(dāng)預(yù)留請(qǐng)求率大于10%時(shí)，REXR策略能顯著降低過(guò)渡預(yù)留導(dǎo)致的資源效率損失；面對(duì)較低的預(yù)留請(qǐng)求率，松弛接納閾值V*可以設(shè)置得較低，但面對(duì)較高的預(yù)留請(qǐng)求率時(shí)，V*取值不應(yīng)過(guò)小。

5.2 實(shí)際工作流分析

WIEN2K工作流[19]包括2個(gè)并行分支，其問(wèn)題規(guī)模由這2個(gè)并行分支決定，實(shí)驗(yàn)設(shè)定問(wèn)題規(guī)模從100逐步增加到 600。實(shí)驗(yàn)過(guò)程中向網(wǎng)格系統(tǒng)注入了一定的背景工作負(fù)載，從而與WIEN2K共同競(jìng)爭(zhēng)系統(tǒng)資源。為分析任務(wù)高估預(yù)留時(shí)間對(duì)其執(zhí)行效率的影響，本次實(shí)驗(yàn)將WIEN2K中各個(gè)任務(wù)節(jié)點(diǎn)的預(yù)留時(shí)間高估了β倍，實(shí)驗(yàn)分4組進(jìn)行，β值分別為10%、20%、30%和40%，實(shí)驗(yàn)結(jié)果如圖6所示。

實(shí)驗(yàn)結(jié)果顯示，當(dāng)任務(wù)預(yù)留時(shí)間高估率為10%且任務(wù)規(guī)模為100～400時(shí)，CONR、MALR和REXR 3種策略對(duì)應(yīng)的WIEN2K執(zhí)行時(shí)間差別很小，但當(dāng)任務(wù)規(guī)模達(dá)到500以上時(shí)，REXR策略的性能優(yōu)勢(shì)就比較明顯了，其對(duì)應(yīng)的工作流執(zhí)行時(shí)間大約只有前2種策略的51%；隨著任務(wù)高估率β值的增加，所有策略所對(duì)應(yīng)的執(zhí)行時(shí)間都顯著增加，不過(guò)相對(duì)增幅出現(xiàn)了明顯差異，其中MALR策略的相對(duì)增幅最明顯，而REXR策略的執(zhí)行時(shí)間隨β值而增加的幅度則遠(yuǎn)遠(yuǎn)小于其他4種策略。

背景負(fù)載對(duì) WIEN2K執(zhí)行效率的影響十分明顯。當(dāng)任務(wù)規(guī)模小于400時(shí)，OVBR策略在本次實(shí)驗(yàn)中的性能表現(xiàn)是最差的，OVBR策略表現(xiàn)不佳的主要原因是，背景負(fù)載在實(shí)驗(yàn)開(kāi)始階段的到達(dá)速度較快，系統(tǒng)在面對(duì)較高額外負(fù)載時(shí)，其資源可用量顯著降低，而超額預(yù)留策略則更加減少了系統(tǒng)未來(lái)的可預(yù)留資源量，因此WIEN2K第2個(gè)并行分支中的許多子任務(wù)出現(xiàn)了執(zhí)行延遲，從而影響任務(wù)整體的執(zhí)行效率。但這種情況在β值較高時(shí)得到了一定程度的緩解，原因剛好是因?yàn)檩^高的β值意味著并行分支中的預(yù)留時(shí)間被高估，很多預(yù)留請(qǐng)求實(shí)際被提前釋放，其效果等價(jià)于取消預(yù)留請(qǐng)求，從而令OVBR策略的性能表現(xiàn)得到一定程度的提升。

MALR策略在任務(wù)規(guī)模超過(guò)400后，其性能表現(xiàn)明顯低于其他策略，產(chǎn)生這種現(xiàn)象的原因與WIEN2K工作流的結(jié)構(gòu)特征有關(guān)。因?yàn)閃IEN2K的主要執(zhí)行時(shí)間集中在2個(gè)大的并行分支部分，其并行子任務(wù)類(lèi)似一組獨(dú)立子任務(wù)。因此WIEN2K的最終執(zhí)行時(shí)間是由這些子任務(wù)集合的最遲完成時(shí)間決定。而MALR策略的優(yōu)越性主要體現(xiàn)在子任務(wù)差異度很大的情況下，此時(shí)MALR策略能依據(jù)子任務(wù)的計(jì)算量和資源需求量之間的線性關(guān)系來(lái)規(guī)劃一個(gè)總體完成時(shí)間較優(yōu)的預(yù)留方案，而本實(shí)驗(yàn)所分析的WIEN2K則不具備這種特許。因此MALR策略的平均執(zhí)行時(shí)間大約是REXR策略的一倍左右。

圖6 不同β值下WIEN2K執(zhí)行時(shí)間對(duì)比

本次實(shí)驗(yàn)的主要結(jié)論是：①高估預(yù)留時(shí)間將對(duì)工作流執(zhí)行效率產(chǎn)生較大負(fù)面影響，REXR策略能夠有效降低這種負(fù)面影響；②OVBR和CBFR難以適應(yīng)突發(fā)負(fù)載增高的情況，當(dāng)系統(tǒng)整體負(fù)載較重時(shí)，2種策略對(duì)任務(wù)執(zhí)行效率的負(fù)面影響顯著增大；③MALR的性能表現(xiàn)受工作流結(jié)構(gòu)特征影響較大。

6 結(jié)束語(yǔ)

提出一種支持時(shí)空二維松弛的預(yù)留策略，用于解決預(yù)留機(jī)制對(duì)系統(tǒng)性能的負(fù)面影響，并采用進(jìn)化算法與松弛預(yù)留策略相結(jié)合的方法設(shè)計(jì)了一個(gè)協(xié)同資源預(yù)留接納算法。實(shí)驗(yàn)結(jié)果顯示，松弛預(yù)留策略不僅能有效降低預(yù)留服務(wù)對(duì)系統(tǒng)性能的負(fù)面影響，而且在能顯著降低由高估預(yù)留時(shí)間而導(dǎo)致電工作流執(zhí)行效率損失。今后的主要工作是在松弛預(yù)留模型中引入資源失效情況下的分析和處理技術(shù)。

[1] FOSTER I, KESSELMAN C. The Grid 2 [M]. San Francisco: Morgan Kaufmann, 2004.

[2] SMITH W, FOSTER I, TAYLOR V. Scheduling with advanced reservations[A]. IPDPS’00[C]. Cancun, Mexico, 2000.127-132.

[3] CAO J W, ZIMMERMANN F. Queue scheduling and advance reservations with COSY[A]. IPDPS’04[C]. Santa Fe, New Mexico, USA,2004.63-70.

[4] SULISTIO A, KIM K H, BUYYA R. Managing cancellations and no-shows of reservations with overbooking to increase resource revenue[A]. CCGRID’08[C]. Lyon, France, 2008.267-276.

[5] AIDA K, CASANOVA H. Scheduling mixed-parallel applications with advance reservations[J]. Cluster Computing, 2009,12(2):205-220.

[6] CASTILLO C, ROUSKAS G N, HARFOUSH K. Efficient resource management using advance reservations for heterogeneous grids[A].IPDPS’08[C]. Miami, Florida, USA, 2008.1-12.

[7] FAROOQ U, MAJUMDAR S, PARSONS E W. Impact of laxity on scheduling with advance reservations in Grids[A]. MASCOTS’05[C].Atlanta, Georgia, USA, 2005.319-322.

[8] LI B, SHEN B. Slack-based advance reservation for grid jobs[A].ICACTE’10[C]. Chengdu, China, 2010.418-423.

[9] SODAN A C, DOSHI C, BARSANTI L, et al. Gang scheduling and adaptive resource allocation to mitigate advance reservation impact[A].CCGRID’06[C]. Singapore, 2006.649-653.

[10] BURCHARD L O. Analysis of data structures for admission control of advance reservation requests[J]. IEEE Transactions on Knowledge and Data Engineering, 2005, 17(3):413-424.

[11] DUN N, TAURA K, YONEZAWA A. Fine-grained profiling for data-intensive workflows[A]. CCGRID’10[C]. Melbourne, Australia,2010.571-572.

[12] PRODAN R, FAHRINGER T. Overhead analysis of scientific workflows in grid environments[J]. IEEE Transactions on Parallel and Distributed Systems, 2008, 19(3):378-393.

[13] 胡春明, 懷進(jìn)鵬, 沃天宇. 一種基于松弛時(shí)間的服務(wù)網(wǎng)格資源能力預(yù)留機(jī)制[J]. 計(jì)算機(jī)研究與發(fā)展, 2007,44(1): 20-28.HU C M, HUAI J P, WO T Y. Flexible resource capacity reservation mechanism for service grid using slack time[J]. Journal of Computer Research and Development, 2007,44(1):20-28.

[14] JAWAD A, THOMAS E. A new resource mapping technique for grid workflows in advance reservation environments[A]. HPCS’10[C].Normandy, France, 2010.63-70.

[15] 公茂果, 焦李成, 楊咚咚等. 進(jìn)化多目標(biāo)優(yōu)化算法研究[J]. 軟件學(xué)報(bào), 2009, 20(2):271-289.GONG M G, JIAO L C, YANG D D, et al. Evolutionary multi- objective optimization algorithms[J]. Journal of Software, 2009, 20(2):271-289.

[16] MENG X H, ZHU Y A, WU X M. Improved dynamic programming algorithms for the 0-1 knapsack problem[A]. ICCSIT’11[C]. Chendu,China, 2011.19-22.

[17] SNEDECOR G W, COCHRAN W G. Statistical Methods[M]. Ames:Iowa State Press, 1980.

[18] BAL H, BHOEDJANG R R, HOFMAN R, et al. The distributed ASCI supercomputer project[J]. ACM Operating Systems Review, 2000,34(4):76-96.

[19] TOPCUOGLU H, HARIRI S, WU M Y. Performance-effective and low-complexity task scheduling for heterogeneous computing[J]. IEEE Transactions on Parallel and Distributed Systems, 2002, 13(2):260-274.

[20] WU L, WU C, CUI J, et al. An adaptive advance reservation mechanism for grid computing[A]. PDCAT’05[C]. Dalian, China,2005.400-403.