云環境下的基于Min-Max的節能資源調度算法的研究

徐京明 王 珺 李成星

(南京郵電大學通信與信息工程學院 江蘇 南京 210003)

0 引 言

隨著云計算數據中心規模的不斷擴大，數據中心消耗的能量也在不斷增加。近年來，數據中心產生的高能耗現象逐漸受到各界的關注[1]。據美國相關機構統計[2]：2012年，全世界IT行業的能量消耗占總比例的40%，排放的二氧化碳占全球的2%。2014年數據中心的基礎設施和能源成本占總成本的75%，而基礎設施成本僅占其中的25%。預計到2020年，云計算能耗在全世界將接近2萬億千瓦時。因此，迫切需要研究云環境中的節能資源調度算法和策略。

根據相關機構的調查結果可知，數據中心能量消耗過高的原因主要有兩個：一方面是資源調度算法設計不合理造成的[3]；另一方面是當物理資源處于空閑狀態時，沒能及時轉換成休眠或者關機等狀態造成的[4]。本文針對第一個問題展開研究。

1 相關工作

云計算的資源調度有無限可能的發展前景，因此，資源調度算法是當前研究的一個熱點。資源調度就是將資源池中的資源根據算法或者策略的規則分配給用戶的過程。目前為止，已經有很多學者在這方面提出了很多的算法，比如：文獻[7]中提出了一種優化的Min-Min算法，該算法不僅基于Min-Min算法，而且基于三個約束。三個約束分別是服務質量、動態優先級模型和服務成本，使用Cloudsim軟件來運行模擬實驗。與傳統的Min-Min算法相比，它可以在合理的時間內執行完長度較大的任務，不僅提高了資源利用率，而且提高了用戶的QoS。文獻[8]中提出了貪心算法[18]的優化，該算法在貪心算法基礎上增加了優先級機制，將云任務根據任務指令條數(單位為MI)的大小按照遞減的順序排列。資源根據處理器速度(單位為MIPS)的大小按照遞增的順序排列。該算法以最小任務完成時間為調度目標，它總是能建立當前最佳的任務到物理資源的映射關系。文獻[9]提出了一種基于Max-Min的調度算法，調度過程中的任務狀態表用于預測虛擬資源的實時負載和任務的預期完成時間，該算法實現了負載均衡但是沒有考慮任務的完成時間。文獻[10]提出了Min-Max算法，調度過程中，首先根據Max-Min算法和Min-Min算法分別選出長度最大和最小的任務，根據計算得出各自在物理機執行的完成時間，分別選出最小任務完成時間的物理資源，最后將這兩個任務分別放在對應的物理機上執行。該算法既提高了系統整體的資源利用率，又實現了負載均衡。當然，還有其他的調度算法，比如粒子群算法、蟻群算法等，但是這些算法大多都只考慮了性能、可靠性以及安全性等問題，而忽略了能量消耗的問題。

近年來，越來越多的人開始關注能耗問題，研究者也提出了一些關于節能的資源調度的算法。文獻[11]中提出一種面向異構機群的低功耗調度算法，在經典的Min-Min算法的基礎上，將休眠狀態控制策略應用于異構集群的各個節點，實現了性能和能耗的平衡。然而，睡眠喚醒機制會增加任務準備時間，減少任務有效性。文獻[11]中的算法考慮了休眠和空閑狀態下如何通過狀態轉換實現節能，本文提出的算法考慮了通過調度算法進行能耗優化，實現工作狀態下的節能。當然，如何在睡眠和空閑狀態下節約能量也是未來需要考慮的問題。在文獻[6]中，針對綠色節能，提出了一種云環境下的資源調度算法。該算法利用了遺傳算法找到最優調度策略，建立兩級調度模型，采用能耗估算模型，該模型考慮了休眠、空閑以及工作三種物理機狀態。相較于GA，該算法減少了任務完成時間和能量消耗，但是文中的能耗估算模型忽略了物理機進行狀態轉換時的能耗損失。本文和文獻[6]采用的都是ECEM能耗估算模型，但本文考慮的是計算密集型任務在工作狀態下的能耗，因此，該模型不考慮狀態轉換期間消耗的能量，對本文沒有影響。在文獻[12]中，提出了一種基于Min-Min的節能資源調度算法，在原有算法的基礎上增加了能量估計機制。首先，根據Min-Min算法找到最小長度任務。然后，根據用戶對任務的期望時間將物理資源分為兩類：滿足時間期望和不滿足時間期望。該算法實現了節能的目標而忽略了負載均衡問題，還需要進一步完善。相比于文獻[12]提出的調度算法，本文的ESSAMM算法實現了負載均衡，并且本文采用的是文獻[6]中的ECEM能耗估算模型，而文獻[12]中使用了MSEM能耗估算模型，兩個模型能耗的計算方式和物理機狀態不同。通過分析，本文將后者作為ESSAMM節能算法能耗估算模型。最后，本文只考慮計算密集型任務在工作狀態下產生的能耗，而文獻[12]研究了多種任務在多種狀態下的不同能耗，內容不限于資源調度。在文獻[13]中，研究了云計算環境下的能源效率問題。首先，該文研究了能耗模型，將計算資源分為CPU、內存、存儲和網絡四大類，并針對不同的組件設計了不同的調控策略。在此基礎上，提出了一種動態資源調度算法，最后的仿真結果也證明了該算法的有效性。但是該算法由于數據收集的不完善，無法在云環境下普遍使用，需要進一步修改和完善。

云計算環境下的資源調度過程需要平衡好性能和能耗這兩個方面。由表1知，Min-Max算法的任務完成時間介于Min-Min算法和Max-Min算法之間，但是其資源利用率最大。因此本文選擇Min-Max算法進行改進。三個算法都沒有考慮能量消耗，所以本文在Min-Max算法的基礎上考慮了能量消耗因素，并且將用戶對于任務的期望完成時間也考慮進去(時間QoS)，即本文所提出的ESSAMM算法。仿真實驗表明：ESSAMM算法不僅實現了負載均衡，而且減少了能量消耗。

表1 三種算法性能對比

2 參考模型

2.1 云計算環境下的兩級資源調度模型

根據虛擬化技術在云計算中的應用，將云計算系統中的所有資源集成到一個巨大的資源池中[14]，將云用戶提交的任務劃分為幾個小任務，先實現資源池中信息的有效輸入和輸出，然后建立任務與資源之間的有效映射關系。云中的資源分為兩類：虛擬資源和物理資源。因此，云環境中的資源調度可以分為兩個層次：第一個層次在虛擬資源層；第二個層次在物理資源層。具體的調度模型如圖1所示。

圖1 云環境的兩級資源調度模型

第1級映射關系可以表示為S1={T,V,f1}，其中T={T1,T2，…，Tm}表示有m個任務的集合；V={V1,V2，…，Vm}表示與任務列表一一對應的m個虛擬機的集合；f1表示任務到虛擬機的映射關系。第2級映射關系可以表示為S2={V,H,f2}。其中H={H1,H2，…，Hn}表示有n個物理機的集合。f2表示虛擬機到物理機的映射。

在第一級映射關系中，云任務和虛擬機是一一對應的關系，根據任務的屬性以及要求，在資源池中匹配到相應的虛擬資源，建立任務到虛擬機的映射關系。在第二級映射關系中，一臺物理機可以對應一個或者多個虛擬機，根據上一級匹配到的虛擬資源的配置信息，以最小能耗和時間QoS為調度目標，選擇最佳的物理資源并建立虛擬機到物理機的映射關系。其中，第二級映射關系是本文的研究重點。通過上述云環境下的兩級資源調度模型，本文可以建立從任務到物理機的有效映射關系。相較于采用多任務和超線程技術，虛擬化的兩級資源調度模型的優勢是一個物理資源可以同時運行多個虛擬資源，執行多個任務，結合優化的調度算法可以減少很多相關開銷、提高數據傳輸速率和性能。

2.2 ECEM能耗估算模型

本文使用的能耗模型是文獻[6]中提到的ECEM能耗估算模型。ECEM能耗估算模型將總能耗分為休眠能耗、空閑能耗和工作能耗之和[15]。工作能耗分為計算能耗、存儲能耗以及通信能耗三類。任務類型分為計算密集型、能量密集型以及通信密集型三類，其中計算密集型任務工作過程中產生的能耗成為計算能耗，計算能耗主要和CPU利用率有關。能量密集型任務工作過程中產生的能耗成為存儲能耗，存儲能耗主要和磁盤讀寫的字節數有關。通信密集型任務工作過程中產生的能耗成為通信能耗，通信能耗主要和傳輸的字節數有關。研究表明，能耗的主要來源是物理機的CPU，主要因素是CPU利用率，一般情況下，每個物理機的CPU利用率基本不同。所以本文只考慮計算密集型任務在工作狀態下產生的計算能耗，采用CPU利用率不同的物理機去執行任務。以下本文所說的能耗都指的是計算能耗。設在物理機Hj上執行任務Ti產生的執行時間用RTij表示；在物理主機Hj上執行任務Ti產生的能耗用CECij表示：

(1)

(2)

式中：CECij表示計算能耗，RTij表示任務Ti在物理機Hj上的執行時間(單位為s)，CIi(單位為MI)表示任務指令條數，CSj表示物理機的處理器速度(單位為MIPS)，PCj表示在物理機Hj上執行任務的計算功耗(單位為W)。

2.3 算法變量以及時間QoS的說明

1) 在說明ESSAMM算法之前，有如下定義：

任務集合表示為T={T1,T2，…，Tm}，虛擬機集合表示為V={V1,V2，…，Vm}，物理機集合表示為H={H1,H2，…，Hn}。長度最大的任務Tp和長度最小的任務Tq。

(1)RTij表示任務Ti在物理資源Hj上的執行時間。

(2)WTij表示任務Ti在被調度之前的等待時間。

(3)CTij表示任務Ti在物理資源Hj上的完成時間，且滿足CTij=RTij+WTij。

(4)TQoS(i)表示任務Ti的時間服務質量即時間QoS。

(5)Eij表示任務Ti在物理資源Hj上的消耗的能量值。

(6) 矩陣ECT表示任務完成時間矩陣，矩陣中的元素為CTij。

(7) 矩陣ECE表示能量消耗矩陣，矩陣中的元素為Eij。

2) 因每個任務在物理機上的完成時間是已知的，當用戶輸入時間QoS時，系統會提示用戶當前任務在各物理機上執行的最小和最大的完成時間，且限定輸入的時間QoS范圍必須在最小和最大的完成時間之間。本文的時間QoS也指用戶期望任務的完成時間。

3 ESSAMM節能調度算法

3.1 算法描述

針對ECEM能耗模型中的第二級調度，ESSAMM算法以系統總能耗最小為優化目標，以滿足任務的時間QoS為約束條件。ESSAMM算法在Min-Max調度算法基礎上考慮了時間QoS和能耗，節省了大量能耗，提高了用戶滿意度，使得整個系統處于負載均衡的狀態。ESSAMM算法總共分為三個階段：第一個階段是計算任務完成時間；第二個階段是根據用戶設定的時間QoS，將滿足時間需求的物理資源選擇出來；第三個階段是根據能耗實現資源調度。

1) 第一階段：計算任務完成時間。

(1) 計算出任務集合T在物理機集合H上的完成時間。

(2) 根據(1)中的任務完成時間，選擇物理機上最大完成時間對應的任務和最小的完成時間對應的任務來組成任務對(同一個物理機上的任務完成時間越長，任務的長度就越大，可以根據完成時間來判斷任務長度)，即當前任務集合中長度最大的任務Tp和長度最小的任務Tq，并確定兩個任務在各物理資源Hp和Hq上的完成時間。

2) 第二階段：根據用戶設定的時間QoS，篩選出滿足用戶時間需求的物理資源。

在滿足用戶設定的時間QoS前提下，將任務Tp分別在n個物理機上執行的完成時間(CTP1，CTP2，…，CTpn)和設定的TQoS(p)進行比較，如果CTp>TQoS(p)，則將該資源標為無效且刪除，若反之，則留下并等待第三階段的調度選擇。對于任務Tq同理之。

3) 第三階段：根據能耗實現資源調度。

(1) 采用式(2)計算Tp和Tq在各物理資源Hj執行產生的能耗值。

(2) 比較任務Tp在各物理資源上的能耗值，取最小能耗值對應的物理資源Hp，將Tp放在Hp上執行，建立任務Tp到物理機Hp的最佳映射關系；對任務Tq，將Tq放在能耗值最小的物理資源Hq上執行，建立任務Tq到物理機Hq的最佳映射關系。

3.2 算法流程

步驟1初始化。初始化任務的等待時間WTij= 0，執行時間RTij=0，完成時間CTij=0，能耗值Eij=0，設定TQoS(i)。

步驟2建立完成時間矩陣ECT。計算每個任務Ti在不同物理機Hj上的完成時間CTij，確定一個M行N列的完成時間矩陣ECT，CTij為ECT矩陣中的元素。

步驟3確定當前任務列表中長度最大和長度最小的任務。根據ECT矩陣，找出每個任務的最小完成時間，并且比較出每個任務的最小完成時間，找出最大值和最小值即為長度最大的任務Tp和長度最小的任務Tq。

步驟4確定滿足時間QoS的物理資源。將任務Tp對應的每個物理資源的完成時間和步驟1中設定的TQoS(p)作比較，若大于TQoS(p)則將該物理資源標為無效；對于任務Tq同理之。

步驟5建立能量消耗矩陣ECE。采用式(2)分別計算出任務Tp和Tq在各物理資源上的能量消耗值，能耗值表示為Eij，確定一個M行N列的能量消耗矩陣ECE。

步驟6建立最佳映射關系。對于任務Tp，比較步驟5中的能耗值，選擇最小值Ep對應的物理資源Hp，將任務Tp放在Hp上執行，建立最佳映射關系；對于任務Tq，比較步驟5中的能耗值，選擇最小值Eq對應的物理資源Hq，將任務Tq放在Hq上執行，建立最佳映射關系。

步驟7將已經執行的任務Tp和Tq從云任務列表T中刪除，然后更新任務列表T，更新完成時間矩陣ECT和能量消耗矩陣ECE。重復上述步驟3，直到任務列表為空，退出循環。

由2.2節中ECEM能量估算模型式(1)、式(2)可知，物理機的計算能耗與任務完成時間和物理機的功耗有關，而物理機的計算功耗與其CPU的利用率有關，因此，在CPU利用率不同的物理機上執行相同任務產生的能耗是不同的。ESSAMM算法以最小能耗為調度目標，通過選擇最小能耗對應的物理機執行該任務，以此來節省系統總能量消耗，而Min-Max算法并未考慮能耗因素，造成能源的浪費。此外，ESSAMM算法在Min-Max算法的基礎上提高了資源利用率，由于Min-Max算法在調度過程中并未根據任務的屬性和用戶的需求考慮了每一個物理資源的分配，導致資源利用率較低。另一方面，由于ESSAMM算法的復雜度比Min-Max算法的復雜度更高，所以，在調度過程中ESSAMM算法的任務總完成時間略長一些。相比于Min-Max算法，本文提出的ESSAMM算法實現降低系統總能耗、提高系統整體資源利用率及用戶滿意度等調度目標。

4 仿真與結果分析

仿真實驗從任務總完成時間、系統資整體源利用率以及系統總能耗幾個方面，分別對ESSAMM算法、Min-Max算法以及Min-Min算法進行比較。其中，任務總完成時間代表了資源調度算法的執行效率，系統的整體資源利用率代表了算法的負載均衡性能，系統總能耗代表了算法的節能效果。任務數量從1到1 000，物理機數量從1到100。

4.1 主要參數設置

實驗環境：CPU 主頻 2.40 GHz，硬盤：150 GB，內存：4 GB，操作系統：Windows10 64位。

開發環境：開發平臺為Eclipse，開發語言為Java，仿真環境為Cloudsim3.0.3。

實驗的參數配置如表2所示，虛擬機的配置與云任務的一致。

表2 實驗參數設置

4.2 仿真結果對比分析

(1) 物理機的數量為100，任務數量從100遞增到1 000。

首先，本文仿真了當任務數從100到1 000遞增時，ESSAMM算法、Min-Max算法以及Min-Min算法的總任務完成時間，結果如圖2所示。

圖2 三種算法的總任務完成時間

如圖2所示，當任務數量從100到1 000遞增時，三種算法的任務總完成時間均在增加，其中Min-Min算法的任務總完成時間最小，Min-Max算法的任務總完成時間介于其他兩個算法之間。原因如下：ESSAMM算法在調度過程中既考慮了任務總完成時間，又考慮了時間QoS和能量消耗兩個因素，相較于另外兩個算法，調度過程更加復雜一些，從而使得該算法的任務總完成時間略長一些。而Min-Min算法以最小完成時間為調度目標，它總是優先調度長度較小的任務，使得大任務的等待時間變少，從而使得總完成時間減少。Min-Max算法既調度大任務又調度小任務，以負載均衡和總任務完成時間作為調度目標，所以完成時間介于其他兩個算法之間。

當任務數從100到1 000遞增時，將ESSAMM算法、Min-Max算法以及Min-Min算法的整體資源利用率進行仿真，結果如圖3所示。

圖3 三種算法的整體資源利用率

如圖3所示，當任務數量從100到1 000遞增時，三個算法的整體資源利用率均在增加，Min-Min算法的整體資源利用率一直處于最低狀態，ESSAMM算法的整體資源利用率最高且均在90%左右，Min-Min算法的資源利用率略低于ESSAMM算法，但也保持在85%以上。原因如下：Min-Min算法總是優先將小任務放在CPU處理速度快的物理機上執行，導致處理速度慢的物理資源處于空閑狀態，不能很好地利用所有資源，所以它的資源利用率較低。而Min-Max算法和ESSAMM算法在調度過程中都考慮了負載均衡的因素，此外，ESSAMM算法在調度過程中又以能耗因素將任務調度到不同物理機上執行，而不僅僅是以CPU處理速度的快慢作為標準。所以，ESSAMM算法的整體資源利用率最高，其次是Min-Max算法，最低是Min-Min算法。

當任務數從100到1 000遞增時，將ESSAMM算法、Min-Max算法以及Min-Min算法的總能量消耗進行仿真，結果如圖4所示。

圖4 三種算法的總能量消耗

如圖4所示，當任務數量從100到1 000遞增時，三種算法的總能量消耗值也逐漸上升，但是ESSAMM算法的總能量消耗一直處于最低值，且增長趨勢較為平緩；Min-Max算法的總能量消耗最高，Min-Min算法的總能量消耗值處于兩者之間。原因如下：Min-Min算法以任務完成時間作為調度目標，Min-Max算法以任務完成時間和負載均衡作為目標進行調度，這兩個算法在資源調度過程中都沒有考慮能量消耗的因素，而ESSAMM算法在Min-Max算法的基礎上考慮了能耗因素，在滿足時間QoS的前提下，取能耗最小值對應的物理資源執行該任務，即以能耗最低為目標進行資源調度。所以ESSAMM算法的總能耗值最低，其次是Min-Min算法，Min-Max算法的總能耗值最高。

(2) 任務數量為1 000，物理機數量從10遞增到100。

當物理機的數量從10遞增到100時，將ESSAMM算法、Min-Max算法以及Min-Min算法的總任務完成時間進行仿真，結果如圖5所示。

圖5 三種算法的總任務完成時間

如圖5所示，隨著物理機數量的增加，三個算法的總任務完成時間均在不斷減小，且下降趨勢較為平緩，其中Min-Min算法的總任務完成時間最小，Min-Max算法的總任務完成時間介于ESSAMM算法和Min-Min算法之間。原因如下：Min-Min算法是以最小任務完成時間為目標，調度過程較簡單；Min-Max算法是以負載均衡為目標，調度過程中將當前任務中長度最大和最小的任務“捆綁”執行，且將任務的等待時間考慮進去，充分利用各物理資源，達到優化的目標；而ESSAMM算法既考慮了負載均衡的因素，又考慮了能量消耗的因素，相較于前面兩個算法，考慮的更加全面一些，所以任務的完成時間略長一點。

當物理機的數量從10遞增到100時，將ESSAMM算法、Min-Max算法以及Min-Min算法的整體資源利用率進行仿真，結果如圖6所示。

圖6 三種算法的整體資源利用率

如圖6所示，隨著物理機數量的增加，三個算法的整體資源利用率均在逐漸增加，其中ESSAMM算法的整體資源利用率最高，Min-Max算法的整體資源利用率略低于ESSAMM算法，而Min-Min算法的整體資源利用率最低。原因如下：ESSAMM算法和Min-Max算法在調度過程中均考慮了負載均衡的因素，而Min-Min算法只以最小任務完成時間為調度目標。

5 結 語

本文以節省能量消耗為調度目標，提出了一種新的節能調度算法(ESSAMM)。面向云環境，本文建立了兩級的資源調度模型，利用時間QoS對每個任務的物理資源進行篩選，將符合時間QoS的物理資源保留，然后根據ECEM能耗估算模型計算出任務在物理機上的執行能耗，比較出最小值，最后建立了最佳映射關系。仿真結果表明， ESSAMM節能調度算法與Min-Max算法和Min-Min算法相比，節能效果最好；ESSAMM算法和Min-Max算法的任務總完成時間基本相同，其中Min-Min算法的任務總完成時間最小；ESSAMM算法的整體資源利用率最高，而Min-Min算法的整體資源利用率最低。目前，本文只考慮了計算密集型任務，并沒有考慮其他類型的任務，所以細化任務類型是下一步工作內容之一。另外，本文提出的算法只考慮了工作過程中的能耗優化，下一步的工作重點是將空閑狀態以及休眠狀態下的節能方案也考慮進來，完善整個節能系統。