王翠娥
(呂梁學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)系,山西 呂梁 033000)
基于分簇能耗聚集的云計(jì)算多目標(biāo)任務(wù)調(diào)度算法
王翠娥
(呂梁學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)系,山西 呂梁 033000)
在云計(jì)算環(huán)境下的多分簇目標(biāo)的任務(wù)調(diào)度是提高軟件嵌入式系統(tǒng)穩(wěn)定性的關(guān)鍵,由于云計(jì)算中能耗擴(kuò)散,在多處理器集群多目標(biāo)任務(wù)調(diào)度中出現(xiàn)任務(wù)調(diào)度優(yōu)先級(jí)列表混亂,調(diào)度性能不好的問題.傳統(tǒng)方法采用節(jié)點(diǎn)行為信息流特征分析方法進(jìn)行任務(wù)調(diào)度,隨著分簇能耗擴(kuò)散,收斂性不好.提出一種基于分簇能耗聚集的云計(jì)算多目標(biāo)任務(wù)調(diào)度算法.待分析任務(wù)調(diào)度信息流的分層能耗聚集軌跡峰值往往含有重要的信息,提取待分析任務(wù)調(diào)度信息的能耗特征,構(gòu)建云計(jì)算多目標(biāo)任務(wù)調(diào)度模型,實(shí)現(xiàn)對(duì)云計(jì)算多目標(biāo)任務(wù)調(diào)度算法的改進(jìn).仿真結(jié)果表明:采用該算法能有效提高云計(jì)算多目標(biāo)任務(wù)調(diào)度效率,任務(wù)執(zhí)行時(shí)間較短,系統(tǒng)穩(wěn)定性高.
云計(jì)算;任務(wù)調(diào)度;軟件;嵌入式
隨著計(jì)算機(jī)技術(shù)的快速發(fā)展,各種嵌入式設(shè)備和應(yīng)用系統(tǒng)對(duì)計(jì)算機(jī)的運(yùn)算速度和水平也提出了更高的要求,例如在ARM和Linux等嵌入式操作系統(tǒng)設(shè)計(jì)和應(yīng)用中,又例如各種先進(jìn)的三維圖形處理、大數(shù)據(jù)處理、實(shí)時(shí)任務(wù)調(diào)度等,均要求計(jì)算機(jī)系統(tǒng)具有非常強(qiáng)大的運(yùn)算能力.云計(jì)算作為一種主要的大數(shù)據(jù)計(jì)算方式,逐漸應(yīng)用到智能數(shù)據(jù)信息處理、資源調(diào)度和數(shù)據(jù)挖掘等領(lǐng)域,同時(shí),云計(jì)算與嵌入式設(shè)備結(jié)合,在模式識(shí)別和計(jì)算機(jī)智能控制等領(lǐng)域有著較大的應(yīng)用前景.在嵌入式云計(jì)算環(huán)境中,需要進(jìn)行多分簇目標(biāo)的任務(wù)調(diào)度,以提高軟件嵌入式系統(tǒng)穩(wěn)定性.研究云計(jì)算環(huán)境下的多目標(biāo)任務(wù)調(diào)度算法,對(duì)提高系統(tǒng)運(yùn)行的穩(wěn)定性和可靠性,提高軟件執(zhí)行任務(wù)的時(shí)效性等方法具有極其重要的意義,因此,研究嵌入式云計(jì)算多目標(biāo)任務(wù)調(diào)度算法成為當(dāng)前計(jì)算機(jī)信息領(lǐng)域研究的熱點(diǎn)課題[1].
由于云計(jì)算中能耗擴(kuò)散,在多處理器集群多目標(biāo)任務(wù)調(diào)度中可能出現(xiàn)任務(wù)調(diào)度優(yōu)先級(jí)列表混亂、調(diào)度性能不好的問題.傳統(tǒng)方法中,對(duì)嵌入式云計(jì)算多目標(biāo)任務(wù)調(diào)度采用的是PSO粒子群調(diào)度算法、神經(jīng)網(wǎng)絡(luò)算法、遺傳自適應(yīng)調(diào)度算法和決策樹算法等[2-6],這些算法在實(shí)現(xiàn)云計(jì)算多目標(biāo)任務(wù)調(diào)度過程中,取得了一定的效果,特別是對(duì)多用戶、多任務(wù)的多線程的目標(biāo)任務(wù)調(diào)度效果較好.其中文獻(xiàn)[7]通過加權(quán)模糊算法實(shí)現(xiàn)對(duì)與計(jì)算多處理器集群的目標(biāo)任務(wù)調(diào)度,通過聚類中心搜索,進(jìn)行模式特征搜索和識(shí)別,改進(jìn)優(yōu)先級(jí)列表,提高調(diào)度性能,但該算法計(jì)算開銷較大.文獻(xiàn)[8]提出基于多目標(biāo)節(jié)點(diǎn)行為融合處理的云計(jì)算任務(wù)調(diào)度算法,通過Linux嵌入式任務(wù)調(diào)度的優(yōu)化設(shè)計(jì),采用聚類中心節(jié)點(diǎn),實(shí)現(xiàn)多目標(biāo)任務(wù)調(diào)度優(yōu)化,但是該算法對(duì)任務(wù)區(qū)間失衡的控制性能不好.可見,傳統(tǒng)方法采用節(jié)點(diǎn)行為信息流特征分析方法進(jìn)行任務(wù)調(diào)度,隨著分簇能耗擴(kuò)散,收斂性不好[9].針對(duì)傳統(tǒng)方法出現(xiàn)的問題和弊端,筆者提出一種基于分簇能耗聚集的云計(jì)算多目標(biāo)任務(wù)調(diào)度算法.首先構(gòu)建云計(jì)算多目標(biāo)任務(wù)調(diào)度模型,提取任務(wù)信息流模型特征,并進(jìn)行分簇能耗聚集算法設(shè)計(jì),最后實(shí)現(xiàn)對(duì)云計(jì)算多目標(biāo)任務(wù)調(diào)度算法改進(jìn),通過仿真實(shí)驗(yàn)進(jìn)行了性能驗(yàn)證,展示了本文算法在實(shí)現(xiàn)云計(jì)算多目標(biāo)任務(wù)調(diào)度中的優(yōu)越性能.
1.1 問題的描述
嵌入式操作系統(tǒng)作為一種新型的網(wǎng)絡(luò)操作系統(tǒng),成為云計(jì)算的主要載體,在發(fā)展過程中產(chǎn)生多目標(biāo)復(fù)合型任務(wù)調(diào)度等問題,有以下幾個(gè)重要的問題需要首先解決:
1)云計(jì)算環(huán)境下,嵌入式設(shè)備的異構(gòu)特征兼容.隨著計(jì)算機(jī)硬件技術(shù)快速發(fā)展,多處理器集群的發(fā)展速度也是非常迅速的,在不同的時(shí)期,不同的多處理器版本層出不窮,由于不同時(shí)期多處理器版本的計(jì)算能力差異很大,而一個(gè)實(shí)際的應(yīng)用系統(tǒng)中,多是由多個(gè)不同版本的多處理器不斷升級(jí)而來的.所以,如何在這些不同版本的多處理器上實(shí)現(xiàn)統(tǒng)一的任務(wù)調(diào)度和分配是其發(fā)展中需要最先解決的兼容性問題.
2)云計(jì)算環(huán)境下,嵌入式設(shè)備的可伸縮能力.在許多實(shí)際的多處理器應(yīng)用系統(tǒng)中,通常需要對(duì)多處理器系統(tǒng)進(jìn)行不斷的擴(kuò)展,在動(dòng)態(tài)擴(kuò)展時(shí),有時(shí)候需要減少系統(tǒng)構(gòu)成,降低成本和組成,有時(shí)候需要加大系統(tǒng)組成,不斷升級(jí),所以需要多處理器集群具有強(qiáng)大的可伸縮能力.
3)云計(jì)算多目標(biāo)任務(wù)調(diào)度中,嵌入式設(shè)備集群的容錯(cuò)能力.在不同版本、不同平臺(tái)上,多處理器運(yùn)行時(shí),不同平臺(tái)之間融合運(yùn)算時(shí),可能會(huì)出現(xiàn)錯(cuò)誤.這時(shí),要求多處理器集群系統(tǒng)具有強(qiáng)大的容錯(cuò)能力來對(duì)不同平臺(tái)下的錯(cuò)誤進(jìn)行融合處理,保證多處理器系統(tǒng)高效完備的執(zhí)行.
4)云計(jì)算多目標(biāo)任務(wù)調(diào)度中任務(wù)調(diào)度優(yōu)先級(jí)策略.在用戶的使用過程中,可能會(huì)實(shí)時(shí)中斷運(yùn)算系統(tǒng),加入新的用戶任務(wù),那么在舊任務(wù)執(zhí)行的過程中,就必須設(shè)定任務(wù)回調(diào)的監(jiān)測(cè)方法,實(shí)時(shí)對(duì)任務(wù)的執(zhí)行情況進(jìn)行監(jiān)測(cè),在用戶有更高優(yōu)先級(jí)的任務(wù)需要執(zhí)行時(shí),系統(tǒng)讓出當(dāng)前資源,給優(yōu)先級(jí)更高的用戶應(yīng)用程序執(zhí)行.
傳統(tǒng)的云計(jì)算任務(wù)調(diào)度運(yùn)算模式在日常的文件處理、數(shù)據(jù)運(yùn)算等方面均能很好的適應(yīng),但是對(duì)于數(shù)據(jù)量非常龐大的圖形運(yùn)算、實(shí)時(shí)多維運(yùn)算等的應(yīng)用性能較弱,需要進(jìn)行多目標(biāo)任務(wù)調(diào)度.
1.2 云計(jì)算多目標(biāo)任務(wù)調(diào)度模型構(gòu)建
筆者構(gòu)建的云計(jì)算多目標(biāo)任務(wù)調(diào)度模型,其結(jié)構(gòu)設(shè)計(jì)如圖1所示.
在圖1中,采用分區(qū)特征融合的策略,以節(jié)點(diǎn)行為信息流特征分析進(jìn)行任務(wù)調(diào)度,當(dāng)執(zhí)行云計(jì)算任務(wù)時(shí),管理節(jié)點(diǎn)將1個(gè)作業(yè)任務(wù)(Task)劃分若干個(gè)特征區(qū)間,設(shè)置其時(shí)間片為當(dāng)前的調(diào)度執(zhí)行規(guī)模BTavg.假設(shè)任務(wù)調(diào)度時(shí)間片內(nèi)目標(biāo)數(shù)據(jù)pi執(zhí)行任務(wù)nj,節(jié)點(diǎn)m發(fā)送數(shù)據(jù)進(jìn)行任務(wù)調(diào)度,節(jié)點(diǎn)交換數(shù)據(jù)序列為:
圖1 云計(jì)算多目標(biāo)任務(wù)調(diào)度節(jié)點(diǎn)模型
在異構(gòu)的云計(jì)算多目標(biāo)任務(wù)調(diào)度模型中,靜態(tài)任務(wù)調(diào)度通常采用帶權(quán)有向無環(huán)圖(DAG)表示任務(wù)模型. DAG圖中結(jié)點(diǎn)表示任務(wù),為了實(shí)現(xiàn)模糊云計(jì)算,需要產(chǎn)生隨機(jī)矩陣z,為c×D維的云數(shù)據(jù),其每個(gè)分量都在(0,1)之間.根據(jù)Lorenz映射形式,得到NP個(gè)隨機(jī)數(shù)序列分量:
W是一個(gè)n×m的矩陣,n表示DAG圖中的任務(wù)數(shù),使編碼端接收到的數(shù)據(jù)出現(xiàn)層間模式重疊,接收端需要將接收到的視頻數(shù)據(jù)進(jìn)行分片重組,通過模糊云計(jì)算,通過結(jié)點(diǎn)的CP(vi)值判斷其是否為關(guān)鍵任務(wù).如果CP(vi)=CP(ventry),則vi為關(guān)鍵任務(wù),相互獨(dú)立并行任務(wù)集合CP(vi)定義如下:
云計(jì)算任務(wù)調(diào)度處理機(jī)pi執(zhí)行任務(wù)nj所能嵌入式系統(tǒng)執(zhí)行效率DR(pi,nj)定義為:
每當(dāng)進(jìn)程k就緒時(shí),類型為rk的任務(wù)在時(shí)間段T進(jìn)行云計(jì)算多目標(biāo)任務(wù)調(diào)度的時(shí)間為:
設(shè)計(jì)模糊云計(jì)算核函數(shù),使得核函數(shù)滿足時(shí)數(shù)據(jù)定位識(shí)別的約束條件和要求,由此實(shí)現(xiàn)了云計(jì)算多目標(biāo)任務(wù)調(diào)度模型構(gòu)建,為多目標(biāo)任務(wù)調(diào)度算法設(shè)計(jì)提供模型基礎(chǔ).
2.1 信息流特征提取及分簇能耗聚集設(shè)計(jì)
在上述云計(jì)算多目標(biāo)任務(wù)調(diào)度節(jié)點(diǎn)模型計(jì)的基礎(chǔ)上,進(jìn)行信息流特征提取,為云計(jì)算多目標(biāo)任務(wù)調(diào)度提供數(shù)據(jù)基礎(chǔ).傳統(tǒng)方法采用節(jié)點(diǎn)行為信息流特征分析方法進(jìn)行任務(wù)調(diào)度,隨著分簇能耗的擴(kuò)散,收斂性不是很好,對(duì)此本文提出一種基于分簇能耗聚集的云計(jì)算多目標(biāo)任務(wù)調(diào)度算法.
首先對(duì)云計(jì)算任務(wù)調(diào)度節(jié)點(diǎn)DAG圖中的任務(wù)進(jìn)行任務(wù)歸并,然后將DAG圖分層,從整個(gè)任務(wù)圖的全局出發(fā)考慮任務(wù)的優(yōu)先級(jí),構(gòu)建分簇能耗聚集模型,在多處理器集群任務(wù)調(diào)度.根據(jù)計(jì)算機(jī)上的每個(gè)處理器的特性,進(jìn)行相應(yīng)的數(shù)據(jù)格式轉(zhuǎn)換,使得系統(tǒng)數(shù)據(jù)兼容,并且具備一定的差錯(cuò)數(shù)據(jù)冗余處理能力.首先進(jìn)行多目標(biāo)任務(wù)信息的特征提取,由數(shù)據(jù)分析函數(shù)定義,對(duì)于尺度為a的多個(gè)任務(wù)流集合,以t/a代替t,則相應(yīng)的分析函數(shù)定義為:
其中,下標(biāo)ia表示尺度a數(shù)據(jù)分析函數(shù)的任務(wù)流的優(yōu)先級(jí)屬性.可知任務(wù)流的優(yōu)先級(jí)屬性的分簇能耗聚集約束關(guān)系為:
當(dāng)下面的條件成立:
分簇能耗聚集調(diào)度狀態(tài)方程:
在云計(jì)算嵌入式設(shè)備中,通過進(jìn)程管理子系統(tǒng),完成進(jìn)程的創(chuàng)建、中止、進(jìn)程間的通信及任務(wù)調(diào)度,云存儲(chǔ)資源時(shí),添加控制速度的約束因子a,待分析任務(wù)調(diào)度信息流的分層能耗聚集軌跡峰值往往含有重要的信息,提取待分析任務(wù)調(diào)度信息,進(jìn)行任務(wù)調(diào)度.
2.2 目標(biāo)任務(wù)調(diào)度算法改進(jìn)實(shí)現(xiàn)
根據(jù)計(jì)算機(jī)上的每個(gè)處理器的特性,進(jìn)行相應(yīng)的數(shù)據(jù)格式轉(zhuǎn)換,添加動(dòng)量慣性系數(shù)ω,用來提高調(diào)度性能的可靠性,由于 r1,r2服從均勻分布,得到多分簇云計(jì)算的特定數(shù)據(jù)層間預(yù)測(cè)結(jié)果為:
采用分簇能耗聚集算法,在特定數(shù)據(jù)在云計(jì)算中的傳輸距離小于閾值d0時(shí),通過亮度均值差的自由空間信道傳輸模型構(gòu)建,得到目標(biāo)任務(wù)調(diào)度感知能耗系數(shù)是εfs;目標(biāo)任務(wù)調(diào)度的聚集能耗用一個(gè)四元組G表示,G=(V,E,W,C),在目標(biāo)任務(wù)調(diào)度中,任務(wù)間的通信開銷集合,C(vi,vj)表示任務(wù)vi與vj間的通信開銷,EST2(vi,pq)是復(fù)制任務(wù)vi關(guān)鍵父結(jié)點(diǎn) 時(shí)任務(wù)vcp,i的最早開始時(shí)間,EST1和EST2的計(jì)算方法如下:
其中,child(vi)={vj|ei,j∈E}表示任務(wù)vi的子結(jié)點(diǎn)集合.計(jì)算模糊云模型中的已經(jīng)調(diào)度到處理器內(nèi)核pq上的任務(wù)全部執(zhí)行完成的時(shí)間,定義量度F(β,X)來評(píng)價(jià)由β=[β1,β2]所定位的目標(biāo)資源的y=βX的空間特征向量,得到目標(biāo)任務(wù)調(diào)度的能耗衰減量度F(β,X)優(yōu)化結(jié)果為:
由此實(shí)現(xiàn)了基于分簇能耗聚集的云計(jì)算多目標(biāo)任務(wù)調(diào)度,在降低系統(tǒng)能耗的同時(shí),提高任務(wù)調(diào)度的效率.
為了驗(yàn)證本文算法在實(shí)現(xiàn)云計(jì)算多目標(biāo)任務(wù)調(diào)度中的優(yōu)越性能,進(jìn)行了仿真實(shí)驗(yàn),仿真實(shí)驗(yàn)建立在Matlab數(shù)學(xué)編程之上,實(shí)驗(yàn)采用的計(jì)算機(jī)型號(hào)Dell 2210b,處理器為Intel Core2 Duo1.80 GHz,1 G內(nèi)存,主頻為DDR2 667.在云計(jì)算任務(wù)調(diào)度中,采用多目標(biāo)任務(wù)組合方式,對(duì)調(diào)度任務(wù)進(jìn)行隨機(jī)重組,模擬100個(gè)系統(tǒng)請(qǐng)求任務(wù),把待調(diào)度的目標(biāo)任務(wù)數(shù)據(jù)集分為3類,每個(gè)類別分別包括59,71和48個(gè)樣本,每個(gè)目標(biāo)任務(wù)的數(shù)據(jù)樣本中有13個(gè)特征屬性.根據(jù)上述仿真環(huán)境設(shè)計(jì),進(jìn)行仿真實(shí)驗(yàn),首先構(gòu)建云計(jì)算下的多目標(biāo)任務(wù)調(diào)度特征信息數(shù)據(jù)模型,得到3個(gè)通道中的目標(biāo)任務(wù)調(diào)度特征信息采集結(jié)果如圖2所示.
圖2 3個(gè)通道中的目標(biāo)任務(wù)調(diào)度特征信息采集結(jié)果
圖3 目標(biāo)任務(wù)調(diào)度分簇能耗聚集結(jié)果
以上述特征信息采集數(shù)據(jù)為研究對(duì)象,進(jìn)行分簇能耗聚集實(shí)驗(yàn),得到能耗聚集結(jié)果如圖3所示.
從圖3可見,通過分簇能耗聚集,實(shí)現(xiàn)了對(duì)調(diào)度任務(wù)數(shù)據(jù)的融合,為提高任務(wù)調(diào)度的均衡性和效率奠定了基礎(chǔ),最后進(jìn)行任務(wù)調(diào)度仿真實(shí)驗(yàn),為了對(duì)比性能,采用本文算法和傳統(tǒng)算法,對(duì)相同規(guī)模的任務(wù)調(diào)度量進(jìn)行多目標(biāo)任務(wù)調(diào)度,以執(zhí)行時(shí)間為參考,得到不同算法的調(diào)度運(yùn)行時(shí)間仿真對(duì)比結(jié)果如圖4所示.從圖4可見,采用本文算法,節(jié)省了目標(biāo)任務(wù)調(diào)度時(shí)間,提高了效率,提高軟件嵌入式系統(tǒng)穩(wěn)定性.
在嵌入式云計(jì)算環(huán)境中,需要進(jìn)行多分簇目標(biāo)的任務(wù)調(diào)度,以提高軟件嵌入式系統(tǒng)穩(wěn)定性.研究云計(jì)算環(huán)境下的多目標(biāo)任務(wù)調(diào)度算法,對(duì)提高系統(tǒng)運(yùn)行的穩(wěn)定性和可靠性,提高軟件執(zhí)行任務(wù)的時(shí)效性等方法具有重要的意義,筆者提出一種基于分簇能耗聚集的云計(jì)算多目標(biāo)任務(wù)調(diào)度算法.首先構(gòu)建云計(jì)算多目標(biāo)任務(wù)調(diào)度模型,提取任務(wù)信息特征碼,并進(jìn)行分簇能耗聚集算法設(shè)計(jì),最后實(shí)現(xiàn)對(duì)云計(jì)算多目標(biāo)任務(wù)調(diào)度算法改進(jìn),實(shí)驗(yàn)結(jié)果表明,采用本文算法能節(jié)省了目標(biāo)任務(wù)調(diào)度時(shí)間,提高了效率,具有優(yōu)越性.
圖4 執(zhí)行效率對(duì)比
[1]王娟,李飛,張路橋.限制解空間的PSO云存儲(chǔ)任務(wù)調(diào)度算法[J].計(jì)算機(jī)應(yīng)用研究,2013,30(1):127-129+154.
[2]張松慧,熊錦江.一種針對(duì)非平穩(wěn)網(wǎng)絡(luò)任務(wù)調(diào)度防沖突算法研究[J].科技通報(bào),2013,29(10):143-145.
[3]許丞,劉洪,譚良.Hadoop云平臺(tái)的一種新的任務(wù)調(diào)度和監(jiān)控機(jī)制[J].計(jì)算機(jī)科學(xué),2013,40(1):112-117.
[4]李靜梅,王雪,吳艷霞.一種改進(jìn)的優(yōu)先級(jí)列表任務(wù)調(diào)度算法[J].計(jì)算機(jī)科學(xué),2014,41(5):20-23.
[5]CHONG S K,GABER M M,KRISHNASWAMY S,et al.Energy Conservation in Wireless Sensor Networks:a Rule-based Approach[J].Knowledge and Information Systems,2011,28(3):579-614.
[6]劉少偉,孔令梅,任開軍,等.云環(huán)境下優(yōu)化科學(xué)工作流執(zhí)行性能的兩階段數(shù)據(jù)放置與任務(wù)調(diào)度策略[J].計(jì)算機(jī)學(xué)報(bào),2011,34(11):2 021-2 130.
[7]孟憲福,解文利.基于免疫算法多目標(biāo)約束P2P任務(wù)調(diào)度策略研究[J].電子學(xué)報(bào),2011,39(1):101-107.
[8]李文娟,張啟飛,平玲娣,等.基于模糊聚類的云任務(wù)調(diào)度算法[J].通信學(xué)報(bào),2012,33(3):146-154.
[9]周浩,高遠(yuǎn),朱昌平.基于雙門限能量檢測(cè)的選擇式協(xié)作頻譜感知[J].計(jì)算機(jī)仿真,2014,31(1):199-203.
(責(zé)任編輯 李健飛)
Cloud Computing Multi-objective Task Scheduling Algorithm Based on Energy Consumption Cluster Aggregation
WANG Cui-e
(Department of Computer Science&Technology,Lvliang University,Lvliang,Shanxi 033000,China)
Computing task scheduling multicluster target environment in the cloud is the key to improve the stability of the software of the embedded system.Owing to the energy diffusion in cloud computing,task scheduling priority list appears chaos in the multi processor cluster multi-objective task scheduling,and scheduling performance is not good.The traditional method uses the node behavior information flow characteristic to analyze task scheduling,with the cluster energy diffusion,convergence is not good.This paper presents a method for calculating the multi-objective task scheduling algorithm based on energy consumption of the cloud cluster aggregation.The simulation results show that,the algorithm can effectively improve the efficiency of cloud computing multi-objective task scheduling,task execution time is short,and it has high stability of the system.
cloud computing;task scheduling;software;embedded type
TP302.7
A
1673-1972(2015)03-0049-06
2015-03-28
王翠娥(1981-),女,山西呂梁人,講師,主要從事軟件技術(shù)研究.
book=54,ebook=55