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

李　明

(上海青年管理干部學(xué)院　上?！?00083)

?

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

李明

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

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

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

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

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

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

(1)

(2)

ρ=avgV1:avgV2:avgV3:…:avgVn

(3)

(4)

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

(5)

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

(6)

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

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

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

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

3參數(shù)設(shè)置及計(jì)算資源的優(yōu)劣度評(píng)價(jià)條件

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

第一組:

虛擬機(jī)配置:

表1　虛擬機(jī)硬件配置

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

表2　虛擬機(jī)模擬云任務(wù)長(zhǎng)度配置

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

第二組:

虛擬機(jī)配置:

表3　不同虛擬機(jī)不同的硬件配置

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

表4　虛擬機(jī)模擬不同云任務(wù)長(zhǎng)度配置

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

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

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

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

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

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

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

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

6結(jié)語(yǔ)

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

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

參 考 文 獻(xiàn)

[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í)與技術(shù),2007,(7):43-44.

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

中圖分類(lèi)號(hào)TP393

DOI:10.3969/j.issn.1672-9722.2016.02.029

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

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