楊 戈,趙 鑫,黃 靜,2

1(北京師范大學珠海分校 智能多媒體技術重點實驗室,珠海 519087)

2(北京師范大學研究生院珠海分院,北京 100875)

3(北京大學深圳研究生院 深圳物聯(lián)網(wǎng)智能感知技術工程實驗室,深圳 518055)

1 引言

而隨著云技術的發(fā)展和云平臺的廣泛部署,云中的工作流調度問題成為一個重要的研究課題[1],在云計算服務交付的過程中,由于用戶直接面對的是虛擬機資源,而真正解決問題的是虛擬機映射的實際的物理資源,所以如何將任務合理分配到資源執(zhí)行是我們所重點關注的.

(1)云計算

云計算通過多種部署方式,包括私有云、社區(qū)云、公有云、混合云4 種部署模型[2],通過基礎設施即服務、平臺即服務、軟件即服務3 種服務模式用戶提供服務.云計算有2 個顯著的特征,快速彈性可擴展[3]、按需付費服務[4].

云計算關鍵技術[5]分別有:虛擬化技術[6]、分布式數(shù)據(jù)存儲技術[7]、大規(guī)模數(shù)據(jù)管理技術[7]、調度技術[8].

(2)調度技術

云計算中的調度一般分為兩個部分:① 資源調度:資源調度是指對物理資源進行合理有效的管理和使用等;② 任務調度:將任務合理分配到合適的計算資源執(zhí)行.

簡單點講,一次正常的用戶服務流程為:用戶提交任務到云端,任務調度器將任務分配到合適的計算資源上執(zhí)行,任務完成后再將結果反饋給用戶.其中,任務分配這一環(huán)尤其重要,一個合理高效的調度策略能夠極大的提升云計算系統(tǒng)的性能.下文重點關注的是任務調度.

隨著云用戶數(shù)量的不斷增加,為用戶提供優(yōu)質的服務勢在必行.因此,任務調度非常重要,因為它專注于在特定時間將任務分配給可用資源.為了獲得良好的用戶服務質量,需要高效的任務調度.現(xiàn)有的云計算任務調度技術已經(jīng)被研究者們提出,但要實現(xiàn)高效的任務調度,還需要進一步的改進.所有算法的主要目標都是最大限度地利用資源,最大限度地減少制造時間和成本,提高性能.

(3)云環(huán)境中的服務交付模型

云計算中的服務交付模型分為4 部分,如圖1 所示.

① 用戶提交任務;

② 任務管理器將其拆分成多個子任務;

③ 任務調度器通過調度技術將子任務與物理資源建立映射關系;

④ 任務完成后進行匯總,反饋到用戶.

由此看出,從任務出發(fā)到完成,在整個任務執(zhí)行過程中,調度技術是重中之重,它影響到了整個系統(tǒng)的運行效率、用戶服務質量、系統(tǒng)負載均衡、系統(tǒng)能耗.

因此一個適合云計算環(huán)境的調度技術十分重要.由于調度技術分為資源調度和任務調度,本文只關注任務調度.

圖1 云計算服務交付模型圖

2 任務調度

任務調度,在云計算環(huán)境下其本質是一個映射的過程,它在一定的約束條件下,根據(jù)云計算環(huán)境下任務、資源兩者的預測信息和狀態(tài)將用戶提交的互相獨立的任務映射到相應的虛擬機資源上執(zhí)行,然后返回處理結果[9].簡單點說,就是將x個任務分配到y(tǒng)個計算機資源上執(zhí)行的過程.

根據(jù)工作流和資源的可用信息以及任務分配給資源的時間可以將任務調度分為靜態(tài)調度和動態(tài)調度[1].

2.1 調度分類

2.1.1 靜態(tài)調度

靜態(tài)調度中分為4 類:列表調度啟發(fā)式[10,11]、聚類調度啟發(fā)式[11]、重復調度啟發(fā)式、元啟發(fā)式.

(1)列表啟發(fā)式

基本思想是通過給任務分配一些優(yōu)先級,并根據(jù)優(yōu)先級對其進行排序,從而生成一個任務調度列表,然后從調度列表中選擇第一個任務,再將任務分配給其對應的資源,直到對所有任務進行調度.

調度列表可以靜態(tài)或動態(tài)構造.如果所有優(yōu)先級都是在任務分配之前構造的,則為靜態(tài)列表調度;如果在每個任務調度之后重新計算未調度任務的優(yōu)先級,則為動態(tài)列表調度.但是無論是哪種列表調度,都必須要有一個優(yōu)先級的判斷屬性和資源選擇策略,并以此決定任務的優(yōu)先級與其對應的最佳資源.

常見的列表調度啟發(fā)式算法,如最早時間優(yōu)先(Earliest Time First,ETF),異類最早完成時間(Predict Earliest Finish Time,PEFT)[10]等.

(2)聚類啟發(fā)式

基本思想是通過在同一個集群中對任務進行聚類,將任務映射到集群,在同一個群集中排序任務.盡量犧牲并行性來降低通信延遲,優(yōu)化數(shù)據(jù)相關任務之間的傳輸時間.

如果同一個集群中有兩個獨立的鄰居任務,則稱為非線性集群;否則稱為線性集群.對于非線性聚類,對獨立任務進行排序.線性聚類保留了并行性,不會增加并行執(zhí)行時間.非線性聚類通過對并行任務進行排序來減少并行性,從而增加并行執(zhí)行時間.

(3)重復啟發(fā)式

基本思想是在目標任務的同一資源上正確地復制任務,從而避免這兩個任務之間的執(zhí)行時間沖突,以及在不同的時間段內可能會發(fā)生一些資源閑置的情況.

因為在實際的調度中,有些任務可能正在等待分配給其他資源的任務的數(shù)據(jù),只有接收到該數(shù)據(jù)之后,任務才能開始執(zhí)行,如果在數(shù)據(jù)接收之前輪到該任務執(zhí)行,就會發(fā)生阻塞,產(chǎn)生空閑時段,直到數(shù)據(jù)到來,影響到后面任務的執(zhí)行.如果使用有效的調度算法,通過識別任務使得這些空閑時段可以有效地利用,那么就可以縮短總的執(zhí)行時間.

基于重復的調度通?？梢钥s短生成時間.然而,這也使得調度問題更加困難.調度算法不僅需要觀察任務之間的優(yōu)先級約束,還需要識別哪些任務需要復制,以及如何將它們放入空閑時段.

(4)元啟發(fā)式

元啟發(fā)式是啟發(fā)式的進化版,是對啟發(fā)式局部搜索的改進,元啟發(fā)式方法通常提供了一種快速朝著一個非常好的解決方案前進的有效方法.如遺傳算法、蟻群算法、粒子群算法等.

與基于局部搜索的啟發(fā)式方法相比,元啟發(fā)式方法能夠在更大的解空間中搜索到任務解決方案.因此,在大多數(shù)情況下,元啟發(fā)式比基于局部搜索的啟發(fā)式性能更好.

將以上局部的靜態(tài)調度做了一個比較,比較結果如表1 所示.

列表啟發(fā)式大部分都適用于資源數(shù)量有限的系統(tǒng),比較關注如何在保證能完成調度的同時降低系統(tǒng)的開銷.

聚類啟發(fā)式通常假定資源數(shù)量無限,并將大量通信任務分配給同一類資源.雖然它減少了資源間的通信,但當任務在資源上按優(yōu)先級約束排序時,也可能導致負載不平衡或空閑時隙.

重復啟發(fā)式算法旨在降低任務的執(zhí)行時間,避免大量的通信.重復啟發(fā)式通常在犧牲計算時間復雜性的情況下具有更好的調度質量.

元啟發(fā)式比以上基于局部的啟發(fā)式性能更好.但是,隨著工作流任務數(shù)的增加,元啟發(fā)式算法的調度時間開銷也會迅速增加.

表1 靜態(tài)調度比較表

2.1.2 動態(tài)調度

動態(tài)調度[12]是為了解決調度信息的不可用性和資源與其他工作流或非工作流系統(tǒng)負載的爭用而開發(fā)的,目標是在可用資源隊列之間平衡負載.

任務執(zhí)行和通信時間由資源和工作流信息共同決定.其中工作流信息包括工作流結構、任務執(zhí)行工作量、通信數(shù)據(jù)量等,資源信息包括云環(huán)境下的可用性、處理能力、通信帶寬等.在實際生產(chǎn)系統(tǒng)中它們都是不完整的、動態(tài)的.要準確地評估每個隊列的負載并不容易,因此需要一個動態(tài)調度策略來處理這些不確定性.

總的來說,在靜態(tài)中,所有關于任務的信息在執(zhí)行之前都是調度程序已知的,可以事先獲取到更多信息,對任務調度的方案進行優(yōu)化,使得任務實際執(zhí)行時開銷更小;而在動態(tài)中,關于任務的信息在執(zhí)行之前不知道,但運行時開銷更大,但是能更好地處理負載平衡的問題.

通過對調度的分析發(fā)現(xiàn),不管是靜態(tài)還是動態(tài)調度,由理論到實際解決問題都是依靠具體的任務調度算法執(zhí)行的.簡單地說,一種任務調度算法就是一種調度方式,云計算中任務調度的優(yōu)劣主要就體現(xiàn)在任務調度算法的優(yōu)劣上.

合理的任務調度要從2 個出發(fā)點進行考慮:云計算提供商,用戶.對提供商來說,最關心的就是成本,所以要能夠有效協(xié)調和分配資源,降低成本;對用戶來說,服務質量放在首位,所以需要在完成需求的同時,降低任務的總執(zhí)行時間.

所以一個既可以對虛擬資源進行有效的協(xié)調和分配,降低提供商的成本;又能快速、準確地完成任務,給用戶一個好的用戶體驗;能讓提供商和用戶都滿意的任務調度算法是云計算所迫切需要的.

而任務調度的約束條件就是依靠具體的任務調度算法來執(zhí)行的,所以選擇合適的任務調度算法對策略的執(zhí)行具有很重大的意義.

2.2 任務調度算法

任務調度算法根據(jù)調度目標的數(shù)量可以分為2 類:針對單一目標優(yōu)化的傳統(tǒng)任務調度算法,針對多目標優(yōu)化的啟發(fā)式思想的智能化算法.

2.2.1 單目標優(yōu)化的任務調度算法

單目標優(yōu)化的任務調度算法主要包括最小完成時間(Minimum Completion Time,MCT)、最小執(zhí)行時間(Minimum Execution Time,MET)、交換算法(Switching Algorithm,SA)、貪心算法(GReedy Algorithm,GRA)、先來先服務(先進先出)算法(First Come First Server,FCFS/First In First Out,FIFO)、短作業(yè)優(yōu)先算法(Shortest Job First,SJF)等.

其中MET 算法考慮到任務的最短執(zhí)行時間,忽略了負載是否平衡的問題;MCT 算法考量到任務最早的完成時間,但是可能導致工作時間變長;SJF 算法考慮選擇用時較短的任務優(yōu)先執(zhí)行,而忽略了任務的優(yōu)先級.

從以上不難看出:單目標優(yōu)化的任務調度算法重點在于單一目標的最優(yōu)解,即某個實例的最優(yōu),體現(xiàn)在“最”字上,這樣的話其他實例沒在考慮的范圍內,就會不可避免的舍棄掉很多東西,比較局限于某個目標最優(yōu),而無法考慮到全局,都是比較極端的算法,為了達到目標,可以不惜犧牲一切.導致的后果是:雖然該實例取得的效果最好,但是因為要最大化的滿足它而舍棄掉太多東西,導致其他實例的效果就不是很理想甚至很糟糕,使得結果具有很大的局限性而無法推廣.

2.2.2 多目標優(yōu)化的任務調度算法

在優(yōu)化設計中,要求多個目標達到最優(yōu)的問題被稱為多目標優(yōu)化或者多約束問題.在這種情況下,基于啟發(fā)式思想的智能化算法應運而生.

啟發(fā)式思想的智能化算法思想在于:解決多約束問題時,在可以接受的花費的前提下,得到一個解決方案,給出盡量滿足多個目標優(yōu)化的一個可行解.其核心點在于“多目標優(yōu)化”,即對于每一個實例來說,也許當下解并不是它的最優(yōu)解,但卻是多個實例在盡量滿足需求條件下的極優(yōu)解.

常用的啟發(fā)式思想的智能化算法包括2 類[13]:

(1)基于生物啟發(fā)(Biological Inspiration,BI)

遺傳算法(Genetic Algorithm,GA)、模因算法(Memetic Algorithm,MA)、獅子算法(Lion Algorithm,LA)、帝國競爭算法(Imperialist Competitive Algorithm,ICA),是在云計算中與任務調度相關的少數(shù)生物啟發(fā)算法.

(2)基于群體智能(Swarm Intelligence,SI)

蟻群(Ant Colony Optimization,ACO)算法、粒子群優(yōu)化(Particle Swarm Optimization,PSO)算法、模擬退火(Simulated Annealing,SA)算法、人工蜂群(Artificial Bee Colony,ABC)算法、貓群優(yōu)化(Cat Swarm Optimization,CSO)算法、蝙蝠算法(Bat Algorithm,BA)、風驅動優(yōu)化(Wind Driven Optimization,WDO)算法等[13].

3 任務調度算法

3.1 遺傳算法

GA 的創(chuàng)造思路來源于達爾文著名的生物進化論中“優(yōu)勝劣汰”的自然選擇原則,將自然生物的進化類比應用到實際問題中,是通過模擬自然進化的過程來解決組合優(yōu)化問題的一種搜索最優(yōu)解的方法.

GA 對于給定問題的任何解決方案都由一組稱為基因的元素組成的染色體代表,即每一條染色體代表一個解決方案.算法終止后,最出色的染色體就是給定問題的最優(yōu)解.

算法的優(yōu)點:進行選擇、交叉、變異等操作的目標是選擇區(qū)域中所有的染色體,初期全局搜索能力強,并行性強;

缺點:要花費大量時間對染色體進行評估、選擇、交叉、變異等操作,后期求解效率低.

遺傳算法的優(yōu)點主要在于其強力的全局搜索,但是在算法的搜索效率以及算法解的多樣性方面還是需要改進,所以以下文獻主要對算法的這2 個部分進行優(yōu)化,如表2 所示.

表2 遺傳算法優(yōu)化表

3.2 蟻群算法

ACO 最早是于20 世紀90 年代,Dorigo M 等[19]通過觀察螞蟻覓食行為,并從中獲得設計靈感而提出的,常用于求解復雜組合優(yōu)化問題的一種元啟發(fā)式智能優(yōu)化技術[20].

信息素的管理主要包括信息素的局部更新和信息素的全局更新2 個部分[21].

算法的優(yōu)點:在后期確定了目標點和最優(yōu)路徑之后,所有成員每次都會按照最優(yōu)路徑進行計算,節(jié)省大量時間,速度快.

缺點:在初期確定目標點和最優(yōu)路徑時,因為信息匱乏需要花費大量的時間做大量的摸索嘗試,速度慢.

蟻群個體之間通過信息素交流,信息素積累起來之后,搜索效率、解的精度極高,但同時,其缺點在于前期信息素的積累花費了太多時間,由于收斂速度快,也容易陷入局部最優(yōu),所以以下文獻主要在算法的解的多樣性和算法前期的搜索效率方面進行優(yōu)化,如表3所示.

表3 蟻群算法優(yōu)化表

3.3 粒子群算法

粒子群算法,也稱為鳥群、魚群覓食算法,是模擬鳥群、魚群的覓食行為規(guī)律在搜索空間進行搜索最優(yōu)解的方法.最早由Kennedy J 和Eberhart R[26],該算法最初是對一個簡化的社會環(huán)境的模擬,主要應用于求解連續(xù)搜索范圍問題[27].

與遺傳算法這種進化算法不同,遺傳算法會舍棄適應度較低的染色體,而粒子群不使用選擇,不會舍棄任何一個解,盡管這個解的質量很差,算法會利用粒子間的信息交流對差解不斷地優(yōu)化,所有的種群成員從試驗開始一直存活到最后.

算法的優(yōu)點:搜索速度快、收斂速度快、參數(shù)少等.

缺點:局部搜索能力差、初始化粒子隨機性強.

粒子群和蟻群算法在某些方面比較相似,搜索速度快,但是容易陷入極值,所以以下文獻主要在算法多樣性和精度方面進行優(yōu)化,如表4 所示.

表4 粒子群算法多樣性優(yōu)化表

3.4 模擬退火算法

模擬退火算法是一種隨機搜索算法,是對熱力學中固體物質退火過程的模擬.文獻[34]中介紹模擬退火算法最早的思想是由Metropolis 等提出.Kirkpatrick 等成功地將退火思想引入到組合優(yōu)化領域.

固體物質退火過程與一般組合優(yōu)化問題之間的相似性如表5 所示.

表5 模擬退火算法與組合優(yōu)化問題的相似性

SA 對于給定問題的任何解決方案都由退火過程中物質的狀態(tài)代表,即每個溫度下物質的狀態(tài)代表一個解決方案,當內能到達最低時,物質的狀態(tài)就代表最優(yōu)解[35].

算法的優(yōu)點:穩(wěn)定性好,在局部最優(yōu)時容易有概率跳出并趨于全局最優(yōu);

缺點:對參數(shù)依賴性強,收斂速度慢,搜索時間長.如果冷卻過程足夠慢,模擬運行時間足夠長,模擬退火幾乎可以保證找到最優(yōu)的解決方案.

與其它智能算法不同的是,SA 在迭代過程中會以一定的概率接受與當前解相比較差的解,接受概率隨著溫度的降低減小.由于在搜索過程中接受差解,所以有可能導致遺失掉最優(yōu)解;另一方面,這種處理可以在一定程度上避免算法陷入局部最優(yōu)解.

以下文獻主要在使用Metropolis 準則對新解進行一個概率接受的部分進行優(yōu)化,減小陷入局部最優(yōu)的可能性.如表6 所示.

3.5 算法對比

由以上第4 章對各算法的闡述,發(fā)現(xiàn)各個算法都有其自身的優(yōu)點和不足,這里對其能力的各個方面進行比較,如表7 所示.

算法搜索過程中會進行信息交互的算法ACO,PSO 都會面臨一個問題:信息交互后,每個個體都會受到優(yōu)秀個體搜索結果的影響,都會向著優(yōu)秀的個體“看齊”,這樣就會導致算法收斂速度大大加快.算法收斂速度快會產(chǎn)生2 種結果:

① 算法整體的進程節(jié)奏加快,更早地達到終止條件;

② 算法喪失多樣性,容易陷入局部最優(yōu).

與之相反,GA,SA 的收斂速度都相對比較慢,其原因是GA 會對種群中的大量個體執(zhí)行操作,SA 則會對溫度變化過程中產(chǎn)生的每一個新解都進行操作,花費了大量的時間,收斂速度自然就快不起來.算法收斂速度慢會產(chǎn)生2 種結果:

③ 算法整體的進程節(jié)奏過慢,算法搜索效率低;

④ 加強了算法的全局搜索能力,有效降低陷入局部最優(yōu)的可能性.

所以如何將算法的收斂性利用好,在加速算法進程的同時增加算法解決方案的多樣性是值得進行研究的.

啟發(fā)式思想的智能化算法相比較于傳統(tǒng)的算法優(yōu)化更全面,適用性更廣,雖然各自有各自的特點,但同時也有自身的不足,要想使其具有更強的生命力,就需要不斷自我提升;同時也需要借鑒其他算法的優(yōu)勢,彼此相互學習,優(yōu)劣互補來彌補自身的不足,同時達到更優(yōu)的效果.

表6 模擬退火算法優(yōu)化表

表7 算法對比

4 結束語

對云計算作了一個概述,闡述了云計算環(huán)境下的任務調度模型,并對其進行了分析,再由任務調度引出4 個比較完善、具有代表性的任務調度算法ACO、GA、PSO、SA,分別對它們做了詳細分析,包括基本思想、算法特點以及可改進的方式,針對各個算法的特點,歸納了一些各個算法兩兩之間可以進行改進以及融合方法;再對相比前面4 種算法,比較新穎的ACO、ICA、BA、CSO 做了分析,包括算法的基本思想、特點和可改進的方式;由于從理論想要應用到實踐,就必須要經(jīng)過實驗對其進行驗證,而直接投入實際環(huán)境中進行實驗會花費大量的時間、資源等.

隨著信息技術的不斷進步,物聯(lián)網(wǎng)在我們的日常生活中發(fā)揮著越加重要的作用,人們生活水平的提高,對各種物聯(lián)網(wǎng)應用的要求也越來越高,對云計算的挑戰(zhàn)也隨之到來.在傳統(tǒng)的云計算中,每一次服務交付都要將計算過程上傳到云,有限的帶寬和網(wǎng)絡資源被大量數(shù)據(jù)傳輸所占用,然而云是遠離用戶的,這就直接造成了云計算所面臨的第一大難點:網(wǎng)絡延遲.此外,物聯(lián)網(wǎng)設備和傳感器的功率是有限的,大量的數(shù)據(jù)傳輸也給物理設備帶來了壓力,這也是云計算所面臨的第二大難點:功耗成本.

為了延長設備的使用壽命,就很有必要通過將計算調度到具有更高功率和計算能力的設備來平衡功耗,即通過改善任務調度可以有效地降低云計算的功耗成本.因此,任務的調度和處理分配就成為了云計算需要解決的關鍵問題.

雖然通過調度方案的優(yōu)化可以減少云計算的功耗,但是由于云計算服務中,每一次服務交付都要將計算過程上傳到云端,即使改進了調度方案,還是無法有效地解決網(wǎng)絡延遲的問題.

為了解決云計算網(wǎng)絡延遲的問題,邊緣計算[40]出現(xiàn)了.邊緣計算不同于云計算,很直觀地,邊緣計算就是在網(wǎng)絡的“邊緣”進行服務交付,執(zhí)行的數(shù)據(jù)計算和存儲在用戶附近.相比較云計算與用戶的距離更近近,最直觀導致的結果就是降低了網(wǎng)絡延遲、網(wǎng)絡的帶寬需求、數(shù)據(jù)計算或存儲期間的傳輸延遲,并且有效地降低了物理設備損耗速度.此外,與云計算相比,邊緣計算可以將計算和通信開銷從具有有限電池或電源的節(jié)點遷移到具有大量功率資源的邊緣節(jié)點.

2016 年5 月,美國自然科學基金委(National Science Foundation,NSF)在計算機系統(tǒng)研究中將邊緣計算替換云計算,列為突出領域[41].雖然其發(fā)展和技術還不太成熟,但是由于其自身的特點,邊緣計算將會成為繼云計算之后的又一大熱點領域.7 個關鍵技術包括:網(wǎng)絡、隔離技術、體系結構、邊緣操作系統(tǒng)、算法執(zhí)行框架、數(shù)據(jù)處理平臺以及安全和隱私;未來幾年迫切需要解決的6 個方向問題:編程模型、軟硬件選型、基準程序與標準、動態(tài)調度、與垂直行業(yè)的緊密結合以及邊緣節(jié)點的落地[41].