云環(huán)境下的基于Min-Max的節(jié)能資源調(diào)度算法的研究

徐京明 王 珺 李成星

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

0 引 言

隨著云計(jì)算數(shù)據(jù)中心規(guī)模的不斷擴(kuò)大，數(shù)據(jù)中心消耗的能量也在不斷增加。近年來(lái)，數(shù)據(jù)中心產(chǎn)生的高能耗現(xiàn)象逐漸受到各界的關(guān)注[1]。據(jù)美國(guó)相關(guān)機(jī)構(gòu)統(tǒng)計(jì)[2]：2012年，全世界IT行業(yè)的能量消耗占總比例的40%，排放的二氧化碳占全球的2%。2014年數(shù)據(jù)中心的基礎(chǔ)設(shè)施和能源成本占總成本的75%，而基礎(chǔ)設(shè)施成本僅占其中的25%。預(yù)計(jì)到2020年，云計(jì)算能耗在全世界將接近2萬(wàn)億千瓦時(shí)。因此，迫切需要研究云環(huán)境中的節(jié)能資源調(diào)度算法和策略。

根據(jù)相關(guān)機(jī)構(gòu)的調(diào)查結(jié)果可知，數(shù)據(jù)中心能量消耗過高的原因主要有兩個(gè)：一方面是資源調(diào)度算法設(shè)計(jì)不合理造成的[3]；另一方面是當(dāng)物理資源處于空閑狀態(tài)時(shí)，沒能及時(shí)轉(zhuǎn)換成休眠或者關(guān)機(jī)等狀態(tài)造成的[4]。本文針對(duì)第一個(gè)問題展開研究。

1 相關(guān)工作

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

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

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

表1 三種算法性能對(duì)比

2 參考模型

2.1 云計(jì)算環(huán)境下的兩級(jí)資源調(diào)度模型

根據(jù)虛擬化技術(shù)在云計(jì)算中的應(yīng)用，將云計(jì)算系統(tǒng)中的所有資源集成到一個(gè)巨大的資源池中[14]，將云用戶提交的任務(wù)劃分為幾個(gè)小任務(wù)，先實(shí)現(xiàn)資源池中信息的有效輸入和輸出，然后建立任務(wù)與資源之間的有效映射關(guān)系。云中的資源分為兩類：虛擬資源和物理資源。因此，云環(huán)境中的資源調(diào)度可以分為兩個(gè)層次：第一個(gè)層次在虛擬資源層；第二個(gè)層次在物理資源層。具體的調(diào)度模型如圖1所示。

圖1 云環(huán)境的兩級(jí)資源調(diào)度模型

第1級(jí)映射關(guān)系可以表示為S1={T,V,f1}，其中T={T1,T2，…，Tm}表示有m個(gè)任務(wù)的集合；V={V1,V2，…，Vm}表示與任務(wù)列表一一對(duì)應(yīng)的m個(gè)虛擬機(jī)的集合；f1表示任務(wù)到虛擬機(jī)的映射關(guān)系。第2級(jí)映射關(guān)系可以表示為S2={V,H,f2}。其中H={H1,H2，…，Hn}表示有n個(gè)物理機(jī)的集合。f2表示虛擬機(jī)到物理機(jī)的映射。

在第一級(jí)映射關(guān)系中，云任務(wù)和虛擬機(jī)是一一對(duì)應(yīng)的關(guān)系，根據(jù)任務(wù)的屬性以及要求，在資源池中匹配到相應(yīng)的虛擬資源，建立任務(wù)到虛擬機(jī)的映射關(guān)系。在第二級(jí)映射關(guān)系中，一臺(tái)物理機(jī)可以對(duì)應(yīng)一個(gè)或者多個(gè)虛擬機(jī)，根據(jù)上一級(jí)匹配到的虛擬資源的配置信息，以最小能耗和時(shí)間QoS為調(diào)度目標(biāo)，選擇最佳的物理資源并建立虛擬機(jī)到物理機(jī)的映射關(guān)系。其中，第二級(jí)映射關(guān)系是本文的研究重點(diǎn)。通過上述云環(huán)境下的兩級(jí)資源調(diào)度模型，本文可以建立從任務(wù)到物理機(jī)的有效映射關(guān)系。相較于采用多任務(wù)和超線程技術(shù)，虛擬化的兩級(jí)資源調(diào)度模型的優(yōu)勢(shì)是一個(gè)物理資源可以同時(shí)運(yùn)行多個(gè)虛擬資源，執(zhí)行多個(gè)任務(wù)，結(jié)合優(yōu)化的調(diào)度算法可以減少很多相關(guān)開銷、提高數(shù)據(jù)傳輸速率和性能。

2.2 ECEM能耗估算模型

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

(1)

(2)

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

2.3 算法變量以及時(shí)間QoS的說明

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

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

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

(2)WTij表示任務(wù)Ti在被調(diào)度之前的等待時(shí)間。

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

(4)TQoS(i)表示任務(wù)Ti的時(shí)間服務(wù)質(zhì)量即時(shí)間QoS。

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

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

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

2) 因每個(gè)任務(wù)在物理機(jī)上的完成時(shí)間是已知的，當(dāng)用戶輸入時(shí)間QoS時(shí)，系統(tǒng)會(huì)提示用戶當(dāng)前任務(wù)在各物理機(jī)上執(zhí)行的最小和最大的完成時(shí)間，且限定輸入的時(shí)間QoS范圍必須在最小和最大的完成時(shí)間之間。本文的時(shí)間QoS也指用戶期望任務(wù)的完成時(shí)間。

3 ESSAMM節(jié)能調(diào)度算法

3.1 算法描述

針對(duì)ECEM能耗模型中的第二級(jí)調(diào)度，ESSAMM算法以系統(tǒng)總能耗最小為優(yōu)化目標(biāo)，以滿足任務(wù)的時(shí)間QoS為約束條件。ESSAMM算法在Min-Max調(diào)度算法基礎(chǔ)上考慮了時(shí)間QoS和能耗，節(jié)省了大量能耗，提高了用戶滿意度，使得整個(gè)系統(tǒng)處于負(fù)載均衡的狀態(tài)。ESSAMM算法總共分為三個(gè)階段：第一個(gè)階段是計(jì)算任務(wù)完成時(shí)間；第二個(gè)階段是根據(jù)用戶設(shè)定的時(shí)間QoS，將滿足時(shí)間需求的物理資源選擇出來(lái)；第三個(gè)階段是根據(jù)能耗實(shí)現(xiàn)資源調(diào)度。

1) 第一階段：計(jì)算任務(wù)完成時(shí)間。

(1) 計(jì)算出任務(wù)集合T在物理機(jī)集合H上的完成時(shí)間。

(2) 根據(jù)(1)中的任務(wù)完成時(shí)間，選擇物理機(jī)上最大完成時(shí)間對(duì)應(yīng)的任務(wù)和最小的完成時(shí)間對(duì)應(yīng)的任務(wù)來(lái)組成任務(wù)對(duì)(同一個(gè)物理機(jī)上的任務(wù)完成時(shí)間越長(zhǎng)，任務(wù)的長(zhǎng)度就越大，可以根據(jù)完成時(shí)間來(lái)判斷任務(wù)長(zhǎng)度)，即當(dāng)前任務(wù)集合中長(zhǎng)度最大的任務(wù)Tp和長(zhǎng)度最小的任務(wù)Tq，并確定兩個(gè)任務(wù)在各物理資源Hp和Hq上的完成時(shí)間。

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

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

3) 第三階段：根據(jù)能耗實(shí)現(xiàn)資源調(diào)度。

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

(2) 比較任務(wù)Tp在各物理資源上的能耗值，取最小能耗值對(duì)應(yīng)的物理資源Hp，將Tp放在Hp上執(zhí)行，建立任務(wù)Tp到物理機(jī)Hp的最佳映射關(guān)系；對(duì)任務(wù)Tq，將Tq放在能耗值最小的物理資源Hq上執(zhí)行，建立任務(wù)Tq到物理機(jī)Hq的最佳映射關(guān)系。

3.2 算法流程

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

步驟2建立完成時(shí)間矩陣ECT。計(jì)算每個(gè)任務(wù)Ti在不同物理機(jī)Hj上的完成時(shí)間CTij，確定一個(gè)M行N列的完成時(shí)間矩陣ECT，CTij為ECT矩陣中的元素。

步驟3確定當(dāng)前任務(wù)列表中長(zhǎng)度最大和長(zhǎng)度最小的任務(wù)。根據(jù)ECT矩陣，找出每個(gè)任務(wù)的最小完成時(shí)間，并且比較出每個(gè)任務(wù)的最小完成時(shí)間，找出最大值和最小值即為長(zhǎng)度最大的任務(wù)Tp和長(zhǎng)度最小的任務(wù)Tq。

步驟4確定滿足時(shí)間QoS的物理資源。將任務(wù)Tp對(duì)應(yīng)的每個(gè)物理資源的完成時(shí)間和步驟1中設(shè)定的TQoS(p)作比較，若大于TQoS(p)則將該物理資源標(biāo)為無(wú)效；對(duì)于任務(wù)Tq同理之。

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

步驟6建立最佳映射關(guān)系。對(duì)于任務(wù)Tp，比較步驟5中的能耗值，選擇最小值Ep對(duì)應(yīng)的物理資源Hp，將任務(wù)Tp放在Hp上執(zhí)行，建立最佳映射關(guān)系；對(duì)于任務(wù)Tq，比較步驟5中的能耗值，選擇最小值Eq對(duì)應(yīng)的物理資源Hq，將任務(wù)Tq放在Hq上執(zhí)行，建立最佳映射關(guān)系。

步驟7將已經(jīng)執(zhí)行的任務(wù)Tp和Tq從云任務(wù)列表T中刪除，然后更新任務(wù)列表T，更新完成時(shí)間矩陣ECT和能量消耗矩陣ECE。重復(fù)上述步驟3，直到任務(wù)列表為空，退出循環(huán)。

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

4 仿真與結(jié)果分析

仿真實(shí)驗(yàn)從任務(wù)總完成時(shí)間、系統(tǒng)資整體源利用率以及系統(tǒng)總能耗幾個(gè)方面，分別對(duì)ESSAMM算法、Min-Max算法以及Min-Min算法進(jìn)行比較。其中，任務(wù)總完成時(shí)間代表了資源調(diào)度算法的執(zhí)行效率，系統(tǒng)的整體資源利用率代表了算法的負(fù)載均衡性能，系統(tǒng)總能耗代表了算法的節(jié)能效果。任務(wù)數(shù)量從1到1 000，物理機(jī)數(shù)量從1到100。

4.1 主要參數(shù)設(shè)置

實(shí)驗(yàn)環(huán)境：CPU 主頻 2.40 GHz，硬盤：150 GB，內(nèi)存：4 GB，操作系統(tǒng)：Windows10 64位。

開發(fā)環(huán)境：開發(fā)平臺(tái)為Eclipse，開發(fā)語(yǔ)言為Java，仿真環(huán)境為Cloudsim3.0.3。

實(shí)驗(yàn)的參數(shù)配置如表2所示，虛擬機(jī)的配置與云任務(wù)的一致。

表2 實(shí)驗(yàn)參數(shù)設(shè)置

4.2 仿真結(jié)果對(duì)比分析

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

首先，本文仿真了當(dāng)任務(wù)數(shù)從100到1 000遞增時(shí)，ESSAMM算法、Min-Max算法以及Min-Min算法的總?cè)蝿?wù)完成時(shí)間，結(jié)果如圖2所示。

圖2 三種算法的總?cè)蝿?wù)完成時(shí)間

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

當(dāng)任務(wù)數(shù)從100到1 000遞增時(shí)，將ESSAMM算法、Min-Max算法以及Min-Min算法的整體資源利用率進(jìn)行仿真，結(jié)果如圖3所示。

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

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

當(dāng)任務(wù)數(shù)從100到1 000遞增時(shí)，將ESSAMM算法、Min-Max算法以及Min-Min算法的總能量消耗進(jìn)行仿真，結(jié)果如圖4所示。

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

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

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

當(dāng)物理機(jī)的數(shù)量從10遞增到100時(shí)，將ESSAMM算法、Min-Max算法以及Min-Min算法的總?cè)蝿?wù)完成時(shí)間進(jìn)行仿真，結(jié)果如圖5所示。

圖5 三種算法的總?cè)蝿?wù)完成時(shí)間

如圖5所示，隨著物理機(jī)數(shù)量的增加，三個(gè)算法的總?cè)蝿?wù)完成時(shí)間均在不斷減小，且下降趨勢(shì)較為平緩，其中Min-Min算法的總?cè)蝿?wù)完成時(shí)間最小，Min-Max算法的總?cè)蝿?wù)完成時(shí)間介于ESSAMM算法和Min-Min算法之間。原因如下：Min-Min算法是以最小任務(wù)完成時(shí)間為目標(biāo)，調(diào)度過程較簡(jiǎn)單；Min-Max算法是以負(fù)載均衡為目標(biāo)，調(diào)度過程中將當(dāng)前任務(wù)中長(zhǎng)度最大和最小的任務(wù)“捆綁”執(zhí)行，且將任務(wù)的等待時(shí)間考慮進(jìn)去，充分利用各物理資源，達(dá)到優(yōu)化的目標(biāo)；而ESSAMM算法既考慮了負(fù)載均衡的因素，又考慮了能量消耗的因素，相較于前面兩個(gè)算法，考慮的更加全面一些，所以任務(wù)的完成時(shí)間略長(zhǎng)一點(diǎn)。

當(dāng)物理機(jī)的數(shù)量從10遞增到100時(shí)，將ESSAMM算法、Min-Max算法以及Min-Min算法的整體資源利用率進(jìn)行仿真，結(jié)果如圖6所示。

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

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

5 結(jié) 語(yǔ)

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