云環(huán)境中DAG調(diào)度算法的設(shè)計和實現(xiàn)

大連理工大學(xué)本科畢業(yè)設(shè)計（論文）云環(huán)境中DAG調(diào)度算法設(shè)計和實現(xiàn)DesignandImplementationofDAGSchedulingAlgorithmsinCloudEnvironment學(xué)院（系）：計算機科學(xué)和技術(shù)學(xué)院專業(yè)：計算機科學(xué)和技術(shù)學(xué)生姓名：xxx學(xué)號：xxxxxxxx指導(dǎo)教師：xxx評閱教師：完成日期：大連理工大學(xué)DalianUniversityofTechnology摘要多年來伴隨網(wǎng)格、云計算工作流等異構(gòu)分布式計算技術(shù)發(fā)展，相關(guān)多DAG共享異構(gòu)分布式資源調(diào)度問題逐步成為備受關(guān)注研究熱點。現(xiàn)在，盡管相關(guān)多DAG共享異構(gòu)分布式資源調(diào)度研究取得了一定進展，但仍有很多問題亟待深入研究和處理。本文圍繞多DAG共享異構(gòu)分布式資源調(diào)度若干問題展開了研究，這些問題包含：含有多優(yōu)先級多DAG調(diào)度和含有期限約束多DAG調(diào)度吞吐量最大化、費用優(yōu)化和費用優(yōu)化公平性等。對這些問題處理將有利于提升網(wǎng)格、云計算工作流等異構(gòu)分布式計算系統(tǒng)資源利用率、合理處理多個DAG應(yīng)用之間調(diào)度關(guān)系和有效降低用戶DAG應(yīng)用費用，所以有著關(guān)鍵理論意義和應(yīng)用價值。相關(guān)DAG共享異構(gòu)分布式資源調(diào)度研究關(guān)鍵是相關(guān)DAG調(diào)度算法研究。本文使用Java語言實現(xiàn)了經(jīng)典DAG靜態(tài)調(diào)度算法HEFT、CPOP和LBP，還實現(xiàn)了側(cè)重公平性E-Fairness算法，最終實現(xiàn)了混合調(diào)度算法MMHS。在實現(xiàn)這些算法基礎(chǔ)上，還測試這些算法相關(guān)性能，如調(diào)度時間和公平性等。同時實現(xiàn)了DAG調(diào)度仿真器，在仿真器基礎(chǔ)上，能夠方便地進行多種算法研究，而且方便做算法性能試驗測試。關(guān)鍵詞：多DAG調(diào)度;多優(yōu)先級;公平性;仿真器DesignandImplementationofDAGSchedulingAlgorithmsinCloudEnvironmentAbstractInrecentyears,withthegrid,cloudcomputingworkflowsandotherheterogeneousdistributedcomputingtechnology,schedulingofmultipleDAGssharingonheterogeneousdistributedresourcesisbecomingahottopicofconcern.Atpresent,despiteaboutmultipleDAGssharingonHeterogeneousDistributedResourceSchedulerhasmadesomeprogress,buttherearestillmanyproblemstobefurtherstudiedandresolved.ThispaperfocusesonanumberofissuesmoreDAGsharingonHeterogeneousDistributedResourceScheduling.Theseissuesinclude:amulti-priorityDAGschedulinganddeadlineconstraintshavemultipleDAGsschedulingtomaximizethroughput,costoptimizationandcostoptimizationofthefairandsoon.Solvingtheseproblemswillhelpimprovegrid,cloudcomputingresourceutilization,workflowandotherheterogeneousdistributedcomputingsystems,rationaltreatmentofmultipleDAGsschedulingrelationshipbetweenapplicationsandreduceuserDAGapplicationfee,sotherearetheoreticalsignificanceandapplicationvalue.ResearchontheDAGshareinHeterogeneousDistributedResourceSchedulingisresearchonDAGschedulingalgorithm.ThisarticleusestheJavalanguagetoachieveaclassicDAGstaticschedulingalgorithmHEFT,CPOPandLBP,butalsotoimplementafocusedequityE-Fairnessalgorithm,andfinallyrealizethehybridschedulingalgorithmMMHS.Onthebasisofthesealgorithms,butalsotesttherelativeperformanceofthesealgorithms,suchasthescheduledtimeandequity.WhileachievingtheDAGschedulingsimulator,asimulatorbasedon,itcaneasilystudyvariousalgorithms,andeasytodoexperimentstotestthealgorithmperformance.KeyWords：multiDAGsscheduling;multipriority;fairness目錄摘要 IAbstract II引言 11緒論 21.1研究背景 21.2研究現(xiàn)實狀況 32相關(guān)定義及理論 82.1DAG任務(wù)調(diào)度模型 82.2計算環(huán)境異構(gòu)性 92.3云環(huán)境下任務(wù)調(diào)度算法概述 92.3.1云環(huán)境下任務(wù)調(diào)度技術(shù)綜述 102.3.2云環(huán)境下任務(wù)調(diào)度過程 102.3.3云環(huán)境下任務(wù)調(diào)度系統(tǒng) 112.3.4云環(huán)境下任務(wù)調(diào)度特點 122.3.5云環(huán)境下任務(wù)調(diào)度算法 123靜態(tài)DAG任務(wù)調(diào)度算法 153.1試驗環(huán)境介紹 153.2靜態(tài)調(diào)度算法HEFT 153.3靜態(tài)調(diào)度算法CPOP 163.4基于表調(diào)度任務(wù)調(diào)度算法LBP 183.5算法時間復(fù)雜度和調(diào)度性能比較 193.5.1時間復(fù)雜度 193.5.2調(diào)度性能 203.6試驗和分析 204含有多優(yōu)先級多DAG混合調(diào)度 214.1含有多優(yōu)先級多DAG調(diào)度系統(tǒng)模型 214.2多DAG公平調(diào)度E-Fairness改善算法 234.3多DAGBackfill算法實現(xiàn) 264.4含有多優(yōu)先級多DAG混合調(diào)度策略MMHS 274.5試驗和分析 294.5.1相關(guān)兩個DAG調(diào)度試驗 294.5.2多個隨機DAG調(diào)度試驗結(jié)果分析 31結(jié)論 33參考文獻 34附錄AMMHS算法關(guān)鍵代碼 36致謝 39引言多年來，伴隨部分異構(gòu)分布式計算環(huán)境工作流系統(tǒng)技術(shù)發(fā)展（如網(wǎng)格、云計算或混合云計算工作流系統(tǒng)），作為這些工作流管理系統(tǒng)關(guān)鍵技術(shù)之一多個DAG任務(wù)共享異構(gòu)分布式資源調(diào)度問題引發(fā)了研究者們關(guān)注。很多工作流任務(wù)及任務(wù)間依靠約束關(guān)系全部可由有向無環(huán)圖DAG（DirectAcyclicGraph）來表示[1]?，F(xiàn)在相關(guān)多個DAG任務(wù)共享資源調(diào)度研究在實施時間最小化（MakespanMinimization）、公平性最大化（FairnessMaximization）、吞吐量最大化（ThroughputMaximization）和資源分配優(yōu)化（ResourceAllocationOptimization）等方面已經(jīng)取得了部分進展。在網(wǎng)格、云計算或混合云計算等平臺工作流研究領(lǐng)域中，相關(guān)有最晚完成期限約束DAG調(diào)度問題也引發(fā)了研究者們關(guān)注。在這些新型異構(gòu)分布式應(yīng)用環(huán)境下，因為資源提供者往往會依據(jù)所提供資源類型、服務(wù)質(zhì)量QoS（QualityofService）和用戶使用（或租用）資源總時長進行計費，用戶考慮到經(jīng)濟費用等原因，往往會依據(jù)應(yīng)用需求為DAG應(yīng)用指定一個最晚完成期限D(zhuǎn)eadline，而并不要求DAG在最短時間內(nèi)完成，這么就需要工作流調(diào)度系統(tǒng)能夠依據(jù)用戶指定最晚完成期限盡可能為用戶DAG任務(wù)選擇經(jīng)濟費用最低資源。針對有期限約束DAG任務(wù)調(diào)度及其費用優(yōu)化，相關(guān)研究提出了部分算法和處理方案。這些相關(guān)有Deadline約束DAG調(diào)度算法大多全部有一個“Deadline分配”關(guān)鍵步驟，也就是用不一樣方法將整個DAGDeadline分配到各任務(wù)（或任務(wù)區(qū)間）上，然后依據(jù)任務(wù)所分配時間窗口盡可能選擇較廉價（所以速度也較慢）資源進行費用優(yōu)化。多年來，相關(guān)單個DAG在異構(gòu)分布式環(huán)境下調(diào)度研究已經(jīng)取得了很大進展[2-9]，但這些算法不能直接利用于多DAG調(diào)度，針對多個DAG工作流調(diào)度研究還處于探索階段?，F(xiàn)有相關(guān)多DAG調(diào)度模型和算法盡管提出和處理了部分關(guān)鍵問題，但對更為復(fù)雜情況下多DAG調(diào)度，如多個用戶可能會在不一樣時間提交DAG，且用戶對DAG實施時間要求可能差異較大，怎樣處理好已被部分調(diào)度實施DAG和新抵達DAG中各任務(wù)之間關(guān)系，以愈加好地兼顧多個DAG之間調(diào)度公平性和資源利用率改善等問題，還沒有得到很好處理。適適用于異構(gòu)分布式環(huán)境下多個不一樣DAG隨機提交多優(yōu)先級DAG調(diào)度模型和算法被提出。正是在這么研究背景下，本文圍繞異構(gòu)分布式計算環(huán)境下含有不一樣QoS需求類型多個DAG共享資源調(diào)度問題、含有期限約束多DAG共享資源調(diào)度吞吐量最大化問題、總費用優(yōu)化問題和費用優(yōu)化公平性問題等四個方面內(nèi)容展開了我們研究工作。1緒論1.1研究背景任務(wù)調(diào)度問題是分布式計算領(lǐng)域中基礎(chǔ)問題。依據(jù)被調(diào)度任務(wù)之間是否存在相關(guān)依靠關(guān)系，任務(wù)調(diào)度可分為獨立任務(wù)調(diào)度和相關(guān)任務(wù)調(diào)度（有時也被稱為依靠任務(wù)調(diào)度）。其中相關(guān)任務(wù)是由一組現(xiàn)有前后數(shù)據(jù)傳輸約束關(guān)系，又有并行關(guān)系多個任務(wù)組成，通常可由有向無環(huán)圖任務(wù)圖來表示。為了提升系統(tǒng)效率，這些DAG類型任務(wù)中子結(jié)點任務(wù)往往需要在多個處理單元或多個計算機所組成資源系統(tǒng)上協(xié)同完成。近些年來，伴隨網(wǎng)絡(luò)和科學(xué)技術(shù)發(fā)展，尤其是部分大型科學(xué)計算、應(yīng)用及信息處理假如僅依靠一臺計算機不輕易處理，就需要利用多個計算機資源來共同完成。比如要統(tǒng)計過去1年間9000篇（或更多）科技論文中高頻詞，方便分析近期研究熱點。假如只有1臺計算機運行這項工作任務(wù)，只能將全部論文按某種次序遍歷一遍進行統(tǒng)計或編制多線程程序來并行實施以提升遍歷效率。然而，假如有N臺運算能力可能互不相同經(jīng)過網(wǎng)絡(luò)互聯(lián)計算機能同時為這項工作任務(wù)服務(wù)，這9000篇論文就能夠分解成N份，讓這N臺計算機并行遍歷統(tǒng)計，效率和速度將大大提升。在這一過程中，這項工作能夠分解為以下部分子任務(wù)：在其中某臺計算機上進行“全部論文遍歷任務(wù)分發(fā)”、每臺計算機被分配“遍歷統(tǒng)計”和某臺計算機最終“匯總統(tǒng)計”，那么這些子任務(wù)結(jié)點及其數(shù)據(jù)傳輸關(guān)系就組成了一個DAG任務(wù)圖。在這個圖中，多個任務(wù)實施有一定前后約束和數(shù)據(jù)傳輸關(guān)系，如某臺計算機被分配“遍歷統(tǒng)計任務(wù)”必需要在“論文遍歷任務(wù)分發(fā)任務(wù)”結(jié)束，并將必需數(shù)據(jù)送達該機器后才能開始實施就是這種約束關(guān)系表現(xiàn)。類似地，在物理、天文、生物、工程等很多領(lǐng)域部分大型科學(xué)計算問題也能夠轉(zhuǎn)化為對應(yīng)DAG任務(wù)，而且這些領(lǐng)域計算規(guī)模日益增大，計算步驟日益復(fù)雜，更需要多計算機資源并行實施和協(xié)同工作來處理相關(guān)問題。多年來，伴隨網(wǎng)格和云計算應(yīng)用和發(fā)展，為這種大型科學(xué)計算應(yīng)用需要提供了良好平臺。這些平臺全部能經(jīng)過網(wǎng)絡(luò)為這類需要多計算機資源協(xié)同工作應(yīng)用系統(tǒng)提供由大量高性能異構(gòu)分布式資源所組成資源池，使應(yīng)用系統(tǒng)能夠依據(jù)應(yīng)用需要獲取計算力、存放空間和多種軟件服務(wù)。尤其是現(xiàn)在研究和發(fā)展中網(wǎng)格工作流或云計算工作流系統(tǒng)，不僅能夠?qū)@些大型計算DAG任務(wù)進行構(gòu)建、調(diào)度實施、監(jiān)控管理，還能夠利用和管理網(wǎng)格和云計算所提供大量計算資源，并在部分科學(xué)計算領(lǐng)域?qū)崿F(xiàn)了對這類DAG任務(wù)計算自動化運行。然而，實現(xiàn)這些系統(tǒng)服務(wù)和服務(wù)效率高低很大程度上取決于DAG任務(wù)調(diào)度方法好壞。要將DAG中多個子結(jié)點任務(wù)調(diào)度映射到多個計算機資源上，不僅要考慮不一樣計算機處理能力不一樣，而且計算機資源間網(wǎng)絡(luò)通信速率也可能不一樣，所以是個復(fù)雜問題。怎樣為這些DAG任務(wù)選擇適宜資源，將這些DAG任務(wù)分配映射到網(wǎng)絡(luò)中多個計算資源上，以達成DAG任務(wù)完成時間最小化等調(diào)度目標，即可歸結(jié)DAG任務(wù)在異構(gòu)分布式計算系統(tǒng)上調(diào)度問題。相關(guān)DAG任務(wù)調(diào)度，多年來引發(fā)了中國外研究者們廣泛關(guān)注。現(xiàn)在很多相關(guān)DAG任務(wù)調(diào)度方法被提出，而且所采取調(diào)度技術(shù)和處理問題角度各有不一樣。其中有部分已成功應(yīng)用于實際網(wǎng)格或云計算等工作流調(diào)度系統(tǒng)中，如H.Topcuoglu于提出異構(gòu)分布式計算系統(tǒng)DAG任務(wù)調(diào)度模型及其著名HEFT調(diào)度算法已被實際應(yīng)用在了ASKALON網(wǎng)格工作流系統(tǒng)中。然而，因為網(wǎng)格、云計算或混合云計算等異構(gòu)分布式計算系統(tǒng)應(yīng)用發(fā)展及其追求更低成本和提升資源利用率需要，肯定會要包含四處理來自多個不一樣用（租）戶DAG應(yīng)用任務(wù)共享同一組資源調(diào)度問題，而且這些應(yīng)用DAG結(jié)構(gòu)類型、服務(wù)質(zhì)量QoS要求（通常包含完成時間、經(jīng)濟花費、可靠性和安全性等幾方面）也會多個多樣，這必將會產(chǎn)生多個DAG對系統(tǒng)資源爭用、完成時間最小化、調(diào)度公平性、費用優(yōu)化和資源利用提升等問題。針對多個DAG應(yīng)用任務(wù)共享一組資源調(diào)度這些問題，近幾年部分研究者們提出了部分相關(guān)處理措施，但因為這類調(diào)度問題研究才起步，有很多新問題亟待深入研究和處理。對這些問題研究和處理，將會對網(wǎng)格、云計算或混合云計算等異構(gòu)分布式計算環(huán)境下多用（租）戶DAG應(yīng)用發(fā)展起到主動推進作用，不僅含有理論研究價值，也有現(xiàn)實應(yīng)用價值。正是在這么研究背景下，本文圍繞異構(gòu)分布式計算環(huán)境下含有不一樣QoS需求類型多個DAG共享資源調(diào)度問題、含有期限約束多DAG共享資源調(diào)度吞吐量最大化問題、總費用優(yōu)化問題和費用優(yōu)化公平性問題等四個方面內(nèi)容展開了我們研究工作。1.2研究現(xiàn)實狀況多種類型DAG任務(wù)在多個處理單元上調(diào)度已被證實是NP（Non-deterministicPolynomial）完全難題，即完全多項式非確定性問題。早在70年代開始就有學(xué)者針對多種類型DAG任務(wù)模型在多種資源環(huán)境模型下調(diào)度相關(guān)問題進行展開了研究。現(xiàn)在盡管對DAG調(diào)度已經(jīng)有了很多研究結(jié)果，但中國外學(xué)者仍在繼續(xù)不停地對其進行深入探索和研究。這些相關(guān)研究結(jié)果，不管是從被調(diào)度對象DAG任務(wù)類型、目標資源環(huán)境和調(diào)度目標等幾方面模型來看，還是從處理問題所采取技術(shù)方法或數(shù)學(xué)模型上來看，全部有很多分類。首先從被調(diào)度對象DAG類型、資源環(huán)境和調(diào)度目標等方面能夠做以下部分歸類：（1）從用戶對DAG應(yīng)用起始和結(jié)束時間是否有限制來看，通常可分為無期限約束DAG調(diào)度和含有期限約束DAG調(diào)度。如前所述，在ASKALON網(wǎng)格工作流系統(tǒng)工作流定義工具AGWL中，作為可選項，用戶可依據(jù)應(yīng)用需要來指定工作流最晚完成時間等服務(wù)質(zhì)量（QoS）。那么這種帶有確定最晚完成時間期限約束DAG則屬于有期限約束類型DAG。（2）從調(diào)度目標環(huán)境可用資源數(shù)目是否固定來說，可分為數(shù)目固定和不固定兩類。針對資源數(shù)目不固定類型DAG調(diào)度方法和技術(shù)適適用于資源數(shù)量可隨DAG調(diào)度應(yīng)用需要動態(tài)擴展分布式系統(tǒng)。比如針對云計算環(huán)境動態(tài)彈性資源管理模式，以降低任務(wù)間數(shù)據(jù)傳輸聚簇方法或以降低資源數(shù)量為目標調(diào)度算法可歸為這一類。（3）從DAG圖中每個結(jié)點任務(wù)是否能夠繼續(xù)被分割而且能并行在任意數(shù)目機器上實施來看，DAG任務(wù)模型又可分為Moldable和Unmoldable兩種類型。通常來說，數(shù)據(jù)集處理、Web訪問日志分析等作業(yè)任務(wù)能夠?qū)⑷蝿?wù)依據(jù)并行處理資源結(jié)點數(shù)量被分為若干等分，可歸為Moldable類型DAG任務(wù)。很多著名算法，如DSC、HEFT算法所針正確是Unmoldable類型DAG。然而，兩種類型DAG調(diào)度相比，Unmoldable類型DAG調(diào)度方法是基礎(chǔ)，多數(shù)現(xiàn)有針對Moldable類型問題方法和技術(shù)全部是在Unmoldable類型DAG調(diào)度方法基礎(chǔ)上進行改善和擴展而來。實際上因為現(xiàn)實資源數(shù)量有限性和結(jié)點任務(wù)粒度大小相對性，Moldable類型DAG調(diào)度最終仍可歸為Unmoldable類型DAG調(diào)度問題。（4）從任務(wù)調(diào)度映射方案是否在DAG實施開始前就已確定來看，有動態(tài)調(diào)度和靜態(tài)調(diào)度兩類算法。靜態(tài)調(diào)度算法是指在DAG實施前依據(jù)目前有效可用計算資源和任務(wù)相關(guān)信息，依據(jù)一定方法確定好調(diào)度方案和映射關(guān)系方法。這類算法有很多，常見列表啟發(fā)式類算法均屬靜態(tài)類。而動態(tài)算法則是指系統(tǒng)運行過程中動態(tài)地為DAG任務(wù)進行調(diào)度和資源分配方法。（5）依據(jù)DAG任務(wù)是否包含必需和非必需計算成份，可分為正確計算DAG和非正確計算DAG任務(wù)調(diào)度算法。通常來說，在實時視頻和聲音等信息處理中常見這類非正確計算DAG任務(wù)。（6）依據(jù)DAG任務(wù)本身大小是否含有隨機性，可分為隨機DAG調(diào)度和非隨機DAG調(diào)度，而和隨機DAG調(diào)度算法親密相關(guān)調(diào)度目標之一則是對算法魯棒性（Robustness）評價。對隨機DAG調(diào)度魯棒性分析或意在改善調(diào)度魯棒性算法認為：DAG中任務(wù)本身因為輸入條件不一樣或程序類型等不一樣（如隨機搜索類遺傳算法程序），在實施前是無法確定DAG形狀、結(jié)構(gòu)或運算量，或因為資源在不一樣時間實施同一任務(wù)所需時間不確定等原因，進而造成DAG任務(wù)大小隨機性，所以需要依據(jù)任務(wù)隨機分布或資源狀態(tài)分布函數(shù)來優(yōu)化DAG任務(wù)調(diào)度。（7）從系統(tǒng)資源管理方面來看，能夠分為依據(jù)計算環(huán)境中資源可靠性而展開資源分配、調(diào)度算法研究和考慮資源負載平衡而展開調(diào)度優(yōu)化研究。（8）依據(jù)多個DAG應(yīng)用是否為共享資源，可分為單DAG和多DAG調(diào)度。為了追求更低成本和資源共享需要，其中相關(guān)多用（租）戶多DAG共享資源調(diào)度成為近幾年來熱點研究問題。DAG應(yīng)用任務(wù)不一樣于獨立任務(wù)調(diào)度，DAG任務(wù)結(jié)點之間數(shù)據(jù)傳輸依靠關(guān)系和網(wǎng)絡(luò)傳輸時延會造成任務(wù)在各分布式資源上留下很多空閑時隙，假如多個DAG共享資源混合調(diào)度，則這些空閑時隙能被多個DAG相互利用，將大大提升資源利用效率。其次，從所采取技術(shù)方法或數(shù)學(xué)模型角度來看，關(guān)鍵有以下幾類：（1）Markov決議過程方法。關(guān)鍵用于處理含有期限約束單個DAG調(diào)度及其費用優(yōu)化問題。關(guān)鍵思想是用Markov決議過程方法將整個DAG劃分為若干任務(wù)區(qū)間，假如能確保每一個任務(wù)區(qū)間在各自限制時間段內(nèi)完成，則工作流即可在約束期限之前完成，進而可求出最小費用任務(wù)資源映射方案。（2）列表啟發(fā)式方法。列表啟發(fā)式方法關(guān)鍵步驟是在DAG中全部任務(wù)被給予屬性并根據(jù)屬性優(yōu)先級大小降序放在任務(wù)表中，一旦任務(wù)要求被處理，高優(yōu)先級任務(wù)首先被調(diào)度。很多文件等所提出算法全部屬于這類方法，其中包含H.Topcuoglu所提出著名HEFT算法。其關(guān)鍵思想分為兩個階段，第一階段是依據(jù)任務(wù)實施時間和和后繼任務(wù)數(shù)據(jù)傳輸時間計算得到這個任務(wù)Ranku值（該任務(wù)結(jié)點到出口結(jié)點之間最大距離，在有些文件中也被記為B-level），將其作為調(diào)度優(yōu)先級，然后依據(jù)ranku值對DAG中任務(wù)進行倒序排序。第二個階段是依據(jù)第一個階段得到任務(wù)排序，選擇未被調(diào)度任務(wù)中優(yōu)先級最高任務(wù)，然后遍歷全部可用資源，查找到能夠最早完成處理該任務(wù)計算資源，并將該任務(wù)分配到資源上對應(yīng)空閑時隙中。（3）遺傳、進化等隨機搜索類方法。遺傳算法是現(xiàn)在廣泛使用處理優(yōu)化組合算法之一。它借鑒了生物學(xué)中遺傳過程中“適者生存”概念。遺傳算法首先假定潛在資源分配或任務(wù)映射匹配處理方案能夠表示為遺傳參數(shù)組合，成為染色體。能夠任意選擇一定數(shù)量染色體，然后全部染色體基于她們值排隊，通常使用輪轉(zhuǎn)法選擇適宜染色體，這能確保最適宜個體得到保留并作為父本。兩個被選中染色體能夠進行交叉配對復(fù)制產(chǎn)生后代。染色體復(fù)制會發(fā)生突變從而產(chǎn)生新個體。經(jīng)過上述過程數(shù)次反復(fù)，產(chǎn)生新染色體會逐步靠近最優(yōu)解。另外，應(yīng)用于DAG調(diào)度其它隨機搜索類方法還有進化算法、蟻群、粒子群等算法。即使隨機搜索類算法適用范圍廣，但通常來說時間復(fù)雜度較高。（4）任務(wù)復(fù)制方法類。任務(wù)復(fù)制降低數(shù)據(jù)傳輸時間，利用計算資源空閑時間復(fù)制前驅(qū)任務(wù)，以避免一些前驅(qū)任務(wù)數(shù)據(jù)傳輸時間過長，從而減小計算資源等候空閑時隙。（5）排隊論方法類。利用排隊論相關(guān)模型來處理DAG調(diào)度中資源優(yōu)化或資源預(yù)定相關(guān)問題。針對有時間限制網(wǎng)格工作流DAG任務(wù)調(diào)度，提出了利用“M/M/1/N/∞排隊論模型”和“Little公式”計算DAG中每個任務(wù)結(jié)點在每個資源上實施時間超出期限約束概率大小，然后進行資源優(yōu)化，最終確定任務(wù)和資源映射調(diào)度方案。（6）模糊理論及模糊聚類方法。模糊理論通常見于隨機DAG調(diào)度問題。針對任務(wù)實施時間不確定隨機DAG調(diào)度問題展開研究，利用模糊集擴展原理推算出DAG關(guān)鍵路徑長度可能性分布和可能關(guān)鍵任務(wù)組合，并在調(diào)度和監(jiān)控中，對那些盡管不是關(guān)鍵路徑任務(wù)，但其隸屬程度高任務(wù)和關(guān)鍵路徑任務(wù)一起給相同關(guān)鍵考慮。而模糊聚類方法常見于依據(jù)DAG調(diào)度目標環(huán)境中計算資源相關(guān)非功效屬性進行聚類并進行資源優(yōu)化處理。（7）隨機過程模型方法類。利用離散時間Markov隨機過程遍歷性或平穩(wěn)分布方法進行DAG吞吐量優(yōu)化，或利用有限狀態(tài)連續(xù)時間Markov隨機過程模型相關(guān)方法對DAG中關(guān)鍵區(qū)間任務(wù)進行資源狀態(tài)估計和資源可靠性優(yōu)化。（8）調(diào)度回溯方法類。該類方法通常見于處理DAG調(diào)度費用優(yōu)化問題。關(guān)鍵思想是，在對DAG中每個任務(wù)進行資源映射過程中，假如對某任務(wù)分配了速度較慢而且花費廉價資源后，需要計算整個DAG完成時間是否超出了時間限制。假如超出，則取消該任務(wù)在這較慢資源上分配，直到選擇到適宜資源為止。以上為現(xiàn)有DAG調(diào)度問題研究中常見部分技術(shù)和方法。伴隨網(wǎng)格、云計算和混合云計算等新型異構(gòu)分布式系統(tǒng)研究和應(yīng)用發(fā)展，依據(jù)系統(tǒng)資源結(jié)構(gòu)、資源管理模式、商業(yè)計費模式、資源可靠性等方面所展現(xiàn)出不一樣特點，現(xiàn)有這些處理DAG調(diào)度問題研究基礎(chǔ)上又以以下其中一個或若干個為調(diào)度目標：調(diào)度長度最小化、吞吐量最大化、資源利用率最大化、費用最低化、資源負載平衡、可靠性最大化、公平性最大化、達成很好魯棒性或滿足用戶指定期限約束要求等。伴隨新技術(shù)不停出現(xiàn)和研究深入發(fā)展，新調(diào)度目標也將會不停地出現(xiàn)，而且很多調(diào)度目標往往會相互沖突，需要依據(jù)具體應(yīng)用任務(wù)需要和資源環(huán)境模型來確定或進行一定平衡?，F(xiàn)在現(xiàn)有DAG任務(wù)調(diào)度研究絕大多數(shù)是針對一個DAG在多個資源上調(diào)度問題。這些研究針對不一樣類型DAG應(yīng)用、不一樣目標資源系統(tǒng)和不一樣調(diào)度目標，以不一樣技術(shù)方法處理了單DAG應(yīng)用任務(wù)調(diào)度中各方面問題，已基礎(chǔ)趨于成熟。然而，伴隨異構(gòu)分布式計算環(huán)境下多種應(yīng)用深入和發(fā)展，尤其是伴隨網(wǎng)格和云計算工作流等應(yīng)用系統(tǒng)追求更低成本和資源共享需要，肯定會包含四處理來自多用（租）戶多DAG共享一組異構(gòu)分布式計算資源調(diào)度問題。如中科院計算所韓艷波研究員在相關(guān)互聯(lián)網(wǎng)分布式系統(tǒng)XaaS（一切皆服務(wù)）模式第三方運行和優(yōu)化論著中指出：同一個物理平臺或應(yīng)用要服務(wù)盡可能多租戶，計算、存放和帶寬資源在多個應(yīng)用程序間進行共享和優(yōu)化調(diào)度，并深入提出了多個租戶共享同一個工作流引擎，但每個租戶全部能夠定義不相同工作流多工作流共享資源應(yīng)用模式。另外，PeterKacsuk也將工作流管理平臺分為兩大類：假如多用戶同時以協(xié)作方法監(jiān)控、控制和實施同一個任務(wù)圖，則稱為MC類型；假如所管理運行多用戶之間不一樣多個工作流DAG任務(wù)圖相互獨立，則稱為MI類型，即多DAG工作流系統(tǒng)。所以研究和處理多DAG共享資源調(diào)度問題對異構(gòu)（或互聯(lián)網(wǎng)）分布式計算系統(tǒng)未來發(fā)展含相關(guān)鍵意義。盡管很多現(xiàn)有處理單DAG調(diào)度問題技術(shù)方法能夠用于多DAG調(diào)度，如處理多DAG調(diào)度一個最直接簡單措施是，利用傳統(tǒng)單個DAG調(diào)度算法將這多個DAG逐次按次序調(diào)度完成，或是對新抵達DAG應(yīng)用實施需求，經(jīng)過采取申請新資源措施來進行調(diào)度，如Mao等針對云計算工作流多個DAG應(yīng)用調(diào)度實施問題，就采取了這種方法。然而，因為DAG任務(wù)和多個獨立任務(wù)調(diào)度最大區(qū)分在于每個DAG內(nèi)部任務(wù)之間有前后約束關(guān)系，而且任務(wù)間有數(shù)據(jù)傳輸關(guān)系。在部分異構(gòu)分布式系統(tǒng)中，比如效用網(wǎng)格或公有云計算系統(tǒng)，資源提供商往往采取基于租賃銷售模式和基于使用量和性能指標計費模式對用戶DAG應(yīng)用實施所提供計算服務(wù)進行計費。所以，針對網(wǎng)格或云計算等分布式計算系統(tǒng)下單個含有期限約束DAG應(yīng)用或工作流調(diào)度問題，相關(guān)研究關(guān)鍵調(diào)度目標之一就是費用最小化。一樣，當多個DAG共享一組資源進行混合調(diào)度時，也會存在在滿足期限內(nèi)完成條件下全部DAG總費用最小化問題，然而現(xiàn)在也未見對這一問題展開研究和討論報導(dǎo)。當含有期限約束多個DAG在共享資源組上進行混合調(diào)度時，顯然DAG吞吐量越大，DAG任務(wù)費用優(yōu)化空間越小。換句話說，DAG吞吐量調(diào)度目標和DAG費用優(yōu)化目標是相矛盾，存在依據(jù)具體系統(tǒng)或應(yīng)用需要對兩個調(diào)度目標進行平衡問題。然而從系統(tǒng)管理角度來看，吞吐量最大化是一個關(guān)鍵目標，所以在DAG吞吐量最大化基礎(chǔ)上降低全部DAG任務(wù)費用是需要研究和處理關(guān)鍵問題之一。不管選擇何種DAG調(diào)度算法，因為這種數(shù)據(jù)傳輸關(guān)系，總會在資源上出現(xiàn)空閑時隙，那么便會降低DAG調(diào)度任務(wù)吞吐量和資源利用率。假如將多個DAG共享資源進行混合調(diào)度，一個DAG任務(wù)會利用其它DAG任務(wù)所留下空閑時隙，將大大提升資源利用率和任務(wù)吞吐量。所以，多年來多DAG共享資源調(diào)度問題成為了研究熱點。

2相關(guān)定義及理論2.1DAG任務(wù)調(diào)度模型一個并行程序能夠抽象為一個帶偏序任務(wù)集，該任務(wù)集合可完全由一個有向無環(huán)圖DAG來表示，定義為：G＝（T，E）。其中，T＝{Ti│i=1，2，…，n}，表示n個任務(wù)節(jié)點集合，|T|＝n；E＝{Eij=（Ti，Tj）|Ti，Tj∈T，i<j}，表示擁有e條邊有向邊集合，|E|＝e。DAG中每個節(jié)點表示并行程序一個任務(wù)，它通常是程序中一段代碼或指令，是調(diào)度中最小單位，假設(shè)它是不能被搶占。節(jié)點Ti權(quán)重稱為計算成本，記作W（Ti）；DAG中任意一條邊，記作Eij或（Ti，Tj），表示節(jié)點Ti和Tj之間存在時間上前后關(guān)系和通信關(guān)系，每條邊權(quán)重稱為通信成本，記作C（Eij）或C（Ti，Tj）。一條邊源節(jié)點稱為父節(jié)點，而其終點節(jié)點稱為子節(jié)點。在DAG中，沒有父節(jié)點節(jié)點稱為入口節(jié)點，而沒有子節(jié)點節(jié)點稱為出口節(jié)點。假如在一個DAG中，不止一個入口節(jié)點，那么我們虛構(gòu)一個零計算成本入口節(jié)點，全部真正入口節(jié)點經(jīng)過一條權(quán)值為零虛邊和其相連；一樣，假如不止一個出口節(jié)點，就虛構(gòu)一個零計算成本出口節(jié)點，全部真正出口節(jié)點全部和它經(jīng)過權(quán)值為零虛邊相連。所以，任何一個DAG，全部可看作只有一個入口節(jié)點和一個出口節(jié)點。顯而易見，增加虛擬節(jié)點和虛擬邊并不影響對DAG調(diào)度。圖2.1是一個一般DAG，圖中圓圈表示節(jié)點，圓圈中符號表示任務(wù)節(jié)點編號，圓圈外左邊方框中數(shù)字表示該節(jié)點計算成本；圖中帶箭頭邊表示通信邊，邊上數(shù)字表示兩個節(jié)點之間計算成本。節(jié)點T1為入口節(jié)點，節(jié)點T10為出口節(jié)點。圖2.1一個一般DAG圖2.2計算環(huán)境異構(gòu)性一個異構(gòu)并行計算系統(tǒng)定義[10-11]為：由一組異構(gòu)計算節(jié)點和異構(gòu)互聯(lián)網(wǎng)絡(luò)形成計算環(huán)境。計算節(jié)點異構(gòu)性指其資源各方面差異性，包含處理器處理能力差異、內(nèi)存大小及訪問差異、I/O訪問速度差異和操作系統(tǒng)不相同等，本文討論調(diào)度問題范圍僅限于處理器資源調(diào)度。異構(gòu)網(wǎng)絡(luò)指連接計算節(jié)點之間互聯(lián)網(wǎng)絡(luò)由不一樣類型網(wǎng)絡(luò)組成，比如能夠是以太網(wǎng)或是Myrinet等等。類似于并行程序能夠表示為DAG，一個異構(gòu)計算系統(tǒng)也能夠表示為一個無向圖。其定義為：R＝（P，L）。其中，P＝{Pk│k=1，2，…，m}，表示m個處理器集合，其中，Pk是異構(gòu)計算系統(tǒng)中任一處理器，|P|=m；L＝{Lij=（Pi，Pj）|Pi，Pj∈P，i≠j}，表示計算節(jié)點之間通信連接邊集合，其中，Lij或（Pi，Pj）表示計算節(jié)點Pi和Pj之間物理通信連接。怎樣量化地表示處理器處理能力差異性。有兩種方法：第一個是以處理器主頻作為度量處理器計算能力唯一標準，對任何類型任務(wù)來說，處理器物理速度越快，其處理任務(wù)時間越短；另一個方法是處理器和計算任務(wù)結(jié)合起來考慮，即處理器對任務(wù)計算時間并不和處理器主頻呈固定百分比，部分處理器更適累計算某種類型任務(wù)而不適累計算另一類任務(wù)，適合是否并不以其物理速度為準。第二種方法和實際情況更符合，也更復(fù)雜，所以我們采取第二種方法。所以，處理器計算能力差異性度量值記作：W（Ti：Pk），表示任務(wù)Ti在處理器Pk上計算時間，表2.1列出了圖2.1中DAG中任務(wù)節(jié)點在三個處理器組成處理器組中W（Ti：Pk）。表2.1圖2.1中DAGW（Ti：Pk）Ti12345678910P1141311131213751821P2161913813161511127P3918197109111420162.3云環(huán)境下任務(wù)調(diào)度算法概述因為云環(huán)境下資源分布性、異構(gòu)性和動態(tài)性，和用戶數(shù)量、用戶應(yīng)用程序?qū)Y源需求等全部在不停改變，使得任務(wù)調(diào)度變得極其關(guān)鍵、極其復(fù)雜，所以需要動態(tài)調(diào)度任務(wù)、動態(tài)劃分或釋放不一樣物理和虛擬資源來適應(yīng)動態(tài)改變環(huán)境。對此，中國外己做了大量研究工作，前后提出了多種調(diào)度算法。本節(jié)首先概述性介紹了云環(huán)境下任務(wù)調(diào)度。其次對云環(huán)境下任務(wù)調(diào)度過程、任務(wù)調(diào)度系統(tǒng)、任務(wù)調(diào)度特點及部分經(jīng)典相關(guān)單DAG、多DAG工作流調(diào)度算法進行了討論。2.3.1云環(huán)境下任務(wù)調(diào)度技術(shù)綜述云環(huán)境下任務(wù)調(diào)度系統(tǒng)通常由三個部分組成[12]：（1）資源篩選：在全部可用空閑資源中找出滿足用戶需求資源；（2）任務(wù)-資源映射：從滿足要求資源中選擇一個適宜資源分配給對應(yīng)任務(wù)，實現(xiàn)任務(wù)和資源一一對應(yīng)關(guān)系；（3）任務(wù)實施：把任務(wù)調(diào)度到映射資源上去實施。云環(huán)境下作業(yè)調(diào)度分當?shù)卣{(diào)度和網(wǎng)格調(diào)度兩個階段。當?shù)卣{(diào)度又稱為低級調(diào)度，當收到用戶提交DAG工作流時，優(yōu)先選擇當?shù)刭Y源對其進行調(diào)度實施。網(wǎng)格調(diào)度又稱為高級調(diào)度，網(wǎng)格調(diào)度器并不直接控制系統(tǒng)中各個資源[13]，而是動態(tài)依據(jù)任務(wù)對資源具體需求，為其選擇最適合計算資源，這么，能夠使資源使用不受所屬區(qū)域限制，提升資源利用率，充足利用不一樣地域資源優(yōu)勢，最大程度實現(xiàn)各地資源協(xié)同工作。2.3.2云環(huán)境下任務(wù)調(diào)度過程在云環(huán)境下，用戶提交DAG工作流通常由一個工作流管理系統(tǒng)統(tǒng)一進行管理和調(diào)度。從系統(tǒng)管理方面來看，工作流管理系統(tǒng)負責處理用戶工作流提交、資源管理和分配、數(shù)據(jù)移動和工作流調(diào)度，而且盡可能地提升資源利用率和工作流任務(wù)吞吐量?，F(xiàn)在通用模式是將大型應(yīng)用任務(wù)分解為多個相關(guān)子任務(wù)，其中每個子任務(wù)全部有獨特資源需求，然后將子任務(wù)提交到調(diào)度系統(tǒng)進行調(diào)度。依據(jù)任務(wù)之間是否存在數(shù)據(jù)依靠關(guān)系，可將任務(wù)分為兩種類型：（1）依靠任務(wù)：即任務(wù)之間存在依靠和前后時序關(guān)系，通常見DAG圖來描述任務(wù)之間這種依靠關(guān)系，而且采取多種啟發(fā)式思想對映射問題進行簡化[14-15]。（2）元任務(wù)（MetaTask）[16]：即相互之間獨立任務(wù)，任務(wù)之間不存在數(shù)據(jù)依靠關(guān)系，任務(wù)調(diào)度實施相互之間不受影響。圖2.2對云環(huán)境下任務(wù)調(diào)度過程進行了描述。其中資源監(jiān)控和發(fā)覺服務(wù)MDS（MonitoringandDiscoveryService）作用是搜集和公布系統(tǒng)中資源狀態(tài)信息。圖2.2云環(huán)境下任務(wù)調(diào)度步驟圖2.3.3云環(huán)境下任務(wù)調(diào)度系統(tǒng)目前，云技術(shù)在很多領(lǐng)域全部得到了廣泛應(yīng)用，針對多種不一樣云應(yīng)用，提出了很多有效云環(huán)境下任務(wù)調(diào)度模型和算法。下面將對多個比較流行任務(wù)調(diào)度系統(tǒng)進行簡單介紹：Globus：此項目是由美國Argonne試驗室等進行研發(fā)，Globus對信息安全、信息服務(wù)、資源管理、數(shù)據(jù)管理和開發(fā)環(huán)境等關(guān)鍵理論和技術(shù)進行了深入研究，并開發(fā)了軟件包，能夠在多個平臺上運行。Globus資源描述和訪問采取可擴展式模型、分布式基于查詢發(fā)覺、層次命名空間、軟QoS、LDAP網(wǎng)絡(luò)目錄存放、周期性推送分發(fā)；資源管理體系結(jié)構(gòu)采取經(jīng)典層次模型等。Nimrod/G：由澳大利亞Monash大學(xué)開發(fā)，它采取Globus中間件作為網(wǎng)格接口，基于經(jīng)濟模型提供一系列計算資源。它遵照層次、分布式調(diào)度模型，并采取由預(yù)算和截止期限所驅(qū)動應(yīng)用級任務(wù)調(diào)度策略等，但Nimrod/G不能進行有效資源計費。P-GRADE平臺：P-GRADE平臺支持多個DAG工作流在實施過程中所用資源之間含有互操作性，而且支持多個不一樣用戶以協(xié)作方法來完成各自DAG工作流。該平臺含有以下功效：（1）分類并定義具體云環(huán)境；（2）創(chuàng)建并修改工作流應(yīng)用；（3）管理云環(huán)境相關(guān)證書；（4）控制工作流在云資源中運行過程；（5）監(jiān)督并實時觀察工作流及其子任務(wù)實施進展。另外還存在GHS、E-Science、DataGrid、Webflow、AppLeS等多個調(diào)度系統(tǒng)，在此不再作介紹。2.3.4云環(huán)境下任務(wù)調(diào)度特點云環(huán)境下任務(wù)調(diào)度含有以下多個特點：（1）任務(wù)調(diào)度是在異構(gòu)平臺上進行。云系統(tǒng)是由分布在廣域網(wǎng)上多種類型個人計算機、工作站、大型機群、大型存放設(shè)備、服務(wù)器或其它精密儀器等組成，可運行在UNIX，Windows等多種操作系統(tǒng)下，所以云系統(tǒng)中任務(wù)調(diào)度必需考慮平臺異構(gòu)性。（2）任務(wù)調(diào)度能夠動態(tài)自適應(yīng)。云中資源不僅是異構(gòu)，而且云系統(tǒng)結(jié)構(gòu)總是在不停地改變，隨時有新資源加入系統(tǒng)、退出系統(tǒng)、有資源出現(xiàn)故障等，且用戶對資源需求也是動態(tài)改變，所以任務(wù)調(diào)度必需能夠滿足這種動態(tài)特征，從而為用戶提供愈加好服務(wù)。（3）任務(wù)調(diào)度是分布式。云系統(tǒng)分布式特征，使其極難實現(xiàn)全局統(tǒng)一集中資源管理和任務(wù)調(diào)度管理，所以，任務(wù)調(diào)度必需是分布式，從而避免造成系統(tǒng)瓶頸。（4）任務(wù)調(diào)度必需滿足系統(tǒng)不停擴展要求。伴隨資源共享程度越來越高，云系統(tǒng)規(guī)模必將不停擴大，所以，在資源數(shù)量和用戶應(yīng)用不停增加情況下，云系統(tǒng)任務(wù)調(diào)度必需含有可擴展性。2.3.5云環(huán)境下任務(wù)調(diào)度算法早期任務(wù)調(diào)度算法關(guān)鍵考慮網(wǎng)格資源分布性和異構(gòu)性，稱為異構(gòu)環(huán)境下獨立任務(wù)調(diào)度算法，包含OLB（OpportunisticLoadBalancing）、Round-RobinAlgorithm、MET（MinimumExecutionTime）、SA（SwitchingA1gorithm）、KPB（K-PercentBest）、Max-Min、Min-Min等等。這些算法通常僅僅優(yōu)化了任務(wù)某首先，如實施時間跨度、負載平衡或任務(wù)吞吐量等。在異構(gòu)環(huán)境中，啟發(fā)式算法通常是用來處理元任務(wù)調(diào)度問題有效方法之一，依據(jù)任務(wù)和資源對應(yīng)關(guān)系是否能夠?qū)崟r、動態(tài)調(diào)整，將這些啟發(fā)式任務(wù)調(diào)度算法劃分為靜態(tài)調(diào)度算法和動態(tài)調(diào)度算法兩大類。靜態(tài)調(diào)度算法是指任務(wù)和資源對應(yīng)關(guān)系在實施任務(wù)之前就已經(jīng)全部確定，在整個實施任務(wù)過程中不再做任何調(diào)整。常見有Min-min、Max-min、P-timePetri網(wǎng)模型算法、任務(wù)截止時間限制下MapReduce算法等靜態(tài)調(diào)度算法。（1）Min-min：首先，計算每個任務(wù)在每個資源上期望完成時間，依據(jù)計算結(jié)果可知每個任務(wù)最早完成時間及其對應(yīng)資源；然后，將含有最小完成時間任務(wù)分配給能夠最早完成該任務(wù)資源，同時，將已分配任務(wù)從初始任務(wù)集合中刪除；最終，每分配完一個任務(wù)就立即更新資源就緒時間。如此反復(fù)，直到全部任務(wù)分配完成。（2）Max-min：Max-min算法和Min-min算法思想基礎(chǔ)相同，區(qū)分是Max-min算法優(yōu)先考慮實施時間較長任務(wù)，當取得每個任務(wù)最早完成時間及其對應(yīng)資源時，不是將含有最小最早完成時間任務(wù)進行分配，而是對含有最大最早完成時間任務(wù)進行分配。（3）P-timePetri網(wǎng)模型算法：經(jīng)典Petri網(wǎng)由兩種節(jié)點（其中圓形節(jié)點代表庫所，方形節(jié)點代表變遷）、有向?。ㄟB接庫所和變遷）、和令牌等元素組成，Token是庫所中動態(tài)對象，能夠從一個庫所移動到另一個庫所，兩個庫所或兩個變遷之間不許可有弧，庫所能夠擁有任意數(shù)量令牌。（4）任務(wù)截止時間限制下MapReduce算法：任務(wù)截止時間限制下MapReduce算法是在Hadoop平臺上實現(xiàn)。該算法許可用戶對任務(wù)限定一個最晚完成截止時間，經(jīng)過計算資源節(jié)點計算能力，對全部資源進行分類，形成異構(gòu)環(huán)境下不一樣計算能力、不一樣層次資源組合，該算法能夠優(yōu)先利用當?shù)財?shù)據(jù)資源，提升資源系統(tǒng)吞吐量，而且該算法能夠經(jīng)過計算任務(wù)合成和任務(wù)分解之間時隙，來選擇適宜任務(wù)進行調(diào)度。接下來對動態(tài)調(diào)度算法進行簡單描述。動態(tài)調(diào)度算法是指，部分機器-任務(wù)映射策略在實施任務(wù)調(diào)度期間依據(jù)實際情況進行確定?，F(xiàn)有動態(tài)調(diào)度算法能夠分為兩類：在線模式和批模式（Batchmode）。在線模式啟發(fā)式動態(tài)任務(wù)調(diào)度算法，是指任務(wù)一經(jīng)抵達立即給它分配可用資源。這類算法環(huán)境適應(yīng)性好、算法靈活、能有效利用資源、避免先抵達任務(wù)必需等候一段時間、含有實時性特點，經(jīng)典在線模式動態(tài)調(diào)度有OLB、MET、輪盤算法等。（1）OLB（OpportunisticLoadBalancing）算法：機會負載均衡算法是最簡單一個算法。該算法不考慮任務(wù)估計實施時間，隨機地將任務(wù)集合中任意一個任務(wù)分配給機器資源集合中任一個可用機器資源，充足利用全部可用機器資源，算法實現(xiàn)比較簡單；但該算法未考慮任務(wù)估計實施時間，假如某個任務(wù)在某臺機器上實施時間過長，則會使整個任務(wù)完成時間增加。（2）MET算法（MinimumExecutionTime）：MET算法是先計算出每個任務(wù)在每個機器資源上實施時間；其次，找出每個任務(wù)所對應(yīng)含有最小估計實施時間機器；最終以任意次序?qū)⒏鱾€任務(wù)分配給選定機器，MET算法關(guān)鍵目標是把每個任務(wù)盡可能地分配給能夠最快完成該任務(wù)機器。（3）輪盤算法（Round-RobinAlgorithm）：輪盤算法是把抵達DAG工作流，經(jīng)過添加一個入口節(jié)點和一個出口節(jié)點合并成一個新DAG工作流，其中，入口節(jié)點和它全部直接后繼節(jié)點、出口節(jié)點和它全部直接前驅(qū)節(jié)點之間通信代價全部為零。該算法在調(diào)度過程中，假如正在實施任務(wù)屬于某個DAG工作流，則在該時刻DAG工作流中其它任務(wù)將不會被實施，即同一個DAG工作流中任務(wù)不會同時被實施。該算法不適合處理對實時性要求比較高DAG工作流調(diào)度。批模式啟發(fā)式動態(tài)任務(wù)調(diào)度算法是當任務(wù)集合中任務(wù)數(shù)量達成一定數(shù)量，或達成一個預(yù)定時間間隔以后，才進行任務(wù)和資源匹配。標準上，靜態(tài)調(diào)度算法全部能夠用作批模式算法。批模式算法最大優(yōu)點是實時性、高效性。經(jīng)典批模式調(diào)度算法有快速貪吃算法、最大時間跨度算法、令牌控制算法等。（1）快速貪吃算法（Fast-Greedy）：快速貪吃算法基礎(chǔ)思想是依據(jù)抵達任務(wù)集合次序，計算出某個任務(wù)相對于全部機器估計完成時間最小值，和含有最小值機器編號，將該任務(wù)匹配給對應(yīng)機器。但因為該算法是根據(jù)任務(wù)抵達前后次序進行資源分配，可能會使后抵達任務(wù)因為長時間等候而無法分配給真正能夠使其完成時間最小機器。（2）最大時間跨度算法（MaximumIntervalheuristic，Max-Int）：Max-Int算法計算每個任務(wù)最小最早完成時間和對應(yīng)機器，和該任務(wù)次小最早完成時間和對應(yīng)機器，同時計算次小最早完成時間和最小最早完成時間差，即時間跨度，依據(jù)時間跨度大小對全部任務(wù)進行排序，將時間跨度最大任務(wù)分配到取得最小最早完成時間機器上。直到全部任務(wù)分配完成。（3）令牌控制算法（TokenPlayerAlgorithm）：令牌控制算法在工作流實施過程中能夠檢測出不正?，F(xiàn)象，并經(jīng)過診療功效查找出現(xiàn)不正?，F(xiàn)象原因。當令牌可用時，判定是否支持變遷，若變遷不在系統(tǒng)沖突中，則初始化令牌，并產(chǎn)生一個新操作；若變遷在系統(tǒng)沖突中，則隔離該系統(tǒng)沖突，并判定能否取消該變遷。假如沖突處理機制在確保令牌可用前提下，許可撤銷變遷，則撤銷該變遷，同時向系統(tǒng)發(fā)送一個初始化操作新消息。3靜態(tài)DAG任務(wù)調(diào)度算法3.1試驗環(huán)境介紹本文實現(xiàn)算法均使用Java語言在Eclipse集成開發(fā)環(huán)境下完成。為了愈加好地實現(xiàn)算法性能比較，需要一款界面友好DAG調(diào)度仿真軟件作為支撐，經(jīng)過GUI界面幫助能夠愈加高效地進行算法性能比較。為此，我們開發(fā)了圖3.1DAG調(diào)度仿真器。圖3.1DAG調(diào)度仿真器該仿真器能實現(xiàn)多個DAG隨機生成，也支持XML格式DAG文件讀入。然后DAG經(jīng)過各個算法處理，生成開銷和時間等性能數(shù)據(jù)，再以文本和圖表格式顯示出來。這么大大提升了算法正確性驗證和性能之間橫向比較。3.2靜態(tài)調(diào)度算法HEFT算法HEFT[2]是一個處理器數(shù)目受限異構(gòu)處理器調(diào)度算法，算法分為兩個關(guān)鍵步驟：一是任務(wù)優(yōu)先等級確實定，即計算全部任務(wù)優(yōu)先等級并依據(jù)優(yōu)先等級排序；另一個是處理器選擇，即依據(jù)任務(wù)優(yōu)先級次序把每個選擇任務(wù)調(diào)度到最適合處理器上。HEFT調(diào)度算法步驟圖3.2所表示。圖3.2HEFT調(diào)度算法任務(wù)優(yōu)先等級確實定：關(guān)鍵依據(jù)任務(wù)Ranku值來確定任務(wù)優(yōu)先等級，任務(wù)Ranku值是基于任務(wù)平均計算成本和通信成本，任務(wù)表是根據(jù)任務(wù)Ranku值降序排列，即Ranku值最大任務(wù)排在表頭。假如有兩個或兩個以上任務(wù)含有相同Ranku值，那么采取隨機選擇方法。從Ranku定義來看，這種依據(jù)降序排列方法滿足了DAG中任務(wù)之間優(yōu)先關(guān)系。處理器選擇：處理器選擇最基礎(chǔ)標準就是把需調(diào)度任務(wù)分配給能使任務(wù)完成時間最早處理器。對于大多數(shù)任務(wù)調(diào)度算法來說，處理器P最早可用時刻是處理器P完成了分配給它最終一個任務(wù)時刻。然而，算法HEFT不一樣是它采取一個額外插入策略，即可能在已經(jīng)調(diào)度到同一個處理器上兩個任務(wù)之間插入目前調(diào)度任務(wù)，當然，在兩個已經(jīng)調(diào)度任務(wù)中間時間空隙調(diào)度目前任務(wù)標準是必需滿足任務(wù)之間優(yōu)先關(guān)系。算法HEFT時間復(fù)雜度為O（e×m），其中e是DAG中通信邊數(shù)目，而m是處理器數(shù)目。對于一個密集任務(wù)圖來說，通信邊數(shù)目是和成正比（n是DAG中任務(wù)節(jié)點數(shù)目），所以時間復(fù)雜度也等于O（×）。從一個經(jīng)典例子角度來看，算法HEFT應(yīng)用于圖2.1DAG，得到調(diào)度長度為80。算法HEFT對任務(wù)調(diào)度次序為：T1，T3，T4，T2，T5，T6，T9，T7，T8，T10。3.3靜態(tài)調(diào)度算法CPOP同HEFT一樣，算法CPOP[2]由確定任務(wù)優(yōu)先級和處理器選擇兩個步驟組成。但確定任務(wù)優(yōu)先級方法和選擇處理器策略全部和HEFT不一樣。CPOP調(diào)度算法圖3.3所表示。圖3.3CPOP調(diào)度算法任務(wù)優(yōu)先級確實定：先計算任務(wù)BLh和TLh值，二者之和作為任務(wù)優(yōu)先級值。假如任務(wù)優(yōu)先級值等于DAG關(guān)鍵路徑長度CP，那么該任務(wù)稱為關(guān)鍵路徑任務(wù)。毫無疑問，入口任務(wù)Tentry優(yōu)先級值等于關(guān)鍵路徑長度CP，它是關(guān)鍵路徑任務(wù)。在調(diào)度過程任一時刻，任務(wù)優(yōu)先級隊列中包含全部就緒任務(wù)，采取了二元樹結(jié)構(gòu)來改善優(yōu)先級隊列操作，所以在該優(yōu)先級隊列中插入和刪除一個任務(wù)時間是O（logn），而尋求最大值時間是O（1）。處理器選擇：對關(guān)鍵路徑任務(wù)和非關(guān)鍵路徑任務(wù)采取不一樣策略，關(guān)鍵路徑任務(wù)只能被調(diào)度到關(guān)鍵路徑處理器，而非關(guān)鍵路徑任務(wù)能夠調(diào)度到全部處理器上。所謂關(guān)鍵路徑處理器是指全部關(guān)鍵路徑任務(wù)在其上實施時，計算成本之和最小處理器。在對優(yōu)先級隊列中任務(wù)調(diào)度時，假如選擇任務(wù)是關(guān)鍵路徑任務(wù)，則把它分配給關(guān)鍵路徑處理器；假如選擇任務(wù)不是關(guān)鍵路徑任務(wù)，則根據(jù)HEFT算法標準選擇處理器，即選擇使任務(wù)完成時間最早處理器。在調(diào)度關(guān)鍵路徑任務(wù)和非關(guān)鍵路徑任務(wù)時，全部考慮和HEFT算法相同插入策略。算法CPOP時間復(fù)雜度也為O（e×m），證實從略。相對于圖2.1例子，采取CPOP算法調(diào)度長度是86，關(guān)鍵路徑任務(wù)是T1，T2，T9，T10，假如全部關(guān)鍵路徑任務(wù)分別調(diào)度四處理器P1，P2和P3上，則計算成本之和分別為66，54和63。所以P2被選為關(guān)鍵路徑處理器。依據(jù)算法CPOP，圖2.1中DAG調(diào)度次序為：T1，T2，T3，T7，T4，T5，T9，T6，T8，T10。3.4基于表調(diào)度任務(wù)調(diào)度算法LBP絕大多數(shù)靜態(tài)啟發(fā)式任務(wù)調(diào)度算法基于古典表調(diào)度思想，其基礎(chǔ)內(nèi)容能夠概括為兩個獨立步驟。第一步：把任務(wù)圖中全部任務(wù)根據(jù)某種優(yōu)先級高低次序排列成調(diào)度表。第二步：從調(diào)度表中依次取出各個任務(wù)，將任務(wù)分配到使它完成時間最早處理器上。HEFT算法就是經(jīng)典靜態(tài)表調(diào)度算法。分析表調(diào)度算法基礎(chǔ)思想，我們認為在步驟一最關(guān)鍵原因是怎樣選擇任務(wù)優(yōu)先等級。決定任務(wù)優(yōu)先等級時采取兩個最基礎(chǔ)屬性是T-LEVEL（任務(wù)TiT-LEVEL是指從入口任務(wù)到Ti一條最長路徑長度）和B-LEVEL（任務(wù)TiB-LEVEL是指從任務(wù)Ti到出口任務(wù)一條最長路徑長度），T-LEVEL值和任務(wù)最早開啟時間有很大關(guān)系，而B-LEVEL值和任務(wù)圖關(guān)鍵路徑相關(guān)。HEFT算法其實是采取B-LEVEL作為其任務(wù)優(yōu)先等級，只不過考慮到對任務(wù)Ti各個處理器處理時間不一樣，在計算任務(wù)處理時間時采取了全部處理器處理時間平均值。對于步驟二來說，大部分算法全部無異義，只不過有算法許可在兩個任務(wù)處理時間間隙中插入目前任務(wù)，HEFT法即是如此，而有算法只許可目前任務(wù)在所在處理器最終一個任務(wù)后調(diào)度。前者調(diào)度開銷顯著比后者高。LBP[19]算法關(guān)鍵在步驟一作出了改善，在選擇優(yōu)先級屬性時并不是單純地采取T-LEVEL或B-LEVEL。因為它們只是考慮了影響調(diào)度性能一個方面，或著重于單個任務(wù)必需盡早開啟，或著重于關(guān)鍵路徑上任務(wù)應(yīng)盡早調(diào)度。但從整體來看，這些考慮全部只可能是局部較優(yōu)而非全局較優(yōu)。LBP具體確定任務(wù)優(yōu)先級算法概括以下：第一步計算DAG圖中每個任務(wù)層次，某個任務(wù)Ti層次值IL（Ti）為入口任務(wù)到Ti之間邊數(shù)之和(虛邊不計算在內(nèi))，入口任務(wù)層次值為零；第二步計算DAG圖中每個任務(wù)分支值，某個任務(wù)Ti分支值B（Ti）為任務(wù)Ti全部出口邊權(quán)值之和；第三步依據(jù)任務(wù)Ti層次值IL（Ti）和分支值B（Ti）來決定其優(yōu)先級。層次值IL（Ti）越小其優(yōu)先級越高，對含有一樣層次值任務(wù)來說，分支值B（Ti）越大其優(yōu)先級越高。特殊情況（出現(xiàn)可能性較?。┫?，假如一些任務(wù)層次和分支值全部相同話，則經(jīng)過計算它們T-LEVEL值（以Tl（Ti）表示）來決定優(yōu)先級高低，Tl（Ti）值越小任務(wù)優(yōu)先級越高。包含決定調(diào)度表優(yōu)先級在內(nèi)，整個LBP算法步驟以下：LBP算法1：計算DAG中全部任務(wù)Ti（i＝1，2，…，k）層次值IL（Ti）、分支值B（Ti）T-LEVEL值Tl（Ti）；2：依據(jù)IL（Ti）、B（Ti）和Tl（Ti）大小，依攝影應(yīng)策略計算任務(wù)Ti優(yōu)先級，然后把任務(wù)Ti根據(jù)優(yōu)先級從大到小次序放入任務(wù)調(diào)度表；3：While任務(wù)調(diào)度表中存在沒有被調(diào)度任務(wù)Do4：從任務(wù)調(diào)度表中取出表頭任務(wù)Ti準備對其進行調(diào)度；5：For空閑主機集合中每一個處理器Pj（j＝1，2，…，m）Do6：計算任務(wù)Ti在處理器Pj上最早完成時間，在計算最早完成時間時不考慮在任意兩個已調(diào)度任務(wù)時間間隙中插入目前任務(wù)；7：把任務(wù)Ti調(diào)度到使其含有最小最早完成時間處理器上（假如兩臺或以上處理器含有相同最小最早完成時間，則把調(diào)度到負載最輕處理器上）；8：Endwhile3.5算法時間復(fù)雜度和調(diào)度性能比較3.5.1時間復(fù)雜度HEFT和CPOP算法時間復(fù)雜度為O（e×m），其中e為DAG中表示通信總邊數(shù)，m為工作處理器總數(shù)。它們算法時間復(fù)雜度關(guān)鍵反應(yīng)在處理器選擇策略上，因為LBP算法和HEFT算法一樣全部是采取貪心算法選擇處理器，不一樣之處于于HEFT算法考慮在任意兩個已調(diào)度任務(wù)時間間隙中插入目前任務(wù)，而LBP算法只考慮在全部處理器上最終一個已調(diào)度任務(wù)后調(diào)度目前任務(wù)，所以LBP算法肯定不會比HEFT算法高，所以它時間復(fù)雜度也是O（e×m）。3.5.2調(diào)度性能我們以調(diào)度長度這一反應(yīng)調(diào)度性能關(guān)鍵指標來評價LBP算法和HEFT及CPOP算法好壞。對于一樣DAG（圖2.1所表示）和一樣工作處理器集合，HEFT調(diào)度次序是{T1，T3，T4，T2，T5，T6，T9，T7，T8，T10}，CPOP調(diào)度次序是{T1，T2，T3，T7，T4，T5，T9，T6，T8，T10}，而采取LBP算法調(diào)度次序是{T1，T4，T2，T3，T6，T5，T7，T9，T8，T10}。對應(yīng)地，HEFT調(diào)度長度為80，CPOP調(diào)度長度為86，而LBP算法調(diào)度長度為77。3.6試驗和分析我們采取和文件[2]相同隨機任務(wù)圖進行了仿真試驗。這些隨機生成DAG由上十至上百個任務(wù)節(jié)點組成，節(jié)點和邊權(quán)重也是隨機生成，但CCR（通信成本和計算成本比率，即邊和節(jié)點權(quán)重之比）改變范圍控制在0.1～10之間。我們關(guān)鍵從算法平均運行時間方面對HEFT、CPOP和LBP算法進行了試驗比較，從圖3.4能夠看出，在相同試驗條件下，LBP算法平均運行時間稍低于HEFT和CPOP算法。圖3.4算法平均運行時間比較

4含有多優(yōu)先級多DAG混合調(diào)度4.1含有多優(yōu)先級多DAG調(diào)度系統(tǒng)模型含有多優(yōu)先級多DAG調(diào)度系統(tǒng)模型圖4.1所表示，它由3部分組成，分別是：多DAG接收和優(yōu)先級判別子系統(tǒng)（Receiver&PriorityIdentification）、多DAG調(diào)度子系統(tǒng)（Multi-DAGScheduler）和對應(yīng)于資源Mi等候?qū)嵤┤蝿?wù)隊列組（Qw-mi：QueueofTaskstobeExecutedonMi）。在多租戶DAG工作流系統(tǒng)中，不一樣用戶會在不一樣時間提交DAG。這些DAG抵達后，由工作流接收和優(yōu)先級判別子系統(tǒng)來管理和識別新DAG優(yōu)先級，并和較早時間抵達正在被調(diào)度實施DAG優(yōu)先級進行比較，為多DAG工作流調(diào)度子系統(tǒng)調(diào)度提供調(diào)度信息。然后，由多DAG工作流調(diào)度子系統(tǒng)依據(jù)混合調(diào)度策略將這些多DAG任務(wù)根據(jù)實施次序分配至系統(tǒng)第3部分，即待實施任務(wù)隊列組Qw-mi中。每次資源Mi實施完一個任務(wù)后，依次從和其相對應(yīng)Qw-mi中取下一個任務(wù)實施。圖4.1多優(yōu)先級DAG管理系統(tǒng)模型本文相關(guān)DAG工作流任務(wù)圖表示、定義和向上權(quán)值Ranku（ni）等和文件[2][20]相關(guān)定義和方法一致，這里不再反復(fù)。在多租戶多DAG系統(tǒng)模型中，資源提供者是依據(jù)用戶任務(wù)運行時間向用戶收取費用。對CO-DAG類型用戶來說，首要QoS需求是整個DAG實施費用最低。假如Pmi表示資源Mj單位時間租用價格，則任務(wù)ni在資源Mj上所發(fā)生費用為Eij=Pmiwij（wij表示任務(wù)結(jié)點ni機器資源Mj上估量運行時間，參見文件[2])。下面經(jīng)過圖4.2兩個工作流實例DAG-A和DAG-B調(diào)度來說明本文介紹調(diào)度方法和策略。這兩個DAG復(fù)雜度、結(jié)構(gòu)和各項參數(shù)基礎(chǔ)和文件[2][20]中實例一樣，機器資源數(shù)為3個。假設(shè)兩個DAG中每項任務(wù)在每個機器資源上實施時間為表4.1，那么計算可得到每個任務(wù)向上權(quán)值Ranku(ni)，見表4.2。 (a)DAG-A (b)DAG-B圖4.2兩個DAG工作流實例表4.1DAG-A和DAG-B中各任務(wù)在機器上實施時間DAGDAG-ADAG-BniA1A2A3A4A5A6A7A8A9A10B1B2B3B4B5M1,Pmi=1.01413111312137518214918217M2,Pmi=1.28191381316151112751017156M3,Pmi=1.11618191710911142016611161915表4.2兩個DAG任務(wù)向上權(quán)值表DAGDAG-ADAG-BniA1A2A3A4A5A6A7A8A9A10B1B2B3B4B5Rank107.77780806963.342.735.744.314.742203134.336本文模型和算法除了要利用以上基礎(chǔ)定義和參數(shù)以外，還用到另一個關(guān)鍵定義，即公平性。多DAG調(diào)度一個關(guān)鍵功效是經(jīng)過一定方法確定各DAG中各任務(wù)調(diào)度和實施次序，既包含到同一DAG內(nèi)前后有依靠關(guān)系任務(wù)調(diào)度次序，也包含到分屬不一樣DAG沒有依靠關(guān)系任務(wù)調(diào)度次序，這些調(diào)度次序會直接影響各個DAG實施時間；以后一個調(diào)度次序是否公平，也會直接影響到各個DAG平均實施時間和調(diào)度系統(tǒng)整體性能好壞。假如調(diào)度不考慮公平性，可能往往會因為多個同級DAG之間結(jié)構(gòu)差異較大而使得任務(wù)量小DAG完成時間比任務(wù)量大完成時間要晚，造成顯著不公平。僅依據(jù)任務(wù)權(quán)值來確定調(diào)度次序，很可能會造成先抵達DAG部分任務(wù)因為后續(xù)DAG任務(wù)權(quán)值總是很大而得不到調(diào)度。所以，除了資源利用率，DAG實施時間、公平性也是衡量多DAG調(diào)度算法性能關(guān)鍵指標。Zhao和Sakellariou[21]首次提出了衡量這種公平性方法，基于這種定義方法上調(diào)度算法，能夠達成愈加好公平性。以下是文件[21]中相關(guān)公平性表述和定義：因為一個DAGa要和其它DAG爭用同一組機器，所以aMakespan（從提交DAGa開始到DAGa最終一個任務(wù)實施完成所用時間）很可能比a單獨使用這組機器Makespan要長，那么這兩個Makespan可分別被表示為Mmulti（a）和Mown（a）。依據(jù)文件[22]定義：Slowdown（a）=Mown（a）/Mmulti（a），那么某種調(diào)度算法S不公平程度Unfairness（S）=|Slowdown(a)-AvgSlowdown|。其中，A為給定多個DAG集，AvgSlowdown是全部DAGSlowdown平均值。Unfairness（S）是能夠用來衡量一個多DAG調(diào)度算法S調(diào)度不公平程度關(guān)鍵指標。4.2多DAG公平調(diào)度E-Fairness改善算法如前所述，ZhaoFairness算法不能處理不一樣時間抵達多個DAG，也不適適用于多優(yōu)先級多個DAG應(yīng)用情況。為了能夠?qū)⑷魏螘r間抵達新DAG和已經(jīng)全部預(yù)分配資源且部分任務(wù)已經(jīng)實施DAG同時公平地進行調(diào)度，改善Fairness算法被提出。以下將經(jīng)過圖4.3來討論改善方法。假如系統(tǒng)在0時刻只有圖4.2（a）中DAG-A抵達請求調(diào)度，利用TopcuogluHEFT算法對DAG-A進行調(diào)度并實施，且在整個DAG-A調(diào)度實施過程中沒有任何其它DAG抵達，那調(diào)度結(jié)果圖4.3（a）示。Mown（DAG-A）=79，Mmulti（DAG-A）=79，Slowdown（DAG-A）=1。不過，假如當DAG-A在調(diào)度實施過程中，新DAG-B抵達，假設(shè)它抵達時間Bar-t=35，且DAG-B優(yōu)先級和DAG-A相同，那么圖4.3（b）所表示，DAG-A中全部任務(wù)能夠分為3部分：（1）實施完成任務(wù)組（A1，A3，A4和A5）；（2）Qw-mi中等候?qū)嵤┤蝿?wù)組（A7，A8，A9和A10）；（3）機器Mi上正在實施任務(wù)組（A2，A6）。因為機器上正在實施任務(wù)含有不可剝奪性，所以在M1和M3上A2和A6這兩個任務(wù)不能被撤銷，不過在Qw-mi中等候?qū)嵤┻€未被實施任務(wù)組（A7，A8，A9和A10）能夠被撤銷而且能夠和新抵達DAG-B一起進行公平調(diào)度?？紤]到原有DAG-A部分任務(wù)撤銷和重新調(diào)度可能會造成數(shù)據(jù)傳輸問題，因為撤銷未被實施任務(wù)組中任務(wù)有可能重新被調(diào)度到一個新機器資源上，這時已經(jīng)實施完成父母任務(wù)結(jié)點數(shù)據(jù)是否能夠立即送達是很關(guān)鍵。為了處理這個問題，多DAG系統(tǒng)模型要求：當一個有后繼結(jié)點任務(wù)完成后，它實施結(jié)果數(shù)據(jù)必需向每個機器發(fā)送。另外，改善Fairness算法關(guān)鍵一個方面就是對新DAG抵達后時隙調(diào)整。因為Fairness調(diào)度策略基于HEFT方法，在本例中，Bar-t=35，B中全部任務(wù)和A中要重新調(diào)度任務(wù)中任何一個任務(wù)實施時間不能早于這個時間，所以在圖4.3（b）中，機器M2上第一個時隙應(yīng)該調(diào)整為新可用時隙，它開始時間應(yīng)被重置為Bar-t。 （a）DAG-A單獨調(diào)度結(jié)果 （b）DAG-B在35時刻抵達時A任務(wù)狀態(tài)圖4.3DAG-A和DAG-B調(diào)度舉例另外，ZhaoFairness算法中首先要對每個DAGSlowdown值初始化為0，全部DAG調(diào)度初始次序為各個DAG單獨調(diào)度時Makespan大小降序排列。只有DAG被調(diào)度1次，DAGSlowdown值發(fā)生改變后，才能實現(xiàn)多個DAG之間公平性調(diào)度。對Fairness另一關(guān)鍵調(diào)整步驟是，新抵達DAG必需首先被調(diào)度1次。在本例中，Aar-t=0，Bar-t>0，針對全部DAG-A中被撤銷任務(wù)和全部DAG-B中任務(wù)，新抵達B中向上權(quán)值最大B1任務(wù)首先被調(diào)度1次。最終一個要調(diào)整步驟是，計算新達成DAG中第i個任務(wù)被調(diào)度后Slowdown（）計算要考慮到新達成DAG抵達時間，最終調(diào)度結(jié)果圖4.4和表4.3。圖4.4E-Fairness算法調(diào)度DAG-A和DAG-B過程表4.32種算法調(diào)度DAG-A和DAG-B結(jié)果比較（Bar-t=35s）算法E-Fairness（B優(yōu)先級=A優(yōu)先級）Backfill（B優(yōu)先級<A優(yōu)先級）兩個DAG調(diào)度次序A1，A3，A4，A2,A5，A6，B1，A9，B4，B3，B2，B5，A7，A8，A10A1，A3，A4，A2，A5，A6，A9，A7，A8，A10，B1，B4，B3，B2，B5資源利用率0.526320.60760Makspan(A+B)95.0000079.00000Unfairness0.090500.07792MakespanA9579MakespanB42424.3多DAGBackfill算法實現(xiàn)在圖4.5中，一樣地，假如Bar-t=35，但B優(yōu)先級不一樣于A，那么應(yīng)該采取Backfill算法來確定A和B調(diào)度關(guān)系，而不能采取E-Fairness算法，因為優(yōu)先級高DAG能夠中止先抵達并被正在調(diào)度低優(yōu)先級DAG，不一樣優(yōu)先級DAG之間比較調(diào)度次序上公平性沒有意義。圖4.5Backfill算法調(diào)度DAG-A和DAG-B過程當B優(yōu)先級高于A時，應(yīng)該撤銷A中未被實施任務(wù)組中任務(wù)，并首先將資源根據(jù)HEFT算法將全部機器分配給B，然后將A中被撤銷任務(wù)插入到B所留下時隙中。假如B優(yōu)先級低于A，那么A中全部任務(wù)仍然根據(jù)在0時刻調(diào)度方案進行調(diào)度，并將B中全部任務(wù)根據(jù)HEFT算法匹配到各個機器Mi上時隙鏈表SMi（根據(jù)時隙開始時間排列）上，并將這些任務(wù)插入到Qw-mi中等候?qū)嵤．斝翫AG-B抵達時，正圖4.5所表示，相關(guān)時隙應(yīng)該被修改為可用時隙。在調(diào)度過程中，其它部分需要調(diào)整時隙情況舉例說明以下：在圖4.5中，EST（Bi，M1）表示任務(wù)Bi全部父母任務(wù)結(jié)果數(shù)據(jù)最晚送達成機器M1上時刻，即任務(wù)Bi最早開始時間。設(shè)tm和tn分別是EST（Bi，M1）兩個可能取值，且tm等于時隙開始時刻，tn是時隙等分時刻。假設(shè)B中某個任務(wù)Bi長度恰好是1/3，且任務(wù)Bi被匹配到時隙隊列SM1中時隙上。那么，當EST（Bi，M1）=tm時，被Bi占用后仍然是1個時隙，只是時隙長度縮短了1/3；當EST（Bi，M1）=tn時被Bi占用后，將會被分成兩個更小時隙。4.4含有多優(yōu)先級多DAG混合調(diào)度策略MMHS正如上述算法E-Fairness和Backfill中所提到，這兩種算法在多優(yōu)先級多DAG調(diào)度中適適用于不一樣情況：E-Fairness適合于確定相同優(yōu)先級DAG之間調(diào)度關(guān)系，而Backfill適合確定不一樣優(yōu)先級DAG間調(diào)度關(guān)系。適適用于多優(yōu)先級多DAG調(diào)度在不一樣時間抵達系統(tǒng)混合調(diào)度策略MMHS以下：混合調(diào)度策略MMHS1：While(DAGnew)do/*當新DAG抵達*/2：計算DAGnew中全部任務(wù)向上權(quán)值Rank；3：If(Pnew≥max{Pscheduling})/*Pscheduling表示集合Uscheduling中元素優(yōu)先級集合(Uscheduling是正在調(diào)度運行DAG集合，并根據(jù)優(yōu)先級從大到小排序)，Pnew表示新達成DAG優(yōu)先級)*/4：依據(jù)新DAG抵達時間修改相關(guān)時隙；5：撤銷Qw-mi中全部任務(wù)；/*正在運行DAG全部任務(wù)包含對應(yīng)于機器MiQw-mi中未被調(diào)度任務(wù)、已經(jīng)實施完成任務(wù)和正在Mi上實施任務(wù)*/6：If(Pnew>max{Pscheduling})7：依據(jù)HEFT算法調(diào)度DAGnew任務(wù)，并將DAGnew任務(wù)依次放入Qw-mi；8：While(Uscheduling)do：9：計算和修改全部機器上時隙鏈表SMi；10：apeer從Uscheduling選擇優(yōu)先級最高DAG(注：最高級可能有多個)；11：If(apeer中DAGCO-DAG)12：apeer中多個同級DAG間調(diào)度關(guān)系采取E-Fairness算法，并采取HEFT方法Backfill算法將這些任務(wù)匹配到SMi，并將任務(wù)依次放入Qw-mi13：Else14：apeer中多個同級DAG間調(diào)度關(guān)系采取E-Fairness算法，并采取LE方法Backfill算法將這些任務(wù)匹配到SMi，并將任務(wù)依次放入Qw-mi；15：Uscheduling=Uschedulingapeer；16：Endwhile17：Else18：If(Pnew=max{Pscheduling})19：apeer依次從Uscheduling選擇優(yōu)先級最高DAG(注：最高級可能有多個)；20：apeer中多個同級DAG間調(diào)度關(guān)系采取E-Fairness算法21：While(Uscheduling)do22：計算和修改對應(yīng)于每個機器時隙鏈表：SMi23：apeer依次從Uscheduling選擇優(yōu)先級最高DAG；24：If(apeer中DAGCO-DAG)25：apeer中多個同級DAG間調(diào)度關(guān)系采取E-Fairness算法，并采取HEFT方法Backfill算法將這些任務(wù)匹配到SMi，同時將任務(wù)依次放入Q26：Else27：apeer中多個同級DAG間調(diào)度關(guān)系采取E-Fairness算法，并采取LE方法Backfill算法將這些任務(wù)匹配到SMi，同時將任務(wù)依次放入Qw-mi；28：Uscheduling=Uschedulingapeer29：Endwhile30：Else31：If(Pnew<max{Pscheduling})32：僅撤銷Qw-mi中優(yōu)先級小于或等于新抵達DAG優(yōu)先級DAG中任務(wù)；保留全部優(yōu)先級大于新DAGDAG中任務(wù)調(diào)度方案，并將這些DAG從Uscheduling中刪除；33：While(Uscheduling)do34：計算和修改全部時隙鏈表SMi；35：apeer在Uscheduling中選擇優(yōu)先級和新DAG相同DAG和新達成DAG；36：If(apeer中DAGCO-DAG)37：apeer中多個同級DAG間調(diào)度關(guān)系采取E-Fairness算法，并采取HEFTBackfill算法將這些任務(wù)匹配到SMi，同時將任務(wù)依次放入Qw-mi；38：Else39：apeer中多個同級DAG間調(diào)度關(guān)系采取E-Fairness算法，并采取LE方法Backfill算法將這些任務(wù)匹配到SMi，同時將任務(wù)依次放入Qw-mi；40：Uscheduling=Uschedulingapeer41：Endwhile42：Endwhile4.5試驗和分析本節(jié)經(jīng)過大量試驗數(shù)據(jù)，著重從資源利用率UR、DAGMakespan和不公平程度Unfairness這3項指標將MMHS策略和相關(guān)算法（E-Fairness，Backfill）進行性能比較。因為針對兩個DAG調(diào)度，MMHS調(diào)度策略只需要在E-Fairness和Backfill之間進行選擇，所以只需對E-Fairness，Backfill這2種算法在不一樣條件下作性能比較即可。4.5.1相關(guān)兩個DAG調(diào)度試驗假設(shè)B優(yōu)先級小于A優(yōu)先級，依據(jù)混合調(diào)度策略MMHS，保留那些優(yōu)先級大于新抵達DAG全部DAG任務(wù)分配方案。那么，當B抵達時，MMHS將保留A中全部任務(wù)在0時刻分配方案，而將B匹配到各個機器時隙上。在下文圖4.6和圖4.7中顯示了在DAG-B不一樣抵達時間上，分別在2個和5個機器上2種調(diào)度算法相關(guān)性能指標情況。我們比較了2種算法MakespanA，圖4.6和圖4.7所表示，采取Backfill算法，DAG-AMakespanA能夠避免受到B影響，很好地確保了DAG-A用戶對實施期限較為嚴格限制。能夠看出，在公平性指標上，Backfill算法比E-Fairness算法相對要差。所以