云計算環境下基于時間期限和預算的調度算法

劉亞秋，邢樂樂，景維鵬

(東北林業大學信息與計算機工程學院，哈爾濱 150040)

1 概述

隨著網格計算和并行計算的發展，云計算應運而生，這宣告低成本、高性能計算時代的到來。它將計算作為一種服務提供給用戶，實際上是計算能力的商品化，用戶根據自己的需求使用云計算服務。在現有的云計算研究中，作業調度作為其運行樞紐，一直是研究的熱點技術之一，除了影響作業響應能力和執行效率外，還直接關系到整個平臺的系統性能、吞吐量和資源利用率。

目前，在已有的云計算調度研究中鮮有考慮云計算動態環境下用戶實際需求對調度影響的算法，其中，對時間期限和最高預算的研究，較早是在網格計算環境中。如文獻[1-2]分別提出一種網格環境下的考慮時間期限或者預算的作業調度，但滿足的是單一用戶需求，達到資源的時間最優或者預算最優，這樣很容易將任務集中分配到某一個資源上，造成負載不平衡。文獻[3]在上述算法基礎上同時考慮時間期限和預算問題，計算網格環境下所有資源在時間和預算上的均衡度，依此為任務分配合適的資源，以達到優化的目的，但該算法在調度時忽略了數據傳輸時間和網格環境的變化，且算法復雜度較高。而文獻[4]算法側重于判斷網格中資源的在時間和預算上不同的效益值，僅以此動態選擇時間最優或者代價最優，沒有明確考慮時間和預算效益值相同時調度的情況，且忽略了作業優先級與用戶需求的關系。

已有的云計算調度問題研究除自帶算法外，如文獻[5]將該路由領域的加權輪詢思想應用于作業調度中，提出了基于優先級的加權輪轉調度算法，算法中優先級和權值的計算僅以作業大小來判斷，既沒有考慮用戶要求，也不能適應動態的云環境。文獻[6-7]僅考慮了動態云的特點，前者提出滑動窗口的設計，通過調節窗口的大小來平衡云計算集群的負載，后者在原有 DLS算法的基礎上，加入Bayesian認知模型和社會學信任模型，提出Cloud-DLS算法。但上述 2種算法均沒有考慮用戶對作業的實際需求。文獻[8]也提出一種動態均衡調度，通過調整優先級為作業提供不同的服務，但是也無法保證在特定時間期限下作業是否能被執行。文獻[9]對作業的評價和最優化進行研究，側重于最優化一組作業的總執行時間，對其中的某一作業無法保證響應時間。為更合理地分配計算資源，提高集群的作業容量，文獻[10]提出一種最后期限評價模型，由模型獲得作業所需的最小資源數，即最小map槽數和最小reduce槽數，以此保證作業完成時間，并盡可能地提高集群作業數。但是此模型是靜態的，最小資源數一旦確定便不再改變，而無法適應動態變化的集群網絡環境，且沒有考慮預算問題。

本文提出一種基于時間期限和預算雙重約束的云計算調度改進算法(DBS)。根據用戶在時間期限和預算上的實際需求，設置不同優先級的隊列，通過權值計算模型得到作業權值，并作為優先級進行作業排序，結合時間和預算評價模型，依次調度作業分配集群計算資源，并且更新作業和集群信息，以適應云環境的動態變化，形成完整的調度策略。

2 基本模型

針對云計算環境下網絡負載及任務數動態變化的特點，同時考慮到用戶對時間期限和預算的實際需求，以及可能在時間期限和預算要求程度上的不同傾向，本文設計權值計算模型、最高預算評價模型和權值更新模型。

模型1 權值計算模型

根據作業的時間影響因子、最后截止時間和最高預算來計算權值，表達式如下：

其中，tasksNum表示作業的大小；D表示用戶設定的作業的最遲截止時間；B表示作業的最高預算；V表示資源在某一時刻的處理能力(考慮資源的當前負載)；c表示資源處理任務時每秒的收費；?表示用戶對作業完成時間要求的影響因子。

模型2 最高預算評價模型

二是拓寬思維視野。思維可以是工作發展的最大動力，也可以是最大的阻力。歷史上任何一次變革，都是首先從拓展思維視野、變革思想觀念開始的。軍民融合參與主體多元、涉及領域寬廣、利益交織重疊，必須倡導對思想的解放與更新，強化融合共贏理念，堅持優長互促、兼容互補、資源互投、效益互享，破除自成體系、自我封閉的陳舊觀念，在更廣范圍、更高層次、更深程度上，凝聚軍民融合發展合力，提升軍民融合發展效能。

以時間期限評價模型[10]為模板，推導出預算評價模型，為使推導簡化，本文做出以下假設：(1)集群中節點對 map任務和reduce任務的處理時間是相等的；(2)輸入數據的塊大小在HDFS中已經配置好；(3)每個reduce節點得到同等比例的reduce數據。

為評價作業 J的執行時間T，考慮 map完成時間，reduce完成時間和數據傳輸時間如下：

其中，Tm表示處理一個 map任務所需的時間；Tr表示處理一個reduce任務所需的時間；Td表示map和reduce任務傳輸一單位數據所需的時間；δ表示job輸入數據；fδ表示reduce任務的輸入數據；nm表示map任務的槽數；nr表示reduce任務的槽數。

當給出時間期限D和最高預算B時，表達式為：

其中，t表示job提交的時間；Sm表示第一個map任務開始的時間。從預算角度考慮，reduce任務最晚開始時間為：

時間期限D和最高預算B滿足：

因此，從預算角度考慮，作業Job需求的最小map槽數和最小reduce槽數分別為：

模型3 權值更新模型

系統設置為每隔500 ms更新一次作業最小槽數和作業權值。根據當前集群的作業運行情況，重新計算得出作業的最小槽數，然后和已得到的槽數進行比較，如果已得到的槽數比應得的槽數少，則適量地增加作業權值，如果已得到的槽數比應得的槽數多，則適量地減少作業權值。

然后比較當前作業的權值和平均值，如果作業權值小于平均值，則：

如果作業權值大于平均值，說明作業在其所在的隊列中已經處于優勢，等待500 ms，在下次更新時，若作業依然無法滿足最小槽數，則提交到上一級隊列，以增加獲得資源和調度的機會。

同理，當作業得到的槽數多于最小槽數，且作業權值大于其所在隊列的平均值時，更新作業權值：

若500 ms后依然獲得過多的資源，則調到下一級隊列。

3 算法設計

本文在云計算環境下加入時間期限和預算的雙重約束，結合評價模型提出了DBS算法，為Hadoop集群設置3 個隊列：HightimeQueue，MidtimeQueue，LowtimeQueue，在配置文件中設置不同的計算資源比例和收費標準：(1)HightimeQueue擁有最多的調度機會和計算資源，盡可能地保證對時間要求高的用戶作業的需求，但是相應的費用比其他2個隊列要高。(2)LowtimeQueue里的作業雖然對時間要求比較低，但是也為它配置一定的計算資源，盡可能避免高時間要求的作業獨占資源，低時間作業遲遲得不到響應的情況，進而可以使集群負載維持在一個較合理的水平。(3)MidtimeQueue的優先級在上述兩者之間，針對的是用戶對時間期限和預算要求相同的作業，保證了該類作業也可以得到一定的調度機會。

當JobClient提交作業后，會進入一個等待隊列，經過預處理，根據式(1)，計算出作業的權值，更新作業信息。然后根據用戶提交的時間影響因子，放入合適的隊列，為降低算法的復雜度，時間影響因子取值 0.0、0.5、1.0，分別對應 LowtimeQueue、MidtimeQueue和 HightimeQueue。分類結束之后，分別對隊列中的作業根據權值和提交時間進行排序，完成之后，等待Tasktracker發送心跳請求分配任務。

TaskTracker自主檢測當前節點的狀態，若發現存在空閑資源，則主動向 JobTracker發送信息，請求任務，JobTracker接收到信息后，啟動作業調度器，選擇作業進行分配。算法的偽代碼如下：

其中，m為集群總的資源數；n為集群中的作業數。算法的時間復雜度為 O (3n)，空間復雜度為 O( m n)。

4 實驗與結果分析

4.1 實驗環境

為了檢測DBS算法的性能，在實驗條件有限的情況下，搭建由6個節點構成的虛擬hadoop集群，其中每個節點內存為4 GB，CPU配置為雙核2.4 GHz，操作系統為Linux Ubuntu 10.0，Hadoop版本為Hadoop0.20.2。使用HDFS進行數據存儲，每一個文件塊大小為64 MB，并有3個副本。其中，一個節點設置為JobTracker和NameNode，其他節點為TaskTracker和DataNode。

4.2 結果分析

為比較調度算法對不同用戶需求作業的影響，實驗將作業分為2組，用Hadoop自帶的FIFO算法進行比較。

實驗1 相同大小作業不同時間影響因子

在相同大小作業不同時間影響因子的情況下，相關作業的參數設定以及集群不同調度算法對作業的響應時間如表1所示。

表1 DBS與FIFO調度算法結果比較1

可以看出，面對相同大小的作業，FIFO算法對作業無差別處理，平均響應時間為1 175.5 s，平均費用為152.6元，DBS算法平均響應時間為1 154.75 s，平均費用為145.29元，不僅提高了集群的處理能力，而且根據作業不同的需求調整執行次序，盡可能保證時間和預算的約束，更好地體現了作業的公平性。

集群內各個作業的map任務執行情況如圖1所示。可以看出，Job1執行速率最快，Job2執行最慢，雖然Job3和Job4的map任務結束時間差不多，但是時間期限為1 300 s的Job3比時間期限為1 200 s的Job4完成時間要早一些，因為2個作業時間影響因子為0.5，綜合考慮時間和預算，Job3權值要比Job4高，增加了一些執行的機會。此外，在Job1和Job3已完成，Job4即將完成的情況下，Job2試圖分配更多的map任務，體現了算法對集群的動態變化的反應，加快了map任務的執行時間。

圖1 DBS算法下作業的map任務數分配執行情況

實驗2 不同作業不同時間影響因子

在不同作業不同時間影響因子的情況下，相關作業參數設定以及DBS算法和FIFO算法作業處理結果對比如表2所示。

表2 DBS與FIFO調度算法結果比較2

可以看出，面對不同大小的作業，DBS算法的平均響應時間為1 230 s，平均花費為148.07元，優于FIFO算法76.5 s，節省21.9元。另外從圖中可以看到，雖然Job4的執行時間比Deadline多了37 s，這是因為在reduce階段可能會出現數據不均衡的情況，但是由于Job4的時間影響因子為0.5，Budget沒有超出最高預算，所以認為Job4執行成功，響應時間在可接受范圍內。

各個作業的map和reduce任務執行情況如圖2所示，Job3之所以比Job1結束的快，一方面是為了滿足截止時間，另一方面當作業規模比較小時，數據本地性比較好，減少了數據在節點間的復制和傳輸，任務執行速率加快。同理Job4作業數據比較大，增加了傳輸時間和處理時間，在reduce階段執行時間較長，但即使如此，也優于FIFO的作業響應時間。

圖2 DBS算法下作業的map和reduce任務分配執行情況

5 結束語

本文提出一種在云計算環境下，根據作業在時間期限和預算上不同需求動態調整分配的調度算法。實驗結果表明，該算法能有效地減少作業響應時間，均衡作業的不同需求，且算法復雜度較低，具有較好的穩定性。由于云計算環境面臨作業類型的復雜多樣，因此下一步將致力于面向數據類型更復雜，且具有多元約束的作業的調度問題，可以從建立一般約束模型，簡化約束等方面進行研究。

[1]Abramson D, Buyya R, Giddy J.A Computational Economy for Grid Computing and Its Implementation in the Nimrod-G Resource Broker[J].Future Generation Computer Systems,2002, 18(8): 1061-1074.

[2]Yu Jia, Buyya R, Tham C K.Cost-based Scheduling of A Scientific Workflow Application on Utility Grids[C]//Proc.of the 1st International Conference on e-Science and Grid Computing.Washington D.C., USA: IEEE Press, 2005.

[3]Garg S K, Buyya R, Siegel H J.Time and Cost Trade-off Management for Scheduling Parallel Applications on Utility Grids[J].Future Generation Computer Systems, 2009, 26(1):1344-1355.

[4]李慧敏, 蔣秀鳳.基于時間期限和預算效益函數的網格資源調度算法[J].福州大學學報, 2009, 37(6): 803-807.

[5]鄧自立.云計算中的網絡拓撲設計和Hadoop平臺研究[D].合肥: 中國科學技術大學, 2009.

[6]張密密.MapReduce模型在Hadoop實現中的性能分析及改進優化[D].成都: 電子科技大學, 2010.

[7]Wang Wei, Zeng Guosun, Tang Daizhong.Cloud-DLS:Dynamic Trusted Scheduling for Cloud Computing[J].Expert Systems with Applications, 2011, 39(3): 2321- 2329.

[8]Sandholm T, Lai T.Dynamic Proportional Share Scheduling in Hadoop[C]//Proc.of the 15th International Workshop on Job Scheduling Strategies for Parallel Processing.Atlanta, USA:[s.n.], 2010.

[9]Zaharia M, Borthakur D, Sarma J S.Delay Scheduling: A Simple Technique for Achieving Locality and Fairness in Cluster Scheduling[C]//Proc.of the 5th European Conference on Computer Systems.New York, USA: ACM Press, 2010.

[10]Kc K, Anyamwu K.Scheduling Hadoop Jobs to Meet Deadlines[C]//Proc.of Conference on Cloud Computing Technology and Science.Indianapolis, USA: IEEE Press, 2010.