高性能計算平臺中基于云計算的虛擬機優化調度研究

吳超越

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

高性能計算平臺中基于云計算的虛擬機優化調度研究

吳超越

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

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

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

1 云計算概述

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

2 優化的蟻群優化算法

2.1 蟻群算法與螞蟻系統

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

2.2 改進螞蟻系統

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

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

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

節點信息素=w1*CPU信息素+w2*內存信息素+w3*外在信息素+w4*帶寬信息素

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

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

2.3 改進蟻群算法

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

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

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

從節點i到節點j概率=

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

3 實驗結果與分析

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

表1 實驗數據

由表1實驗數據得出，當α=1，β=2，n=2.5時組合達到最優.以此組合為參數，實驗用基于改進螞蟻系統模型和基于改進蟻群算法調度方法處理具有20個任務量的作業，實驗結果如表2：

表2 實驗結果

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

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

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

TP393

A

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