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

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

4具有多優先級的多DAG混合調度4.1具有多優先級的多DAG調度系統模型具有多優先級的多DAG調度系統模型如圖4.1所示，它由3部分組成，分別是：多DAG接收與優先級判別子系統（Receiver&PriorityIdentification）、多DAG調度子系統（Multi-DAGScheduler）和對應于資源Mi的等待執行任務隊列組（Qw-mi：QueueofTaskstobeExecutedonMi）。在多租戶DAG工作流系統中，不同用戶會在不同時間提交DAG。這些DAG到達后，由工作流接收與優先級判別子系統來管理和識別新DAG的優先級，并與較早時間到達的正在被調度執行的DAG優先級進行比較，為多DAG工作流調度子系統調度提供調度信息。然后，由多DAG工作流調度子系統根據混合調度策略將這些多DAG的任務按照執行順序分配至系統的第3部分，即待執行任務隊列組Qw-mi中。每次資源Mi執行完一個任務后，依次從與其相對應的Qw-mi中取下一個任務執行。圖4.1多優先級DAG管理系統模型本文關于DAG工作流任務圖的表示、定義和向上權值Ranku（ni）等與文獻[2][20]的有關定義和方法一致，這里不再重復。在多租戶多DAG系統模型中，資源的提供者是根據用戶任務的運行時間向用戶收取費用的。對CO-DAG類型的用戶來說，首要的QoS需求是整個DAG的執行費用最低。如果Pmi表示資源Mj的單位時間的租用價格，則任務ni在資源Mj上所發生的費用為Eij=Pmiwij（wij表示任務結點ni機器資源Mj上的估計運行時間，參見文獻[2])。下面經過圖4.2的兩個工作流實例DAG-A和DAG-B的調度來說明本文介紹的調度方法和策略。這兩個DAG的復雜度、結構和各項參數基本與文獻[2][20]中的實例一樣，機器資源數為3個。假設兩個DAG中每項任務在每個機器資源上的執行時間為表4.1，那么計算可得到每個任務的向上權值Ranku(ni)，見表4.2。 (a)DAG-A (b)DAG-B圖4.2兩個DAG工作流的實例表4.1DAG-A和DAG-B中各任務在機器上的執行時間DAGDAG-ADAG-BniA1A2A3A4A5A6A7A8A9A10B1B2B3B4B5M1,Pmi=1.01413111312137518214918217M2,Pmi=1.28191381316151112751017156M3,Pmi=1.11618191710911142016611161915表4.2兩個DAG的任務向上權值表DAGDAG-ADAG-BniA1A2A3A4A5A6A7A8A9A10B1B2B3B4B5Rank107.77780806963.342.735.744.314.742203134.336本文的模型和算法除了要利用以上基本的定義和參數以外，還用到另一個重要定義，即公平性。多DAG調度的一個重要功能是經過一定的方法確定各DAG中各任務的調度和執行順序，既涉及到同一DAG內前后有依賴關系任務的調度順序，也涉及到分屬不同DAG沒有依賴關系任務的調度順序，這些調度順序會直接影響各個DAG的執行時間；而后一種調度順序是否公平，也會直接影響到各個DAG的平均執行時間和調度系統整體性能的好壞。如果調度不考慮公平性，可能往往會因為多個同級DAG之間的結構差異較大而使得任務量小的DAG完成時間比任務量大的完成時間要晚，造成明顯的不公平。僅根據任務的權值來確定調度順序，很可能會造成先到達的DAG部分任務因為后續的DAG任務權值總是很大而得不到調度。因此，除了資源利用率，DAG的執行時間、公平性也是衡量多DAG調度算法性能的重要指標。Zhao和Sakellariou[21]首次提出了衡量這種公平性的方法，基于這種定義方法上的調度算法，能夠達到更好的公平性。以下是文獻[21]中關于公平性的表述和定義：由于一個DAGa要與其它DAG爭用同一組機器，因此a的Makespan（從提交DAGa開始到DAGa的最后一個任務執行完畢所用的時間）很可能比a單獨使用這組機器的Makespan要長，那么這兩個Makespan可分別被表示為Mmulti（a）和Mown（a）。根據文獻[22]的定義：Slowdown（a）=Mown（a）/Mmulti（a），那么某種調度算法S不公平程度Unfairness（S）=|Slowdown(a)-AvgSlowdown|。其中，A為給定的多個DAG的集，AvgSlowdown是所有DAG的Slowdown平均值。Unfairness（S）是能夠用來衡量一種多DAG調度算法S調度的不公平程度的重要指標。4.2多DAG公平調度E-Fairness改進算法如前所述，Zhao的Fairness算法不能處理不同時間到達的多個DAG，也不適用于多優先級的多個DAG的應用情況。為了能夠將任何時間到達的新DAG與已經全部預分配資源且部分任務已經執行的DAG同時公平地進行調度，改進的Fairness算法被提出。以下將經過圖4.3來討論改進方法。如果系統在0時刻只有圖4.2（a）中的DAG-A到達請求調度，利用Topcuoglu的HEFT算法對DAG-A進行調度并執行，且在整個DAG-A調度執行過程中沒有任何其它DAG到達，那的調度結果如圖4.3（a）示。Mown（DAG-A）=79，Mmulti（DAG-A）=79，Slowdown（DAG-A）=1?？墒牵绻擠AG-A在調度執行過程中，新的DAG-B到達，假設它的到達時間Bar-t=35，且DAG-B的優先級與DAG-A相同，那么如圖4.3（b）所示，DAG-A中的所有任務能夠分為3部分：（1）執行完畢的任務組（A1，A3，A4和A5）；（2）Qw-mi中等待執行的任務組（A7，A8，A9和A10）；（3）機器Mi上正在執行的任務組（A2，A6）。由于機器上正在執行的任務具有不可剝奪性，因此在M1和M3上的A2和A6這兩個任務不能被撤銷，可是在Qw-mi中等待執行還未被執行的任務組（A7，A8，A9和A10）能夠被撤銷而且能夠與新到達的DAG-B一起進行公平調度?？紤]到原有DAG-A部分任務的撤銷和重新調度可能會導致數據傳輸問題，因為撤銷的未被執行的任務組中的任務有可能重新被調度到一個新的機器資源上，這時已經執行完畢的父母任務結點的數據是否能夠及時送達是非常重要的。為了解決這個問題，多DAG系統模型要求：當一個有后繼結點的任務完成后，它的執行結果數據必須向每個機器發送。另外，改進的Fairness算法的重要的一個方面就是對新DAG到達后時隙的調整。由于Fairness調度策略基于HEFT方法，在本例中，Bar-t=35，B中的所有任務和A中要重新調度的任務中任何一個任務的執行時間不能早于這個時間，因此在圖4.3（b）中，機器M2上的第一個時隙應該調整為新的可用時隙，它的開始時間應被重置為Bar-t。 （a）DAG-A的單獨調度結果 （b）DAG-B在35時刻到達時A的任務狀態圖4.3DAG-A和DAG-B調度舉例另外，Zhao的Fairness算法中首先要對每個DAG的Slowdown值初始化為0，所有DAG調度的初始順序為各個DAG單獨調度時Makespan大小的降序排列。只有DAG被調度1次，DAG的Slowdown值發生變化后，才能實現多個DAG之間的公平性調度。對Fairness另一重要調整的步驟是，新到達的DAG必須首先被調度1次。在本例中，Aar-t=0，Bar-t>0，針對所有DAG-A中被撤銷的任務和所有DAG-B中的任務，新到達B中向上權值最大的B1任務首先被調度1次。最后一個要調整的步驟是，計算新達到DAG中第i個任務被調度后的Slowdown（）的計算要考慮到新達到DAG的到達時間，最后的調度結果如圖4.4和表4.3。圖4.4E-Fairness算法調度DAG-A和DAG-B過程表4.32種算法調度DAG-A和DAG-B的結果比較（Bar-t=35s）算法E-Fairness（B優先級=A優先級）Backfill（B優先級<A優先級）兩個DAG調度次序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多DAG的Backfill算法的實現在圖4.5中，同樣地，如果Bar-t=35，但B的優先級不同于A，那么應該采用Backfill算法來確定A和B的調度關系，而不能采用E-Fairness算法，因為優先級高的DAG能夠中斷先到達的并被正在調度的低優先級DAG，不同優先級DAG之間比較調度順序上的公平性沒有意義。圖4.5Backfill算法調度DAG-A和DAG-B的過程當B的優先級高于A時，應該撤銷A中未被執行的任務組中的任務，并首先將資源按照HEFT算法將所有機器分配給B，然后將A中的被撤銷的任務插入到B所留下的時隙中。如果B的優先級低于A，那么A中的所有任務依然按照在0時刻的調度方案進行調度，并將B中所有任務按照HEFT算法匹配到各個機器Mi上時隙鏈表SMi（按照時隙的開始時間排列）上，并將這些任務插入到Qw-mi中等待執行。當新DAG-B到達時，正如圖4.5所示，相關的時隙應該被修改為可用時隙。在調度過程中，其它一些需要調整時隙的情況舉例說明如下：在圖4.5中，EST（Bi，M1）表示任務Bi的所有父母任務結果數據的最晚送達到機器M1上的時刻，即任務Bi的最早開始時間。設tm和tn分別是EST（Bi，M1）兩個可能的取值，且tm等于時隙的開始時刻，tn是時隙的等分時刻。假設B中某個任務Bi的長度恰好是的1/3，且任務Bi被匹配到時隙隊列SM1中的時隙上。那么，當EST（Bi，M1）=tm時，被Bi占用后依然是1個時隙，只是時隙長度縮短了1/3；當EST（Bi，M1）=tn時被Bi占用后，將會被分成兩個更