基于機(jī)器學(xué)習(xí)的云計(jì)算資源調(diào)度綜述

王占豐，張林杰，呂 博，季宇凱，胡 超，溫勝昔

(1.東南大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，江蘇 南京 211189；2.中國電子科技集團(tuán)公司第五十四研究所 河北 石家莊 050081； 3.中國電子科技集團(tuán)公司第三十研究所,四川 成都 610093；4.南京理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，江蘇 南京 210094；5.陸軍工程大學(xué) 指揮控制工程學(xué)院，江蘇 南京 210007；6.南京萊克貝爾信息技術(shù)有限公司,江蘇 南京 210000)

0 引言

自2006年谷歌前CEO埃里克·施密特正式提出云計(jì)算概念后，經(jīng)過十多年的發(fā)展，云計(jì)算已成為當(dāng)前重要的信息基礎(chǔ)設(shè)施。國內(nèi)外互聯(lián)網(wǎng)巨頭紛紛建立了自己的云計(jì)算或數(shù)據(jù)中心，如谷歌、亞馬遜、微軟、阿里、華為、騰訊等，這些數(shù)據(jù)中心分布在世界各地且資源差異很大。云計(jì)算包括基礎(chǔ)設(shè)施即服務(wù)(IaaS)、平臺(tái)即服務(wù)(PaaS)和軟件即服務(wù)(SaaS) 3種服務(wù)類型。與傳統(tǒng)的網(wǎng)絡(luò)應(yīng)用模式相比，云計(jì)算具有彈性可擴(kuò)展、性價(jià)比高、可靠性高等優(yōu)點(diǎn)。特別是近年來伴隨著大數(shù)據(jù)技術(shù)、物聯(lián)網(wǎng)技術(shù)、5G等新興技術(shù)的出現(xiàn)，我國各級(jí)政府也紛紛建立數(shù)據(jù)中心，推進(jìn)企業(yè)上云，云計(jì)算得到了不斷發(fā)展與演化。

在云計(jì)算集群中通過優(yōu)化資源調(diào)度可以提高服務(wù)質(zhì)量，從而確保用戶服務(wù)水平。據(jù)統(tǒng)計(jì)，亞馬遜如果響應(yīng)時(shí)延增加100 ms則會(huì)導(dǎo)致1%的收入損失，谷歌的響應(yīng)時(shí)延增加0.5 s則會(huì)損失20%的用戶流量[1]。云計(jì)算的資源調(diào)度按照目標(biāo)的不同可以分為不同的類型：如按照調(diào)度的目標(biāo)，可以分為降低能耗的調(diào)度算法、完成目標(biāo)的調(diào)度算法、面向負(fù)載均衡的調(diào)度算法等；如按照調(diào)度的對(duì)象劃分來看，包括面向CPU、網(wǎng)絡(luò)、存儲(chǔ)等基礎(chǔ)資源的調(diào)度算法，面向Docker、面向服務(wù)的調(diào)度算法等；如按照調(diào)度策略來說，可以分為資源分配負(fù)載均衡和動(dòng)態(tài)調(diào)度策略等。

本文對(duì)近十年來關(guān)于云計(jì)算資源調(diào)度文獻(xiàn)進(jìn)行了廣泛的調(diào)研，研究了云計(jì)算資源調(diào)度算法的演進(jìn)策略，文中對(duì)云計(jì)算資源調(diào)度的框架和各類調(diào)度算法進(jìn)行了詳細(xì)論述分析，并指出未來研究方向。

1 云計(jì)算調(diào)度概述

云服務(wù)提供者主要的目標(biāo)是盡可能減少運(yùn)行開銷并同時(shí)能夠滿足用戶需求，主要是服務(wù)質(zhì)量和可用的資源。按照調(diào)度目標(biāo)可以分為：① 實(shí)現(xiàn)時(shí)延敏感業(yè)務(wù)和非敏感業(yè)務(wù)之間的平衡；② 實(shí)現(xiàn)性能和服務(wù)質(zhì)量(QoS)之間的平衡；③ 在公平和效率之間實(shí)現(xiàn)平衡；④ 適應(yīng)作業(yè)數(shù)目的增長。

資源調(diào)度問題存在于各類云計(jì)算環(huán)境中，包括數(shù)據(jù)密集型、PaaS、CaaS和IaaS等不同云計(jì)算法服務(wù)模式。如圖1所示，在所有公共云系統(tǒng)[2]涉及多個(gè)參與者，主要是云提供商和用戶，將其建模為：提供者(providers)、用戶(users)和調(diào)度器(scheduler)。

圖1 云計(jì)算資源調(diào)度框架Fig.1 Cloud computing resource scheduling framework

1.1 云計(jì)算資源

云計(jì)算提供商負(fù)責(zé)管理和維護(hù)大規(guī)模的計(jì)算、存儲(chǔ)和網(wǎng)絡(luò)資源池以提供云服務(wù)。云計(jì)算提供商提供了3種不同類別的服務(wù)：IaaS、PaaS和容器即服務(wù)(CaaS)，其中IaaS提供商以虛擬機(jī)實(shí)例的形式提供基礎(chǔ)設(shè)施資源(計(jì)算、網(wǎng)絡(luò)和存儲(chǔ)資源)，而PaaS和CaaS提供商提供完全管理的計(jì)算環(huán)境，用戶可以在這些環(huán)境中運(yùn)行應(yīng)用程序和/或容器。IaaS提供商通常部署IaaS群集管理系統(tǒng)，如OpenStack和Amazon EC2；PaaS提供商部署分布式計(jì)算平臺(tái)，如Hadoop、Google App Engine和Azure App service來提供服務(wù)；CaaS供應(yīng)商部署容器編排系統(tǒng)，如Kubernetes[3]和Docker Swarm[4]。每個(gè)平臺(tái)都集成了一個(gè)調(diào)度器，負(fù)責(zé)在計(jì)算集群上調(diào)度用戶的任務(wù)(PaaS服務(wù))或應(yīng)用程序的容器(CaaS服務(wù))。如今的數(shù)據(jù)中心由具有不同硬件配置的服務(wù)器組成[5]，以支持各種不同的用戶需求(例如數(shù)據(jù)分析應(yīng)用程序和批處理應(yīng)用程序)。

1.2 云計(jì)算用戶

云用戶是與云計(jì)算提供商保持業(yè)務(wù)關(guān)系的個(gè)人或組織。云用戶分為兩類：終端用戶和第三方云用戶。第三方用戶也可能是云提供商(PaaS、CaaS或SaaS提供商)，它們從IaaS提供商租賃計(jì)算資源以提供PaaS和CaaS服務(wù)。終端用戶通過提交任務(wù)、作業(yè)或容器來產(chǎn)生工作負(fù)載。在當(dāng)前云系統(tǒng)中的工作負(fù)載在許多方面都是高度異構(gòu)，如優(yōu)先級(jí)、大小和需求。設(shè)計(jì)高效調(diào)度器需要深入了解和掌握云平臺(tái)工作負(fù)載的特征和使用模式，然而只有很少的公共資源使用記錄被公布。

到目前為止，谷歌數(shù)據(jù)集[6]是迄今為止發(fā)布的最大的集群使用數(shù)據(jù)集，此外還有阿里巴巴數(shù)據(jù)集[2,7]、微軟Azure數(shù)據(jù)中心數(shù)據(jù)集[8]、Spark數(shù)據(jù)集等[9]，各個(gè)數(shù)據(jù)集的詳細(xì)情況如表1所示。

表1 云資源使用日志數(shù)據(jù)集

上述數(shù)據(jù)集反映了云計(jì)算經(jīng)歷的幾個(gè)不同階段，包括從主機(jī)資源分配、服務(wù)以及容器調(diào)度等。數(shù)據(jù)分析表明：多數(shù)的網(wǎng)絡(luò)空間作業(yè)都是短時(shí)間的作業(yè)，因此導(dǎo)致調(diào)度器需要進(jìn)行高頻率的調(diào)度；虛擬機(jī)的CPU利用率很低，60%的虛擬機(jī)利用率低于20%，同時(shí)80%的虛擬機(jī)是單核或雙核，70%內(nèi)存低于4G。用戶對(duì)于資源需求模式的轉(zhuǎn)變，導(dǎo)致了云計(jì)算供應(yīng)商在構(gòu)建集群時(shí)技術(shù)上的變遷。

1.3 調(diào)度器

調(diào)度器的作用是根據(jù)用戶的需求將調(diào)度單元(如任務(wù)、容器或進(jìn)程)分配給資源單元(如物理機(jī)器、資源容器或插槽)。表2列舉了在不同調(diào)度場景下需要解決的問題。

調(diào)度系統(tǒng)處理來自不同參與者(用戶和提供者)的多種需求，因此云計(jì)算中的調(diào)度通常被描述為一個(gè)多目標(biāo)優(yōu)化問題。提供商主要關(guān)注的是通過有效利用其資源(集群效率)來降低所有運(yùn)營成本，同時(shí)提供滿足用戶QoS要求的可靠服務(wù)，其中調(diào)度器的目標(biāo)一般可概況為三類：公平、效率和性能。

表2 不同場景下調(diào)度系統(tǒng)

1.4調(diào)度約束

在數(shù)據(jù)中心，各種計(jì)算資源的調(diào)度是在一系列的約束條件下進(jìn)行的，如分配約束、位置約束、相互依賴(優(yōu)先)約束和截止日期約束。

分配約束：分配約束包括用戶對(duì)特定計(jì)算資源類型的偏好，如用戶可能會(huì)要求一臺(tái)具有特定內(nèi)核版本、軟件環(huán)境或特殊硬件要求的機(jī)器。

位置約束：用戶可能會(huì)要求節(jié)點(diǎn)位于存儲(chǔ)輸入數(shù)據(jù)的同一機(jī)架上或虛擬機(jī)位于特定地理位置。

依賴約束：一些作業(yè)之間具有相互依賴關(guān)系，如Hadoop作業(yè)由map和reduce任務(wù)組成，reduce任務(wù)大多在map任務(wù)完成后啟動(dòng)；在Spark中，應(yīng)用程序的任務(wù)按照在有向無環(huán)圖(DAG)中相互依賴關(guān)系進(jìn)行。

親和性和反親和性約束：親和性約束要求將屬于同一用戶的任務(wù)或VM實(shí)例放置在同一節(jié)點(diǎn)或機(jī)架上，以減少網(wǎng)絡(luò)流量；反親緣關(guān)系約束要求將任務(wù)(或VM實(shí)例)放置在不同的節(jié)點(diǎn)或機(jī)架上，以避免干擾。

當(dāng)然，在某些文獻(xiàn)中，調(diào)度約束標(biāo)準(zhǔn)也可以根據(jù)滿足程度要求分為硬約束和軟約束[10]。

通過上面的分析可以看到，在云計(jì)算調(diào)度過程中，涉及到資源、需求、調(diào)度約束和調(diào)度器四個(gè)要素。本文分析的重點(diǎn)就是調(diào)度器，調(diào)度器設(shè)計(jì)取決于資源構(gòu)成的方式，同時(shí)也取決于其用戶的需求特點(diǎn)。

2 云計(jì)算資源調(diào)度架構(gòu)分類

云集群調(diào)度按照?qǐng)鼍皠澐挚梢苑譃閿?shù)據(jù)密集的分布式系統(tǒng)，按照調(diào)度結(jié)構(gòu)可以分為4類：集中調(diào)度、分層調(diào)度、分布式調(diào)度和混合式調(diào)度。

2.1 集中調(diào)度系統(tǒng)

集中調(diào)度系統(tǒng)被多數(shù)的集群管理系統(tǒng)所采用，典型包括Hadoop YARN[11]、Google Borg[12]、Google Kubernetes[3]、Tetris[13]、Quincy[14]、Firmament[15]和Gemini[16]等。 此外，高性能計(jì)算(High-performance computing,HPC)等IaaS系統(tǒng)也通常采用這種架構(gòu)，如OpenStack Nova[17]。在集中調(diào)度系統(tǒng)中，包括3個(gè)主要的組件。

節(jié)點(diǎn)管理：部署在每個(gè)節(jié)點(diǎn)上匯報(bào)節(jié)點(diǎn)狀態(tài)并管理執(zhí)行的任務(wù)。

作業(yè)管理：對(duì)作業(yè)進(jìn)行調(diào)度和生命周期管理。

集群資源管理：接受作業(yè)管理的服務(wù)請(qǐng)求，根據(jù)更新和集群全局視圖在集群間分配資源。

該類分為兩個(gè)具體類型：基于隊(duì)列的調(diào)度和基于流的調(diào)度?；陉?duì)列的調(diào)度為不同用戶建立任務(wù)隊(duì)列，然后基于全局的公平性、容量、延時(shí)等策略完成分配，如Borg[12]和Kubernetes[3]等采用的單隊(duì)列模型；基于流的調(diào)度通過求解最小開銷的問題來進(jìn)行調(diào)度，如Quincy[14]、Firmament[15]等，此類算法的缺點(diǎn)是對(duì)于異構(gòu)作業(yè)缺乏擴(kuò)展性和適應(yīng)性。

2.2 分層調(diào)度

分層調(diào)度框架是為了適應(yīng)在共享資源上部署多個(gè)計(jì)算框架的場景而設(shè)計(jì)的，此類模型分為兩層供給者模型和全控制系統(tǒng)。前者將資源調(diào)度和作業(yè)分配去耦合，通過周期性收集空閑資源來進(jìn)行作業(yè)分配，如Apache Mesos[18]通過一個(gè)集中資源控制器為每個(gè)計(jì)算框架提供資源，計(jì)算框架根據(jù)優(yōu)先度和公平性接受或拒絕作業(yè)請(qǐng)求。這種靜態(tài)資源分配導(dǎo)致集群利用率低下，此外，兩層設(shè)計(jì)會(huì)導(dǎo)致相對(duì)較大的調(diào)度延遲。

全控制系統(tǒng)引入資源管理器去管理所有的資源和應(yīng)用程序，而后使用調(diào)度系統(tǒng)調(diào)度單個(gè)任務(wù)并與資源管理器進(jìn)行通信。如Mira[19]在每個(gè)集群的管理單元和計(jì)算框架的基礎(chǔ)上，引入一個(gè)執(zhí)行環(huán)境接口來提高各個(gè)計(jì)算框架和中心調(diào)度服務(wù)器的交換效率。此類算法的優(yōu)點(diǎn)在于與完全集中的系統(tǒng)相比，能夠以可擴(kuò)展的方式在多個(gè)計(jì)算框架之間復(fù)用共享計(jì)算集群。

2.3 分布式調(diào)度系統(tǒng)

分布式調(diào)度系統(tǒng)由運(yùn)行在各個(gè)節(jié)點(diǎn)上的獨(dú)立調(diào)度單元構(gòu)成，而沒有中心化的調(diào)度管理器。這類調(diào)度系統(tǒng)，可以分為兩大類：狀態(tài)共享系統(tǒng)和完全獨(dú)立分布式系統(tǒng)。如微軟Apollo[20]、谷歌的Omega[21]、Tarcil[22]都是典型的狀態(tài)共享分布式系統(tǒng)。共享狀態(tài)分布式系統(tǒng)不能在毫秒級(jí)進(jìn)行任務(wù)分配，因而無法滿足時(shí)延敏感性應(yīng)用。完全分布式系統(tǒng)則不存在上述問題，每個(gè)調(diào)度器根據(jù)集群內(nèi)部的資源情況獨(dú)立地進(jìn)行調(diào)度，如Sparrow[23]。這類系統(tǒng)存在以下幾個(gè)缺點(diǎn)：① 無法實(shí)現(xiàn)全局目標(biāo)，如保證資源分配的公平性等；② 分布式系統(tǒng)只能滿足簡單的分配要求而無法滿足復(fù)雜要求；③ 由于缺乏各個(gè)調(diào)度器之間的協(xié)調(diào)，在高負(fù)載情況下，會(huì)影響執(zhí)行效率。

2.4 混合式調(diào)度系統(tǒng)

混合式調(diào)度系統(tǒng)由集中調(diào)度系統(tǒng)和分布式調(diào)度系統(tǒng)構(gòu)成，將其分為三類：完全混合、共享狀態(tài)混合和雙調(diào)度器混合調(diào)度系統(tǒng)。完全混合調(diào)度系統(tǒng)由一(各)個(gè)中心資源管理器和一組分布式調(diào)度器構(gòu)成，調(diào)度系統(tǒng)運(yùn)行在一個(gè)長期運(yùn)行和具有高優(yōu)先權(quán)的集群中，每種不同類型的任務(wù)運(yùn)行在不同類型的集群上，如Hawk[24]、Mercury[25]。這種調(diào)度方式可以同時(shí)兼?zhèn)浼姓{(diào)度和分布式調(diào)度的優(yōu)點(diǎn)，但同時(shí)也存在以下不足：① 無法確定任務(wù)類型的劃分標(biāo)準(zhǔn)，例如是按照運(yùn)行的時(shí)長或其他因素；② 由于云計(jì)算中多數(shù)作業(yè)都十分短暫，隨機(jī)進(jìn)行任務(wù)調(diào)度會(huì)降低系統(tǒng)的運(yùn)行效率。共享混合式調(diào)度系統(tǒng)允許各個(gè)調(diào)度節(jié)點(diǎn)部分使用中心調(diào)度器共享的狀態(tài)信息來進(jìn)行作業(yè)分配，如Eagle[26]、Ray[27]、Phoenix[28]，其中Phoenix構(gòu)建了一個(gè)向量來表示各個(gè)節(jié)點(diǎn)間的時(shí)延。雙調(diào)度器則是通過構(gòu)建兩個(gè)不同的調(diào)度器：一個(gè)中心調(diào)度器來處理長作業(yè)，另一個(gè)分布式調(diào)度器則處理其他作業(yè)，如MEDEA[29]。

集群調(diào)度架構(gòu)的演化受到作業(yè)異構(gòu)性和擴(kuò)展性兩個(gè)因素的影響，從發(fā)展的過程看，集群資源的調(diào)度正在由集中調(diào)度向混合和分布式調(diào)度演化。然而，集中調(diào)度在實(shí)際中仍有大量應(yīng)用，可以實(shí)現(xiàn)集群內(nèi)部的調(diào)度，同時(shí)也可實(shí)現(xiàn)復(fù)雜的調(diào)度限制。

表3總結(jié)了常見的云資源調(diào)度系統(tǒng)的結(jié)構(gòu)和目標(biāo)。

表3 云計(jì)算系統(tǒng)調(diào)度框架對(duì)比

3 資源分配中的智能算法

在云計(jì)算資源調(diào)度過程中，不僅要確定調(diào)度框架，還要設(shè)計(jì)調(diào)度算法?？砂凑照{(diào)度的目標(biāo)，如公平性、效率、性能等進(jìn)行分類；按照方法的原理可以分為基于優(yōu)先級(jí)、隨機(jī)、優(yōu)化和博弈論的方法。本文主要研究的是基于人工智能的算法，包括遺傳算法、蟻群算法、魚群算法、模擬退火算法、人工免疫系統(tǒng)以及模糊調(diào)度算法等。按照其基本原理將其分為兩大類，基于群體智能的調(diào)度算法和非群體智能的調(diào)度算法。

3.1 基于群體智能的調(diào)度算法

3.1.1 基因遺傳算法

基因遺傳算法是一種基于達(dá)爾文進(jìn)化論隨機(jī)搜索算法[30-31]，通過使用當(dāng)前和歷史數(shù)據(jù)來預(yù)測未來，從而進(jìn)行虛擬機(jī)的調(diào)度。基于達(dá)爾文“適者生存”的理論，根據(jù)資源與調(diào)度任務(wù)的適應(yīng)度函數(shù)來進(jìn)行資源分配。使用評(píng)估技術(shù)的方法具有很好的擴(kuò)展性，能夠獲得最佳的負(fù)載均衡以避免在不同虛擬機(jī)間的遷移從而獲得更高的使用效率。算法以作業(yè)消耗時(shí)間和能量消耗作為兩個(gè)優(yōu)化目標(biāo)。該算法具有良好的并行特征，每個(gè)虛擬機(jī)自動(dòng)決定搜素方向，因此虛擬機(jī)數(shù)目的增加不會(huì)影響響應(yīng)時(shí)間。

3.1.2 蟻群算法

蟻群算法(ACO)是一種元啟發(fā)式、基于種群的[32]隨機(jī)和仿生算法，模仿螞蟻的行為來解決組合問題。螞蟻使用一種名為信息素的化學(xué)物質(zhì)與其他螞蟻進(jìn)行隱性交流。當(dāng)螞蟻探索并找到食物等目標(biāo)時(shí)，它會(huì)沿著返回蟻群的路線分泌信息素；其他螞蟻將跟隨信息素沿著路徑行進(jìn)，如果它們找到食物，也會(huì)分泌信息素。然而，隨著時(shí)間的推移，信息素逐漸蒸發(fā)?；谙伻核惴?，優(yōu)化問題可以轉(zhuǎn)化為在加權(quán)圖上尋找最佳路徑的問題[33]，螞蟻通過在圖上移動(dòng)來逐步構(gòu)建解決方案。ACO可用于調(diào)度，通常側(cè)重于減少物理機(jī)器的數(shù)量。它能獲得較好的全局最優(yōu)解，具有較強(qiáng)的魯棒性和并行算法。它的缺點(diǎn)是開銷大，容易陷入局部最優(yōu)。

3.1.3 粒子群優(yōu)化算法

粒子群優(yōu)化[34]是一種高度先進(jìn)的啟發(fā)式仿生智能優(yōu)化算法，它模仿了基于群體智能的動(dòng)物群行為。它是一種基于粒子群優(yōu)化算法(PSO)的自適應(yīng)搜索算法，通過個(gè)體間的協(xié)作，可以記錄個(gè)人最佳信息和全局最佳信息。在一個(gè)空間中初始化一組隨機(jī)粒子，粒子位置代表可能的解，每個(gè)粒子以一定的速度前進(jìn)，粒子群經(jīng)過反復(fù)的前進(jìn)(也稱為迭代)逐漸接近最優(yōu)位置，從而得到最優(yōu)解。在每次迭代中[31]，粒子根據(jù)兩個(gè)極值進(jìn)行自我更新：一個(gè)是單個(gè)粒子的最優(yōu)解，即單個(gè)極值；另一個(gè)是全局極值，即采用整體粒子群算法尋找最優(yōu)解。粒子群中的每個(gè)粒子都代表待優(yōu)化問題的可能解決方案，其目標(biāo)是通過建模和預(yù)測昆蟲的社會(huì)行為來解決這個(gè)問題。它不是使用隨機(jī)方法，而是為更多的虛擬機(jī)服務(wù)。它提供了最佳的負(fù)載平衡，并減少了吞吐量和響應(yīng)時(shí)間。PSO算法容易陷入局部最優(yōu)，它的計(jì)算時(shí)間比其他現(xiàn)有的超啟發(fā)式算法短，其最終解對(duì)大型復(fù)雜優(yōu)化問題的精度相對(duì)較差[35]。PSO算法對(duì)求解不同約束條件下的組合優(yōu)化問題不具有魯棒性，具有并行分布、可擴(kuò)展性強(qiáng)、易于實(shí)現(xiàn)、魯棒性強(qiáng)、在動(dòng)態(tài)環(huán)境中具有很高的靈活性等優(yōu)點(diǎn)，成功地解決了許多組合優(yōu)化問題。

3.1.4 細(xì)菌覓食優(yōu)化算法

細(xì)菌覓食優(yōu)化算法是一種基于種群[36]搜索的全局優(yōu)化算法，是分布式計(jì)算中一種高效的全局搜索方法。細(xì)菌覓食算法是一種模仿大腸桿菌覓食行為的自然優(yōu)化技術(shù)，這是一個(gè)多目標(biāo)優(yōu)化問題，它為需要同時(shí)滿足多個(gè)條件的多目標(biāo)問題提供了優(yōu)化的解決方案，這種方法可用于定位、處理和攝入食物。在覓食過程中，細(xì)菌可以表現(xiàn)出兩種不同的行為：翻滾或游泳。翻滾動(dòng)作會(huì)改變細(xì)菌的方向[37]。而在游泳過程中，一旦游出意味著趨化性的一步，細(xì)菌將向其當(dāng)前的方向移動(dòng)。這是基于選擇過程中試圖保護(hù)那些有能力成功覓食的動(dòng)物，并試圖排除那些覓食較差的動(dòng)物的性質(zhì)。因?yàn)榍罢咴诜敝尺^程中有更大的成功能力，它具有資源利用率最大化和資源使用成本最小的優(yōu)點(diǎn)，同時(shí)最大限度地減少了并行計(jì)算和分布式計(jì)算中重要的調(diào)度標(biāo)準(zhǔn)——流完成時(shí)間。

3.1.5 人工魚群算法

人工魚群算法(AFSA)[38]是一種基于種群的元啟發(fā)式智能優(yōu)化算法，靈感來自魚群行為，用于解決組合問題。AFSA是一種隨機(jī)并行搜索算法，屬于群體智能的范疇。該算法適應(yīng)了一組魚群智能的行為，其中該組全局搜索食物，以到達(dá)營養(yǎng)物質(zhì)濃度較高的區(qū)域。然后，將這種智能行為與其中一種方法相結(jié)合，以獲得組合優(yōu)化問題的最優(yōu)解[39]。在AFSA系統(tǒng)中，每個(gè)人工魚(AF)根據(jù)其當(dāng)前狀態(tài)和環(huán)境狀態(tài)調(diào)整其行為，利用其自身和鄰居遇到的最佳位置。它具有高度的靈活性和容錯(cuò)性，因此它可以用于云中的調(diào)度，這將帶來最好的預(yù)期結(jié)果。該算法對(duì)初值不敏感，收斂速度快，魯棒性強(qiáng)。它在多目標(biāo)優(yōu)化和聚類等問題上得到了越來越多的研究和廣泛的應(yīng)用。

3.1.6 貓群優(yōu)化算法

貓群優(yōu)化算法(CSO)是一種基于貓的社會(huì)行為的智能啟發(fā)式調(diào)度算法，屬于群智能的范疇[40]。該算法基于貓的尋找和追蹤行為，在搜索模式下，貓坐在某個(gè)位置(不移動(dòng))時(shí)感知下一個(gè)最佳移動(dòng)；而在跟蹤模式下，貓通過以一定速度移動(dòng)到下一個(gè)最佳位置來追逐目標(biāo)。貓群優(yōu)化算法適應(yīng)了貓的這種行為，從而解決多目標(biāo)工作流調(diào)度問題。CSO以執(zhí)行時(shí)間、數(shù)據(jù)量和能耗為輸入映射任務(wù)和虛擬機(jī)，然后公平地搜索最佳任務(wù)資源映射，并提供最佳適應(yīng)值，所獲得的解決方案優(yōu)化了總體能耗。它還提供了一個(gè)優(yōu)化的任務(wù)到資源調(diào)度，使調(diào)度成本最小化，從而減少迭代次數(shù)，該算法是對(duì)PSO的改進(jìn)。

3.1.7 螢火蟲算法

螢火蟲算法(FA)是一種基于群體的智能元啟發(fā)式算法，靈感來自螢火蟲的閃光行為。螢火蟲方法是基于群體智能動(dòng)態(tài)地創(chuàng)建一個(gè)最優(yōu)計(jì)劃，調(diào)查螢火蟲的旅行行為，尋找最接近的可能的最大選擇。螢火蟲身上閃爍的光是它們的吸引力，主要用來吸引配偶和保護(hù)自己免受其他捕食者的攻擊。在FA中，螢火蟲被視為簡單的代理，在搜索空間中移動(dòng)和交互，并記錄它們訪問過的最佳解決方案。因此，可以使用FA生成替代設(shè)計(jì)選項(xiàng)，以便有效支持云計(jì)算上的智能任務(wù)調(diào)度，將接收到的作業(yè)動(dòng)態(tài)映射到可用資源，以便在最小完工時(shí)間內(nèi)完成作業(yè)的執(zhí)行，并均勻分配負(fù)載。該算法可以用來解決多目標(biāo)問題[41-42]。

3.1.8 人工蜂群算法

人工蜂群算法(ABC)是一種基于蜜蜂智能行為的群體優(yōu)化元啟發(fā)式算法，有兩種常見類型；覓食行為和繁殖(交配)行為。ABC算法基于蜜蜂群的巧妙覓食行為。一個(gè)典型的蜂巢可能包括5 000～20 000只蜜蜂。隨著時(shí)間的推移，蜜蜂在其蜂群中具有不同的功能?；钴S的覓食蜜蜂去尋找食物來源，收集食物，然后返回蜂巢。偵察蜜蜂檢查蜂巢周圍的區(qū)域，尋找豐富的新食物來源。由于其隨機(jī)性，在任何時(shí)候，一些覓食的蜜蜂都可能放棄食物源，變得不活躍。該策略可以應(yīng)用于任務(wù)調(diào)度領(lǐng)域，即覓食行為。將蜜蜂的覓食行為映射到任務(wù)調(diào)度問題，通?？梢赃@樣定義：雇傭的蜜蜂與分配資源上的任務(wù)相關(guān)，并共享它們關(guān)于食物來源的信息。它通過解決方案空間最小化搜索的完成時(shí)間，并使搜索多樣化。這些特點(diǎn)使得人工蜂群技術(shù)能夠有效地應(yīng)用于云任務(wù)調(diào)度領(lǐng)域[43-44]。

3.1.9 布谷鳥搜索算法

布谷鳥搜索算法是一種模擬布谷鳥物種自然行為的元啟發(fā)式算法。布谷鳥的繁殖遵循以下規(guī)則：一次產(chǎn)一個(gè)蛋，然后將蛋傾倒在隨機(jī)選擇的巢中;下一步，質(zhì)量更好的蛋將被帶到下一代的巢中。假設(shè)有固定數(shù)量的寄主巢,該策略可用于云中的調(diào)度，其中雞蛋代表解決方案，算法通過采用更好的解決方案替換較弱的解決方案來工作。該算法給出了最優(yōu)解，并通過切換參數(shù)有效地平衡了局部搜索和全局搜索，所得結(jié)果優(yōu)于粒子群優(yōu)化算法[44-45]。

3.2 非群體智能的調(diào)度算法

在調(diào)度器所采用的調(diào)度算法中，除了采用群體智能算法外，還使用其他大量的人工智能調(diào)度算法，下面對(duì)一些常用的算法進(jìn)行論述。

3.2.1 模擬退火

模擬退火(SA)的靈感來源于固體中的退火，在固體中，例如金屬或玻璃中的退火意味著加熱并使其緩慢冷卻，以消除內(nèi)應(yīng)力并使其增韌[31]。它是一種啟發(fā)式方法，已用于獲得各種離散問題的優(yōu)化解。該算法起源于統(tǒng)計(jì)機(jī)制，其基本思想是將箱子中成本最高的物品與成本最低的隨機(jī)物品交換。在這種方法中，隨機(jī)請(qǐng)求被分配到一個(gè)bin中，直到當(dāng)前bin中的一個(gè)參數(shù)被完全填充。它基于軟約束和硬約束兩個(gè)約束條件，在軟約束中，允許用更好的解決方案替換現(xiàn)有解決方案；在硬約束中，資源的容量不應(yīng)超過容器的大小。通過不斷的迭代交換，解決方案逐漸達(dá)到穩(wěn)定狀態(tài)。該方法是一種高度靈活的局部搜索方法，可以成功地應(yīng)用于大多數(shù)實(shí)際問題。SA算法[35]需要相對(duì)較長的時(shí)間才能找到全局最優(yōu)值，文中已經(jīng)證明，通過優(yōu)化指定溫度的冷卻速率，SA算法可以收斂到全局最優(yōu)值。該算法首先生成初始解，然后初始化溫度參數(shù)，因?yàn)檫@純粹是一個(gè)假設(shè)，所以是其主要缺點(diǎn)。該算法通常會(huì)陷入局部極大值，夾帶不需要的分配，并且該算法還取決于請(qǐng)求可用性和bin容量。當(dāng)物體溫度越高時(shí)，降溫的概率越大，因此這種方法適用于高溫。

3.2.2 禁忌搜索

禁忌搜索是一種“高級(jí)”元啟發(fā)式方法，用于解決基于移動(dòng)概念的優(yōu)化問題[31]。禁忌搜索算法是一種模擬人類智能的全局優(yōu)化算法，具有較好的局部優(yōu)化能力。它旨在指導(dǎo)其他方法擺脫局部最優(yōu)的陷阱，并已應(yīng)用于解決資源分配和其他優(yōu)化問題。其總體方法是通過禁止或懲罰在下一次迭代中采取解決方案的行動(dòng)，避免在循環(huán)中陷入困境，指向以前訪問過的解決方案空間中的點(diǎn)。在基于禁忌搜索的啟發(fā)式算法中，使用最佳擬合啟發(fā)式算法得到的解作為初始解，并采用隨機(jī)移動(dòng)來尋找鄰居。該啟發(fā)式方法的終止條件是所需要的移動(dòng)時(shí)間，一般來說，要求移動(dòng)時(shí)間應(yīng)該是解決方案池中候選方案數(shù)量的兩倍，以增加通過隨機(jī)移動(dòng)訪問每個(gè)候選方案的概率。禁忌搜索使用最近度(短期記憶)和頻率(長期記憶)，通過禁止搜索停留在局部最優(yōu)的區(qū)域，并強(qiáng)制探索尚未遇到的其他區(qū)域，從而高效地搜索解決方案空間。與其他傳統(tǒng)方法相比，它可以在更短的時(shí)間內(nèi)找到問題的最優(yōu)解。

3.2.3 模糊調(diào)度

模糊調(diào)度引入了模糊算法來對(duì)云計(jì)算資源進(jìn)行調(diào)度，F(xiàn)ahmy[46]解釋了在實(shí)時(shí)系統(tǒng)中如何使用模糊算法調(diào)度非周期性作業(yè)。該算法假定有一臺(tái)負(fù)載很重的機(jī)器，其單處理器由多個(gè)用戶分配，計(jì)劃使用模糊邏輯算法來檢查首先要執(zhí)行的任務(wù)的優(yōu)先級(jí)。模糊邏輯算法用于適應(yīng)等待中的其他工作的優(yōu)先級(jí)，以防出現(xiàn)新的工作，并為這些工作設(shè)定最后期限。該模糊邏輯負(fù)載調(diào)度算法被用于多目標(biāo)算法中，以減少平均延遲、過期作業(yè)數(shù)和作業(yè)的吞吐量時(shí)間，提高用戶滿意度。另一方面，虛擬化是有爭議的，主要是因?yàn)樵诰哂心：A(yù)測的虛擬化數(shù)據(jù)中心中，資源管理和任務(wù)調(diào)度優(yōu)于有能力的動(dòng)態(tài)任務(wù)調(diào)度，正如Kong等人[47]所解釋的那樣。通過使用I型和II型模糊邏輯系統(tǒng)，指定了一種優(yōu)雅的模糊預(yù)測方法來建模虛擬化服務(wù)器節(jié)點(diǎn)的不確定負(fù)載和模糊可訪問性。其引入并評(píng)估了一種在線動(dòng)態(tài)任務(wù)調(diào)度算法SALAF。此外，他們還基于Abda等人[48]的模糊方法，將機(jī)器人柔性裝配單元集成到系統(tǒng)中，以開發(fā)一個(gè)適合調(diào)度的規(guī)則。他們采用了模糊排序規(guī)則(FSR)，該規(guī)則是通過使用模糊邏輯(FL)技術(shù)，將不同的輸入變量組合起來建立的：加工時(shí)間、交貨日期、批量大小和必要的裝配站數(shù)量。Suer等人[49]提出了模糊遺傳調(diào)度中多個(gè)調(diào)度器配置文件之間的反饋評(píng)估，該文詳細(xì)研究了模糊遺傳調(diào)度中多調(diào)度程序配置文件的早期方法。一個(gè)新的軟件應(yīng)用程序通過將另一個(gè)調(diào)度器群體中最好的染色體植入一個(gè)調(diào)度器群體，從而促進(jìn)調(diào)度器之間的反饋。多個(gè)調(diào)度器被安排在各自的模糊隸屬度范圍內(nèi)，這影響了單機(jī)調(diào)度多目標(biāo)問題的評(píng)估。

Mehranzadeh和Hashemi[50]利用模糊邏輯進(jìn)行任務(wù)調(diào)度，提供并評(píng)估了一種新的調(diào)度算法，該算法能夠在數(shù)據(jù)中心調(diào)度虛擬機(jī)。通過與第一次擬合(FCFS)和循環(huán)調(diào)度(RR)兩種調(diào)度技術(shù)的對(duì)比，仿真結(jié)果表明，該調(diào)度算法在云端是成功的。但該算法在調(diào)度多個(gè)任務(wù)時(shí)會(huì)影響外部優(yōu)先級(jí)，而規(guī)則生成在模糊邏輯中是一項(xiàng)非常困難的任務(wù)，因此會(huì)導(dǎo)致計(jì)算時(shí)間增加。此外，Priya和Babu[51]解釋了虛擬化云數(shù)據(jù)服務(wù)的移動(dòng)平均模糊資源調(diào)度，針對(duì)用戶云需求和云用戶資源之間的系統(tǒng)可訪問性，設(shè)計(jì)了模糊控制理論。

3.2.4 無監(jiān)督學(xué)習(xí)資源分配算法

無監(jiān)督學(xué)習(xí)資源分配方法將無監(jiān)督機(jī)器學(xué)習(xí)方法引入到資源分配評(píng)估階段，通過識(shí)別少量的工作負(fù)載，作出資源分配的最優(yōu)評(píng)估，而后進(jìn)行資源的調(diào)度分配。在DejaVu[52]中，每個(gè)服務(wù)都有一個(gè)代理，負(fù)責(zé)將用戶的請(qǐng)求轉(zhuǎn)發(fā)到探查器。探查器計(jì)算每個(gè)工作負(fù)載的特征碼，這些特征碼由低級(jí)指標(biāo)組成，以提供非侵入性和低開銷的監(jiān)控。這些簽名用于使用K-means對(duì)工作負(fù)載進(jìn)行聚類，通過線性搜索計(jì)算每個(gè)集群所需的資源。為工作負(fù)載計(jì)算所需資源后，調(diào)諧器將該工作負(fù)載映射到虛擬化資源。當(dāng)DejaVu檢測到工作負(fù)載的變化時(shí)，它將基于其VM Id和簽名數(shù)據(jù)使用C4.5決策樹對(duì)工作負(fù)載進(jìn)行分類。當(dāng)分類確定性級(jí)別較低時(shí)，DejaVu將工作負(fù)載設(shè)置為其全容量配置，并再次進(jìn)行集群和調(diào)諧。它們通過比較分析器中的工作負(fù)載性能和生產(chǎn)環(huán)境來計(jì)算性能干擾，并通過向相應(yīng)的服務(wù)提供更多資源來解決這個(gè)問題。為了進(jìn)行評(píng)估，通過重放MSN messenger和Hotmail跟蹤進(jìn)行了測試。DejaVu在減少總體資源管理工作和開銷方面產(chǎn)生了積極的影響。

4 未來研究方向

通過上述分析可知云計(jì)算資源正在向異構(gòu)多元的方向發(fā)展，而用戶需求也變得更加多樣化和暫態(tài)化，因此未來構(gòu)建云計(jì)算智能調(diào)度器需要從以下幾個(gè)方面開展研究：

① 需要根據(jù)用戶需求建立全方位的狀態(tài)感知能力，以實(shí)現(xiàn)針對(duì)性的調(diào)度。伴隨著用戶對(duì)云計(jì)算資源需求的更加多樣化以及更新頻率高等問題，實(shí)現(xiàn)云計(jì)算資源池狀態(tài)的快速收集，并對(duì)資源實(shí)現(xiàn)從虛擬機(jī)、容器、作業(yè)環(huán)境的全面的狀態(tài)收集和匹配，包括資源類型、CPU、內(nèi)存、GPU、硬盤讀寫速度、網(wǎng)絡(luò)速度、軟件環(huán)境、地理位置、機(jī)架位置等，從而使用戶滿足需求。

② 基于預(yù)測的資源分配，從而實(shí)現(xiàn)資源最大粒度分配，發(fā)揮云計(jì)算資源的價(jià)值。研究表明在云計(jì)算中心存在大量的資源過度分配或者資源分配不夠充分等問題。因此，準(zhǔn)確預(yù)測工作需求和資源消耗有助于資源分配，提高集群利用率，而機(jī)器學(xué)習(xí)模型在這一研究方向上將發(fā)揮核心作用。

③ 如何實(shí)現(xiàn)用戶和云提供商多目標(biāo)之間平衡。集群調(diào)度問題本質(zhì)上是一個(gè)多目標(biāo)問題，在資源分配中還存在著分配沖突，此外又涉及到各個(gè)方面之間利益的博弈，因而需要引入博弈論等新的理論和方法實(shí)現(xiàn)資源分配中各個(gè)目標(biāo)的平衡，如公平/效率交易、公平/性能交易和效率/性能交易。

④ 研究在線負(fù)載作業(yè)快速調(diào)度的方法，實(shí)現(xiàn)快速資源分配。目前大多數(shù)調(diào)度系統(tǒng)都以離線方式使用調(diào)度啟發(fā)式，然而在實(shí)際生產(chǎn)系統(tǒng)中，離線資源分配并不實(shí)用。在新型的智能調(diào)度器中，機(jī)器學(xué)習(xí)技術(shù)可以用于動(dòng)態(tài)和自適應(yīng)調(diào)度，應(yīng)該能夠不斷更新自己的調(diào)度模型，以適應(yīng)工作負(fù)載的變化。此外，在調(diào)度過程還存在有向無環(huán)圖(DAG)等負(fù)載作業(yè)，各個(gè)作業(yè)間存在著負(fù)載的依賴關(guān)系，必須研究這種復(fù)雜調(diào)度關(guān)系的資源分配。

5 結(jié)束語

本文首先系統(tǒng)分析云計(jì)算中資源調(diào)度的框架并分析了資源調(diào)度從長期工作到亞秒級(jí)工作的變遷，同時(shí)不同類型和規(guī)模的需求對(duì)計(jì)算資源要求差異巨大，然后系統(tǒng)論述了云計(jì)算資源調(diào)度的集中模式、層次結(jié)構(gòu)、分布式以及混合結(jié)構(gòu)所適應(yīng)的場景和優(yōu)缺點(diǎn)；之后，系統(tǒng)地分析了云計(jì)算資源調(diào)度中所采用的各種智能算法，并將其分為群體智能算法和非群體智能算法，最后對(duì)各類算法進(jìn)行了系統(tǒng)的總結(jié)梳理，指出了未來智能調(diào)度器能夠快速獲得資源狀態(tài)情況，更多地借助于人工智能技術(shù)考慮用戶多樣化需求和動(dòng)態(tài)變化，并解決調(diào)度中沖突性問題，從而實(shí)現(xiàn)資源的高效實(shí)時(shí)性調(diào)度。