基于多維度資源需求的改進遺傳調度算法*

高 原顧文杰彭 暉陳 鵬

（1.南瑞集團有限公司（國網電力科學研究院） 南京 211106）（2.國電南瑞科技股份有限公司 南京 211106）（3.智能電網保護和運行控制國家重點實驗室 南京 211106）

1 引言

隨著網絡和云計算［1～2］技術的飛速發展，網絡數據正以幾何級數的方式迅速增長，為了解決對海量數據的存儲與處理，云計算海量數據處理平臺（如Hadoop［3］、Dryad［4］等）應運而生。同時IT基礎設施發展也呈現CPU、內存速度得到快速提升，而存儲設備的速度提升相對緩慢的狀態。如何在這些云平臺上利用有效的資源管理與調度策略提高處理效率成為一個非常重要的問題。

國內外已有學者或者技術領先的IT公司研究任務調度技術。如Google的Borg［5］任務調度系統、Yahoo公司開發的新一代MapReduce框架YARN［6］和誕生于加州大學伯克利分校的Mesos系統［7］。它們的特點是只針對CPU、內存資源進行調度，容易造成其他類型的資源如磁盤IO在各個節點的不均衡使用。因為IO速度相對于CPU和內存有數量級差異，它的不均衡會造成整個系統的效率低下。

任務調度問題是經典的NP-Hard問題［8］，許多學者提出了多種啟發式算法來進行解決。文獻［9～10］提出使用遺傳算法解決網格任務調度問題，但是尋找最優解時只考慮了任務的執行時間這一個目標。文獻［11］雖然提出了兩個適應度函數，但本質上還都是執行時間這一種屬性。文獻［12］提出的多目標遺傳算法以執行時間最短和執行費用最低為目標，但是與文獻［9～11］一樣，算法的輸入參數只有任務的執行時間，沒有考慮到分布式任務調度中多種資源的負載均衡問題，比如CPU、內存（下簡稱MEM）、磁盤IO（下簡稱IO）等。文獻［13］的蟻群算法以任務延遲時間最短為目標。但是算法中的參數是在大量實驗基礎上的經驗值，不具備通用性。文獻［14］中的粒子群算法仍然僅以任務的總完成時間最短作為調度目標，而且由于沒有進行局部最優處理，算法很快便收斂到局部最優。綜上所述，在求解分布式任務調度問題時，多數啟發式算法的研究文獻存在以下不足：1）大多選擇執行時間作為適應度函數，但是實際工程中任務的執行時間是一個預先很難確定，也容易受到環境影響而變化的量，導致算法的實用性不高。并且執行時間參數不適合調度常駐進程；2）算法初始解和參數的優化力度不足，算法隨機性較大；3）由于啟發式算法固有的特點，求解容易陷入局部最優，往往不能得到問題最優的解決方案；4）沒有考慮資源使用的負載均衡，特別是沒有考慮使用更容易造成任務延遲的IO資源作為調度參數。

考慮到上述調度系統和調度算法的不足，本文提出一種基于CPU、MEM、IO三種資源維度的遺傳算法用于任務調度，并對初始種群提出三種優化方法，對遺傳變異過程也進行了改進。考慮到硬件資源的爭搶會拖慢任務的執行速度，本文采用在實際系統中較為實用的各類資源占用均方差作為多目標的適應度函數，目的在于使任務調度后的整個系統的資源使用更加負載均衡，減少任務之間的資源沖突，提高任務的執行速度。最后用測試數據說明了本算法在收斂性和優化目標方面都有良好的表現。

2 支持多資源維度的分布式任務調度模型

2.1 任務調度的軟件框架

基于本文調度算法實現的軟件框架由資源管理器、節點管理器、任務管理器等模塊組成，如圖1所示。

圖1 任務調度的軟件框架

首先是由用戶定義需要被調度的任務的屬性，如各類資源的需求等。然后資源管理器中含有的調度器會根據本文的算法將任務調度到具體的節點，由節點管理器將任務實例啟動。

2.2 任務調度的數學模型

本文任務調度算法中的各個參數的數學描述如下：

1）N個任務的集合T=｛T1，T2，T3，…，TN｝；

2）資源類型的集合R=｛CPU，MEM，IO｝；

3）M個節點第i種資源總量的集合Rti=｛Rti1，Rti2，Rti3，…，RtiM｝，i∈R；

4）M個節點第i種資源已使用量的集合Rui=｛Rui1，Rui2，Rui3，…，RuiM｝，i∈R；

5）負載均衡值：

式（1）中的負載均衡值σi是第i種資源已使用量的均方差，用來衡量該資源的使用分布情況。其中Ruij是第j個節點的第i種資源的使用量，Riavg是所有節點上第i種資源使用量的平均值。均方差越小，資源使用分布越平均，任務之間的資源競爭越少，系統的整體運行效率越高。

3 基于多維度資源需求的遺傳調度算法

本文對遺傳算法做了多個方面的優化，首先任務的參數使用實際可測得的CPU、MEM和IO屬性，沒有使用不確定的執行時間，這樣常駐類型的任務也可進行調度；然后對初始種群使用三種方法進行了優化；并對算法的遺傳操作進行了改進；算法的適應度函數也采用多目標進行了優化。改進后的遺傳算法流程圖如圖2所示。

圖2 改進遺傳算法的流程圖

3.1 染色體編碼

在任務調度的遺傳算法中，一個染色體代表一種任務調度方案。如圖3所示，染色體的長度是任務總數的2倍，虛線左側是任務調度的序列，左側基因的值為任務的序號。虛線右側是資源節點的選擇序列，右側基因的值是節點的序號。圖中整個染色體表示8個任務被分別調度到4個可用的資源上去執行，其中任務T1被調度到R3即第三個節點上，任務T3被調度到R4，依次類推。

圖3 染色體示例

也可用｛1，3，4，8，6，5，2，7；3，4，1，2，4，2，1，3｝的形式表示，染色體的長度由待調度任務的數量確定。

3.2 初始種群優化

對初始種群的優化思想是染色體表示的任務調度方案能夠使得各維度的資源均方差盡量小，即各個節點的資源使用更加均衡。本文首先使用改進的主資源公平算法（詳見3.2.1）得到1個精英染色體；然后使用單資源維度的貪心算法（詳見3.2.2）得到3個精英染色體；最后采用讓初始種群在可能取值的范圍內盡可能均勻分布的方法（詳見3.2.3）產生多個隨機均勻分布的染色體。這些染色體組成初始種群，作為遺傳算法的初始解集。

3.2.1 CMI-DRF算法

本文將IO與CPU、MEM資源統一考慮，設計了一種支持三維度的主資源公平算法，下稱為CMI-DRF（CPU，Memory，IO based-Dominant Resource Fairness）算法，此算法用于遺傳算法的初始種群優化。并通過Linux操作系統的/proc文件系統采集CPU、MEM和IO資源的狀態。包括系統總資源容量和每個進程資源使用的狀態。本文使用每個任務的IO需求占整個系統總IO容量的比值進行調度。

以下舉例說明多資源維度DRF算法的執行過程。假設系統中有4臺服務器，每臺服務器有24個CPU核心、16G的內存，單機IO能力設定為10個單位。假設有三種類型的任務，每個任務需要在調控系統中啟動4個實例，每個實例需要的資源量為

A：<2CPU，2GB，4IO>

B：<3CPU，4GB，2IO>

C：<4CPU，1GB，1IO>

對于A任務，每個實例要消耗系統總體CPU的1/48、內存的1/32和IO的1/10，所以A的主消耗資源（以下簡稱為主資源）為IO；同理可得B的主資源為內存，C的主資源為CPU。

算法的調度過程如下：

初始化狀態下所有任務的主資源比例都為0，先選取A任務進行調度，部署在node1上；然后是B和C分布在node2和node3上部署一個實例。此時三種任務的主資源使用量分別是1/10、1/16、1/24，因此下一個部署的實例應該是任務C，部署在node4。此時C的主資源變為1/12，B的主資源份額變為最小，因此應該部署一個B的實例，B的主資源是內存，考慮到負載均衡，選擇一個內存消耗最小的node3進行部署。因此直到全部12個任務實例部署完成，可得到調度序列如表1。

任務在4節點的集群中的調度結果如圖4所示，圖中圓括號中的數字代表調度序列中的步驟編號。

圖4 多資源維度DRF算法的調度結果

將圖4的調度結果轉換為染色體的的表達方式則為：｛1，2，3，3，2，3，1，2，3，2，1，1；1，2，3，4，3，1，4，1，2，4，2，3｝。

表1 CMI-DRF算法的調度序列

3.2.2 貪心算法

本文使用貪心算法產生初始種群中的精英染色體，目的是使得初始種群中部分個體適應度大，因而能更好地指導種群的尋優過程。但是與DRF不同，貪心算法每次只能處理一類資源，所以需要執行三次得到三個精英染色體加入到初始種群中，算法的流程如下：

1）如果待調度任務集合不為空，選取本次算法指定資源需求最大的任務i，否則調度完成；

2）選取該項資源已使用量最小的節點j，如果任務i的各項資源需求均小于節點j的資源空閑量，將任務調度到該節點，否則算法結束；

3）Di←任務i的資源需求；

4）Ruj←Ruj+Di（更新節點j的資源使用量）；

5）返回1）。

理論上，通過貪心算法得到的3個染色體并非最優解，但是都是比較優秀的可行解，它們都將被加入到本文遺傳算法的初始種群中。

3.2.3 均勻分布算法

初始種群的數量越大，遺傳算法越容易找到最優解，但是算法的執行時間也越長。隨著待調度的任務數量增加，排列組合形成的全體染色體的數量呈指數級增長。在保證算法的執行時間可接受的同時，如何保證初始種群的多樣性是影響遺傳算法性能的一個關鍵問題，本文采用的是一種讓初始種群盡量均勻分布在全局解空間范圍內的方法，盡最大可能保證算法能夠搜索到最優解。

因為初始種群規模太大會讓遺傳算法執行時間過長，但是隨機生成初始種群染色體的時間是較快的。本優化方法的思想就是盡可能多地在全局解空間內產生染色體，然后在其中根據均勻分布的原則選取一個染色體子集參與遺傳算法運算，即在全局解空間內進行均勻的采樣。假設有8個任務要部署在8個節點上，所有的部署方法組成的集合就是這個問題的全局解空間，染色體后半段的隨機值介于｛0，0，0，0，0，0，0，0｝和｛7，7，7，7，7，7，7，7｝之間（節點號在實際編程時采用從0開始）。圖5是一個全局解空間大體形狀的示意圖，是32個任務部署在8個節點上的8196個染色體的分布圖。橫坐標是染色體個數，縱坐標是染色體在解空間中的位置。圖中可以看出在縱軸方向分為較明顯的8段，是因為節點數為8，染色體中8和9的數值不可能存在。

圖5 染色體全局解空間示意圖

從中按照均勻分布原則抽取128個染色體加入到初始種群中，這128個染色體的分布圖如圖6所示。

圖6 優化后的初始種群示意圖

在128個均勻分布染色體的基礎上，用CMI-DRF算法和貪心算法產生的4個精英個體替換掉其中的4個染色體，組成新的既有精英個體，分布又較為均勻的初始種群。

3.3 適應度函數設計

為了將問題的目標函數轉換為指導遺傳算法尋優的適應度函數，本文的適應度函數由三個部分組成，分別是σCPU、σMEM以及σIO，如下所示：

式（2）、（3）、（4）分別衡量CPU、MEM、IO的負載均衡狀態。在處理多目標規劃問題時，一般需要將多目標規劃問題轉化為單目標問題，類似地，遺傳算法的適應度函數的設計也遵循這個原則。

假設LoadBalance（i）為第i條染色體的整體資源負載均衡值，那么它可以表示為

其中，σCPU(i)、σMEM(i)和*σIO(i)是第i條染色體的CPU、MEM和IO部分的負載均衡值。w1+w2+w3=1，且w1≥0，w2≥0，w3≥0。這里，w1、w2、w3分別為CPU、MEM和IO負載均衡部分的權重。

如果集群整體資源的負載均衡值越小，那么該任務調度方案越好。因此，本文的適應度函數為

其中，Fitness（i）為第i條染色體的適應值。

3.4 遺傳操作改進

選擇：選擇操作是為了有效地選出優秀個體進行交叉，將其優秀基因遺傳到下一代，本文根據每個個體適應度在整個種群總適應度中所占的比例，采用輪盤賭選擇機制；

交叉：交叉操作的作用是使得算法能遍歷更大的解空間，本文采用了基于交叉點的多點交叉的方式，即對一對染色體交叉點的后半部分基因進行交叉；

變異：變異操作是一種預防算法陷入局部最優的手段，本文采用的變異方式是，基于變異點的單點隨機變異；

局部最優處理：在一般啟發式算法中，在迭代過程中，算法容易陷入局部最優，導致最優個體的搜尋陷入停滯狀態，如果沒有干預，算法得到的解質量并不會很高。遺傳算法也有同樣的問題，雖然變異操作也可以預防局部最優，但是由于變異概率較小，而且變異點多為單點變異，跳出局部最優也需要較長的時間開銷。為了處理該問題：本文提出了一種基于適應度大小的大變異。

Step1：比較當代最優個體適應值與上代最優個體適應值大小，如果相等，更新計數器：SAME_GEN，SAME_GEN←SAME_GEN+1；否則，繼續下一輪迭代；

Step2：比較SAME_GEN與MAX_SAME_GEN大小，如果相等，則進入Step3；否則，繼續下一輪迭代；

Step3：將當代所有個體按照適應值從大到小進行排序，找到排在后面的REPLACE_NUM個個體，替換其所有基因，替換方式為隨機替換，形成新一代種群；

Step4：將Step3中形成的新一代種群替換當前種群，繼續參與迭代計算。

由于新的種群既保留了前面迭代后遺傳下來的優秀個體基因，又加入了新的個體，因此，能更好地跳出局部最優。

4 實驗結果與分析

本文的算法實現采用C++編程語言，分別實現了基本遺傳算法以及改進后的遺傳算法，在任務數量固定和不固定場景下共進行了數百次實驗，對兩種算法的性能進行對比，驗證了改進算法的有效性和在任務調度方面的性能提高情況。

4.1 任務數固定情況下的實驗

在任務數固定的情況下，進行100次實驗，比較基本遺傳算法和改進遺傳算法得到的最終可行解的適應值。

考慮到磁盤IO對性能影響較大，在實驗中，我們給予了IO較高的權重，具體的實驗參數設置如下。

任務數量：32，每次實驗迭代次數：100，處理機數量：8，種群規模：128，遺傳選擇：輪盤賭選擇，交叉概率：0.75，變異概率：0.05，CPU權重系數：0.1，內存權重系數：0.1，IO權重系數：0.8。

圖7是100次實驗后，基本遺傳算法（BGA）和改進遺傳算法（IGA）的適應值大小對比圖。

圖7 任務數固定情況下，多次實驗的最終適應值對比圖

由圖7可以看出，在任務數量固定的場景中，改進后的遺傳算法在100次實驗中，最終的適應值絕大部分都大于基本遺傳算法（下稱BGA）得出的值，改進遺傳算法（下稱IGA）的平均適應值大約是基本算法的2.5倍。說明精英個體的加入以及局部最優處理確實可以起到指導種群向更好方向進化的作用，因而得到的可行解的質量也更好。

4.2 任務數變化情況下的實驗

本次實驗測試在不同任務數量的場景中，基本遺傳算法和改進遺傳算法的性能。考慮到遺傳算法的隨機性，本實驗每組數據是連續10次實驗結果的平均值。

實驗參數設置如下：

每次實驗迭代次數：100，處理機數量：8，種群規模：128，遺傳選擇：輪盤賭選擇，交叉概率：0.75，變異概率：0.05，CPU權重系數：0.1，內存權重系數：0.1，IO權重系數：0.8。

實驗中被調度的任務類型有8種，每種任務對CPU、MEM和IO的需求如表2所示，其中CPU單位是核心、內存是G字節、IO是一個比值。

表2 每種任務的資源需求

每輪實驗通過增加任務的實例個數達到任務數量遞增的效果，如每種任務部署5個實例則共有40個任務。每輪測試的結果如圖8所示。

圖8 不同任務數量下，兩種算法最終適應值對比圖

由圖8可以看出：隨著調度任務數量的增加，基本遺傳算法的適應值有下降的趨勢，BGA得到的最終可行解的質量并不高；但是與BGA不同的是，IGA在待調度任務數量增加時，依然可以得到較優的可行解，在0-120個任務的范圍內，改進遺傳調度算法的平均適應值大約是基本算法的2.6倍，表現出了更好的負載均衡性能。這是因為不論任務調度的規模如何，IGA算法的初始種群要優于BGA，而且IGA在迭代過程中會根據適應值的變化情況，適時地進行局部最優處理，保證了后代種群向著全局最優解的方向不斷進化。與BGA相比，IGA不會因為調度任務規模的增大而出現適應值降低的情況，因此使用IGA算法進行任務調度時，能夠獲得更好的系統級負載均衡的效果。

5 結語

本文提出的基于多維度資源需求的改進遺傳調度算法能夠支持使用CPU、內存、磁盤IO三個維度的資源進行調度，使得任務對系統中各個節點資源的使用更加負載均衡，并能同時支持調度常駐和非常駐任務。算法通過初始種群的優化和局部最優處理，引導種群向更好的方向發展。實驗結果表明，本文的改進遺傳算法相對于傳統的遺傳算法取得了更好的效果。