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

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

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

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