高性能計算平臺中基于云計算的虛擬機優(yōu)化調(diào)度研究

吳超越

（南京曉莊學院，江蘇 南京 211171）

高性能計算平臺中基于云計算的虛擬機優(yōu)化調(diào)度研究

吳超越

（南京曉莊學院，江蘇 南京 211171）

虛擬機資源在云計算環(huán)境的分配是云計算的重要技術(shù)環(huán)節(jié)，虛擬資源是否能被高效調(diào)用是制約是云計算效率的重要指標.本文提出一種引入螞蟻相遇機制的改進蟻群算法，并將其應用到云計算虛擬機資源調(diào)度中.

云計算；虛擬機；蟻群算法

1 云計算概述

云計算是以虛擬化技術(shù)為基礎(chǔ)，以網(wǎng)絡為載體提供基礎(chǔ)架構(gòu)、平臺、軟件等服務為形式，整合大規(guī)模可擴展的計算、存儲、數(shù)據(jù)、應用等分布式計算資源進行協(xié)同工作的超級計算模式.云系統(tǒng)的后臺有大量的集群使用虛擬機的方式，通過高速的互聯(lián)網(wǎng)互連，組成大型的虛擬資源池.這些資源池可自主管理和配置，用數(shù)據(jù)冗余的方式保證虛擬資源的高可用性.并具有分布式存儲和計算、高擴展性、高可用性、用戶良好性等特征.

2 優(yōu)化的蟻群優(yōu)化算法

2.1 蟻群算法與螞蟻系統(tǒng)

蟻群算法能模擬真實螞蟻搜索食物時相互間的反饋和群體分布協(xié)作行為，獲得優(yōu)化的行進路線，因此路徑蟻群算法在諸如旅行查找等隨機搜索方面具有廣泛的應用.總結(jié)蟻群算法的運算過程，可概括出以下特點：(1)路徑上各個節(jié)點的信息素濃度隨著時間的推進按一定比例逐漸變化.到訪螞蟻根據(jù)周圍節(jié)點信息素的濃度來計算周圍各個節(jié)點的可能概率，擇優(yōu)選擇概率最高的節(jié)點作為下一步的行進節(jié)點.(2)為避免螞蟻陷入程序死循環(huán)，當前循環(huán)中已經(jīng)訪問的節(jié)點將被標記并禁止再次訪問.(3)當走過某段路線后，根據(jù)該路線的長度信息，螞蟻將會標記與其長度相適應的相應的信息素.因此，如果經(jīng)過某路段螞蟻數(shù)量較少，該路徑所累積的信息素會隨著時間按比例逐漸變少，表明該路線的成功率不高，后面螞蟻選擇的可能性也將慢慢減小.

2.2 改進螞蟻系統(tǒng)

Map/Reduce是目前廣泛使用的海量數(shù)據(jù)處理編程模型.它將一個較大的用戶任務分割成幾個較小任務量的子任務，通過虛擬資源分配機制將網(wǎng)絡中的空閑節(jié)點資源調(diào)配到各個子任務.蟻群算法憑借其高穩(wěn)定性和能分布式并行的優(yōu)點，被應用到Map/Reduce模型下虛擬機資源的優(yōu)化調(diào)度方面.在云計算環(huán)境中任何一個節(jié)點能同時運行多個任務，但如果根據(jù)每個節(jié)點的運行效率，盡量把用戶任務分配給網(wǎng)絡中效率較高的節(jié)點，將大大提高整個云計算網(wǎng)絡的效率.基于這一思路，本文為每一個節(jié)點定義一個執(zhí)行任務的預期時間閾值，如果任一節(jié)點執(zhí)行任務的時間不超過該閾值，則判定該節(jié)點為有效節(jié)點，可供調(diào)配給新交的用戶任務.

2.2.1 信息素.通過CPU數(shù)量及處理能力、內(nèi)外存和帶寬等硬件資源的容量來比較虛擬節(jié)點的信息素.CPU計算能力、內(nèi)外存及帶寬的信息素初始化分別為：

每個虛擬機節(jié)點上的信息素是各個硬件信息素的加權(quán)和，不同的硬件重要性具有不同的加權(quán)系數(shù)，具體如下式表示：

節(jié)點信息素=w1*CPU信息素+w2*內(nèi)存信息素+w3*外在信息素+w4*帶寬信息素

算法運行過程中需要對各信息素執(zhí)行動態(tài)修改，當某個有效節(jié)點被分配給當新任務時，節(jié)點上CPU利用率會相應增加，相應地該該節(jié)點上的信息素將減小.

2.2.2 虛擬機資源調(diào)度算法.改進螞蟻系統(tǒng)在云計算虛擬機資源優(yōu)化調(diào)度方面的步驟主要包括有：（1）首先初始化Worker節(jié)點的信息素.（2）將交含有多個任務的用戶作業(yè)先提交到Master節(jié)點，供其分發(fā).（3）Master節(jié)點按順序依次提取出存儲隊列中的作業(yè)，并按該作業(yè)的任務數(shù)調(diào)配相應的節(jié)點螞蟻.如該節(jié)點作用有a個任務量，Master節(jié)點則為其分配a*b個螞蟻進行路徑探索，同時啟動探索定時器.（4）每只螞蟻預先設定的規(guī)則選擇下一步的行進節(jié)點，并同時標記經(jīng)過的節(jié)點是否是有效節(jié)點，如果是有效節(jié)點則拷貝有效節(jié)點的信息原路返回；否則，螞蟻則繼續(xù)判定和選擇下一步的先進節(jié)點，直到找到有效節(jié)點為止，依次規(guī)律不斷嘗試.（5）如果在定時器計數(shù)完成前有螞蟻向Master節(jié)點報告有效節(jié)點，表示當前有有效節(jié)點可用，則該節(jié)點會被分配給新接受的用戶任務.（6）當某節(jié)點被調(diào)配給用戶任務，或某節(jié)點已完成用戶任務，則該節(jié)點上的信息素會被隨之更新，以及時表示該節(jié)點是否被占用及可用性.（7）將步驟（3）到（6）一起重復，直到用戶作業(yè)里的任務全部分配完畢.

2.3 改進蟻群算法

本文提出一種對螞蟻系統(tǒng)模型的改進措施，并在此基礎(chǔ)上，設計一種改進的蟻群算法.

2.3.1 螞蟻相遇機制.根據(jù)螞蟻在節(jié)點網(wǎng)絡中的行進方向，將人工螞蟻分為前向螞蟻和反向螞蟻兩種.前向螞蟻搜索云計算環(huán)境中的有效虛擬資源節(jié)點；當有效虛擬機節(jié)點被前身螞蟻搜索到后，算法產(chǎn)生反向螞蟻向Master節(jié)點報告發(fā)現(xiàn).反向螞蟻按原路程返回,在返回途中經(jīng)過節(jié)點時標記其中可用資源的信息素及任務預期時間等.初始時，系統(tǒng)為每個節(jié)點分配存儲區(qū)，用于存儲反向螞蟻所攜帶的節(jié)點信息，同時開戶定時器.如果前向螞蟻在計時器預設時間到來之前行進到該節(jié)點，算法判定此時有兩只螞蟻在此節(jié)點相遇.而定時器歸零后系統(tǒng)自動清除節(jié)點上所登記的信息，以準備更新可能的新信息.同一個節(jié)點在不同時刻可能會有不止一個反向螞蟻到訪，這些不同的反向螞蟻源自于多個被發(fā)現(xiàn)的有效節(jié)點，因此算法需要判別每一只反向螞蟻由中哪一個有效節(jié)點生成.

2.3.2 前向螞蟻行進規(guī)則.前向螞蟻在考慮下一步行進節(jié)點時需要考慮兩種情形，一種情形是前向螞蟻在行進過程中還沒有遇到返回的反向螞蟻；另一種情形是前向螞蟻在選擇下一步行進節(jié)點時遇到了反向螞蟻，此時需要參考反向螞蟻所報告的信息，以提高選擇下一步節(jié)點的有效性.據(jù)此，前向螞蟻需要根據(jù)不同的情形選擇不同的下一步行進節(jié)點.前向螞蟻如果在行進過程中沒有與反射螞蟻相遇，則根據(jù)以下公式計算各節(jié)點概率，并選擇概率最大的節(jié)點為行進方向.

從節(jié)點i到節(jié)點j概率=

假設前向螞蟻在某節(jié)點與反射螞蟻相遇，則在選擇下一步行進節(jié)點時需按兩種情況進行分析：（1）若前向螞蟻和反向螞蟻在某節(jié)點相遇，而該相遇節(jié)點僅登記唯一一個反向螞蟻標記的信息，且該相遇節(jié)點的相鄰節(jié)點也同樣登記了來自反向螞蟻的信息，此時需要逐一計算選擇某候選節(jié)點的概率，并將此概率與其該相鄰節(jié)點的概率進行比較，擇優(yōu)選擇有效概率最大的節(jié)點作為下一步行進的節(jié)點.（2）若前向螞蟻和反向螞蟻在某節(jié)點相遇，且相遇節(jié)點已登記了來自多個反向螞蟻的信息，此時需要在所有被反向螞蟻標記過的節(jié)點集合和候選節(jié)點集合中擇優(yōu)選擇有效概率最大的節(jié)點作為下一步行進的節(jié)點.

3 實驗結(jié)果與分析

實驗中信息素及任務預期時間在調(diào)度中的的權(quán)重分別以α、β表示；螞蟻數(shù)量以n表示.α，β和n的優(yōu)化組合需要通過實驗獲得.本文中涉及的比例因子均為0.2.本實驗將虛擬機節(jié)點數(shù)量設定為150，每個虛擬機具有約500MIPS的雙核計算能力；內(nèi)存容量設定為200兆；帶寬為2兆每秒；外存容量為1G.實驗中提交一個可被分割成20個任務量的用戶作業(yè)，將其向云計算中心反復提交10次，并分別使用基于改進螞蟻系統(tǒng)模型和基于改進蟻群算法的虛擬機優(yōu)化調(diào)度算法進行資源的分配.實驗首先需要得到α，β和n的最優(yōu)組合，該最優(yōu)組合可通過多次嘗試試驗得到(如表1所示).

表1 實驗數(shù)據(jù)

由表1實驗數(shù)據(jù)得出，當α=1，β=2，n=2.5時組合達到最優(yōu).以此組合為參數(shù)，實驗用基于改進螞蟻系統(tǒng)模型和基于改進蟻群算法調(diào)度方法處理具有20個任務量的作業(yè)，實驗結(jié)果如表2：

表2 實驗結(jié)果

可見，由于增加了螞蟻相遇機制，借助反向螞蟻標記的節(jié)有效資源節(jié)點信息，前向螞蟻搜索虛擬機資源效率得以提高，因此基于改進蟻群算法在任務分配時間方面明顯要優(yōu)于基于改進螞蟻系統(tǒng)模型.

〔1〕吳吉義，平玲娣，潘學增，等.云計算:從概念到平臺[J].電信科學，2009(12)：23-30.

〔2〕陳全，鄧倩妮.云計算及其關(guān)鍵技術(shù)[J].計算機應用，2009 (9)：2562-2567.

TP393

A

1673-260X（2014）09-0024-02