基于多種云環(huán)境的任務調度算法綜述

陳紅華　崔翛龍　王耀杰

摘 要：任務調度算法是云計算資源分配部署的核心方法。針對當前云計算發(fā)展面臨的任務需求和數據量指數級增長的問題，重點對任務調度算法進行了系統(tǒng)的梳理和歸納，以云環(huán)境為分類依據，研究分析了單云、聯(lián)盟云、混合云、多云四類調度算法。在單云環(huán)境中，從傳統(tǒng)啟發(fā)式、元啟發(fā)式以及混合式任務調度算法角度進行闡述。在聯(lián)盟云、混合云、多云環(huán)境中，從工作流和獨立任務調度算法角度進行闡述。通過比較，總結了現(xiàn)有算法的優(yōu)點、缺點以及優(yōu)化性能，并形成結論性意見和開放性問題，為未來對容器云、數據云以及兼顧資源分配與任務調度算法的研究奠定基礎。

關鍵詞：云計算； 任務調度； 單云； 聯(lián)盟云； 混合云； 多云

中圖分類號：TP393 文獻標志碼：A 文章編號：1001-3695（2023）10-002-2889-07

doi：10.19734/j.issn.1001-3695.2023.02.0076

Summary of task scheduling algorithms based on multiple cloud environments

Chen Honghua1a，1b， Cui Xiaolong1a，2， Wang Yaojie3

（1.a.Anti-Terrorism Command Information Engineering Research Team， b.Postgraduate Brigade， Engineering University of PAP， Xian 710086， China; 2.Urumqi Campus of Engineering University of PAP， Urumqi 830000， China; 3.Construction & Development Research Institute of the Armed Police Research Institute， Beijing 100000， China）

Abstract：Task scheduling algorithms are the core method for resource allocation and deployment in cloud computing. To meet the current task demand of cloud computing while the amount of data grows exponentially， the paper focused on systematically sorting and summarizing of task scheduling algorithms. Categorized by cloud environment， it studied and analyzed four types of scheduling algorithms， namely single cloud， federated cloud， hybrid cloud， and multi-cloud. For single cloud environment， the paper elaborated from the perspectives of traditional heuristics， meta heuristics， and hybrid task scheduling algorithms. For federated cloud， hybrid cloud， and multi-cloud environments， the paper elaborate from the perspectives of workflow and independent task scheduling algorithms. Through comparisons， this paper summarized the advantages， disadvantages， and optimization performance of existing algorithms， and formed conclusive opinions and open questions， laying the foundation for future research on container clouds， data clouds， and algorithms that balanced resource allocation and task scheduling.

Key words：cloud computing; task scheduling; single cloud; federated cloud; hybrid cloud; multi-cloud

0 引言

2006年，在Google的搜索引擎會議上，云計算（cloud computing）［1］概念被正式提出。2008年BingoCloudOS產品的發(fā)布成為中國第一個獲得自主知識產權的基礎架構云。我國高度重視云計算領域的發(fā)展，從“十二五”開始就將云計算作為專項計劃，并視為重點產業(yè)進行建設。云計算領域的地位日益突顯，也迎來嶄新的發(fā)展。

發(fā)展至今，云計算在諸多領域有著重要運用和廣泛研究，但仍沒有統(tǒng)一的定義。美國國家標準與技術研究院（NIST）［2］、Google維基百科［3］、中國云計算網［4］都對云計算有各自的定義，其最本質的要素是以共享資源池的方式，通過調度算法，提供各種服務。從理論上來說，云計算可以提供無限的存儲、計算能力和資源，但在現(xiàn)實運用中，由于資源需求激增和調度策略發(fā)展的限制，極易導致資源爭用、服務中斷、缺乏互操作性、QoS降級和SLA違規(guī)等問題［5］。從技術發(fā)展角度來看，從早期分布式系統(tǒng)到網格系統(tǒng)［6］進而云計算技術出現(xiàn)，一定程度解決異構網絡資源共享與利用問題，但不同于集群系統(tǒng)與網格系統(tǒng)單一的調度目標，現(xiàn)有云服務需要充分考慮多種用戶服務質量需求，而且還要維持動態(tài)變化的系統(tǒng)處于負載相對均衡的狀態(tài)，達到既提高資源利用率和最大化經濟效益，又為用戶提供高質量服務的目標（兩個目標呈相互制約關系）。總的來說，云計算發(fā)展難點可以概括如下：a）計算節(jié)點資源處于不斷增減的動態(tài)變化中，包括新計算節(jié)點的擴展以及停止工作的計算節(jié)點的重新工作，從而需要對資源實時監(jiān)控與統(tǒng)計；b）云計算規(guī)模非常大，對計算節(jié)點的監(jiān)測需要占用大量計算資源［7］；c）在大規(guī)模的云計算中，常常發(fā)生節(jié)點失效與程序錯誤的現(xiàn)象，從而需要充分保障任務執(zhí)行的可靠性與算法的魯棒性。

此外，云環(huán)境由單云環(huán)境發(fā)展到多個云的云間環(huán)境，單一的云環(huán)境實現(xiàn)簡單，但單點故障能夠導致嚴重服務危機。2022年12月18日阿里云香港可用區(qū)C某機房設備異常，導致多個網站癱瘓，云服務器ECS、云數據庫PolarDB等云產品無法使用，造成不可估量的損失。多種云間環(huán)境解決了單云環(huán)境容易故障和受到DDoS攻擊問題，但是云種類與數量的增加對任務調度算法提出更大的挑戰(zhàn)［8］。基于上述問題，本文通過收集、整理、對比、分析目前主流云計算調度算法，采取從單云、多云、混合云、聯(lián)盟云等不同云間環(huán)境，對調度算法進行分類闡述。在單云環(huán)境中，根據求解優(yōu)化問題的技術，將任務調度算法分為傳統(tǒng)啟發(fā)式、元啟發(fā)式和混合式；云間環(huán)境的任務調度算法通常從單云調度算法的基礎上優(yōu)化發(fā)展而來，因此根據用戶請求任務的相互關系，分為工作流調度算法和獨立任務調度算法，并從算法策略、算法描述、優(yōu)化目標、算法特征、存在問題等角度進行對比分析，為云計算調度算法未來研究重點提供理論支持。

1 云環(huán)境與任務調度

1.1 任務調度

任務調度旨在滿足用戶服務需求，提高資源的使用效率并且保持均衡的資源負載，降低整個數據中心的能耗，驅動綠色發(fā)展。任務調度策略一般分為資源配置策略［9］和任務調度兩個部分。資源分配從服務提供商角度出發(fā)，按照規(guī)則拆分和配給資源；任務調度是從用戶提交的任務角度出發(fā)，把任務拆分并投放到合適的資源模塊的過程，但是對于任何一個具體場景來說，資源往往是有限的，調度優(yōu)化問題旨在實現(xiàn)任務請求與資源的最佳匹配。由于資源的重新分配與調度往往帶來巨大的系統(tǒng)開銷，所以本文主要從任務調度角度出發(fā)對算法進行分析與討論。任務調度是一個 NP-hard［10］優(yōu)化問題，調度目標函數為基于QoS參數的適應度函數（FFQoS），進行資源合理分配。資源分配與任務調度成正比，資源分配得越合理，任務調度實行的效率越高。而如何實現(xiàn)任務請求與資源的最佳匹配，即選擇最合適的資源對任務處理，是云算法發(fā)展面臨的最大難題。資源調配與調度（RPS）［11］過程如圖1所示。

資源供應與調度（RPS）的目標是最大程度地滿足用戶的QoS需求以及與資源提供商協(xié)定的SLA，進行資源合理分配與均衡負載。具體流程為：首先根據任務實際，確定用戶的需求與目標，結合工作負載情況分析用戶與云服務提供商定義服務級別協(xié)議（SLA）；其次，基于QoS來計算適應度函數［12］（FFQoS）以及不考慮QoS參數的值（FFnonQoS），并進行比較；再次，如果FFQoS

為了讓用戶獲得更好的服務體驗并最大化提供商的利益，在資源有限的情況下設計更好的調度方案，通常通過設置不同的調度目標［13］來描述云服務提供商的服務質量和效果。常見調度目標有完成時間（makespan）、成本、能源消耗量、吞吐量、負載平衡、服務質量（QoS）、資源利用率。而對于云服務提供商提供的服務，用戶通常有不同的約束條件，主要有任務完成截止時間、預算、可靠性和任務執(zhí)行的具體優(yōu)先級以及整個過程的安全性。

1.2 單云與云間環(huán)境

云計算廣泛應用于各個領域，其云環(huán)境也由單云逐漸發(fā)展到云間環(huán)境，單云主要包括彼此沒有關聯(lián)的單一公有云或私有云構成。私有云和公共云在各自領域都有其特定運用，能夠實現(xiàn)有效資源利用，但是隨著日益復雜的云環(huán)境體系以及日益增長的服務需求，需要更具體和更廣泛地共享信息和數據［14］。因此多種云間環(huán)境應運而生，實現(xiàn)了資源之間的跨云使用，降低了對單云的依賴性，提升應對故障的能力。云間環(huán)境包括聯(lián)盟云環(huán)境［15］、混合云環(huán)境［16］和多云環(huán)境［17］。Gartner在《中國混合云運營的三個重要經驗》報告中指出，多云以及混合云的云策略得到了企業(yè)和市場的喜愛，并將逐步成為研究熱點。

云計算有各種類型的調度算法，可按靜態(tài)和動態(tài)、集中和分布式、在線和離線（批處理模式）、搶占式和非搶占式和協(xié)作與非協(xié)作調度等進行分類［18］。靜態(tài)調度算法需要預先獲取有關任務的相關信息，當工作負載不頻繁變化且系統(tǒng)行為變化很小時，靜態(tài)算法的性能更好且易于實現(xiàn)。然而，在云環(huán)境中，資源實時變化，負載不斷波動，因此動態(tài)調度算法是應對波動需求的關鍵技術。當任何節(jié)點發(fā)生增減變化時，算法會對任務進行合理的轉移和再分配。事實上，所有元啟發(fā)式調度方法本質上都是動態(tài)的［19］。這也意味著，動態(tài)算法和元啟發(fā)式算法更適用于目前云計算的復雜環(huán)境。

2 任務調度算法分類

不同的云環(huán)境適用于不同的場合，因此根據云環(huán)境的四種不同類型（單云環(huán)境、聯(lián)盟云環(huán)境、多云環(huán)境和混合云環(huán)境）進行任務調度算法分類。在單云環(huán)境中，根據求解優(yōu)化問題的技術，將任務調度算法分為傳統(tǒng)啟發(fā)式算法、元啟發(fā)式算法和混合式算法。由于云間環(huán)境的任務調度算法通常在單云調度算法的基礎上發(fā)展而來，并結合各自云環(huán)境特點，完成不同目標并滿足各種約束，進行優(yōu)化升級，因此從任務間的依賴關系分類工作流調度算法和獨立任務調度算法。圖2展示了云計算任務調度的分類。

2.1 單云環(huán)境

單云環(huán)境部署簡單，是出現(xiàn)形式最早的云算法環(huán)境，其任務調度算法的發(fā)展也最悠久，有大量的研究。本文主要從傳統(tǒng)啟發(fā)式算法、元啟發(fā)式算法和混合式算法三個類別進行分類比較分析。

2.1.1 傳統(tǒng)啟發(fā)式算法

啟發(fā)式算法是指在一個尋求最優(yōu)解的過程中能夠根據個體或者全局的經驗來解決問題的方法。

min-min算法［20］的基本思想是先將小的任務分配到性能最好的機器上執(zhí)行，實現(xiàn)簡單，但是容易出現(xiàn)饑餓現(xiàn)象與負載不均衡問題。max-min算法改進min-min算法，保證長任務的執(zhí)行，但該算法面臨部分資源過度利用和部分未充分利用，無法改善參數等問題。

HEFT算法［21］基于優(yōu)先級進行任務的分配執(zhí)行，Dubey等人提出了改進的HEFT算法，一定程度上緩解負載壓力，但該算法未能改善各種QoS參數。

先來先服務算法（FCFS）按照用戶的任務請求到達的先后順序執(zhí)行，導致短作業(yè)等待時間長。Mondal等人（2015）提出最短作業(yè)優(yōu)先（SJF）調度算法，但節(jié)點負載不均勻，引發(fā)饑餓現(xiàn)象。因此，Devi等人［22］基于增強加權循環(huán)（WRR）進行資源分配，改善了QoS，但頻繁的任務切換導致額外的開銷。

Sheikhalishahi等人［23］提出了多容量感知資源調度算法，減少等待時間，但未考慮任何QoS限制，算法的性能效低。為克服能效問題，Sheikhalishahi等人［24］提出Bin Packing算法，改進關鍵性能指標。文獻［25］提出了最佳擬合算法（best fit algorithm），使得最快完成任務同時減少資源浪費。傳統(tǒng)啟發(fā)式算法還包括最小完成時間（MET）、機會負載均衡（OLB）［26］ 、最小執(zhí)行時間（MCT）、爬山算法、sufferage算法、主成分分析［27］等。

傳統(tǒng)啟發(fā)式算法存在可行解與最優(yōu)解的偏離，即能夠求得可行解，但是并不一定是最優(yōu)解，并且多數算法依賴于某個特定問題，從而在普適性上性能較差。

2.1.2 元啟發(fā)式算法

元啟發(fā)式是啟發(fā)式與隨機化的結合，它不借助于問題的特定條件，生成或選擇啟發(fā)式（部分搜索算法）可行的解決方案。其優(yōu)勢在于用更少的計算量找到好的解決方案，主要從自然界中獲得靈感，并注重防止搜索陷入局部最優(yōu)解的問題。由于元啟發(fā)式算法的優(yōu)勢，目前，元啟發(fā)式算法成為云環(huán)境任務調度算法的主流，這些算法用于在短時間內獲得NP完全問題的次優(yōu)（近似）解。通常將元啟發(fā)式調度算法基于具有簡單通信和交互行為的大種群/群體的集體智能、生物進化機制和物理過程分為群體智能優(yōu)化算法、進化優(yōu)化算法和物理優(yōu)化算法，同時隨著技術發(fā)展，產生了新興算法和混合算法。

1）群體智能（swarm intelligence，SI）優(yōu)化算法

a）蟻群優(yōu)化（ACO）。該算法由“螞蟻系統(tǒng)”［28］發(fā)展而來。為了解決云計算中的瞬時峰值負載問題，Duan等人［29］提出了基于ACO的改進算法，稱為Pre-Ant Policy，該算法由預測模型組成，改進了各種QoS參數。

b）人工蜂群（ABC）［30］。最初由Karaboga于2005年提出，其基本原理是通過觀察蜜蜂搜索和采蜜的行為，找到最優(yōu)采蜜路徑。Babu和Krishna提出了一種基于ABC算法的行為負載平衡算法，該算法不斷地平衡工作負載，并改進各種關鍵性能指標參數。

c）細菌飼料優(yōu)化（BFO）。其由Muller等人于2002年提出，主要原理是細菌覓食的集體行為，包括群居、趨化、繁殖和消除/擴散四個過程。Tang等人［31］通過在線處理實時應用程序，以少量資源來平衡負載，通過離線使用BFO算法進行全局調度，增加整個系統(tǒng)的穩(wěn)定性和性能。

d）粒子群優(yōu)化（PSO）。由Eberhart等人［32］于1995年提出，其主要思想是利用粒子的集體行為找到食物。PSO發(fā)展迅速，如標準PSO、改良粒子群算法［33］和二元粒子群算法及其變體等。

2）進化優(yōu)化算法

進化算法（EA）是進化計算的算法分支，最初由Holland［34］于1975年提出，通過開發(fā)一組初始候選解決方案來找到最佳解決方案。

遺傳算法（GA）由約翰·霍蘭德于1960年提出，算法基于適應度值選擇染色體，進行交叉和突變產生新的解決方案，直到求得可行解。Shishido等人［35］提出的一種主要針對截止時間作為約束的遺傳算法，有效提升成本效益和確保安全方面。遺傳算法被證明是計算機科學中解決的NP難題的有效工具。Tsai等人［36］基于GA，使用差分策略實現(xiàn)變異操作，提出改進的差分進化算法（IDEA），以提升性能。

3）物理算法

物理算法是由物理學定律啟發(fā)而來。物理環(huán)境復雜多變，具有隨機性，算法混合全局和局部（基于鄰域的）搜索方法，使得在解決任務調度優(yōu)化問題時表現(xiàn)得非常出色。

a）模擬退火（SA）。其由Kirk于1984年引入，主要原理是模擬了材料的退火過程，屬于無記憶算法，即在搜索過程中不存儲任何信息。Wang等人［37］提出了一種名為SA的高效物理資源分配算法，其性能優(yōu)于GA和PSO算法，并克服了具有成本意識的VNE問題。

b）和諧搜索（HS）。Geem等人［38］提出HS進化算法，通過模仿音樂即興創(chuàng)作，和聲即代表可能的解決方案。此外，還有引力搜索算法（GSA）和Tabu搜索算法等（TS）。

4）新興算法

近年來，許多新的元啟發(fā)式算法已經被設計用于適應復雜的云計算環(huán)境，以應用于云計算中的不同復雜優(yōu)化問題。如樹生長算法（TGA）、飛餓撲火優(yōu)化算法（MFO）和珊瑚礁優(yōu)化［39］等。元啟發(fā)算法無須特定條件，但模塊聚合復雜，搜索易過早陷入局部最優(yōu)解。

2.1.3 混合式算法

單獨的調度算法對于特定領域的效果有著較好的反響，但面對實際任務調度中用戶需求動態(tài)多變的現(xiàn)狀，產生了將不同算法融合的混合式算法，有效提高時間與效果方面的性能，成為目前重要的研究方向。Saravanan等人［40］提出了IWHOLF-TSC算法，改進帶有Lévy飛行算法的野馬優(yōu)化。實驗結果表明，該算法的性能優(yōu)于其他最先進的調度算法。何婧媛等人［41］將布谷鳥搜索（CS）和粒子群優(yōu)化（PSO）兩種算法相結合，提出多目標布谷鳥粒子群優(yōu)化算法（MO-CPSO）。CloudSim評估表明，與CS、ACO、和min-min算法相比，MO-CPSO算法使完成時間、開銷和截止時間違背率均最小。表1是單云環(huán)境下任務調度算法的對比總結。

對比發(fā)現(xiàn)，啟發(fā)式算法的研究與發(fā)展歷史最為悠久，其通常能夠實現(xiàn)某一方面的性能最優(yōu)，如SJF算法在獨立性上表現(xiàn)出色。但是，相對于FCFS、RR、SJF等靜態(tài)調度算法，min-min、RR、OLB、MCT、MET等動態(tài)算法更適應于動態(tài)變化的云環(huán)境。此外，傳統(tǒng)的調度算法無法找到多維調度問題的最優(yōu)結果。因此，元啟發(fā)式任務調度算法成為解決云計算任務調度算法的主流選擇，但是往往實現(xiàn)更加復雜，難以廣泛應用，實用性較差。而混合式算法通過保留傳統(tǒng)式啟發(fā)算法部署簡單的特點與啟發(fā)式算法的高性能，實現(xiàn)算法優(yōu)化升級，實驗數據表明，混合算法產生1+1>2的效果，在不同程度上獲得了較好的性能結果。但是也會導致額外開銷、利用率不高等現(xiàn)象。

2.2 聯(lián)盟云環(huán)境

聯(lián)盟云環(huán)境［15］是指各用戶獨立擁有自己的云服務提供商或私有云環(huán)境，同時在聯(lián)盟云中的每一個用戶彼此之間互聯(lián)基礎設施實現(xiàn)資源共享。在政府機關、教育機構或學術組織中較為常見。通常分為對等聯(lián)盟和集中式聯(lián)盟兩種聯(lián)盟方式。對等聯(lián)盟是指聯(lián)合中的每個參與者云都是一個對等云，在沒有任何中介的情況下與其他人協(xié)作。在這種類型的云聯(lián)盟中，沒有中央組件，通常使用某個參與者云作為代理處理。集中式聯(lián)盟指聯(lián)合中的所有參與者云通過一個中央實體完成事物處理。本節(jié)從任務的依賴關系出發(fā)將任務調度算法分為工作流調度和獨立任務調度。

2.2.1 云聯(lián)盟中的工作流調度

文獻［42］提出一種基于QoS權重的聯(lián)盟云工作流的調度算法，在SmartFed的實驗中，它為聯(lián)合DC、分配器、隊列管理和存儲添加所需的包，使用循環(huán)算法對DC中的VM進行分配，并取得較好的效果。

Coutinho等人［43］提出了 GraspCC-fed，基于貪婪隨機自適應搜索程序（GRASP），有效處理聯(lián)邦云中的工作流執(zhí)行，并與Sci-Cumulus工作流程引擎相結合。

文獻［44］提出了MOHEFT，算法擴展了異構最早完成時間（HEFT）工作流調度算法，處理多個沖突目標并逼近帕累托前沿最優(yōu)調度。實驗表明，當具有幾個并行任務以及多個并行工作流時，MOHEFT性能最優(yōu)。

2.2.2 云聯(lián)盟中的任務調度

文獻［45］提出了一種在聯(lián)邦云中執(zhí)行大規(guī)模分布式計算的通用框架，通過引入云計算能力（GWcloud）改進的試點系統(tǒng)（GWpilot），可以根據可用資源實例化VM，允許用戶整合其資源調配，但模型不支持公共服務提供商。

文獻［46］提出一種基于FDMR（federated distributed Map-educe）的分布式算法，以在云聯(lián)盟中跨地理分布地調度作業(yè)。性能評估證明，F(xiàn)DMR解決方案非常接近精確方法，并提高了資源的利用率、數據傳輸性能、和資源可用性等因素，但是成本巨大。

Gouasmi等人［47］提出了一種分布式調度方案FedSCD，用于處理聯(lián)盟分布式集群中的MapReduce應用程序。它通過減少空閑VM和防止資源浪費來提供更好的資源管理和調度響應時間，降低執(zhí)行成本，提高性能。表2對聯(lián)盟云環(huán)境下任務調度算法進行總結歸納。

對比發(fā)現(xiàn)，聯(lián)盟云是學術與政府等機構的常見形式，其中開發(fā)了大量科學技術結合任務調度算法，并通常將多目標優(yōu)化作為目標函數，主要針對完成時間和成本進行優(yōu)化，同時也充分考慮了網絡帶寬資源利用率等。但是由于計算需求的激增以及云環(huán)境的特殊性，需要對各云用戶進行規(guī)范，目前的聯(lián)盟云任務調度算法仍然無法滿足數據密集和計算密集型的需求，極大地制約了聯(lián)盟云任務調度算法的研究與發(fā)展。

2.3 混合云環(huán)境

混合云指包含公有云和私有云的兩個或兩個以上的云，用戶往往將其敏感工作流程分配給私有云，當私有云缺乏執(zhí)行用戶任務所需的資源時，可以從公有云獲得共享資源，充分利用兩者優(yōu)勢，得到價格便宜又優(yōu)質的服務，但對不同服務提供商以及云類型的統(tǒng)一納管和高效運維難度加大。混合云是目前工業(yè)市場主流的選擇，也是學術界的研究熱點。

2.3.1 混合云中的工作流調度

文獻［48］提出通信鏈路可用性的不確定性調度算法。在云中，由于通信鏈路中的并發(fā)性，很難獲得精確數據，導致制造時間和成本增加。Lin等人［49］提出HIAP，這是一種混合云上SWF的在線調度方法，將應用程序劃分為一組相關任務，并考慮帶寬、數據傳輸成本和計算成本等約束，提升執(zhí)行時間的準確。

2.3.2 混合云中的任務調度

Yuan等人［50］提出一種利潤最大化算法（PMA），PMA提供的臨時任務調度可以動態(tài)調度所有到達任務。通過混合啟發(fā)式優(yōu)化算法模擬退火粒子群優(yōu)化（SAPSO）來解決PMA每次迭代中的子問題。大量的仿真實驗表明，算法在保證服務延遲的同時，大大提高了私有云的吞吐量和利潤。

文獻［51］提出TTSA調度算法，通過混合整數線性程序求解成本問題，并通過混合模擬退火粒子群來優(yōu)化。實驗結果表明，TTSA生成的最優(yōu)或次優(yōu)調度策略可以有效地提高私有CDC的吞吐量并降低成本，滿足任務響應時間的要求。表3對混合云環(huán)境下任務調度算法進行總結歸納。

對比發(fā)現(xiàn)，混合云環(huán)境的任務調度算法通常是對單云環(huán)境任務調度算法的優(yōu)化，主要集中于對完成時間與成本上的優(yōu)化，但總體仍是對多目標的優(yōu)化。但目前多數任務調度算法無法在真實環(huán)境中進行部署與測試，限制了算法的發(fā)展。

2.4 多云環(huán)境

多云環(huán)境是指由不同云服務提供商CSP（cloud service provider）提供的公有云的混合。多個公有云服務提供商的競爭提供了更好的服務，但構建復雜，管理困難。

2.4.1 多云中的工作流調度

Gupta等人［52］提出了一種基于傳輸時間意識的多云環(huán)境下的高效工作流調度算法。算法包括計算任務的優(yōu)先級和基于優(yōu)先級進行虛擬機（VM）選擇兩個階段，仿真結果表明，算法在生成時間和利用率方面都優(yōu)于其他算法。文獻［53］提出一種基于多目標PSO的調度方法，在PSO算法基礎上，對每個CSP應用定價模型和一些性能指標，進行工作流調度。實驗表明，算法性能優(yōu)于CMOHEFT和隨機調度算法。

2.4.2 多云中的任務調度

文獻［54］針對異構多云環(huán)境提出了三種任務劃分調度算法，分別是CTPS、CMMTPS和CMAXMTPS，它包括預處理和處理步驟兩個程序，達到縮短調度時間并提高資源利用率的效果，但是對于預處理和處理階段之間的通信時間以及傳輸和執(zhí)行時間的成本考慮不夠。文獻［55］提出一種用于多云系統(tǒng)的自適應調度方法（DSS），它結合了可分割負載理論和節(jié)點可用性預測方法，提出的多云架構支持幾個地理分散的網關，具有各種計算和通信功能的資源池，可以使用具有各種容量的鏈路連接到所有節(jié)點。結果表明，算法能夠有效減少任務的處理時間。表4對多云環(huán)境下任務調度算法進行總結歸納。

對比發(fā)現(xiàn)，多云環(huán)境越來越被應用于實際中，但是不同云之間進行大量的信息傳輸與共享，導致時間開銷加大，而任務調度算法容易時間復雜度過高，因此，大量算法對時間復雜度進行優(yōu)化，但是對優(yōu)化目標的優(yōu)化上沒有考慮多種優(yōu)化目標。

綜合對任務調度算法的分類與評價發(fā)現(xiàn)，目前任務調度算法的發(fā)展逐步向更適用于復雜云環(huán)境與滿足多目標的QoS優(yōu)化。但云計算通過資源虛擬化與容器等技術，能夠對各類資源進行統(tǒng)一管理，通常有基本資源分配算法（basic resource allocation，BRA）、公平調度算法（fair scheduler）、容量調度算法（capacity scheduker）以及基于用戶資源配額的資源彈性分配算法（QREA）等［55］，各類資源分配算法能夠提升多目標優(yōu)化效果，此外，基于資源組合預測的云計算任務調度算法［56］綜合考慮資源的分布情況與任務的調度，避免盲目調度，但資源未能根據任務情況動態(tài)改變。因此，目前算法中缺乏同時兼顧資源分配與任務調度的算法。

3 挑戰(zhàn)與展望

未來應從以下四個方面進行進一步研究。

a）本文通過整理調度算法相關文章，發(fā)現(xiàn)現(xiàn)有算法都以單云任務調度算法改進優(yōu)化為主，缺少對云間環(huán)境的架構研究，導致算法的普適性差，無法適應多種多樣的云間環(huán)境。下一步應從云間環(huán)境本身出發(fā)，以統(tǒng)一的API屏蔽底層基礎設施導致的差異，設計更普適的算法。

b）通過整理發(fā)現(xiàn)，無論是單云環(huán)境還是云間環(huán)境，用戶對于云服務的需求快速增長，不但要考慮多種優(yōu)化目標，同時很多優(yōu)化目標之間存在彼消此漲問題，導致多目標優(yōu)化無法兼顧的問題，下一步應綜合考量多種優(yōu)化目標，并根據重要程度賦權重，提出滿足多個維度優(yōu)化目標的任務調度算法。

c）隨著人工智能、物聯(lián)網、霧計算以及基于納米計算/量子、非傳統(tǒng)體系結構等多種新興技術興起，今后的云計算環(huán)境將更加復雜多樣，下一步應將新興技術與傳統(tǒng)云計算進行融合，實現(xiàn)任務調度智能化、輕量化，推動云計算實現(xiàn)跨越式發(fā)展。

d）目前的調度優(yōu)化算法主要從任務調度角度出發(fā)進行優(yōu)化，往往忽略資源分配的重要性，但在現(xiàn)有系統(tǒng)中，對資源優(yōu)化分配所取得的微弱效果往往帶來巨大的系統(tǒng)開銷。容器技術的提出，其輕量化和彈性擴縮容的性能，為兼顧資源分配與任務調度提供可行的方案。下一步應從容器技術出發(fā)，對資源進行更加有效的納管與彈性分配并實現(xiàn)資源根據任務量變化的動態(tài)調度，同時將用戶提交的任務請求與資源進行最佳映射，達到多QoS優(yōu)化，實現(xiàn)云環(huán)境下任務調度性能的進一步優(yōu)化。

e）目前，大多數企業(yè)、政府、軍隊等機構對于行業(yè)云、數據云的需求越來越大，位于Pass層的大量軟件下沉到Iass層，任務調度算法不再局限于傳統(tǒng)對算力、存儲、網絡等基礎資源調度，還要對應用的資源進行智能化調度，為數據云全域內的虛擬化資源和容器化資源實現(xiàn)自動及自主調度。目前，針對行業(yè)云、數據云的算法研究仍然存在大量空白，下一步應基于行業(yè)云、數據云架構，提出適用的任務調度算法。

4 結束語

本文主要完成了任務調度與云環(huán)境的概念明確。通過梳理現(xiàn)有的云計算任務調度算法，提出一種新的任務調度算法分類方法。根據云環(huán)境的不同，將云環(huán)境分為單云環(huán)境、聯(lián)盟云環(huán)境、混合云環(huán)境、多云環(huán)境，并基于不同環(huán)境進行了分類和比較。對比發(fā)現(xiàn)，傳統(tǒng)啟發(fā)式任務調度算法對某一特定目標優(yōu)化效果較好，但是用戶往往提出多種優(yōu)化目標，因此提出元啟發(fā)式算法，但由于其實現(xiàn)復雜，難以應用部署。混合式算法是傳統(tǒng)啟發(fā)式算法與混合式算法的結合，保留了兩者的優(yōu)勢，是目前主流的任務調度算法，但是存在額外開銷以及資源負載不均衡等問題，因此仍值得進一步研究優(yōu)化。此外，云環(huán)境中任務復雜多樣，任務間的關系也相互交疊，獨立任務調度無法再適應現(xiàn)有環(huán)境，目前，任務調度算法研究主要以工作流調度為主。

總的來說，本文提供了調度算法的全面理解，未來在數據云、行業(yè)云的調度算法研究中，應注重對混合式工作流調度的研究。

參考文獻：

[1]許子明，田楊鋒.云計算的發(fā)展歷史及其應用［J］.信息記錄材料，2018，19（8）：66-67.（Xu Ziming， Tian Yangfeng. The development history and applications of cloud computing［J］.Information Recor-ding Materials，2018，19（8）：66-67.）

［2]Mell P M， Grance T. The NIST definition of cloud computing， 800-145［R］.Gaithersburg，MD：National Institute of Standards and Technology，2011.

［3]Wikipedia.Cloud computing［EB/OL］.（2009-03-10）.http：//en.wikipedia.org/wiki/Cloud_computing.

［4]中國云計算網.什么是云計算？［EB/OL］.（2008-05-14）［2009-02-27］.http：//www.cloudcomputing-china.cn/Article/ShowArticle.asp？ArticleID=1.（Cloud Computing Network of China.What is cloud computing？［EB/OL］.（2008-05-14）［2009-02-27］.http：//www.cloudcomputing-china.cn/Article/ShowArticle.asp？ArticleID=1.）

［5]Amin R， Kumar N， Biswas G P， et al. A light weight authentication protocol for IoT-enabled devices in distributed cloud computing environment［J］.Future Generation Computer Systems，2018;78：1005-1019.

［6]羅紅，慕德俊，鄧智群，等.網格計算中任務調度研究綜述［J］.計算機應用研究，2005，22（5）：16-19.（Luo Hong， Mu Dejun， Deng Zhiqun， et al. A review of job scheduling for grid computing［J］.Application Research of Computers，2005，22（5）：16-19.）

［7]Juarez F， Ejarque J， Badia R M. Dynamic energy-aware scheduling for parallel task-based application in cloud computing［J］.Future Generation Computer Systems，2018，78：257-271.

［8]Madni S H H， Latiff M S A， Coulibaly Y， et al. Recent advancements in resource allocation techniques for cloud computing environment： a systematic review［J］.Cluster Computing，2017，20（3）：2489-2533.

［9]Mikavica B， Kostic＇-Ljubisavljevic＇ A. Pricing and bidding strategies for cloud spot block instances［C］//Proc of the 41st International Convention on Information and Communication Technology， Electronics and Microelectronics.Piscataway，NJ：IEEE Press，2018：0384-0389.

［10]Ullman J D. NP-complete scheduling problems［J］.Journal of Computer and System Sciences，1975，10（3）：384-393.

［11]Singh S， Chana I. Resource provisioning and scheduling in clouds： QoS perspective［J］.The Journal of Supercomputing，2016，72（3）：926-960.

［12]Wu Kaiyue， Lu Ping， Zhu Zuqing. Distributed online scheduling and routing of multicast-oriented tasks for profit-driven cloud computing［J］.IEEE Communications Letters，2016，20（4）：684-687.

［13]Hosseini Shirvani M， Rahmani A M， Sahafi A. An iterative mathema-tical decision model for cloud migration： a cost and security risk approach［J］.Software： Practice Experience，2018，48（3）：449-485.

［14]Zhang Bo， Zeng Zeng， Shi Xiupeng， et al. A novel cooperative resource provisioning strategy for multi-cloud load balancing［J］.Journal of Parallel and Distributed Computing，2021，152：98-107.

［15]Chauhan1 S S， Pilli E S， Joshi R C. A broker based framework for federated cloud environment［C］//Proc of International Conference on Emerging Trends in Communication Technologies.Piscataway，NJ：IEEE Press，2016：1-5.

［16]Linthicum D S. Emerging hybrid cloud patterns［J］.IEEE Cloud Computing，2016，3（1）：88-91.

［17]Li Xiaoyong， Ma Huadong， Yao Wenbin， et al. Data-driven and feedback-enhanced trust computing pattern for large-scale multi-cloud collaborative services［J］.IEEE Trans on Services Computing，2018，11（4）：671-684.

［18]Shi Yang， Chen Zhaoyun， Quan Wei， et al. A performance study of static task scheduling heuristics on cloud-scale acceleration architecture［C］//Proc of the 5th International Conference on Computing and Data Engineering.New York：ACM Press，2019：81-85.

［19]Xhafa F， Abraham A. Meta-heuristics for grid scheduling problems［M］//Xhafa F， Abraham A. Metaheuristics for scheduling in distri-buted computing environments.Berlin：Springer，2008：1-37.

［20]Liu Juefu， Liu Peng. The research of load imbalance based on min-min in grid［C］//Proc of International Conference on Computer Design and Applications.Piscataway，NJ：IEEE Press，2010：V4-1-V4-4.

［21]童釗，鄧小妹，陳洪劍，等.云環(huán)境下基于強化學習的多目標任務調度算法［J］.小型微型計算機系統(tǒng)，2020，41（2）：285-290.（Tong Zhao， Deng Xiaomei， Chen Hongjian， et al. A multi-objective task scheduling algorithm based on reinforcement learning in cloud environments［J］.Journal of Chinese Computer Systems，2020，41（2）：285-290.）

［22]Devi D C. Load balancing in cloud computing environment using improved weighted round robin algorithm for non-preemptive dependent tasks［J］.The Scientific World Journal，2016，2016：article ID 3896065.

［23]Sheikhalishahi M， Wallace R M， Grandinetti L， et al. A multi-dimensional job scheduling[J].Future Generation Computer Systems， 2016，54：123-131.

［24]Sheikhalishahi M， Wallace R M， Grandinetti L， et al. A packing problem approaches to energy-aware load distribution in clouds［J］.Future Generation Computer Systems，2016，54：123-131.

［25]Shyam G K， Manvi S S. Resource allocation in cloud computing using agents［C］//Proc of IEEE International Advance Computing Confe-rence.Piscataway，NJ：IEEE Press，2015：458-463.

［26]Lavanya M， Shanthi B， Saravanan S. Multi objective task scheduling algorithm based on SLA and processing time suitable for cloud environment［J］.Computer Communications，2020，151：183-195.

［27]Al-Maytami B A， Fan P， Hussain A， et al. A task scheduling algorithm with improved makespan based on prediction of tasks computation time algorithm for cloud computing［J］.IEEE Access，2019，7：916-926.

［28]Dorigo M. Optimization， learning and natural algorithms［D］.Italy：Politecnico di Milano，1992.

［29]Duan Hancong， Chen Chao， Min Geyong， et al. Energy-aware scheduling of virtual machines in heterogeneous cloud computing systems［J］.Future Generation Computer Systems，2017，74：142-150.

［30]Hajimirzaei B， Navimipour N J. Intrusion detection for cloud computing using neural networks and artificial bee colony optimization algorithm［J］.ICT Express，2019，5（1）：56-59.

［31]Tang Linlin， Li Zuohua， Ren Pingfei. et al. Online and offline based load balance algorithm in cloud computing［J］.Knowledge-Based Systems，2017，138：91-104.

［32]Eberhart R， Kennedy J. A new optimizer using particle swarm theory［C］//Proc of the 6th International Symposium on Micro Machine and Human Science.Piscataway，NJ：IEEE Press，1995：39-43.

［33]Kumar M， Sharma S C. PSO-COGENT： cost and energy efficient scheduling in cloud environment with deadline constraint［J］.Sustai-nable Computing：Informatics and Systems，2018，19：147-164.

［34]Holland J H. Adaptation in natural and artificial systems：an introductory analysis with applications to biology， control， and artificial intelligence［M］.Cambridge，MA：MIT Press，1992.

［35]Shishido H Y， Estrella J C， Toledo C F M， et al. Genetic-based algorithms applied to a workflow scheduling algorithm with security and deadline constraints in clouds［J］.Computers & Electrical Engineering，2018，69：378-394.

［36]Tsai J T， Feng Jiacen， Chou J H， et al. Optimized task scheduling and resource allocation on cloud computing environment using improved differential evolution algorithm［J］.Computers & Operations Research，2013，40（12）：3045-3055.

［37]Wang Wenbo， Chang Xiaolin， Liu Jiqiang， et al. Simulated annealing based resource allocation for cloud data centers［C］//Proc of the 15th Annual Conference Companion on Genetic and Evolutionary Computation.New York：ACM Press，2013：81-82.

［38]Geem Z W， Kim J H， Loganathan G V. A new heuristic optimization algorithm：harmony search［J］.Simulation，2001，76（2）：60-68.

［39]Wan Shuzhen， Qi Lixin. An improved coral reef optimization-based scheduling algorithm for cloud computing［J］.Journal of Mathema-tics，2021，2021：article ID 5532288.

［40]Saravanan G， Neelakandan S， Ezhumalai P， et al. Improved wild horse optimization with Lévy flight algorithm for effective task scheduling in cloud computing［J］.Journal of Cloud Computing，2023，12（1）：1-14.

［41]何婧媛，孫乾坤.布谷鳥粒子群優(yōu)化算法的多目標任務調度［J］.信息技術，2020，44（5）：37-40.（He Jingyuan， Sun Qiankun. Multi objective task scheduling of Cuckoo particle swarm optimization［J］.Information Technology，2020，44（5）：37-40.）

［42]Chudasama V， Shah J， Bhavsar M. Weight based workflow scheduling in cloud federation［M］//Satapathy S， Joshi A. Information and Communication Technology for Intelligent Systems.Cham：Springer，2017：405-411.

［43]Coutinho R D C， Drummond L M， Frota Y， et al. Optimizing virtual machine allocation for parallel scientifc workflows in federated clouds［J］.Future Generation Computer Systems，2015，46：51-68.

［44]Durillo J J， Prodan R， Barbosa J G. Pareto tradeoff scheduling of workflows on federated commercial clouds［J］.Simulation Modelling Practice and Theory，2015，58：95-111.

［45]Rubio-Montero A J， Huedo E， Mayo-García R. Scheduling multiple virtual environments in cloud federations for distributed calculations［J］.Future Generation Computer Systems，2017，74：90-103.

［46]Gouasmi T， Louati W， Kacem A H. Exact and heuristic MapReduce scheduling algorithms for cloud federation［J］.Computers & Electrical Engineering，2018，69：274-286.

［47]Gouasmi T， Louati W， Kacem A H. Cost-efficient distributed mapreduce job scheduling across cloud federation［C］//Proc of IEEE International Conference on Services Computing.Piscataway，NJ：IEEE Press，2017：289-296.

［48]Bittencourt L F， Madeira E R M， Da Fonseca N L S. Impact of com-munication uncertainties on workflow scheduling in hybrid clouds［C］//Proc of IEEE Global Communications Conference.Piscataway，NJ：IEEE Press，2012：1623-1628.

［49]Lin Bing， Guo Wenzhong， Lin Xiuyan. Online optimization scheduling for scientifc workflows with deadline constraint on hybrid clouds［J］.Concurrency and Computation，2016，28（11）：3079-3095.

［50]Yuan Haitao， Bi Jing， Tan Wei， et al. Temporal task scheduling with constrained service delay for profit maximization in hybrid clouds［J］.IEEE Trans on Automation Science and Engineering，2017，14（1）：337-348.

［51]Yuan Haitao， Bi Jing， Tan Wei， et al. TTSA： an effective scheduling approach for delay bounded tasks in hybrid clouds［J］.IEEE Trans on Cybernetics，2017，47（11）：3658-3668.

［52]Gupta I， Kumar M S， Jana P K. Transfer time-aware workflow sche-duling for multi-cloud environment［C］//Proc of International Confe-rence on Computing，Communication and Automation.Piscataway，NJ：IEEE Press，2016：732-737.

［53]Hu Haiyang， Li Zhongjin， Hu Hua， et al. Multi-objective scheduling for scientifc workflow in multicloud environment［J］.Journal of Network and Computer Applications，2018，114：108-122.

［54]Panda S K， Pande S K， Das S. Task partitioning scheduling algorithms for heterogeneous multi-cloud environment［J］.Arabian Journal for Science and Engineering，2018，43（2）：913-933.

［55]Kang S， Veeravalli B， Aung K M M. Dynamic scheduling strategy with efficient node availability prediction for handling divisible loads in multi-cloud systems［J］.Journal of Parallel and Distributed Computing，2018，113：1-16.

［56]劉曉東，趙曉芳，金巖，等.企業(yè)私有云環(huán)境下面向高性能計算的資源彈性分配算法［J］.高技術通信，2018，28（8）：669-676.（Liu Xiao-dong， Zhao Xiaofang， Jin Yan， et al. Resource elastic allocation algorithm for high performance computing in enterprise private cloud environment［J］.High Technology Letters，2018，28（8）：669-676.）

［57]程宏兵.基于資源預測的網格任務調度模型［J］.計算機應用，2010，30（9）：2530-2534，2544.（Cheng Hongbing. Grid task sche-duling model based on resource prediction［J］.Journal of Computer Application，2010，30（9）：2530-2534，2544.）

收稿日期：2023-02-28；修回日期：2023-04-20

基金項目：軍委網信科研資助項目

作者簡介：陳紅華（1998-），女，浙江桐鄉(xiāng)人，碩士研究生，主要研究方向為面向多樣化任務的云計算；崔翛龍（1973-），男（通信作者），安徽長豐人，教授，博導，主要研究方向為智能化指揮、任務大數據（xlspace@hotmail.com）；王耀杰（1990-），男，河南洛陽人，博士，主要研究方向為反恐預警、信息安全、深度學習.