基于決策樹分類的云作業(yè)調度算法研究與實現

強 彥，盧軍佐，裴 博

（太原理工大學 計算機科學與技術學院，太原030024）

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

1 決策樹分類算法

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

C4.5算法描述如下。

輸入：訓練樣本samples、候選屬性集合attribute list、當前樣本T；

輸出：一棵決策樹；

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

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

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

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

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

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

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

Step8：計算每個節(jié)點的分類錯誤，進行樹剪枝。

2 決策樹分類作業(yè)調度

2.1 網絡訓練

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

表1 訓練樣本集

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

圖1 決策樹

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

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

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

2.2 決策樹分類作業(yè)調度

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

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

輸出：作業(yè)分類、調度結果；

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

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

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

Step3：預測相應的作業(yè)的類型、執(zhí)行時間，然后按照時間的先后順序和執(zhí)行時間的長短，對作業(yè)進行分類執(zhí)行；

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

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

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

3 實驗與分析

本文采用8個節(jié)點的集群來評估該算法，其中一個為主控節(jié)點，其他為輔助節(jié)點［9］。每個節(jié)點的配置為Inter雙核，2.4Hz，250G硬盤和2G內存，這些節(jié)點通過千兆交換機相連。每個節(jié)點裝有Linux系統和Hadoop平臺。實驗中Hadoop中參數設置如表2所示。

表2 Hadoop參數設置

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

3.1 算法的可行性

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

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

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

3.2 算法的效率驗證

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

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

圖4 兩種調度算法的結果

4 結束語

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

［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］ 李亞瓊，宋瑩，黃永兵.一種面向虛擬化云計算平臺的內存優(yōu)化技術［J］.計算機學報，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決策樹的流量分類方法［J］.軟件學報，2009，20（10）：2692-2704.

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

［7］ 李麗英，唐卓，李仁發(fā).基于LATE的 Hadoop數據局部性改進調度算法［J］.計算機科學，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云檢測算法研究［J］.中國圖象圖形學報，2011，16（9）：1696-1701.

［12］ 張偉哲，張宏莉，張迪，等.云計算平臺中多虛擬機內存協同優(yōu)化策略研究［J］.計算機學報，2011，34（12）：2265-2275.