基于云計(jì)算的集群擴(kuò)展中的調(diào)度算法研究.pdf

《基于云計(jì)算的集群擴(kuò)展中的調(diào)度算法研究.pdf》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、中國(guó)科學(xué)技術(shù)大學(xué)碩士學(xué)位論又基于云計(jì)算的集群擴(kuò)展中的調(diào)度算法研究作者姓名：學(xué)科專業(yè)：導(dǎo)師姓名：完成時(shí)間：葛新管理科學(xué)與工程陳華平教授二。一一年五月三十一曰UniversityofScienceandTechnologyofChinaAdissertationformaster’SdegreeAuthor’SName：XinGespeciality：ManagementScienceandEngine硎ng一‘Supervisor：Prof．HuapingChenFinishedtime：May31th，2011nDg．㈣凹n甜Ⅲ嘶翟例舊帥n扎山講Cb孫嶼甜色nj鼬M劃鏈

2、附：{：瞿訓(xùn)珧R蚪盼中國(guó)科學(xué)技術(shù)大學(xué)學(xué)位論文原創(chuàng)性聲明本人聲明所呈交的學(xué)位論文，是本人在導(dǎo)師指導(dǎo)下進(jìn)行研究工作所取得的成果。除已特別加以標(biāo)注和致謝的地方外，論文中不包含任何他人已經(jīng)發(fā)表或撰寫過的研究成果。與我一同工作的同志對(duì)本研究所做的貢獻(xiàn)均已在論文中作了明確的說明。作者簽名：葛塹簽字日期：絲!f：魚：墮中國(guó)科學(xué)技術(shù)大學(xué)學(xué)位論文授權(quán)使用聲明作為申請(qǐng)學(xué)位的條件之一，學(xué)位論文著作權(quán)擁有者授權(quán)中國(guó)科學(xué)技術(shù)大學(xué)擁有學(xué)位論文的部分使用權(quán)，即：學(xué)校有權(quán)按有關(guān)規(guī)定向國(guó)家有關(guān)部門或機(jī)構(gòu)送交論文的復(fù)印件和電子版，允許論文被查閱和借閱，可以將學(xué)位論文編入《中國(guó)學(xué)位論文全文數(shù)據(jù)庫》等有關(guān)數(shù)據(jù)

3、庫進(jìn)行檢索，可以采用影印、縮印或掃描等復(fù)制手段保存、匯編學(xué)位論文。本人提交的電子文檔的內(nèi)容和紙質(zhì)論文的內(nèi)容相一致。保密的學(xué)位論文在解密后也遵守此規(guī)定?？诠_口保密(——年)作者簽名：葛薹丘簽字日期：2望!!：笪：!蘭導(dǎo)師簽名：簽字日期：摘要作業(yè)調(diào)度算法一直是集群系統(tǒng)中的一個(gè)非常重要的研究課題，是決定一個(gè)集群性能好壞的前提和基礎(chǔ)。良好的調(diào)度算法可以幫助提高集群處理能力，有效地分配資源，加速作業(yè)運(yùn)行。隨著業(yè)務(wù)的不斷發(fā)展，集群壓力越來越大，企業(yè)不得不擴(kuò)展其內(nèi)部集群。但是傳統(tǒng)的購(gòu)入大量服務(wù)器的做法會(huì)消耗大量的資金和成本。在這樣的環(huán)境下，云計(jì)算靈活的使用方式為企業(yè)集群擴(kuò)展提供了新

4、的集群擴(kuò)展方式，解決了企業(yè)面臨的兩難局面?；谘芯勘尘暗霓D(zhuǎn)變，集群環(huán)境的變化，傳統(tǒng)的作業(yè)調(diào)度算法己然不能適應(yīng)新的集群環(huán)境。為了順應(yīng)了企業(yè)發(fā)展的需要，我們迫切需要探索基于云計(jì)算的集群擴(kuò)展中的作業(yè)調(diào)度算法。這對(duì)于企業(yè)節(jié)約成本，提高用戶滿意度等都具有重要意義。由于基于云計(jì)算的集群擴(kuò)展中的調(diào)度算法研究剛剛起步，目前并沒有詳細(xì)的研究資料和參照算法。因而，本文采用逐步深入的方式設(shè)計(jì)了多種基于云計(jì)算的集群擴(kuò)展中的作業(yè)調(diào)度算法。首先，提出了兩種簡(jiǎn)單調(diào)度算法作為我們的參照調(diào)度算法。接著，針對(duì)這兩種算法中作業(yè)分配不合理性，利用集群計(jì)算能力不同的特點(diǎn)，提出了一種基于計(jì)算強(qiáng)度的調(diào)度算法。該算法

5、提出使用集合U代替整個(gè)等待隊(duì)列對(duì)作業(yè)篩選，這種方式不但減少了作業(yè)完成總時(shí)間和總成本，而且兼顧作業(yè)調(diào)度的公平性。隨后，本文提出一種等體積預(yù)留回填EV-RB(EqualVolume．ReservationBackfilling)調(diào)度算法，該算法認(rèn)識(shí)到基于計(jì)算強(qiáng)度的調(diào)度算法存在資源利用率低、超時(shí)作業(yè)數(shù)量多的問題，創(chuàng)造性地將BackFilling算法中的二維時(shí)空表轉(zhuǎn)變成三維的方式，將原本只能在傳統(tǒng)集群中運(yùn)行的BackFilling算法成功引入到云環(huán)境擴(kuò)展的集群中。同時(shí)，該算法為了解決BackFilling算法回填作業(yè)不足的缺點(diǎn)，使用體積變換的方式代替單一的時(shí)間比較，進(jìn)一步提高了

6、資源利用率。最后，本文又提出一種改進(jìn)的等體積預(yù)留回填I(lǐng)EV-RB(ImprovedEqualVolume．ReservationBackfilling)調(diào)度算法，該算法基于對(duì)EV-RB算法的改進(jìn)，放寬了需求CPU數(shù)量不可變這一限制，進(jìn)一步增加了可回填作業(yè)數(shù)量。之后，本文進(jìn)行了仿真實(shí)驗(yàn)。設(shè)計(jì)了9類子問題，每個(gè)問題隨機(jī)生成多個(gè)實(shí)例，從成本和超出時(shí)間約束的作業(yè)數(shù)量?jī)蓚€(gè)方面對(duì)我們所設(shè)計(jì)的算法的有效性進(jìn)行了驗(yàn)證。實(shí)驗(yàn)結(jié)果與算法思想基本一致，表明算法設(shè)計(jì)合理有效。最后，對(duì)幾種算法的適用性進(jìn)行了分析。關(guān)鍵詞：作業(yè)調(diào)度算法；集群擴(kuò)展；云計(jì)算；BackFilling算法l摘要Abstra

7、ctABSTRACTJobschedulingalgorithmisalwaysaveryimportantresearchtopicinclustersystem，whichiSthepremiseandfoundationtodeterminetheperformanceofaclusterisgoodornot．Goodschedulingalgorithmcanhelpimprovetheclusterprocessing，allocateresourceeffectivelyandacceleratejobrunning．Wit