CloudSim中基于偏序關(guān)系的調(diào)度算法研究

熊 磊， 陳宏偉， 王淑平

(湖北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院， 湖北 武漢 430068)

云計(jì)算是一個(gè)以經(jīng)濟(jì)模式為驅(qū)動(dòng)的大型分布式計(jì)算模式[1]．在這種模式的驅(qū)動(dòng)下，以云存儲(chǔ)和云安全為基礎(chǔ)的各種服務(wù)相繼出現(xiàn)．云計(jì)算通過虛擬技術(shù)，將云的計(jì)算能力及各類資源提供給用戶．將云端資源有效的分配給用戶是一個(gè)關(guān)鍵的技術(shù)問題．

學(xué)者們提出了先來先服務(wù)算法(FCFS，first come first service)、貪心算法(Greedy)、蟻群優(yōu)化算法(ACO)[2]，遺傳算法等來解決這個(gè)問題．先來先服務(wù)算法優(yōu)點(diǎn)在于它容易實(shí)現(xiàn)，其缺點(diǎn)在于其沒有考慮虛擬機(jī)的處理能力和任務(wù)的長(zhǎng)度等一系列屬性．貪心調(diào)度算法很好地避免了將長(zhǎng)任務(wù)分配給處理能力弱的情況，但這個(gè)算法是一個(gè)局部最優(yōu)的算法，它沒有考慮系統(tǒng)的整體執(zhí)行效率．蟻群優(yōu)化算法作為一種智能算法，任務(wù)在經(jīng)過蟻群的多次迭代之后必然能分配給一個(gè)合理的虛擬機(jī)，但其時(shí)間復(fù)雜度會(huì)高于FCFS和Greedy算法．

這些算法都沒有涉及到任務(wù)的依賴關(guān)系和優(yōu)先級(jí)．針對(duì)這個(gè)問題，本文提出了一種帶偏序關(guān)系的調(diào)度算法(POA, Partial Order Algorithm)，給每個(gè)任務(wù)設(shè)置依賴關(guān)系和優(yōu)先級(jí)，然后將FCFS、Greedy、ACO分別嵌入到POA中用于任務(wù)調(diào)度．帶偏序關(guān)系的調(diào)度算法將會(huì)用CloudSim工具包[3-5]進(jìn)行模擬仿真．CloudSim是在離散事件模擬包SimJava上開發(fā)的函數(shù)庫，它繼承了GridSim的編程模型，支持云計(jì)算的研究和開發(fā)．

本文在第1部分介紹CloudSim的體系結(jié)構(gòu)；在第2部分和第3部分中分別給出POA的算法實(shí)現(xiàn)及相關(guān)的仿真結(jié)果．

1 CloudSim的體系結(jié)構(gòu)

云計(jì)算平臺(tái)任務(wù)調(diào)度的基本模型包含3個(gè)主要的部分：Users、Tasks、Virtual Machines．Users即為云計(jì)算平臺(tái)的終端用戶，他們不需要了解云計(jì)算平臺(tái)的技術(shù)實(shí)現(xiàn)細(xì)節(jié)，只需要通過終端接入云計(jì)算平臺(tái)提供的接口便能夠使用其提供的服務(wù)．Tasks是用戶向云計(jì)算平臺(tái)請(qǐng)求處理的任務(wù)單元，它和用戶是多對(duì)一的關(guān)系，一個(gè)用戶可以請(qǐng)求處理多個(gè)任務(wù)，但一個(gè)具體的任務(wù)只隸屬于一個(gè)用戶．用戶的任務(wù)最終都會(huì)放到Virtual Machines上進(jìn)行處理．CloudSim中的基本模型見圖1．

圖 1 CloudSim的基本模型

2 POA算法

CloudSim中的任務(wù)默認(rèn)是沒有依賴關(guān)系和優(yōu)先級(jí)的．但是實(shí)際生活中的云任務(wù)，往往存在這些偏序關(guān)系，某個(gè)任務(wù)的執(zhí)行必須等待其它某個(gè)任務(wù)執(zhí)行完畢；而且，在云計(jì)算中，虛擬機(jī)屬于稀有資源，它需要合理地處理那些優(yōu)先級(jí)比較高的任務(wù)．本文中，如果任務(wù)A依賴B，我們則以A→B的形式來描述它們的依賴關(guān)系；設(shè)置任務(wù)的默認(rèn)優(yōu)先級(jí)為10．最后將任務(wù)的依賴關(guān)系和優(yōu)先級(jí)寫入到兩個(gè)不同的文件．

圖 2 POA算法執(zhí)行流程圖

如果在任務(wù)的依賴關(guān)系文件中有如下依賴：A→B，B→C．因?yàn)锳不需要依賴任何任務(wù)，故規(guī)定任務(wù)A為依賴關(guān)系圖的第一層，根據(jù)圖的深度，B屬于第二層，C屬于第三層．POA執(zhí)行的流程圖見圖2，其具體執(zhí)行步驟如下：

Step1. 分析任務(wù)的依賴關(guān)系文件，如果任務(wù)存在相互依賴或依賴關(guān)系形成環(huán)，則報(bào)錯(cuò)并退出．

Step2. 如果依賴關(guān)系合理，則對(duì)這些依賴關(guān)系進(jìn)行分析，并將依賴關(guān)系圖的每一層保存．

Step3. 依次讀取步驟2中依賴關(guān)系圖的每一層，如果某一層中某個(gè)任務(wù)的優(yōu)先級(jí)別比其依賴任務(wù)的優(yōu)先級(jí)要高，則表明依賴關(guān)系和優(yōu)先級(jí)別沖突，報(bào)錯(cuò)并退出．

Step4. 如果步驟3不報(bào)錯(cuò)，則重新讀取依賴關(guān)系圖的每一層，然后分別通過先來先服務(wù)算法(FCFS)、貪心算法(Greedy)、蟻群優(yōu)化算法(ACO)對(duì)這一層中的任務(wù)進(jìn)行調(diào)度，并以最后一個(gè)任務(wù)完成的時(shí)間作為調(diào)度時(shí)間進(jìn)行記錄．

Step5. 當(dāng)每一層都調(diào)度結(jié)束以后，對(duì)步驟4中記錄的每一層的調(diào)度時(shí)間進(jìn)行累加，最終得到的就是完成所有任務(wù)調(diào)度的時(shí)間．

3 仿真及結(jié)果分析

仿真系統(tǒng)中設(shè)置了兩種不同的參數(shù)設(shè)置方式，其分別是平均隨機(jī)和高斯隨機(jī)．其中，平均隨機(jī)出來的虛擬機(jī)和任務(wù)參數(shù)將平均地分布在參數(shù)下限和上限之間；高斯隨機(jī)出來的參數(shù)將呈現(xiàn)正態(tài)分布．在平均隨機(jī)中，虛擬機(jī)要設(shè)置其數(shù)量、處理能力下限、處理能力上限；任務(wù)需要設(shè)置其數(shù)量、長(zhǎng)度下限、長(zhǎng)度上限．通過這樣隨機(jī)得到的參數(shù)會(huì)均勻的分布到一條直線上．在高斯隨機(jī)中，虛擬機(jī)要設(shè)置其數(shù)量、處理能力平均值μ、處理能力標(biāo)準(zhǔn)差σ；任務(wù)需要配置其數(shù)量、長(zhǎng)度平均值μ、長(zhǎng)度標(biāo)準(zhǔn)差σ．

圖3、圖4描述了虛擬機(jī)參數(shù)和任務(wù)參數(shù)變化時(shí)對(duì)POA算法中三種不同調(diào)度策略的影響．當(dāng)采用平均隨機(jī)進(jìn)行調(diào)度，設(shè)定虛擬機(jī)數(shù)量在200～400間波動(dòng)、Mips在200～400間變化、任務(wù)數(shù)量在400～800之間變化、任務(wù)長(zhǎng)度在10 000～20 000間變化，POA中三種不同調(diào)度策略完成任務(wù)調(diào)度的時(shí)間如圖3所示；采用高斯隨機(jī)調(diào)度，設(shè)定虛擬機(jī)數(shù)量在200～400間波動(dòng)，Mips在平均值為200方差為50，任務(wù)數(shù)量在400～800之間變化，任務(wù)長(zhǎng)度平均值為15 000，標(biāo)準(zhǔn)差為500時(shí)，POA中三種調(diào)度策略完成任務(wù)調(diào)度的時(shí)間見圖4．

圖 3 平均隨機(jī)下的POA算法

圖 4 高斯隨機(jī)下的POA算法

4 結(jié)束語

本文的主要工作是對(duì)CloudSim中的任務(wù)調(diào)度算法進(jìn)行改進(jìn)，提出了POA算法．本文通過平均隨機(jī)、高斯隨機(jī)的方式來測(cè)試POA算法的性能．最后，在參數(shù)相同的情況下對(duì)內(nèi)嵌于POA算法的FSFS、Greedy、ACO進(jìn)行比較并以此評(píng)判各算法的優(yōu)劣．在本文談及的POA任務(wù)調(diào)度中，我們只將FCFS、Greedy、ACO這些相對(duì)比較簡(jiǎn)單的算法用于任務(wù)調(diào)度．這些算法本身存在著一些弊端，應(yīng)該有其它調(diào)度算法在低時(shí)間復(fù)雜度的情形下更合理地將任務(wù)分配給虛擬機(jī)，這些未考慮的問題，在以后的工作中將會(huì)被改進(jìn)．

[參考文獻(xiàn)]

[1] Cenk Erdil D.Simulating peer-to-peer cloud resource scheduling[J]. Peer-to-Peer Networking and Applications, 2012, 5(03): 219-230.

[2] Xiangqian Song, Lin Gao, Jieping Wang.Job scheduling based on ant colony optimization in cloud computing[C].2011 International Conference on Computer Science and Service System (CSSS), 2011： 3 309-3 312.

[3] Buyya R, Ranjan R, Calheiros R N. Modeling and simulation of scalable Cloud computing environments and the CloudSim toolkit: Challenges and opportunities [C]. International Conference on High Performance Computing & Simulation, 2009(HPCS '09), 2009：1-11.

[4] Xiaocheng Liu, Qiang He, Xiaogang Qiu, et al.Cloud-based computer simulation: Towards planting existing simulation software into the cloud[J].Simulation Modelling Practice and Theory, 2012,26:135-150.

[5] Werner J, Geronimo G, Westphall C, et al. Simulator improvements to validate the Green Cloud Computing approach[C].2011 7th Latin American Network Operations and Management Symposium (LANOMS), 2011：1-8.