李　明

(上海青年管理干部學(xué)院　上海　200083)

?

基于特征粒子算法的云資源調(diào)度策略研究*

李明

(上海青年管理干部學(xué)院上海200083)

摘要詳細分析特征粒子算法的基本原理和特征粒子算法數(shù)學(xué)模型,將特征粒子算法的基本思想結(jié)合云計算環(huán)境中實際的服務(wù)質(zhì)量參數(shù)要求,設(shè)計基于特征粒子算法來的參數(shù)的設(shè)置以及計算資源的優(yōu)劣度評價標(biāo)準(zhǔn),給出任務(wù)調(diào)度的算法流程。最后詳細在CloudSim上進行仿真。通過仿真實驗,將特征粒子算法與CloudSim自帶的時間最優(yōu)調(diào)度算法和貪婪算法進行了比較,驗證了該算法的正確性和有效性。

關(guān)鍵詞特征粒子; 云計算; 資源調(diào)度; 任務(wù)分配

Research about the Scheduling Strategy of the Cloud Resource Based on the Characteristics Particle Algorithm

LI Ming

(Shanghai Institute for Youth Management, Shanghai200083)

AbstractThe fundamental principles and mathematical model of the characteristics particle algorithm were analyzed detailed. And the basic idea of the characteristics particle algorithm was combined with the service quality parameter requirement in the cloud calculation environment, then evaluation criterion of the calculation resource was designed based on the design of the characteristics particle algorithm parameter, and the algorithm process of the task scheduling was presented. Finally, the related experiments were simulated on the CloudSim, and the characteristics particle algorithm was compared with the time optimal scheduling algorithm and greedy algorithm built in the CloudSim, then the correctness and effectiveness of this algorithm was verified.

Key Wordscharacteristics of particles, cloud computing, resource scheduling, task allocation

Class NumberTP393

1引言

云數(shù)據(jù)中心的資源調(diào)度技術(shù)是云計算應(yīng)用的核心,是云計算得以大規(guī)模應(yīng)用、提高系統(tǒng)性能、兼顧節(jié)約能源的關(guān)鍵技術(shù)。優(yōu)越的動態(tài)資源調(diào)度,對于提高政府、學(xué)校和企業(yè)計算資源的利用效率、節(jié)約能源、提高資源共享和降低成本。建立起了云計算應(yīng)用平臺,加上一套完善的資源管理與調(diào)度過程進行軟配合,才可以充分利用云計算這個大平臺的所有資源,發(fā)揮云平臺最大的效率。目前已經(jīng)把貪婪算法、粒子群算法、蟻群算法運用到了云計算數(shù)據(jù)中心的資源調(diào)度上面。不過每種算法都有明顯的優(yōu)缺點,本文在總結(jié)以上各種算法的基礎(chǔ)上,提出了基于特征粒子的調(diào)度算法,該算法不僅具有全局性,可以解決貪心算法很難找到一個簡單可行并難以保證正確的缺點;而且還有很強的目的性,解決粒子群算法隨機性非常大的缺點。

2特征粒子算法的基本原理

特征粒子算法是模擬從沒有(或者很少)相似性、彼此之間離散分布的人群中尋找一個具有特定特征的目標(biāo)人物的過程,設(shè)計出的根據(jù)特征群體分布尋找目標(biāo)的智能搜索算法。運用特征粒子算法進行搜索的時候,不再考慮搜索的路徑,而是對一個個的群體進行特征匹配搜索。當(dāng)搜索的時候,將這個特征群體中最具有代表性的特征提供出來,然后將目標(biāo)粒子的特征與該群體的特征進行特征集對比,如果這個特征群體完全不具備目標(biāo)粒子的特征,則該群體中的所有的粒子將不再進行搜索。

面對大量的配置不同、效率不同的計算節(jié)點,初期采用動態(tài)對群體協(xié)作方法,主群側(cè)重于全局搜索,次群側(cè)重于局部搜索,將眾多不同的計算節(jié)點根據(jù)特征系數(shù)ρ而分成不同的群體。每一個子群,計算出群的特征常量系數(shù)ρ:

(1)

(2)

ρ=avgV1:avgV2:avgV3:…:avgVn

(3)

(4)

其中,Vi表示計算節(jié)點第i號屬性的屬性值,一個節(jié)點可以有n個屬性;totalVi表示一個計算節(jié)點分組屬性Vi的總和;avgVi表示屬性Vi在一個分組中的平均值;ρ表示一個分組的分組特征系數(shù);Mi表示第i個分組中單個節(jié)點的特征對比常量,該常量表示與該分組的匹配度,常量越大,表示節(jié)點越不匹配當(dāng)前所在組。

(5)

根據(jù)式(1)~式(3),獲得子集的特征系數(shù),對比每一代子群每個節(jié)點的特征系數(shù)ρi,根據(jù)學(xué)習(xí)參數(shù)M,將其找到的處于學(xué)習(xí)范圍之外的子集Ri(Ri∈Ui)。根據(jù)式(4),獲得子集中的每一個計算節(jié)點的子集相對系數(shù),根據(jù)式(5),將Ri中的每一個節(jié)點Rij歸并到其他的能夠容納到相似特征系數(shù)的子群中,逐層計算子集并進行子集遷移,形成新的不同于初始化的集合,每一個集合都擁有在學(xué)習(xí)參數(shù)M認識范圍內(nèi)的子集;或者根據(jù)學(xué)習(xí)參數(shù)M無法找到被篩選出來的非子集的歸屬,則將未歸屬的子集,建立起新的集合Rnew(如圖1所示)。最終形成一個擁有相似特征系數(shù)的集群。

(6)

T(i)表示一個特征節(jié)點執(zhí)行模擬任務(wù)消耗的時間,g(Pi)表示節(jié)點的性能函數(shù),f(ρi)表示節(jié)點i在模擬任務(wù)中執(zhí)行函數(shù)。

圖1　節(jié)點遷移示意圖

對已經(jīng)特征化的種群搜索,主群對全局進行匹配搜索,次群則根據(jù)個體要求,從每一個特征種群中提取出最優(yōu)特征個體,并滿足個體的成本要求,從而得到次群中最優(yōu)解,子群將最優(yōu)可用個體集信息傳遞給主群,主群根據(jù)式(6),對子群最優(yōu)個體重新進行歸并優(yōu)化,逐層挑選出最優(yōu)個體。

通過這種方式,可以將各種特征的節(jié)點有序地管理在可控域中,對自己進行檢索,即將各個自己中最優(yōu)個體直接篩選出來,從而可以更加快速地避免對額外節(jié)點的篩選。

3參數(shù)設(shè)置及計算資源的優(yōu)劣度評價條件

根據(jù)Map-Reduce架構(gòu)模型,云中的每個計算節(jié)點由兩部分組成:主作業(yè)調(diào)度節(jié)點、任務(wù)分配節(jié)點。主作業(yè)調(diào)度節(jié)點,負責(zé)一個區(qū)的節(jié)點任務(wù)分配,以及最終的任務(wù)執(zhí)行結(jié)果的匯總處理;任務(wù)分配節(jié)點則負責(zé)執(zhí)行被分配的作業(yè),以及提交完成的作業(yè)。任務(wù)分配時,主作業(yè)調(diào)度節(jié)點將一個可分配的大任務(wù),分解為可獨立、并發(fā)執(zhí)行的小任務(wù)——任務(wù)片段,并將這些任務(wù)片段,根據(jù)調(diào)度算法分配到各個任務(wù)分配節(jié)點中。Map端分配完成后,由各個節(jié)點分別執(zhí)行被分配到節(jié)點上的任務(wù),完成后通知主作業(yè)調(diào)度節(jié)點,完成收集任務(wù)節(jié)點執(zhí)行的結(jié)果,并根據(jù)原來已經(jīng)設(shè)計好的組合方案將結(jié)果整理起來并反饋最終結(jié)果——Reduce操作。

資源調(diào)度的優(yōu)先級分配中,本地資源的優(yōu)先級最高,異地的優(yōu)先級次之。在分配作業(yè)的時候,如果本地的節(jié)點資源足以承受被分配的資源任務(wù),根據(jù)本地優(yōu)先的原則,將按照任務(wù)需要以及負載均衡的辦法,完成本地資源的分配,保證任務(wù)可以完成的同時,整體使用的硬件資源最低、時間成本最低。如果本地的資源無法滿足,則需要根據(jù)資源調(diào)度算法,對遠程的節(jié)點進行任務(wù)分配。本文提到的特征粒子調(diào)度算法就是調(diào)度算法中的一種。

根據(jù)云計算資源調(diào)度的高度目的性——時間成本或價格成本等特性,可將各個節(jié)點根據(jù)成本進行特征劃分。

根據(jù)資源特性,首先將本地資源充分利用,根據(jù)資源與任務(wù)的關(guān)系,可以獲取一個任務(wù)曲線T、資源特征曲線R、時間成本矩陣M。如果任務(wù)曲線比較平緩,說明子任務(wù)的劃分比較均衡;如果資源特征曲線比較平緩,說明本地的節(jié)點資源在性能上比較均衡;時間成本矩陣是根據(jù)當(dāng)前的任務(wù)和當(dāng)前的資源性能做出的一個時間成本無向圖G(V,E),矩陣中每一個元素,都表示該任務(wù)在對應(yīng)特征資源中使用的時間成本。

首先將本地的資源根據(jù)特征資源做一個基本的特征均衡分配,保證本地的資源已經(jīng)被完全使用,并模擬測算出本地的模擬時間tsimu,根據(jù)tsimu將云中分配的多個主控域管理的最快時間進行對比,直接淘汰掉不符合最小時間成本的云團。當(dāng)淘汰掉不符合基本時間成本的云團之后,在剩余的云團Cuse中,根據(jù)時間成本曲線Se,從云團中找到對應(yīng)的特征節(jié)點,并由主作業(yè)調(diào)度節(jié)點,對該特征集中的節(jié)點進行預(yù)算,找到其中的最佳匹配節(jié)點,并反饋到最原始主作業(yè)調(diào)度節(jié)點中,針對尚未分配的資源節(jié)點,形成一個新的時間成本矩陣Gnew(V,E)。

Gnew(V,E)中V由多個異地節(jié)點組成,原本已經(jīng)分配m個接近平衡的任務(wù),一共有ntotal個任務(wù)需要分配,則需要從云節(jié)點中分配的節(jié)點為

V={v1,v2,…,vn};n=ntotal-m

而每一個云節(jié)點上的時間消耗,由計算市場tcalc和因在網(wǎng)絡(luò)上傳輸?shù)南膖delay組成:

ti=tcalc+tdelay;i∈[1,n]

當(dāng)本地的資源分配的特征變化很大、本地資源不足以承擔(dān)任務(wù)時,則將任務(wù)以游離的方式,在附近的云中的主作業(yè)控制節(jié)點進行資源交流,從而將任務(wù)特征屬性轉(zhuǎn)移到臨近的資源節(jié)點中進行調(diào)度,而時間的成本,由原有的資源為起始進行疊加。直到找到在限制條件以內(nèi)的時間成本盡量小的資源調(diào)度結(jié)果。

4算法調(diào)度的工作流程

首先,獲取用戶的任務(wù)并按照優(yōu)先級進行排序、分類,分類體現(xiàn)了用戶任務(wù)對不同QoS的需求,并根據(jù)的特征分類,利用特征粒子調(diào)度算法進行資源調(diào)度、分配。最大限度地滿足要求、整體任務(wù)計劃執(zhí)行時間相對最短,達到此目標(biāo)之后,即表示已經(jīng)挑選出了最佳的任務(wù)分配,將計算任務(wù)與云中的計算資源進行M-N進行綁定,運行任務(wù)。其流程圖如圖2所示。

圖2　算法調(diào)度流程圖

5調(diào)度算法驗證

由于CloudSim平臺的限制,各個虛擬機資源的實時資源占用情況、虛擬機的故障率無法直接從平臺中獲取,以及CloudSim平臺本身在通信上的約束管理上的不確定性,現(xiàn)使用CloudSim中任務(wù)的最終完成時間進行驗證調(diào)度算法。為了驗證調(diào)度算法,需要模擬盡可能復(fù)雜、具有代表性的虛擬環(huán)境條件,因此根據(jù)最有效的參數(shù)進行模擬:帶寬、CPU的Mips、內(nèi)存。

模擬分為兩組進行,第一組的模擬,使用完全相同的虛擬機配置,對不同的任務(wù)進行處理;第二組使用不同的虛擬機配置——虛擬機具有不同的參量比,對不同的任務(wù)進行處理。

第一組:

虛擬機配置:

表1　虛擬機硬件配置

任務(wù)設(shè)置:

表2　虛擬機模擬云任務(wù)長度配置

對于第一組的虛擬機、任務(wù)的設(shè)置,所有的虛擬機都是用了相同的配置,在任務(wù)執(zhí)行的時候,虛擬機之間沒有了性能上的差異,則重點就在于對于任務(wù)的處理上。這里分別使用了輪轉(zhuǎn)法、貪心法、特征粒子算法執(zhí)行相同的任務(wù),得出在相同配置條件下執(zhí)行任務(wù)使用的時間來進行對比。

第二組:

虛擬機配置:

表3　不同虛擬機不同的硬件配置

任務(wù)設(shè)置:

表4　虛擬機模擬不同云任務(wù)長度配置

對于第二組來說,更接近于現(xiàn)實的環(huán)境,使用了三組計算能力分別不同,形成了三組特征粒子,使用的是相同的任務(wù)配置。對這樣的接近現(xiàn)實的環(huán)境,繼續(xù)使用三種不同的調(diào)度算法(輪轉(zhuǎn)法、貪心法、特征粒子算法)執(zhí)行,并對最終的執(zhí)行時間進行對比。

第一組為多組相同配置虛擬機、多組相同任務(wù)、多次運行取平均值的模擬結(jié)果統(tǒng)計:

圖3　同任務(wù)同虛擬機配置對比結(jié)果

第二組為多組不同的虛擬機、多組不同的任務(wù)、多次運行取平均值的模擬結(jié)果統(tǒng)計:

圖4　不同任務(wù)不同虛擬機配置對比結(jié)果

對于穩(wěn)定性和健壯性而言,輪轉(zhuǎn)法整體上波動范圍比較大,雖然是最基本的調(diào)度算法,但是對于這樣的執(zhí)行效率上的波動,還是相當(dāng)大的。而對于輪轉(zhuǎn)法來講,在相同的配置的情況下,無論是執(zhí)行效率,還是執(zhí)行時間,都有一個相對穩(wěn)定的線性增長,屬于比較穩(wěn)定的一種,而對于配置條件完全不同的任務(wù)和虛擬機而言,則執(zhí)行情況存在一個明顯的曲線,整體上無法解決配置不同的情況。

在時效上,輪轉(zhuǎn)法一直沒有什么優(yōu)勢,而對于貪婪法和特征粒子法而言,貪婪法在相同配置的條件下,尋找虛擬機的過程比較容易,相對于特征粒子來說,省去了小部分的計算時間,因此相同的配置條件下,和特征粒子沒有什么區(qū)別。而對于不同配置的大環(huán)境下,貪婪法由于無狀態(tài)的部分最優(yōu)的局限性便展現(xiàn)出來,對于特征粒子法而言,它考慮了整體上的處理效率的問題,因此在整體上會尋求一個平衡點,從而解決整體上運行的時間問題。

綜上,對于特征粒子調(diào)度而言,它能夠有效地規(guī)避不可用節(jié)點,以及效率低下的節(jié)點,可以從全局出發(fā),對全局的節(jié)點進行了統(tǒng)籌管理,對于高效的、具有特征性的處理機有機地劃分為一組,另一方面,云計算節(jié)點的搜索非常具有目的性,因此對于特征粒子算法而言,恰巧應(yīng)用了這一優(yōu)勢,有效地利用了所有的資源,并保證了處理效率。

6結(jié)語

云計算的技術(shù)特性、需求特性、發(fā)展趨勢,決定

了云計算中針對數(shù)據(jù)中心的調(diào)度方式,必須具備高效、合理的資源調(diào)度管理方案,以及快速的用戶作業(yè)處理兩個特性。本文分析了基于特征粒子算法在資源調(diào)度在云計算中的應(yīng)用與實現(xiàn),該算法在節(jié)點的全局統(tǒng)籌方面具有很大的優(yōu)勢,無論是在搜索過程,還是在負載均衡方面,均具有特殊的優(yōu)勢。

參 考 文 獻

[1] L. Smarr, C. Catlett. MetaComputing[J]. Communications of the ACM,1992,35(6):452.

[2] Dean J, Ghemawat S. MapReduce: Simplified Data Processing on Large Clusters. OSDI’04: Sixth Symposium on Operating System Design and Implementation,2004:137-150.

[3] Wickremasinghe B, et al. CloudAnalyst: A CloudSim-based Tool for Modeling and Analysis of Large Scale Cloud Computing Environments[C]//Proceddings of the 24th IEEE International Conference on Advanced Information Networking and.

[4] I. Foster. Internet Computing and the Emerging Grid[D]. Nature Web Matter, December 7,2000.

[5] Jeffrey Dean, Sanjay Ghemawant. MapReduce: Simplelied Data Processing on Large Clusters[C]//OSDI,2004.

[6] Sabata B, Chatterjee S, Davis M, et al. Taxonomy forspecifications[C]//Proceddings of the 3rd International Workshop Object-Qriented Real-Time Dependable System,1997:100-107.

[7] Rodrigo N. Calheiros, Rajiv Ranjan, Cesar A. F. De Rose, and Rajkumar Buyya, CloudSim: A Novel Framework for Modeling and Simulation of Cloud Computing Infrastruct users and Services. Technical Report, GRIDs-TR-2009-1, Grid Computing and Distributed Systems Laboratory, The University of Melbourne, Australia, March 13,2009.

[8] 李立.GridSim網(wǎng)格仿真工具研究[J].電腦知識與技術(shù),2007,(7):43-44.

LI Li. Research of GridSim Grid Simulation Tool[J]. Computer Knowledge and Technology(Academic Enchange),2007,(7):43-44.

中圖分類號TP393

DOI:10.3969/j.issn.1672-9722.2016.02.029

作者簡介:李明,男,碩士,講師,研究方向:計算機技術(shù)與軟件。

*收稿日期:2015年8月11日,修回日期:2015年9月20日