基于決策樹(shù)分類的云作業(yè)調(diào)度算法研究與實(shí)現(xiàn)

強(qiáng) 彥，盧軍佐，裴 博

（太原理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，太原030024）

云計(jì)算以其高效的服務(wù)而著稱，是計(jì)算機(jī)界目前研究的熱點(diǎn)［1］。云計(jì)算中的虛擬技術(shù)、作業(yè)調(diào)度技術(shù)和存儲(chǔ)技術(shù)是幾個(gè)重要的研究?jī)?nèi)容。特別是云的作業(yè)調(diào)度技術(shù)，因?yàn)殡S著云環(huán)境下用戶數(shù)量的增加、服務(wù)類別的復(fù)雜和作業(yè)規(guī)模的不斷龐大，如何通過(guò)改進(jìn)作業(yè)的調(diào)度來(lái)保證云服務(wù)的質(zhì)量和性能不受影響已成為大家的關(guān)注點(diǎn)［2］。例如，當(dāng)不同種類、大小的作業(yè)同時(shí)進(jìn)入服務(wù)平臺(tái)，可能會(huì)造成作業(yè)調(diào)度算法的調(diào)度效率低下，造成計(jì)算資源的浪費(fèi)，導(dǎo)致用戶滿意度降低。筆者通過(guò)對(duì)傳統(tǒng)云調(diào)度算法的研究，提出將決策樹(shù)分類算法引入云調(diào)度算法中，實(shí)現(xiàn)對(duì)傳統(tǒng)調(diào)度算法的改進(jìn)，改進(jìn)后的調(diào)度算法對(duì)作業(yè)進(jìn)行分類，達(dá)到同類作業(yè)進(jìn)入同一個(gè)隊(duì)列接受調(diào)度，有效提高了作業(yè)執(zhí)行效率。

1 決策樹(shù)分類算法

分類是數(shù)據(jù)挖掘的一種重要手段，能夠?yàn)橐欢ǖ墓こ虘?yīng)用提供決策支持，特別是決策樹(shù)分類算法是應(yīng)用最廣泛的邏輯方法之一［3］。它能夠通過(guò)訓(xùn)練數(shù)據(jù)集的學(xué)習(xí)來(lái)產(chǎn)生相應(yīng)的決策規(guī)則樹(shù)，并且通過(guò)信息增益計(jì)算，得到每個(gè)屬性的重要程度，加快分類速度。目前已成功地應(yīng)用于Web智能、金融分析、天文學(xué)和分子生物學(xué)等領(lǐng)域。常用的決策樹(shù)算法有ID3、C4.5等［4］。其中 C4.5在ID3基礎(chǔ)上做出了一些改進(jìn)，因此本文采用C4.5算法來(lái)進(jìn)行云作業(yè)分類［5］。

C4.5算法描述如下。

輸入：訓(xùn)練樣本samples、候選屬性集合attribute list、當(dāng)前樣本T；

輸出：一棵決策樹(shù)；

Step1：創(chuàng)建根節(jié)點(diǎn)N；

Step2：如果T都屬于同一類C，則返回N為葉節(jié)點(diǎn)，標(biāo)記為類C；

Step3：如果attribute list為空或T中所剩的樣本數(shù)少于某給定值，則返回N為葉節(jié)點(diǎn)，并標(biāo)記N為T中出現(xiàn)最多的類；

Step4：對(duì)于每一個(gè)作業(yè)屬性，計(jì)算信息增益率；

Step5：N 的測(cè)試屬性test.attribute＝attribute list具有最高信息增益率的屬性；

Step6：如果測(cè)試屬性為連續(xù)型則找到該屬性的分割閾值；

Step7：對(duì)于每一個(gè)新的葉子節(jié)點(diǎn)，如果該葉子節(jié)點(diǎn)對(duì)應(yīng)的樣本子集T′為空，則分裂此葉子節(jié)點(diǎn)生成新葉子節(jié)點(diǎn)，并將其標(biāo)記為T中出現(xiàn)最多的類；否則在該葉子節(jié)點(diǎn)上執(zhí)行C4.5form tree（T′，T′.attribute list），繼續(xù)對(duì)它分裂；

Step8：計(jì)算每個(gè)節(jié)點(diǎn)的分類錯(cuò)誤，進(jìn)行樹(shù)剪枝。

2 決策樹(shù)分類作業(yè)調(diào)度

2.1 網(wǎng)絡(luò)訓(xùn)練

選取常見(jiàn)的幾種不同類型的云作業(yè)，分別為WordCount：計(jì)算文本里每個(gè)詞出現(xiàn)的頻率；URLGet：模仿網(wǎng)頁(yè)爬蟲的抓取網(wǎng)頁(yè)行為；CPUActivity：對(duì)輸入的每個(gè)key-value對(duì)進(jìn)行一次計(jì)算量巨大的數(shù)值計(jì)算，如大整數(shù)乘法。每種類型的作業(yè)的大小不同，因此所占用資源也不同［6］。得到的模擬訓(xùn)練集如表1所示。其中class代表分類的狀態(tài)，標(biāo)號(hào)為作業(yè)的首字母。

表1 訓(xùn)練樣本集

選擇好訓(xùn)練集后，用算法對(duì)作業(yè)進(jìn)行訓(xùn)練，得到訓(xùn)練模型，方便以后利用決策樹(shù)對(duì)作業(yè)進(jìn)行分類。得到的決策樹(shù)如圖1所示。

圖1 決策樹(shù)

從圖1中可以看出由C4.5生成決策樹(shù)，進(jìn)行的信息增益得到了每個(gè)屬性的重要程度，信息增益中選擇最重要的屬性作為分裂屬性，其中比較重要的是CPU和Memory，由于其他兩個(gè)屬性對(duì)分類的貢獻(xiàn)較小，因此在決策樹(shù)中沒(méi)有體現(xiàn)。如圖1中所示，決策樹(shù)中存在如下兩條規(guī)則［7］。

規(guī)則1：如果CPU所占資源大于40，那么這些作業(yè)劃分為一類，否則劃分為另外一類；

規(guī)則2：對(duì)于上面劃分好的類，按照Memory劃分，如果所占內(nèi)存大于50則劃分為一類，如果所占內(nèi)存小于等于50則劃分為一類。

2.2 決策樹(shù)分類作業(yè)調(diào)度

決策樹(shù)分類作業(yè)調(diào)度算法的中心思想是：利用決策樹(shù)算法對(duì)訓(xùn)練集進(jìn)行訓(xùn)練，得到分類模型，利用分類模型對(duì)作業(yè)進(jìn)行分類，使得相同的作業(yè)進(jìn)入相同隊(duì)列，最后對(duì)作業(yè)進(jìn)行調(diào)度［8］。不僅可以預(yù)測(cè)每個(gè)作業(yè)執(zhí)行時(shí)間而且可以使相關(guān)作業(yè)得到有序執(zhí)行。算法描述如下。

輸入：作業(yè)訓(xùn)練集、測(cè)試集；

輸出：作業(yè)分類、調(diào)度結(jié)果；

Step1：利用上述決策樹(shù)C4.5算法進(jìn)行信息增益，創(chuàng)建決策樹(shù)，訓(xùn)練樣本，建立分類模型；信息增益的方法為

其中D為每個(gè)屬性的值，j＝1，…，n；

Step2：利用Step1創(chuàng)建的分類模型對(duì)作業(yè)集進(jìn)行分類；

Step3：預(yù)測(cè)相應(yīng)的作業(yè)的類型、執(zhí)行時(shí)間，然后按照時(shí)間的先后順序和執(zhí)行時(shí)間的長(zhǎng)短，對(duì)作業(yè)進(jìn)行分類執(zhí)行；

Step4：輸出作業(yè)的實(shí)際執(zhí)行時(shí)間。

作業(yè)調(diào)度模型如圖2所示。

圖2 作業(yè)調(diào)度模型

3 實(shí)驗(yàn)與分析

本文采用8個(gè)節(jié)點(diǎn)的集群來(lái)評(píng)估該算法，其中一個(gè)為主控節(jié)點(diǎn)，其他為輔助節(jié)點(diǎn)［9］。每個(gè)節(jié)點(diǎn)的配置為Inter雙核，2.4Hz，250G硬盤和2G內(nèi)存，這些節(jié)點(diǎn)通過(guò)千兆交換機(jī)相連。每個(gè)節(jié)點(diǎn)裝有Linux系統(tǒng)和Hadoop平臺(tái)。實(shí)驗(yàn)中Hadoop中參數(shù)設(shè)置如表2所示。

表2 Hadoop參數(shù)設(shè)置

實(shí)驗(yàn)采取的作業(yè)如3.1節(jié)所示，模擬不同類型的作業(yè)，利用上述決策樹(shù)調(diào)度算法對(duì)作業(yè)進(jìn)行調(diào)度，分別統(tǒng)計(jì)每個(gè)作業(yè)的類劃分情況、作業(yè)執(zhí)行時(shí)間、作業(yè)等待時(shí)間，分析算法效率。

3.1 算法的可行性

模擬20個(gè)3種類型的作業(yè)進(jìn)入Hadoop環(huán)境［10］后，會(huì)按照決策樹(shù)調(diào)度算法將作業(yè)分為3個(gè)不同的類，來(lái)證明算法的可行性。為體現(xiàn)這8個(gè)作業(yè)的分類狀況，本文采用FastMap技術(shù)［11］將作業(yè)的屬性映射到2維上。其結(jié)果如圖3所示。

圖3 作業(yè)分類結(jié)果

從圖3可以看出20個(gè)作業(yè)進(jìn)入環(huán)境后被分為了3類，在圖中分別用不同標(biāo)識(shí)標(biāo)注，經(jīng)驗(yàn)證分類的結(jié)果和模擬的作業(yè)類型完全一致，從而驗(yàn)證了算法的可行性。

3.2 算法的效率驗(yàn)證

模擬8個(gè)不同種類的作業(yè)，進(jìn)入Hadoop環(huán)境，分別配置Hadoop中默認(rèn)的調(diào)度算法和基于決策樹(shù)分類的作業(yè)調(diào)度算法，用2中算法分別對(duì)8個(gè)作業(yè)進(jìn)行處理，得到這兩種算法的作業(yè)運(yùn)行時(shí)間和作業(yè)等待時(shí)間，并比較兩種算法的結(jié)果，驗(yàn)證算法的效率。

圖4為兩種算法的作業(yè)調(diào)度結(jié)果，其中圖4－a為Hadoop默認(rèn)的調(diào)度算法的執(zhí)行結(jié)果，圖4-b為決策樹(shù)分類作業(yè)調(diào)度算法的結(jié)果。圖中橫坐標(biāo)為作業(yè)的執(zhí)行時(shí)間，縱坐標(biāo)為作業(yè)的執(zhí)行順序?？梢钥闯鰞煞N算法的執(zhí)行順序是不一樣的，由于Hadoop中默認(rèn)的調(diào)度算法為FIFO，因此作業(yè)調(diào)度順序?yàn)橄冗M(jìn)先出［12］。而基于決策樹(shù)調(diào)度算法是根據(jù)作業(yè)的配置訓(xùn)練分類得到作業(yè)的估計(jì)運(yùn)行時(shí)間才進(jìn)行的調(diào)度，利于作業(yè)的合理調(diào)度，得到作業(yè)的執(zhí)行順序?yàn)?、2、7、5、3、8、4、6。比較兩者作業(yè)的總運(yùn)行時(shí)間，F(xiàn)IFO算法的總執(zhí)行時(shí)間為35.6s，而基于決策樹(shù)調(diào)度算法的執(zhí)行時(shí)間為22.7s，縮短了作業(yè)的總執(zhí)行時(shí)間，同時(shí)使得短作業(yè)不至于等待時(shí)間過(guò)長(zhǎng)導(dǎo)致用戶滿意度降低，證明了該算法具有較高的效率。

圖4 兩種調(diào)度算法的結(jié)果

4 結(jié)束語(yǔ)

作業(yè)調(diào)度的效率對(duì)Hadoop性能提高至關(guān)重要。因此本文提出一種云計(jì)算環(huán)境下的基于決策樹(shù)分類算法的作業(yè)調(diào)度算法，用決策數(shù)據(jù)對(duì)作業(yè)的配置進(jìn)行訓(xùn)練。該算法可以預(yù)測(cè)進(jìn)入環(huán)境的作業(yè)的運(yùn)行時(shí)間，從而來(lái)調(diào)度作業(yè)。通過(guò)實(shí)驗(yàn)驗(yàn)證該算法是可行的，并且與Hadoop環(huán)境中默認(rèn)的FIFO算法的調(diào)度結(jié)果進(jìn)行比較后，驗(yàn)證了該算法的效率。

［1］ Lin C，Tian Y，Yao M.Green network and green evaluation：Mechanism，modeling and evaluation［J］.Chinese Journal of Computers，2011，34（4）：593-612..

［2］ 李亞瓊，宋瑩，黃永兵.一種面向虛擬化云計(jì)算平臺(tái)的內(nèi)存優(yōu)化技術(shù)［J］.計(jì)算機(jī)學(xué)報(bào)，2011，34（4）：684-693.

［3］ Application of Multi-level Compressed Decision Tree in Computer Forensics［C］∥Proceedings 2010IEEE 2nd Symposium on Web Society，2010.

［4］ Zalewska A M.Relationships between anxiety and job satisfaction—Three approaches：‘Butoom-up’，‘Buttom-down’and‘transactional’［J］.Personality and Individual Differences，2011，5（50）：977-986.

［5］ 徐鵬，林森.基于C4.5決策樹(shù)的流量分類方法［J］.軟件學(xué)報(bào)，2009，20（10）：2692-2704.

［6］ 李強(qiáng)，郝沁汾，肖利民，等.云計(jì)算中虛擬機(jī)放置的自適應(yīng)管理與多目標(biāo)優(yōu)化［J］.計(jì)算機(jī)學(xué)報(bào)，2011，34（12）：2253-2264.

［7］ 李麗英，唐卓，李仁發(fā).基于LATE的 Hadoop數(shù)據(jù)局部性改進(jìn)調(diào)度算法［J］.計(jì)算機(jī)科學(xué)，2011，38（11）：67-70.

［8］ Liu Zongtian.Research on Logic Rules for Refinement Learning［C］∥Proceedings of 2010International Colloquium on Computing，Communication，Control and Management（CCCM2010），2010.

［9］ Guo Y J.Research and Implementation of Future Network Computer based on Cloud Computing［C］∥Proceedings of 2010 Third International Symposium on Knowledge Acquisition and Modeling（KAM 2010），2010.

［10］ Wang L Z，Laszewski G V，Dayal J，et al.Towards energy aware scheduling for precedence constrained parallel tasks in a cluster with DVFS［C］∥Procecdings of the 10th IEEE／ACM Int’l Conf on Cluster，Cloud and Grid Computing.Melbourne：IEEE Computer Society，2010.

［11］ 李微，李德仁.基于 HSV色彩空間的 MODIS云檢測(cè)算法研究［J］.中國(guó)圖象圖形學(xué)報(bào)，2011，16（9）：1696-1701.

［12］ 張偉哲，張宏莉，張迪，等.云計(jì)算平臺(tái)中多虛擬機(jī)內(nèi)存協(xié)同優(yōu)化策略研究［J］.計(jì)算機(jī)學(xué)報(bào)，2011，34（12）：2265-2275.