一種面向教育云資源共享的優(yōu)先級隊列任務(wù)調(diào)度算法

文孟飛，朱忍，周峰，胡超

(1.長沙幼兒師范高等?？茖W(xué)校 信息技術(shù)系，湖南 長沙,410116;2.湖南外國語職業(yè)學(xué)院 學(xué)前教育系，湖南 長沙,410015;3.長沙理工大學(xué) 電氣與信息工程學(xué)院，湖南 長沙,410114;4.中南大學(xué) 大數(shù)據(jù)研究院，湖南 長沙,410087)

隨著云計算技術(shù)的發(fā)展，將教育資源和云計算結(jié)合，可以構(gòu)成一種新型云平臺即教育云平臺。教育云平臺對于學(xué)生、教師、學(xué)校具有較重要的作用。對學(xué)生而言，可以不受時間和空間限制學(xué)習(xí)，從而提高學(xué)習(xí)效率；對教師而言，可以利用已有的資源進(jìn)行教學(xué)準(zhǔn)備、評估和反饋，從而提高教學(xué)質(zhì)量；對學(xué)校而言，可以借鑒云計算平臺建設(shè)數(shù)字化校園，消除信息孤島現(xiàn)象，促進(jìn)教育現(xiàn)代化。

云計算的任務(wù)調(diào)度是指根據(jù)一定的規(guī)則，將CPU等資源分配給特定的任務(wù)。由于云平臺內(nèi)容復(fù)雜、海量資源、用戶眾多，因此，設(shè)計良好的任務(wù)調(diào)度算法具有較重要的意義。云平臺任務(wù)調(diào)度的主要內(nèi)容是根據(jù)不同任務(wù)的特性，設(shè)計任務(wù)調(diào)度算法，實現(xiàn)任務(wù)調(diào)度目標(biāo)。

常用的任務(wù)調(diào)度算法可以分為集中式算法、分散式算法和分布式算法。集中式算法中，通常需要一個中央控制器實現(xiàn)所有資源的調(diào)度，當(dāng)云計算資源過多或規(guī)模過大時，中央控制器往往構(gòu)成了單點故障，如果其發(fā)生故障，將導(dǎo)致整個云計算調(diào)度系統(tǒng)的崩潰，因此，集中式算法往往應(yīng)用于小規(guī)模系統(tǒng)中。分散式算法中，存在多個局部控制器，每個控制器負(fù)責(zé)特定的用戶和資源需求，可以根據(jù)不同的用戶需求采用不同的局部控制器處理。因此，其可擴(kuò)展性較好，但由于其具有分散屬性，難以實現(xiàn)同步全局最優(yōu)。在分布式算法中，既存在一個中央控制器負(fù)責(zé)整體的協(xié)調(diào)，又存在局部控制器負(fù)責(zé)實際的調(diào)度，因此，其調(diào)度結(jié)果能夠在系統(tǒng)復(fù)雜度和調(diào)度性能之間實現(xiàn)較好的折中。

云計算任務(wù)調(diào)度的目標(biāo)通常為優(yōu)化某一個特定的指標(biāo)，常用的指標(biāo)包括服務(wù)質(zhì)量、成本、時延性能和負(fù)載均衡性能等。所謂服務(wù)質(zhì)量，是指用戶對任務(wù)調(diào)度算法的滿意度。成本是指云平臺在進(jìn)行任務(wù)調(diào)度時的系統(tǒng)收益減去系統(tǒng)開銷。時延是指用戶提交任務(wù)請求到用戶請求被處理所需要的總體時間。負(fù)載均衡是指云平臺的負(fù)載應(yīng)當(dāng)盡可能的均衡，從而避免某些資源承擔(dān)過多任務(wù)，而導(dǎo)致負(fù)載過大。

以上介紹明確了云平臺任務(wù)調(diào)度的必要性和調(diào)度算法、調(diào)度目標(biāo)的基本原理。下面介紹任務(wù)調(diào)度的研究現(xiàn)狀。

1 研究現(xiàn)狀

隨著信息技術(shù)的快速發(fā)展，信息技術(shù)已經(jīng)開始融入教育的多個方面[1]。教育云以其成熟的技術(shù)得到了高度重視，成為教育信息化的發(fā)展趨勢。為了改善傳統(tǒng)教學(xué)管理中教學(xué)資源難以共享和同步等問題，借助云計算技術(shù)構(gòu)造云服務(wù)平臺，解決現(xiàn)有的教育信息化資源平臺投資重復(fù)、零散分布等突出問題，具有重要的意義[2]。

作為教育云的核心部分，任務(wù)調(diào)度算法是云計算的研究熱點[3-4]。目前，主流的云計算任務(wù)調(diào)度算法[5]包括：模擬生物學(xué)中種群的產(chǎn)生和發(fā)展的遺傳算法；模擬固體加熱后的溫度冷卻的退火算法；模擬蟻群尋找目標(biāo)的蟻群算法；模擬人工免疫系統(tǒng)工作原理的人工免疫系統(tǒng)算法；模擬細(xì)菌尋找食物的細(xì)菌覓食算法；模擬魚群行為的人工魚群算法；模擬螢火蟲閃爍行為的螢火蟲算法等。

遺傳算法理論來源于生物學(xué)中種群的產(chǎn)生和發(fā)展，根據(jù) “適者生存”原則，確定每一個種群的適應(yīng)度函數(shù)，從而進(jìn)行任務(wù)調(diào)度。遺傳算法利用當(dāng)前數(shù)據(jù)和歷史數(shù)據(jù)分析未來趨勢，具有可擴(kuò)展性好、能耗低的優(yōu)點。

模擬退火算法來自固體的退火過程，即固體加熱后通過緩慢冷卻消除其內(nèi)應(yīng)力。這一方法具有高度的靈活性，通過設(shè)置溫度的冷卻速率可以保證模擬退火算法收斂到全局最優(yōu)解。

蟻群算法模擬螞蟻爬行，假如某只螞蟻發(fā)現(xiàn)目標(biāo)，它分泌信息素沿路線回到蟻群,其他螞蟻將沿著信息素前進(jìn)，尋找到目標(biāo)。從圖論的角度看，蟻群可以等效為一個加權(quán)圖，而蟻群算法可以建模為尋找其最優(yōu)路徑的問題。蟻群算法魯棒性強(qiáng)，但計算復(fù)雜度較大。

人工免疫系統(tǒng)算法是基于免疫學(xué)研究以及生物免疫系統(tǒng)模型構(gòu)成的仿生算法。通過結(jié)合一般病原體和一般病原體的保護(hù)能力，成功應(yīng)用于人工智能的基本問題分析、圖像識別等領(lǐng)域，其優(yōu)點是能夠?qū)Σ煌愋偷膯栴}進(jìn)行最優(yōu)時間求解。

細(xì)菌覓食算法是一種模仿大腸桿菌的覓食行為的自然啟發(fā)式優(yōu)化算法，該算法提供了同時優(yōu)化多目標(biāo)問題的解決方法，從而在使用較少資源的基礎(chǔ)上，在較少的工作時間內(nèi)盡可能地提高資源使用效率。

人工魚群算法是一種基于魚群行為的啟發(fā)式智能優(yōu)化算法，起源于群體搜索食物到達(dá)較高濃度區(qū)域的魚群智能群的行為。該算法非常靈活，容錯性強(qiáng)，可以用于云中的調(diào)度問題求解，并且該算法對初值不敏感，收斂快，魯棒性好，因此，可以用于目標(biāo)優(yōu)化和聚類問題求解。

螢火蟲算法是一種啟發(fā)式優(yōu)化算法，它是根據(jù)螢火蟲在夜間進(jìn)行閃爍的行為來進(jìn)行模擬優(yōu)化問題的求解。螢火蟲通過閃爍光吸引配偶和保護(hù)自己免受其他捕食者的攻擊，并記錄它們訪問過的最佳求解方案。螢火蟲算法能作為一種回溯式的優(yōu)化算法，對于求解優(yōu)化問題具有獨特的優(yōu)點。

人工蜂群算法是一種基于蜜蜂智能行為的元啟發(fā)式算法，蜂蜜在覓食過程中采用分工合作的方法，蜜蜂尋找食物來源、檢查鄰居來源、收集食物并返回蜂箱，蜂蜜覓食對應(yīng)于分配資源上的任務(wù)，并共享有關(guān)食物來源的信息。該算法最大程度地減少了使用時間。

值得注意的是，以上任務(wù)調(diào)度算法沒有考慮任務(wù)的優(yōu)先級[6]。而在教育云任務(wù)調(diào)度中，不同的任務(wù)對資源的需求是截然不同的。所以，在任務(wù)調(diào)度時，需要考慮任務(wù)的不同屬性[7]。

因此，文中提出一種考慮任務(wù)優(yōu)先級的、以優(yōu)化教育服務(wù)質(zhì)量為目標(biāo)的最優(yōu)調(diào)度算法。首先分析各種任務(wù)的服務(wù)質(zhì)量需求，進(jìn)而對任務(wù)進(jìn)行分類；然后，基于服務(wù)質(zhì)量需求的不同對任務(wù)進(jìn)行分類，設(shè)計一種基于優(yōu)先級的隊列調(diào)度核心算法，最后分析所設(shè)計調(diào)度算法的實施過程和具體步驟。

2 基于時延的任務(wù)分類

服務(wù)質(zhì)量(quality of service,QoS)是一種用戶或第三方對服務(wù)提供者的評價標(biāo)準(zhǔn)，主要側(cè)重對信道丟包率、信噪比、時延等指標(biāo)的衡量。考慮到云計算平臺任務(wù)執(zhí)行相當(dāng)一部分通過移動互聯(lián)網(wǎng)進(jìn)行，文中將時延指標(biāo)引入教育云中，優(yōu)化教育云平臺的處理時延，從而提高用戶的服務(wù)體驗。

為了進(jìn)行最優(yōu)的任務(wù)調(diào)度，需要根據(jù)不同任務(wù)對時延的需求，對各種任務(wù)進(jìn)行分類，進(jìn)而確定各種任務(wù)的優(yōu)先級。然后，根據(jù)各個任務(wù)的優(yōu)先級不同，采用相應(yīng)的調(diào)度方法，優(yōu)化系統(tǒng)的時延。

2.1 調(diào)度需求與調(diào)度資源的特征描述

用戶在使用云平臺時對云平臺的系統(tǒng)資源有一定的需求，這通常被成為調(diào)度需求。為了設(shè)計有效的任務(wù)調(diào)度算法，首先，需要定義調(diào)度需求向量，其數(shù)學(xué)表達(dá)式如下：

Ra=[Ca，Ma，Na，Da]

(1)

其中：Ca表示CPU需求量，b/s；Ma表示內(nèi)存需求量，MB；Na表示網(wǎng)絡(luò)需求量，Mb/s；Da表示硬盤需求量，GB。利用權(quán)重向量來衡量用戶對特定資源的偏好程度：

W=[W1，W2，W3，W4]

(2)

尚未調(diào)度的資源通過資源特征向量來表示：

Rb=[Cb，Mb，Nb，Db]

(3)

其中:Cb為處理器實時的可用量，b/s；Mb為內(nèi)存實時的可用量，MB；Nb為帶寬的實時可用量，Mb/s；Db為云計算平臺的硬盤存儲空間實時可用量，GB。

2.2 優(yōu)先級隊列調(diào)度的引入

文中提出的優(yōu)先級隊列調(diào)度算法的基本思路描述如下：首先，根據(jù)用戶需求和不同任務(wù)的時延為每個任務(wù)分配一個優(yōu)先級的指標(biāo)；然后，根據(jù)不同任務(wù)的優(yōu)先級指標(biāo)構(gòu)成不同的調(diào)度隊列，保證隊列間互不影響，并且根據(jù)優(yōu)先級的高低獲得優(yōu)先調(diào)度資格；最后，資源搶占時對低優(yōu)先級任務(wù)必要的進(jìn)程信息(如堆棧、寄存器、打開文件等)進(jìn)行存儲，再執(zhí)行高優(yōu)先級任務(wù)。

2.3 優(yōu)先級隊列調(diào)度算法

用于表示任務(wù)優(yōu)先級的指標(biāo)為appid和userid。教育云中的資源用appid標(biāo)記，表示該資源在系統(tǒng)中的標(biāo)識。教育云的用戶用userid標(biāo)記，表示該用戶的標(biāo)識。當(dāng)用戶將[userid,appid]發(fā)送給調(diào)度服務(wù)器時，表示某個用戶將會使用某個應(yīng)用。

資源和請求的匹配度描述的是用戶的請求與服務(wù)器提供的資源之間的匹配程度。綜合考慮多種因素后，匹配度可以表示為

(4)

值得注意的是，Tmatch的取值與調(diào)度匹配度密切相關(guān)，一般Tmatch值越大，匹配度越好。當(dāng)服務(wù)器不能夠滿足調(diào)度需求時，Tmatch<0；當(dāng)服務(wù)器剛好滿足調(diào)度需求時，Tmatch=0；當(dāng)服務(wù)器能充分地滿足調(diào)度需求，Tmatch>0。

基于優(yōu)先級隊列的任務(wù)調(diào)度算法的基本原理描述如下。首先，用戶提交任務(wù)需求給控制器，控制器根據(jù)不同任務(wù)的優(yōu)先級負(fù)責(zé)所有任務(wù)排序，返回給每個任務(wù)一個優(yōu)先級序列。然后，控制器根據(jù)每個任務(wù)的優(yōu)先級序列，優(yōu)先調(diào)用優(yōu)先級高的任務(wù)，從而完成云計算平臺的任務(wù)調(diào)度。

3 仿真結(jié)果

本節(jié)利用仿真驗證所設(shè)計的優(yōu)先級隊列任務(wù)調(diào)度算法的優(yōu)越性?？紤]某一個固定的教育云平臺，其任務(wù)個數(shù)分別為50,100,150,200和250。本節(jié)將在不同的任務(wù)個數(shù)下，將優(yōu)先級隊列調(diào)度算法與已有的遺傳算法、退火算法進(jìn)行比較，分析各個算法的處理時延，從而確定各個算法在教育云平臺實施時的優(yōu)劣。

在不考慮任務(wù)優(yōu)先級的情況下，文中提出的算法與遺傳算法、退火算法進(jìn)行比較的結(jié)果見圖1，從圖1中可以看到：在任務(wù)數(shù)量較低時，3種算法得到的總?cè)蝿?wù)處理延時差距并不是很大；當(dāng)任務(wù)數(shù)量增加時，由于遺傳算法和退火算法由于陷入搜索局部最優(yōu)解的情況，算法劣化嚴(yán)重。但文中的算法由于對各個設(shè)備單元進(jìn)行了適配，任務(wù)數(shù)量增加對算法的影響相對較小。因此，在實際教育云平臺中實施時，文中設(shè)計的算法具有較小的處理時延，從而用戶體驗度提高。

圖1 不考慮任務(wù)優(yōu)先級3種算法性能比較

在考慮任務(wù)優(yōu)先級的情況下，3種算法比較的處理時延見圖2。從圖2可見：相比不考慮任務(wù)優(yōu)先級的情況，遺傳算法和退火算法性能退化明顯，其處理時延分別達(dá)到了5 000 ms和3 000 ms；而文中提出的算法在設(shè)計之初就考慮到了任務(wù)處理的優(yōu)先級，其處理時延低于1 000 ms，對于保證用戶的服務(wù)質(zhì)量需求具有一定的意義。因此，在教育云平臺實施時，文中設(shè)計的算法具有減小處理時延的巨大優(yōu)勢。

圖2 考慮任務(wù)優(yōu)先級3種算法性能比較

4 結(jié)論

教育云平臺的任務(wù)調(diào)度對于提高教育資源的利用率、優(yōu)化教育云平臺用戶的使用體驗、促進(jìn)教育云平臺的推廣和使用、提高基礎(chǔ)教育水平具有一定的意義。本文提出一種考慮任務(wù)優(yōu)先級的的最優(yōu)調(diào)度算法，可以優(yōu)化教育資源共享云計算的處理時延。根據(jù)處理時延需求對任務(wù)進(jìn)行分類，然后引入優(yōu)先級隊列調(diào)度核心算法，合理利用資源匹配進(jìn)程，最終實現(xiàn)教育資源共享。