呂計英

（西山煤電集團信息中心，山西 太原 030053）

云計算不僅要面向大量的用戶群，還要處理海量任務(wù)與數(shù)據(jù)，因此任務(wù)調(diào)度就成為了云計算中的重點與難點?，F(xiàn)有的常見任務(wù)調(diào)度算法有3種：FIFO調(diào)度算法、公平調(diào)度算法（Fair Scheduler）和計算能力調(diào)度算法（Capacity Scheduler）。它們都存在一些不足：FIFO調(diào)度算法會忽略不同用戶的不同作業(yè)需求，使交互性的用戶作業(yè)長期處于等待狀態(tài)，影響系統(tǒng)效率；公平調(diào)度算法會造成計算資源的部分浪費，影響資源利用效率；計算能力調(diào)度算法容易使作業(yè)處于長期等待狀態(tài)，陷入局部最優(yōu)。為了解決這些算法的不足，一些借鑒遺傳算法、蟻群算法等智能算法的云環(huán)境任務(wù)調(diào)度算法相繼被提出?；诟倪M的蟻群算法的云環(huán)境任務(wù)調(diào)度算法[1]，避免了蟻群優(yōu)化算法陷入局部最優(yōu)，縮短了任務(wù)平均運行時間，提高了資源利用效率。針對云計算的編程模型框架，提出了一種具有雙適應(yīng)度的遺傳算法的任務(wù)調(diào)度算法[2]，不僅能夠快速確定完成所有任務(wù)的時間，而且還能保證該調(diào)度策略的任務(wù)平均完成時間也較短。這增加了問題搜索空間，避免了局部最優(yōu)。

本文利用免疫算法中的克隆選擇算法，將其應(yīng)用于云計算環(huán)境中的任務(wù)調(diào)度問題。根據(jù)抗體與抗原之間親和力的大小，獲取優(yōu)秀抗體，并對抗體進行不同程度的變異，最終找出優(yōu)秀的抗體種群，得出問題的最優(yōu)解。通過仿真實驗，驗證其算法的有效性，并能夠快速確定任務(wù)調(diào)度最優(yōu)策略，提高了系統(tǒng)的整體性能與資源利用效率。

1 基于克隆選擇算法的云計算調(diào)度算法的設(shè)計

1.1 云計算的任務(wù)調(diào)度

目前，云計算環(huán)境大多采用Google公司提出的Map-Reduce編程模型，它是一種并行編程模式，非常適于產(chǎn)生和處理大規(guī)模的數(shù)據(jù)集。在Map-Reduce計算框架模型中，主要分為Map階段和Reduce階段。Map階段：將用戶提交的較大的作業(yè)拆分成若干個較小的任務(wù)，然后分配給多個任務(wù)服務(wù)器（Task Tracker）并行執(zhí)行，輸出處理后的中間數(shù)據(jù)；Reduce階段：將Map階段處理后的中間數(shù)據(jù)進行匯總分析處理，輸出最終結(jié)果。

1.2 基于免疫算法的云計算任務(wù)調(diào)度算法

針對云計算環(huán)境中的任務(wù)調(diào)度問題，利用免疫算法中的克隆選擇算法，可以確定使總?cè)蝿?wù)執(zhí)行時間和任務(wù)平均執(zhí)行時間都較短的任務(wù)調(diào)度策略，提高系統(tǒng)效率和資源利用率，滿足用戶的使用需求。

1.2.1 抗體的編碼與解碼

假設(shè)有p個作業(yè)（job），n個任務(wù)服務(wù)器node（計算資源），第t個作業(yè)被拆分為的任務(wù)（task）的數(shù)量為：taskNum（t），然后再對這些任務(wù)進行編號。假設(shè)抗體基因序列的長度為10，每個基因位的取值為1～5，隨機產(chǎn)生下面一個抗體基因序列：{3，2，4，5，2，1，4，3，1，5}，這個抗體基因序列代表第 1 個 task 在第3個node上執(zhí)行，第2個task在第2個node上執(zhí)行，……，第10個task在第5個node上執(zhí)行。如上述抗體基因序列解碼為：

Node1：{6，9}；Node2：{2，5}；Node3：{1，8}；Node4：{3，8}；Node5：{4，10}。

1.2.2 初始抗體種群生成

若初始抗體種群規(guī)模為S，作業(yè)個數(shù)為J，任務(wù)個數(shù)為m，任務(wù)服務(wù)器（計算資源）的個數(shù)為n，則抗體的種群初始化描述如下：系統(tǒng)隨機產(chǎn)生S個抗體，抗體基因序列的長度為m，每個基因位的取值在任務(wù)服務(wù)器個數(shù)的范圍內(nèi)隨機選取，即在[1，n]中隨機選擇。

1.2.3 克隆選擇

克隆選則是根據(jù)抗體與抗原之間的親和力大小，從抗體種群中選取優(yōu)秀抗體進行克隆，增加優(yōu)秀抗體的濃度，并通過不斷的變異進化找到最優(yōu)抗體（問題的最優(yōu)解）。因此，親和力的計算顯得尤為重要，它關(guān)系到算法的收斂速度以及解的優(yōu)劣性。

對于云環(huán)境的作業(yè)調(diào)度，一個最主要的性能指標(biāo)就是全部作業(yè)的完成時間，另外還需考慮作業(yè)的平均完成時間。在保證所有作業(yè)完成時間最短的基礎(chǔ)上，還應(yīng)該滿足作業(yè)的平均完成時間也最短。

在云環(huán)境下，基于免疫算法的任務(wù)調(diào)度算法的流程如下：

第一，初始化抗體種群：隨機產(chǎn)生規(guī)模為S的初始抗體種群Ag.

第二，F(xiàn)or每一代種群do

{

計算種群中每個抗體的親和力，根據(jù)親和力大小，選擇出N個優(yōu)秀抗體組成臨時抗體種群Ag*N；

對臨時抗體種群Ag*N進行不同規(guī)模的克隆增殖，生成增殖種群Agp；

對種群中親和力較低的抗體進行不同程度的基因重組，完成變異操作，生成目標(biāo)種群Ag′N；

引入隨機抗體進入目標(biāo)種群，豐富抗體種類，變陷入局部最優(yōu)；

}

第三，直到滿足算法結(jié)束條件。

第四，從抗體種群中選擇出親和力最高的抗體，確定最佳的任務(wù)調(diào)度方案。

2 仿真實驗及結(jié)果分析

由于云計算可以看作是一個特殊的網(wǎng)格環(huán)境，所以本文用Gridsim來模擬一個云計算的局部環(huán)境。在相同情況下，分別用遺傳算法和克隆選擇算法進行比較。

初始條件：作業(yè)（job）個數(shù)為 10，任務(wù)（task）個數(shù)為 20，任務(wù)服務(wù)器node（計算資源）的個數(shù)為5，初始抗體種群規(guī)模為50.

算法終止條件：①到達最大進化代數(shù)（這里取最大進化代數(shù)為100）；②連續(xù)20代總?cè)蝿?wù)完成時間和任務(wù)平均完成都沒有變化時，認(rèn)為算法基本收斂，算法結(jié)束。

圖1 總?cè)蝿?wù)完成時間比較

從圖1、圖2中可以看出，在進化初期，克隆選擇算法的收斂速度要明顯快于遺傳算法的，并且通過克隆選擇算法得出的總?cè)蝿?wù)的完成時間和任務(wù)平均完成時間均要小于遺傳得出的。另外，在進化后期，雖然2種算法都達到了一種基本收斂，但是克隆選擇算法收斂迭代次數(shù)以及總?cè)蝿?wù)完成時間和任務(wù)平均完成時間均小于遺傳算法的，說明了其算法的優(yōu)良性與有效性。

圖2 任務(wù)平均完成時間比較

3 結(jié)束語

本文借鑒了免疫算法中的克隆選擇算法，并應(yīng)用到云計算環(huán)境的任務(wù)調(diào)度中?？寺∵x擇算法可以解決云計算環(huán)境中的任務(wù)調(diào)度問題，能夠確定較優(yōu)的任務(wù)調(diào)度策略，提高了系統(tǒng)效率與資源利用率，是一種有效的任務(wù)調(diào)度算法。

[1]王永貴，韓瑞蓮.基于改進蟻群算法的云環(huán)境任務(wù)調(diào)度研究[J].計算機測量與控制，2011，19（5）：1203-1206.

[2]李建鋒，彭艦.云計算環(huán)境下基于改進遺傳算法的任務(wù)調(diào)度算法[J].計算機應(yīng)用，2011，31（1）：184-186.