基于云計算的調(diào)度算法

周捷 汪烊

摘要??? 文章從云計算的優(yōu)勢分析入手，論述了基于云計算的調(diào)度算法。期望通過本文的研究能夠?qū)Ω咝履芩惴ㄔ谠朴嬎阆到y(tǒng)任務(wù)調(diào)度中的合理運用有所幫助。

【關(guān)鍵詞】云計算 任務(wù) 調(diào)度算法

1 云計算的優(yōu)勢

云計算是由全球最大的搜索引擎公司-谷歌（Google），于2006年全球搜索引擎會議上提出的一種計算方法，其以效率高、成本低等特點，在各個領(lǐng)域中得到越來越廣泛的應(yīng)用，它的出現(xiàn)使計算科學領(lǐng)域發(fā)生了巨大改變。云計算的優(yōu)勢具體體現(xiàn)在如下幾個方面：

1.1 低廉的成本

目前，大部分企事業(yè)單位在IT方面的主要支出包括以下費用：設(shè)備成本、能耗及管理費用等。云計算不需要在設(shè)備上投入較多的資金，運維費用相對較少，由此可以為企業(yè)節(jié)省大量的資金。同時，云計算的成本優(yōu)勢與規(guī)模成正比，即企業(yè)應(yīng)用的云計算規(guī)模越大，成本優(yōu)勢就明顯，資金缺乏的企業(yè)可以利用云計算進行項目開發(fā)和研究。

1.2 對設(shè)備的要求不高

云計算用戶的應(yīng)用全部都是在云數(shù)據(jù)中心運行，只要用戶設(shè)備能夠接入網(wǎng)絡(luò)，便可對云計算進行使用。因此，只要基本的設(shè)備配置即可滿足使用需要。

1.3 數(shù)據(jù)可靠性高

在云計算下，用戶的數(shù)據(jù)全都存儲在云端，當用戶設(shè)備發(fā)生故障時，這些數(shù)據(jù)并不會丟失或是損壞，數(shù)據(jù)的安全性和可靠性得到有效保證。正是因為云計算所具備的上述優(yōu)勢，使其成為大多數(shù)用戶的首選計算方式。

2 基于云計算的調(diào)度算法

云計算系統(tǒng)具有異常強大的功能，可以為用戶提供與數(shù)據(jù)挖掘、數(shù)據(jù)處理等方面有關(guān)的服務(wù)。通常情況下，云計算系統(tǒng)會借助分布式處理技術(shù)，對任務(wù)進行分割，隨后利用調(diào)度算法將各個子任務(wù)映射到虛擬資源節(jié)點上，調(diào)度策略是這一過程實現(xiàn)的前提和基礎(chǔ)，調(diào)度算法則是獲得調(diào)度策略的關(guān)鍵。采用最優(yōu)的調(diào)度算法，可以得到最佳的調(diào)度策略，從而使云計算系統(tǒng)保持高效運行，滿足不同用戶的使用需求。

在云計算系統(tǒng)中，可將任務(wù)分為兩種情況，一種是獨立任務(wù)，另一種是關(guān)聯(lián)任務(wù)。不同的任務(wù)類型，需要采用相應(yīng)的調(diào)度算法。下面對此進行具體分析。

2.1 獨立任務(wù)調(diào)度算法

對于云計算系統(tǒng)中的獨立任務(wù)調(diào)度而言，可將其歸入到NP-完全問題的范疇，此類問題可以運用傳統(tǒng)的調(diào)度算法和啟發(fā)式算法。

2.1.1 傳統(tǒng)算法

在傳統(tǒng)調(diào)度算法中，比較常用的有以下幾種：

（1）Max-Min算法。這種算法的基本原理是將小任務(wù)優(yōu)先映射到速度最快的虛擬機上。在該算法下，調(diào)度器會對每個任務(wù)在不同虛擬機上運行的執(zhí)行時間進行計算，根據(jù)計算結(jié)果，找出執(zhí)行時間最少的任務(wù)，并將該任務(wù)調(diào)度至速度最快的虛擬機上。按照這樣的順序，直至全部任務(wù)調(diào)度完畢為止。這種算法最為突出的優(yōu)點是可以確保任務(wù)處理時間最短，但需要指出的是，部分虛擬機在該算法下可能會一直處于空閑狀態(tài)，不利于資源的有效利用。

（2）回填算法。這是一種能夠大幅度提升虛擬機利用效率的算法，在該算法下，系統(tǒng)會為等待隊列當中相對較小的任務(wù)預留出一定的資源，并對預約任務(wù)隊列的空隙加以合理利用，從而將這部分任務(wù)回填至前面，可以使任務(wù)的平均等待時間有所減少。回填算法最為突出的特點在于復雜程度相對較低，整個過程易于實現(xiàn)，并且具有較為明顯的調(diào)度優(yōu)勢。

2.1.2 啟發(fā)式算法

在啟發(fā)式算法中，比較常用的有以下幾種：

（1）蟻群算法。這種算法歸屬于概率型算法的范疇，可以借助該算法尋找優(yōu)化路徑，其最為基本的特征是分布計算和啟發(fā)式搜索。蟻群算法是以螞蟻的行走路徑，對待優(yōu)化問題的可行解進行表示，整個蟻群的所有路徑構(gòu)成了優(yōu)化問題的解空間。可將該算法在任務(wù)分配到虛擬機的場景中進行應(yīng)用，雖然通過蟻群算法可以獲得最優(yōu)解，但若是系統(tǒng)的規(guī)模過大，則會導致算法的效率降低。所以在大規(guī)模的系統(tǒng)中進行任務(wù)調(diào)度時，不推薦使用這種算法。

（2）遺傳算法。該算法簡稱GA，其理論基礎(chǔ)是達爾文的生物進化論，通過對自然進化過程的模擬，來搜索最優(yōu)解。GA在對多個個體的價值進行評估的過程中，主要是借助適應(yīng)度函數(shù)，通過對初始種群的交叉以及變異操作，使最終結(jié)果滿足終止條件的要求。該算法的優(yōu)勢體現(xiàn)在并行處理能力強，可對解空間中的多個解進行同時搜索等方面。

（3）粒子群算法。該算法簡稱PSO，歸屬于進化算法的范疇，其原理與模擬退火算法極為相似。PSO以隨機解作為起點，通過不斷地迭代尋找最優(yōu)解，實踐證明，PSO比遺傳算法的規(guī)則更加簡單，省去了交叉與變異過程，由此使其更容易實現(xiàn)，并且精度更高。

根據(jù)獨立任務(wù)的特點，結(jié)合對上述調(diào)度算法的分析，可以采用傳統(tǒng)算法中的回填算法或是啟發(fā)式算法中的粒子群算法，實現(xiàn)云計算系統(tǒng)獨立任務(wù)最優(yōu)調(diào)度的目標。

2.2 關(guān)聯(lián)任務(wù)調(diào)度算法

在云計算系統(tǒng)中，關(guān)聯(lián)任務(wù)可以分為靜態(tài)和動態(tài)兩種類型，前者的執(zhí)行與通信成本均為已知，而后者的這些條件則全部都是未知數(shù)，所以必須在系統(tǒng)運行時，才能進行調(diào)度決策。由于動態(tài)調(diào)度必須在運行的過程中完成，所以調(diào)度算法大多都是針對靜態(tài)調(diào)度任務(wù)。常用的有以下幾種：

2.2.1 基于表調(diào)度的算法

該算法包括兩個階段，在第一個階段時，會對任務(wù)進行調(diào)度優(yōu)先級劃分，進而形成調(diào)度列表;在第二階段時，會按照優(yōu)先級將表中的任務(wù)分配到虛擬機上執(zhí)行，直至全部任務(wù)調(diào)度完畢為止。

2.2.2 基于聚類的算法

該算法會以映射的方式，將任務(wù)映射到集群中，由于集群不會受到數(shù)量的限制，所以可承載海量的任務(wù)。然后集群中的任務(wù)進行聚類，迭代前先合并類似的集群，當兩個任務(wù)被分配到同一個集群內(nèi)時，可由一臺虛擬機完成任務(wù)執(zhí)行。

在這兩種算法中，表調(diào)度的計算過程較為簡單，并且其各方面性能都較為優(yōu)異，所以可將之作為關(guān)聯(lián)任務(wù)的主要調(diào)度算法。

3 結(jié)論

綜上所述，隨著云計算應(yīng)用領(lǐng)域的不斷拓寬，用戶的使用需求隨之發(fā)生了一定的變化。為對各種不同的任務(wù)進行高效調(diào)度，應(yīng)當加大對云計算調(diào)度算法的研究力度，除對現(xiàn)有的算法進行逐步改進和完善之外，還應(yīng)結(jié)合云計算的特點，開發(fā)一些新的調(diào)度算法，以此來推動云計算的持續(xù)發(fā)展。

參考文獻

[1]?滕云.云計算下資源調(diào)度算法的節(jié)能研究[J].電腦知識與技術(shù)，2018（30）.

[2]?柳興.移動云計算中的資源調(diào)度與節(jié)能問題研究[D].2015.

[3]?汪敏，汪正舟.實時服務(wù)框架設(shè)計于實現(xiàn)[J].指揮信息系統(tǒng)與技術(shù)，2017，8（02）：36-40.

[4]?蘇淑霞.面向云計算的任務(wù)調(diào)度算法研究[J].安徽大學學報（自然科學版），2014，38（05）：24-30.