周婉++王移芝
摘要:資源調(diào)度是云計(jì)算的一個(gè)主要研究方向,本文在研究現(xiàn)有云計(jì)算資源調(diào)度算法的基礎(chǔ)上,為了提高云計(jì)算資源的利用率,保持負(fù)載平衡,設(shè)計(jì)了基于卡爾曼預(yù)測(cè)器的云計(jì)算資源調(diào)度算法,采用卡爾曼預(yù)測(cè)器預(yù)測(cè)虛擬資源下一時(shí)刻的狀態(tài),由此得到虛擬資源的向量,然后計(jì)算任務(wù)的代價(jià),建立任務(wù)與資源的映射模型,將任務(wù)分配到合適的虛擬資源進(jìn)行調(diào)度,避免了盲目調(diào)度,提出了基于卡爾曼預(yù)測(cè)器的云計(jì)算資源動(dòng)態(tài)調(diào)度的具體算法,最后在云計(jì)算仿真平臺(tái)CloudSim上進(jìn)行仿真實(shí)驗(yàn)與分析。仿真實(shí)驗(yàn)的結(jié)果證明,本文提出的算法在任務(wù)執(zhí)行的跨度和負(fù)載均衡離差方面具有一定的優(yōu)勢(shì)。
關(guān)鍵詞:云計(jì)算;虛擬資源調(diào)度;卡爾曼預(yù)測(cè)器
中圖分類號(hào):TP311.12
文獻(xiàn)標(biāo)識(shí)碼:A
DOI:10.3969/j.issn.1003-6970.2015.09.003
0 引言
隨著計(jì)算機(jī)性能的不斷提高和互聯(lián)網(wǎng)規(guī)模的不斷擴(kuò)大,人們的計(jì)算需求和海量數(shù)據(jù)處理需求日益增長,出現(xiàn)了云計(jì)算這種新興的計(jì)算方式。云計(jì)算是在并行計(jì)算、分布式計(jì)算、網(wǎng)格計(jì)算的基礎(chǔ)上發(fā)展起來的一種商業(yè)模型,是虛擬化技術(shù)、效用計(jì)算、基礎(chǔ)設(shè)施即服務(wù)、平臺(tái)即服務(wù)和軟件即服務(wù)等概念優(yōu)化整合的結(jié)果。云平臺(tái)采用虛擬化技術(shù)將集群中的各種資源構(gòu)成資源池,接收用戶任務(wù)請(qǐng)求,并將任務(wù)調(diào)度到合適的資源上執(zhí)行。云環(huán)境下的任務(wù)數(shù)量以海量形式存在,而云計(jì)算資源具有動(dòng)態(tài)、異構(gòu)特性,這就使得云計(jì)算環(huán)境下的虛擬資源調(diào)度成為了云計(jì)算研究的一個(gè)熱點(diǎn)問題。
師雪霖等借鑒網(wǎng)絡(luò)效用最大化模型,提出了一種資源調(diào)度模型——云效用最大化模型,以達(dá)到效用最大為調(diào)度目標(biāo),可以充分提高用戶的滿意程度。徐文忠等提出了一種基于遺傳算法的關(guān)于虛擬機(jī)負(fù)載均衡的調(diào)度策略,算法在很大程度上能夠解決負(fù)載不均衡和高遷移成本問題。王艷平等設(shè)計(jì)了一種基于改進(jìn)蟻群的云計(jì)算資源調(diào)度算法。在算法中添加了查找表,存儲(chǔ)其他螞蟻推薦的節(jié)點(diǎn),縮短了搜尋資源節(jié)點(diǎn)的時(shí)間,從而使任務(wù)可以更快地獲得資源并執(zhí)行,保證了任務(wù)能夠按時(shí)完成。
本文設(shè)計(jì)了一種基于卡爾曼預(yù)測(cè)器的云計(jì)算資源調(diào)度算法,采用卡爾曼預(yù)測(cè)器預(yù)測(cè)虛擬資源下一時(shí)刻的狀態(tài),得到可用資源向量,然后建立任務(wù)與資源的映射模型,將任務(wù)分配給合適的虛擬資源進(jìn)行調(diào)度,避免了盲目調(diào)度,并提出了具體的基于卡爾曼預(yù)測(cè)器的云計(jì)算資源動(dòng)態(tài)調(diào)度算法。
l 調(diào)度模型
在云計(jì)算的虛擬資源調(diào)度模型中,主流的是Map-Reduce調(diào)度模型。由Google最早提出并應(yīng)用到云平臺(tái)中,云用戶只需編程實(shí)現(xiàn)Map-Reduce接口即以實(shí)現(xiàn)計(jì)算的并發(fā)和分布執(zhí)行。它由“Map”和”Reduce”兩部分組成。具體結(jié)構(gòu)如圖1。
Map-Reduce調(diào)度模型中,首先根據(jù)文件的大小,將其分割。在集群中分為主控制模塊和普通模塊,主控制模塊的主要職責(zé)是將工作分配給普通模塊。主控制模塊的主要工作流程是首先選取空閑狀態(tài)的服務(wù)器,然后將映射或者簡化的任務(wù)分配到這些空閑的服務(wù)器上,分配到映射任務(wù)的服務(wù)器根據(jù)主控制模塊傳達(dá)的指令讀取輸入文件的分片,之后執(zhí)行映射操作,將執(zhí)行結(jié)果保存在緩存中。映射階段的任務(wù)完成之后,將中間結(jié)果寫入硬盤,同時(shí)進(jìn)行分區(qū),將分區(qū)信息傳遞給主控制模塊。主控制模塊將中間結(jié)果保存的分區(qū)信息通知分配了簡化任務(wù)的服務(wù)器,這些服務(wù)器讀取中間結(jié)果,同時(shí)執(zhí)行用戶定義的簡化操作,最后將結(jié)果保存在輸出文件中,同時(shí)將結(jié)果通知主控制模塊。最終由主控制模塊綜合所有的輸出模塊,輸出最終的結(jié)果。
2 相關(guān)描述
2.1 任務(wù)描述
Kalman于1960年提出了卡爾曼濾波,采用由狀態(tài)方程和觀測(cè)方程組成的線性隨機(jī)系統(tǒng)的狀態(tài)空間模型來描述濾波器,并利用狀態(tài)方程的遞推性,按線性無偏最小均方誤差估計(jì)準(zhǔn)則,用遞推算法對(duì)該濾波器的狀態(tài)變量作最佳估計(jì),從而求得濾掉噪聲的有用信號(hào)的最佳估計(jì)。
卡爾曼濾波器使用遞推的方式來進(jìn)行預(yù)測(cè)。濾波器先通過上一時(shí)刻系統(tǒng)的狀態(tài)預(yù)測(cè)下一時(shí)刻系統(tǒng)的狀態(tài),然后再通過觀測(cè)的到的系統(tǒng)運(yùn)行時(shí)表現(xiàn)進(jìn)行反饋修正,如此反復(fù)。
步驟1:獲取虛擬機(jī)的資源,根據(jù)資源分別計(jì)算虛擬機(jī)的性能。
步驟2:根據(jù)卡爾曼濾波預(yù)測(cè)下一時(shí)刻虛擬機(jī)的資源。
步驟3:根據(jù)步驟1與步驟2的計(jì)算結(jié)果計(jì)算虛擬機(jī)與任務(wù)的Cost值,按性能與任務(wù)從大到小進(jìn)行對(duì)應(yīng)的映射與綁定,任務(wù)數(shù)按虛擬機(jī)數(shù)進(jìn)行平均分配。
步驟4:迭代次數(shù)i是否達(dá)到最大值迭代次數(shù)n,若達(dá)到最大迭代次數(shù),則虛擬資源調(diào)度結(jié)束;否則i=i+l,并返回步驟2繼續(xù)運(yùn)行。
4 實(shí)驗(yàn)仿真與分析
為了驗(yàn)證算法,本實(shí)驗(yàn)在云仿真平臺(tái)CloudSim上進(jìn)行仿真。CloudSim是澳大利亞墨爾本大學(xué)開發(fā)的云計(jì)算仿真器,是一個(gè)通用的和可擴(kuò)展的模擬框架,支持模擬云計(jì)算基礎(chǔ)設(shè)施和管理服務(wù),具有對(duì)不同應(yīng)用和服務(wù)模型的調(diào)度和分配策略的性能進(jìn)行量化和比較等優(yōu)點(diǎn)。CloudSim是在離散事件模擬包Simjava上開發(fā)的函數(shù)庫,CloudSim繼承了GridSim的編程模型,并具有以下特點(diǎn):一個(gè)自足的支持?jǐn)?shù)據(jù)中心、服務(wù)代理人、調(diào)度和分配策略的平臺(tái).CloudSim的軟件結(jié)構(gòu)框架和體系結(jié)構(gòu)組件包括Simjava、GridSim、CloudSim、UserCode4個(gè)層次,CloudSim的CIS(CloudInformation Service)和DataCenterBroker實(shí)現(xiàn)資源發(fā)現(xiàn)和信息交互,是模擬調(diào)度的核心,提出的算法主要在DataCenterBroker中實(shí)現(xiàn)。
本實(shí)驗(yàn)的仿真環(huán)境同李園園等,采用李園園等的方法對(duì)實(shí)例進(jìn)行仿真,將得到的任務(wù)跨度和負(fù)載均衡離差進(jìn)行比較,得出的仿真曲線如圖2和圖3所示。
從圖2中可以看出,本文所研究的方法的任務(wù)跨度與李園園等的方法和魏銳等的方法相比,任務(wù)跨度比較低,平均任務(wù)跨度與李園園等的方法相比,降低了19.87%,與魏銳等的方法相比,降低了29.75%。
從圖3中可以看出,負(fù)載均衡離差的值隨著任務(wù)數(shù)的增加而增加,隨著任務(wù)數(shù)的增加負(fù)載均衡離差呈增加趨勢(shì),本文所研究的方法得到的負(fù)載均衡離差值較李園園等的方法和魏銳等的方法偏低,說明了該方法較好地實(shí)現(xiàn)了資源負(fù)載平衡。
5 總結(jié)
云計(jì)算的資源調(diào)度技術(shù)是云計(jì)算中的關(guān)鍵技術(shù),一個(gè)好的調(diào)度算法對(duì)提高整個(gè)云計(jì)算系統(tǒng)的性能起著重要作用。本文研究并設(shè)計(jì)了一種基于卡爾曼預(yù)測(cè)器的云計(jì)算資源調(diào)度算法,建立了云資源調(diào)度模型,采用卡爾曼預(yù)測(cè)器預(yù)測(cè)虛擬資源下一時(shí)刻的狀態(tài),得到可用資源向量,然后建立任務(wù)與資源的映射模型,將任務(wù)分配給合適的虛擬資源進(jìn)行調(diào)度,避免了盲目調(diào)度,使用cloudsim工具進(jìn)行仿真,實(shí)驗(yàn)結(jié)果表明,本研究方法有效地實(shí)現(xiàn)云環(huán)境下虛擬資源調(diào)度,具有較小的負(fù)載均衡離差,有效地提高了資源利用率。