本文關(guān)鍵詞：有期限約束的多DAG共享資源的調(diào)度及公平費(fèi)用優(yōu)化方法

  更多相關(guān)文章： 多DAG調(diào)度 期限約束 工作流 費(fèi)用優(yōu)化 公平性

【摘要】：隨著網(wǎng)格和云計(jì)算工作流技術(shù)的發(fā)展,近來(lái)關(guān)于多DAG(Directed Acyclic Graph)共享資源調(diào)度的研究取得了一些進(jìn)展,然而,關(guān)于具有最晚完成期限約束的多DAG共享一組有限異構(gòu)資源的調(diào)度及其費(fèi)用最低化等問(wèn)題還有待進(jìn)一步研究和解決.針對(duì)這些問(wèn)題,文中首先提出了衡量DAG期限緊急水平的"相對(duì)嚴(yán)格程度"的新方法,并在此基礎(chǔ)上提出了基于相對(duì)嚴(yán)格程度的調(diào)度算法MDRS(Scheduling for Multi-DAGs with Deadline based on Relative Stritness).該算法不僅能夠合理處理多個(gè)DAG之間調(diào)度的緊急水平關(guān)系,也能對(duì)由于DAG期限過(guò)于嚴(yán)格而可能產(chǎn)生的"過(guò)飽和"情況進(jìn)行探測(cè)和處理.一旦遇到"過(guò)飽和"情況,則采用"堆棧"與"調(diào)度回溯"相結(jié)合的機(jī)制盡可能少地丟棄其中的DAG,從而達(dá)到DAG吞吐量最大化調(diào)度目標(biāo).在MDRS算法的基礎(chǔ)上,為了滿足各DAG期限內(nèi)完成約束條件,并盡可能公平地降低多個(gè)DAG執(zhí)行的費(fèi)用,又提出了基于單位相對(duì)嚴(yán)格程度變化量的費(fèi)用降低率最大化方法的費(fèi)用優(yōu)化算法CDVRS(Cost Decrease based on Variance of the Relative Strictness).實(shí)驗(yàn)表明:這些方法及算法能夠達(dá)到較好的性能.
【作者單位】： 北京工業(yè)大學(xué)計(jì)算機(jī)學(xué)院;新疆工程學(xué)院計(jì)算機(jī)工程系;
【關(guān)鍵詞】： 多DAG調(diào)度 期限約束 工作流 費(fèi)用優(yōu)化 公平性
【基金】：北京市自然科學(xué)基金項(xiàng)目(4110001) 國(guó)家自然科學(xué)基金(61363004,61063042)資助~~
【分類(lèi)號(hào)】：TP393.01
【正文快照】： 1引言很多的工作流任務(wù)及任務(wù)間的依賴(lài)約束關(guān)系都可由有向無(wú)環(huán)圖DAG(Directed Acyclic Graph)來(lái)表示或者能夠轉(zhuǎn)化為DAG任務(wù)圖.近年來(lái),隨著一些異構(gòu)分布式計(jì)算環(huán)境下工作流系統(tǒng)技術(shù)研究和應(yīng)用的發(fā)展(如網(wǎng)格、云計(jì)算或混合云計(jì)算工作流系統(tǒng)),作為這些工作流管理系統(tǒng)的關(guān)鍵技術(shù)之

【參考文獻(xiàn)】

中國(guó)期刊全文數(shù)據(jù)庫(kù) 前1條

1 田國(guó)忠;肖創(chuàng)柏;徐竹勝;肖霞;;異構(gòu)分布式環(huán)境下多DAG工作流的混合調(diào)度策略[J];軟件學(xué)報(bào);2012年10期

【共引文獻(xiàn)】

中國(guó)期刊全文數(shù)據(jù)庫(kù) 前4條

1 劉丹琦;于炯;英昌甜;;云計(jì)算環(huán)境下多有向無(wú)環(huán)圖工作流的節(jié)能調(diào)度算法[J];計(jì)算機(jī)應(yīng)用;2013年09期

2 陳冬林;付敏;康艷芳;吳鐘;;面向數(shù)據(jù)挖掘的云資源多實(shí)例組合購(gòu)買(mǎi)決策研究[J];計(jì)算機(jī)應(yīng)用研究;2013年11期

3 孫月;于炯;朱建波;;云計(jì)算中一種多DAG工作流可搶占式調(diào)度策略[J];計(jì)算機(jī)科學(xué);2014年03期

4 謝國(guó)琪;李仁發(fā);楊帆;黃衛(wèi)紅;;異構(gòu)網(wǎng)絡(luò)化汽車(chē)電子系統(tǒng)中多DAG離線任務(wù)調(diào)度[J];通信學(xué)報(bào);2013年12期

中國(guó)碩士學(xué)位論文全文數(shù)據(jù)庫(kù) 前3條

1 張丹闖;分布式環(huán)境下基于整體最優(yōu)的資源分配研究[D];大連理工大學(xué);2013年

2 劉莉;異構(gòu)集群下并行任務(wù)的復(fù)制調(diào)度算法[D];武漢紡織大學(xué);2013年

3 任豐玲;云環(huán)境下多DAG工作流的調(diào)度算法研究[D];新疆大學(xué);2013年

【二級(jí)參考文獻(xiàn)】

中國(guó)期刊全文數(shù)據(jù)庫(kù) 前1條

1 苑迎春;李小平;王茜;王克儉;;成本約束的網(wǎng)格工作流時(shí)間優(yōu)化方法[J];計(jì)算機(jī)研究與發(fā)展;2009年02期

【相似文獻(xiàn)】

中國(guó)期刊全文數(shù)據(jù)庫(kù) 前7條

1 薛桂香;趙政;馬懋德;張世勇;;網(wǎng)格任務(wù)調(diào)度策略研究[J];微處理機(jī);2007年03期

2 田國(guó)忠;于炯;劉洪偉;龔紅翠;;基于排隊(duì)論時(shí)間預(yù)測(cè)的網(wǎng)格工作流調(diào)度算法[J];石河子大學(xué)學(xué)報(bào)(自然科學(xué)版);2008年03期

3 王磊;夏陽(yáng);史強(qiáng);文艾;;網(wǎng)格環(huán)境下基于QoS的協(xié)作型任務(wù)調(diào)度算法研究[J];小型微型計(jì)算機(jī)系統(tǒng);2011年08期

4 劉紅梅;;網(wǎng)格環(huán)境下任務(wù)調(diào)度算法的分析研究[J];電腦知識(shí)與技術(shù);2007年24期

5 唐小勇;唐小勇;李肯立;PADUA Divid;;考慮通信競(jìng)爭(zhēng)的任意處理機(jī)網(wǎng)絡(luò)表調(diào)度算法[J];中國(guó)科學(xué)(F輯:信息科學(xué));2009年07期

6 劉欣媛;張忠平;雷炳銀;;網(wǎng)格環(huán)境下的靜態(tài)啟發(fā)式任務(wù)調(diào)度算法[J];廣西師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2007年04期

7 陳敏;李旺;;計(jì)算機(jī)網(wǎng)絡(luò)中的故障定位技術(shù)研究[J];國(guó)外電子測(cè)量技術(shù);2007年07期

中國(guó)碩士學(xué)位論文全文數(shù)據(jù)庫(kù) 前7條

1 唐小勇;基于動(dòng)態(tài)通信競(jìng)爭(zhēng)的任意處理機(jī)網(wǎng)絡(luò)表調(diào)度算法[D];湖南大學(xué);2007年

2 朱玉丹;基于非獨(dú)立任務(wù)優(yōu)先級(jí)的網(wǎng)格調(diào)度算法的研究[D];大連理工大學(xué);2010年

3 邢常振;基于虛擬計(jì)算環(huán)境的元調(diào)度器研究[D];中國(guó)石油大學(xué);2010年

4 陳杰;面向網(wǎng)格的并行應(yīng)用接口研究[D];中國(guó)石油大學(xué);2011年

5 黃俊一;樹(shù)形網(wǎng)格任務(wù)調(diào)度方法研究[D];東北大學(xué);2008年

6 朱耀強(qiáng);網(wǎng)格安全策略沖突檢測(cè)及其消解機(jī)制的研究[D];長(zhǎng)春工業(yè)大學(xué);2010年

7 張智民;基于化學(xué)反應(yīng)優(yōu)化的網(wǎng)格任務(wù)調(diào)度研究[D];湖南大學(xué);2012年

，

本文編號(hào)：972760