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

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

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

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

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

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

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

1 研究現(xiàn)狀

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

用戶在使用云平臺(tái)時(shí)對(duì)云平臺(tái)的系統(tǒng)資源有一定的需求，這通常被成為調(diào)度需求。為了設(shè)計(jì)有效的任務(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表示硬盤(pán)需求量，GB。利用權(quán)重向量來(lái)衡量用戶對(duì)特定資源的偏好程度：

W=[W1，W2，W3，W4]

(2)

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

Rb=[Cb，Mb，Nb，Db]

(3)

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

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

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

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

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

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

(4)

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

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

3 仿真結(jié)果

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

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

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

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

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

4 結(jié)論

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