基于機器學習的云計算資源調度綜述

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

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

0 引言

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

在云計算集群中通過優化資源調度可以提高服務質量，從而確保用戶服務水平。據統計，亞馬遜如果響應時延增加100 ms則會導致1%的收入損失，谷歌的響應時延增加0.5 s則會損失20%的用戶流量[1]。云計算的資源調度按照目標的不同可以分為不同的類型：如按照調度的目標，可以分為降低能耗的調度算法、完成目標的調度算法、面向負載均衡的調度算法等；如按照調度的對象劃分來看，包括面向CPU、網絡、存儲等基礎資源的調度算法，面向Docker、面向服務的調度算法等；如按照調度策略來說，可以分為資源分配負載均衡和動態調度策略等。

本文對近十年來關于云計算資源調度文獻進行了廣泛的調研，研究了云計算資源調度算法的演進策略，文中對云計算資源調度的框架和各類調度算法進行了詳細論述分析，并指出未來研究方向。

1 云計算調度概述

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

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

圖1 云計算資源調度框架Fig.1 Cloud computing resource scheduling framework

1.1 云計算資源

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

1.2 云計算用戶

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

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

表1 云資源使用日志數據集

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

1.3 調度器

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

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

表2 不同場景下調度系統

1.4調度約束

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

分配約束：分配約束包括用戶對特定計算資源類型的偏好，如用戶可能會要求一臺具有特定內核版本、軟件環境或特殊硬件要求的機器。

位置約束：用戶可能會要求節點位于存儲輸入數據的同一機架上或虛擬機位于特定地理位置。

依賴約束：一些作業之間具有相互依賴關系，如Hadoop作業由map和reduce任務組成，reduce任務大多在map任務完成后啟動；在Spark中，應用程序的任務按照在有向無環圖(DAG)中相互依賴關系進行。

親和性和反親和性約束：親和性約束要求將屬于同一用戶的任務或VM實例放置在同一節點或機架上，以減少網絡流量；反親緣關系約束要求將任務(或VM實例)放置在不同的節點或機架上，以避免干擾。

當然，在某些文獻中，調度約束標準也可以根據滿足程度要求分為硬約束和軟約束[10]。

通過上面的分析可以看到，在云計算調度過程中，涉及到資源、需求、調度約束和調度器四個要素。本文分析的重點就是調度器，調度器設計取決于資源構成的方式，同時也取決于其用戶的需求特點。

2 云計算資源調度架構分類

云集群調度按照場景劃分可以分為數據密集的分布式系統，按照調度結構可以分為4類：集中調度、分層調度、分布式調度和混合式調度。

2.1 集中調度系統

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

節點管理：部署在每個節點上匯報節點狀態并管理執行的任務。

作業管理：對作業進行調度和生命周期管理。

集群資源管理：接受作業管理的服務請求，根據更新和集群全局視圖在集群間分配資源。

該類分為兩個具體類型：基于隊列的調度和基于流的調度。基于隊列的調度為不同用戶建立任務隊列，然后基于全局的公平性、容量、延時等策略完成分配，如Borg[12]和Kubernetes[3]等采用的單隊列模型；基于流的調度通過求解最小開銷的問題來進行調度，如Quincy[14]、Firmament[15]等，此類算法的缺點是對于異構作業缺乏擴展性和適應性。

2.2 分層調度

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

全控制系統引入資源管理器去管理所有的資源和應用程序，而后使用調度系統調度單個任務并與資源管理器進行通信。如Mira[19]在每個集群的管理單元和計算框架的基礎上，引入一個執行環境接口來提高各個計算框架和中心調度服務器的交換效率。此類算法的優點在于與完全集中的系統相比，能夠以可擴展的方式在多個計算框架之間復用共享計算集群。

2.3 分布式調度系統

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

2.4 混合式調度系統

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

集群調度架構的演化受到作業異構性和擴展性兩個因素的影響，從發展的過程看，集群資源的調度正在由集中調度向混合和分布式調度演化。然而，集中調度在實際中仍有大量應用，可以實現集群內部的調度，同時也可實現復雜的調度限制。

表3總結了常見的云資源調度系統的結構和目標。

表3 云計算系統調度框架對比

3 資源分配中的智能算法

在云計算資源調度過程中，不僅要確定調度框架，還要設計調度算法。可按照調度的目標，如公平性、效率、性能等進行分類；按照方法的原理可以分為基于優先級、隨機、優化和博弈論的方法。本文主要研究的是基于人工智能的算法，包括遺傳算法、蟻群算法、魚群算法、模擬退火算法、人工免疫系統以及模糊調度算法等。按照其基本原理將其分為兩大類，基于群體智能的調度算法和非群體智能的調度算法。

3.1 基于群體智能的調度算法

3.1.1 基因遺傳算法

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

3.1.2 蟻群算法

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

3.1.3 粒子群優化算法

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

3.1.4 細菌覓食優化算法

細菌覓食優化算法是一種基于種群[36]搜索的全局優化算法，是分布式計算中一種高效的全局搜索方法。細菌覓食算法是一種模仿大腸桿菌覓食行為的自然優化技術，這是一個多目標優化問題，它為需要同時滿足多個條件的多目標問題提供了優化的解決方案，這種方法可用于定位、處理和攝入食物。在覓食過程中，細菌可以表現出兩種不同的行為：翻滾或游泳。翻滾動作會改變細菌的方向[37]。而在游泳過程中，一旦游出意味著趨化性的一步，細菌將向其當前的方向移動。這是基于選擇過程中試圖保護那些有能力成功覓食的動物，并試圖排除那些覓食較差的動物的性質。因為前者在繁殖過程中有更大的成功能力，它具有資源利用率最大化和資源使用成本最小的優點，同時最大限度地減少了并行計算和分布式計算中重要的調度標準——流完成時間。

3.1.5 人工魚群算法

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

3.1.6 貓群優化算法

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

3.1.7 螢火蟲算法

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

3.1.8 人工蜂群算法

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

3.1.9 布谷鳥搜索算法

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

3.2 非群體智能的調度算法

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

3.2.1 模擬退火

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

3.2.2 禁忌搜索

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

3.2.3 模糊調度

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

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

3.2.4 無監督學習資源分配算法

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

4 未來研究方向

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

① 需要根據用戶需求建立全方位的狀態感知能力，以實現針對性的調度。伴隨著用戶對云計算資源需求的更加多樣化以及更新頻率高等問題，實現云計算資源池狀態的快速收集，并對資源實現從虛擬機、容器、作業環境的全面的狀態收集和匹配，包括資源類型、CPU、內存、GPU、硬盤讀寫速度、網絡速度、軟件環境、地理位置、機架位置等，從而使用戶滿足需求。

② 基于預測的資源分配，從而實現資源最大粒度分配，發揮云計算資源的價值。研究表明在云計算中心存在大量的資源過度分配或者資源分配不夠充分等問題。因此，準確預測工作需求和資源消耗有助于資源分配，提高集群利用率，而機器學習模型在這一研究方向上將發揮核心作用。

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

④ 研究在線負載作業快速調度的方法，實現快速資源分配。目前大多數調度系統都以離線方式使用調度啟發式，然而在實際生產系統中，離線資源分配并不實用。在新型的智能調度器中，機器學習技術可以用于動態和自適應調度，應該能夠不斷更新自己的調度模型，以適應工作負載的變化。此外，在調度過程還存在有向無環圖(DAG)等負載作業，各個作業間存在著負載的依賴關系，必須研究這種復雜調度關系的資源分配。

5 結束語

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