唐續(xù)豪 劉發(fā)貴, 王 彬 李 超 蔣 俊 唐 泉 陳維明 何鳳文

1 （華南理工大學(xué)計算機科學(xué)與工程學(xué)院 廣州 510006）

2 （鵬城實驗室 廣東 深圳 518000）

3 （國家稅務(wù)總局廣東省稅務(wù)局 廣州 510627）

云計算作為國家“新基建”中重要的新技術(shù)基礎(chǔ)設(shè)施，為5G、物聯(lián)網(wǎng)、工業(yè)互聯(lián)網(wǎng)等領(lǐng)域的發(fā)展提供了重要的支持.目前，云計算已經(jīng)廣泛應(yīng)用于不同領(lǐng)域，為云服務(wù)使用者提供數(shù)據(jù)處理、大規(guī)模數(shù)據(jù)存儲相關(guān)服務(wù).云服務(wù)使用者可以根據(jù)自身需求選擇不同的部署模式，如有可用資源多、按計算使用量付費的需求則可選擇公有云作為部署模式；如有安全性高的需求則可選擇私有云作為部署模式，這些彼此沒有關(guān)聯(lián)的單一公有云或私有云構(gòu)成了單云環(huán)境.近年來由于云計算技術(shù)的快速發(fā)展，政府機關(guān)、企業(yè)、機構(gòu)、個人用戶等不同類別的云服務(wù)使用者在應(yīng)用過程中形成了不同的技術(shù)路線，累積了大量不同架構(gòu)、不同品牌的網(wǎng)絡(luò)、計算、存儲設(shè)備及多種應(yīng)用和虛擬化環(huán)境[1]，這些不同種類的硬件資源、異構(gòu)的虛擬化系統(tǒng)使得云環(huán)境日趨復(fù)雜，而單云環(huán)境已無法滿足云服務(wù)使用者日益增長的計算需求和服務(wù)需求.同時，數(shù)據(jù)量的不斷增加和云服務(wù)應(yīng)用場景的多元化讓單云環(huán)境還面臨著3 個方面的挑戰(zhàn)：

1）單云環(huán)境資源利用率有限，應(yīng)對突發(fā)業(yè)務(wù)成本較高.云服務(wù)使用者在業(yè)務(wù)高峰時往往需要比平時高幾倍甚至數(shù)十倍的資源，在單云環(huán)境中如按照峰值需求配置云資源，則會導(dǎo)致資源利用率低，為了保證服務(wù)質(zhì)量，云服務(wù)提供者的成本會增加，而這部分成本最終將轉(zhuǎn)嫁給云服務(wù)使用者，使得業(yè)務(wù)成本增加.同時，單云環(huán)境無法擁有云服務(wù)供應(yīng)商的議價權(quán)，無法結(jié)合多個云服務(wù)供應(yīng)商提供的資源價格來制定更加合理的經(jīng)濟策略，優(yōu)化使用成本.

2）單云環(huán)境無法解決供應(yīng)商鎖定問題，阻礙業(yè)務(wù)發(fā)展.單一云服務(wù)供應(yīng)商可能會因監(jiān)管、法律、政治等因素中斷服務(wù)，導(dǎo)致供應(yīng)商鎖定，這會使云服務(wù)使用者在業(yè)務(wù)發(fā)展中面臨極大風(fēng)險.

3）單云環(huán)境中云服務(wù)的可靠性無法得到保證.如果將所有數(shù)據(jù)都放在同一云平臺上，出現(xiàn)宕機或數(shù)據(jù)丟失事故將對云服務(wù)，使用者的業(yè)務(wù)造成巨大損失，云服務(wù)的可靠性無法得到保證.

這些問題的存在都會導(dǎo)致云服務(wù)使用者無法統(tǒng)一管理云資源，制約了云服務(wù)使用者對于云資源的有效利用.為了集成云服務(wù)，統(tǒng)一管理云資源，有效地解決單云環(huán)境所面臨的各種問題，跨云環(huán)境應(yīng)運而生，跨云環(huán)境包括混合云（hybrid cloud）[2-3]、聯(lián)盟云（federated cloud）[4]和多云（multi-cloud）[5].據(jù)全球著名市場研究公司IDC（international data corporation）預(yù)測，到2024 年，90%的全球1 000 強企業(yè)將建立跨云管理的戰(zhàn)略，云計算環(huán)境正在經(jīng)歷從單云到跨云的轉(zhuǎn)變[6].

云計算中的關(guān)鍵研究問題之一是任務(wù)調(diào)度，它根據(jù)任務(wù)的各種需求及資源的實際情況采用適當(dāng)?shù)牟呗詫⒉煌娜蝿?wù)分配到云內(nèi)最佳的資源上執(zhí)行[7].其中需要綜合考慮任務(wù)的執(zhí)行時間、完成時間、資源利用率、可靠性、成本、網(wǎng)絡(luò)吞吐量、可伸縮性能、能耗等優(yōu)化參數(shù)及相關(guān)評價指標(biāo)[8].由于跨云環(huán)境中資源呈現(xiàn)復(fù)雜性、異構(gòu)性，這使得統(tǒng)一管理并有效利用跨云資源的難度大大增加[9-10].因此，為了實現(xiàn)跨云資源的高效利用，如何合理調(diào)度用戶任務(wù)并將其分配到最佳的跨云資源上執(zhí)行，成為了跨云環(huán)境中需要解決的重要問題.同時，如何提高任務(wù)調(diào)度的效率，使其更好地適應(yīng)跨云環(huán)境，滿足日益增長的云計算能力與對各類云服務(wù)的需求，也成為目前云計算平臺研究領(lǐng)域急需解決的瓶頸問題.

近年來，跨云環(huán)境的不斷推廣應(yīng)用使得國內(nèi)外出現(xiàn)了研究跨云環(huán)境下任務(wù)調(diào)度算法的高質(zhì)量論文.由于跨云環(huán)境的分類界定較為模糊，相關(guān)研究的側(cè)重不一，導(dǎo)致此類研究的綜述性論文較為缺乏、研究較為滯后.目前，已有的綜述論文大多只對單云環(huán)境下任務(wù)調(diào)度算法進行了總結(jié)分析，尚未針對跨云環(huán)境下任務(wù)調(diào)度算法研究展開綜述.因此，本文根據(jù)國內(nèi)外研究現(xiàn)狀，結(jié)合跨云環(huán)境的相關(guān)資料和特點對其進行梳理，同時選取代表性論文對跨云環(huán)境下任務(wù)調(diào)度算法進行總結(jié)、分析，最后探討了跨云環(huán)境下任務(wù)調(diào)度算法研究中的不足和未來的研究趨勢，為跨云環(huán)境的分類、跨云環(huán)境下任務(wù)調(diào)度的進一步研究提供了參考.

1 跨云環(huán)境下任務(wù)調(diào)度概述

本節(jié)主要介紹跨云環(huán)境及任務(wù)調(diào)度算法的分類.由于跨云環(huán)境中部分概念及其場景無精確定義，本節(jié)重點梳理其中的關(guān)系，力求全面，以供讀者理解.

1.1 跨云環(huán)境分類

跨云環(huán)境一般分為2 類：一類是聯(lián)盟云環(huán)境，另一類是多云環(huán)境[11].如圖1（a）所示，聯(lián)盟云環(huán)境是指一組云服務(wù)供應(yīng)商彼此愿意互連其基礎(chǔ)設(shè)施以實現(xiàn)資源共享；多云環(huán)境是指云服務(wù)使用者可以使用多個獨立的云，如圖1（b）所示，其中云服務(wù)供應(yīng)商彼此之間并不互連且不共享其基礎(chǔ)設(shè)施[12].近年來，混合云作為新的云架構(gòu)體系已成為云計算領(lǐng)域研究的熱點，根據(jù)美國國家標(biāo)準(zhǔn)與技術(shù)（national institute of standards and technology，NIST）研究院的定義，混合云是由2 個或2 個以上的云（公有云、私有云或社區(qū)云）組成的，它們各自獨立但通過標(biāo)準(zhǔn)化技術(shù)或?qū)Ｓ屑夹g(shù)綁定在一起，實現(xiàn)了跨云之間數(shù)據(jù)和應(yīng)用程序的可移植性[13].因此，作為獨立的云架構(gòu)體系，混合云也屬于多云環(huán)境.

Fig.1 Inter-cloud environment comparison diagram圖1 跨云環(huán)境對比圖

在跨云環(huán)境中，通常使用代理（broker）來實現(xiàn)任務(wù)的調(diào)度及部署.如圖2 所示，代理作為獨立的第三方，將跨云環(huán)境中所有的云資源虛擬化形成一個統(tǒng)一的虛擬資源池，在該資源池中代理分別與各個獨立的云進行通信，但對于云服務(wù)使用者來說代理屏蔽了資源、通信等方面的異構(gòu)性，只向云服務(wù)使用者提供統(tǒng)一資源池的資源目錄及通信接口，并將任務(wù)分配給統(tǒng)一資源池中合適的資源執(zhí)行，實現(xiàn)跨云資源的有效利用.

Fig.2 Schematic diagram of task scheduling in inter-cloud environment圖2 跨云環(huán)境下任務(wù)調(diào)度示意圖

聯(lián)盟云環(huán)境大都以政府或?qū)W術(shù)組織為主發(fā)起，是政府內(nèi)部用云或?qū)W術(shù)組織擁有的私有云之間的合作[14].聯(lián)盟云環(huán)境更多地強調(diào)合作、共享的重要性，通常是通過部署和管理多個云計算服務(wù)來匹配云服務(wù)使用者的業(yè)務(wù)需求，通過聚合多個云平臺來合作完成同一個目標(biāo)任務(wù)[15].聯(lián)盟云環(huán)境中代理會收集并不斷更新環(huán)境中各個云的資源狀態(tài)信息，之后根據(jù)云服務(wù)使用者的服務(wù)級別協(xié)議（service level agreement,SLA）將任務(wù)分配到聯(lián)盟云環(huán)境中可用資源的虛擬機上，來實現(xiàn)資源利用率、可靠性、成本等相關(guān)性能的最優(yōu)化.聯(lián)盟云環(huán)境的提出，實現(xiàn)了多個云計算節(jié)點的互聯(lián)，提出了互操作協(xié)議標(biāo)準(zhǔn)、共享資源、相關(guān)數(shù)據(jù)管理等一些基于聯(lián)盟云環(huán)境下的云服務(wù)管理方法，解決了部分單云環(huán)境下所遇到的問題.但由于聯(lián)盟云需要共享資源的特殊性，導(dǎo)致其應(yīng)用范圍較小，難以推廣使用，其資源的異構(gòu)性也會引起整個聯(lián)盟云環(huán)境的不穩(wěn)定.綜合來看，聯(lián)盟云為解決單云環(huán)境下所面臨的部分問題提出了有參考價值的方案，但其中還存在一些尚待研究和解決的問題，同時聯(lián)盟云需要共享資源的特殊性使其無法避免法律合規(guī)等相關(guān)問題，這也大大制約了聯(lián)盟云的推廣.

多云環(huán)境目前并無精確的定義，在學(xué)術(shù)界和工業(yè)界一般意義上的多云環(huán)境是指由多個不同的（infrastructure as a service, IaaS）基礎(chǔ)設(shè)施即服務(wù)提供商組成的新環(huán)境，這些云服務(wù)供應(yīng)商相互獨立，同時向云服務(wù)使用者提供不同價格、不同性能的虛擬機以滿足其需求[5].而混合云一般認(rèn)為是公有云和私有云的混合，但云混合的形態(tài)有多種，根據(jù)NIST 的定義，混合云的形態(tài)應(yīng)該包括公有云之間的混合、私有云之間的混合、公有云和私有云的混合.Gartner 公司曾經(jīng)將混合云定義為混合的IT 架構(gòu)，在現(xiàn)實應(yīng)用中也存在大量傳統(tǒng)IT 設(shè)施和公有云混合的情況，所以混合云的形態(tài)也應(yīng)該包括傳統(tǒng)IT 與公有云的混合.因此，如圖3 所示混合云的形態(tài)可以總結(jié)為4 種：

Fig.3 The whole classification of inter-cloud environment圖3 跨云環(huán)境整體分類

1）公有云之間的混合

公有云之間的混合還存在同構(gòu)公有云混合和異構(gòu)公有云混合的情況，同構(gòu)公有云的混合一般是指相同云服務(wù)提供商的云平臺在不同地域之間的混合；異構(gòu)公有云的混合是指不同云服務(wù)提供商的混合，也就是目前學(xué)術(shù)界和工業(yè)界一般意義上的多云，而在應(yīng)用中則是將多個異構(gòu)公有云統(tǒng)一納管，實現(xiàn)云資源的統(tǒng)一管理，但此處的多云是為了區(qū)別混合云中公有云和私有云的混合類型.目前，異構(gòu)公有云的混合是研究的熱點，市場上也有很多工具來幫助云服務(wù)使用者同時部署管理多個異構(gòu)公有云，如HashiCorp提供的Terraform 就是較為流行的一種部署工具，它通過抽象化基礎(chǔ)架構(gòu)模型來屏蔽各個云之間IaaS 的具體差別[16].

2）私有云之間的混合

私有云之間的混合一般是企業(yè)或組織內(nèi)部的IT架構(gòu)，為了降低運營成本通常都是采用同一種私有云進行連接，當(dāng)然也會存在異構(gòu)的私有云的混合，但這種混合并不是研究和應(yīng)用的主流，如OpenStack 和VMware 可以進行混合，但并無太大意義甚至有可能增加運營成本.

3）公有云和私有云之間的混合

公有云與私有云的混合是一般意義上的混合云，它是目前工業(yè)界市場的主流選擇，同時學(xué)術(shù)界對于跨云環(huán)境的研究也大多集中于此.這種形態(tài)的混合云能夠同時兼顧公有云和私有云的優(yōu)點，給云服務(wù)使用者帶來更好的體驗.公有云與私有云的混合依然存在同構(gòu)和異構(gòu)之分，同構(gòu)是指2 個或多個云采用同一個技術(shù)架構(gòu)（開源架構(gòu)或同一廠家的平臺）；異構(gòu)是指公、私有云混合的技術(shù)架構(gòu)不同.目前，研究和應(yīng)用以同構(gòu)混合云為主.

4）公有云和傳統(tǒng)IT 的混合

這種混合一般需要盡可能地屏蔽公有云和傳統(tǒng)IT 之間的差異，以公有云為主適配傳統(tǒng)IT，進而達到對資源的有效利用.

綜合來看，跨云環(huán)境的主體是多云環(huán)境，而多云環(huán)境又重點關(guān)注異構(gòu)公有云的混合和公有云、私有云的混合.因此，多云環(huán)境可以理解為一種融合的IT架構(gòu)，區(qū)別于單云環(huán)境，在這種環(huán)境下云服務(wù)使用者可以將獨立的云資源盡可能地連接起來，實現(xiàn)應(yīng)用的編排、管理，最終達到資源高效利用的目的，其中混合云的各種形態(tài)都屬于多云環(huán)境.

學(xué)術(shù)界從很早之前就對多云環(huán)境展開相關(guān)研究，2014 年國際上出現(xiàn)了以研究多云環(huán)境下任務(wù)調(diào)度、資源管理等問題的研討會，命名為Cross Cloud[17].2017 年國內(nèi)的國防科技大學(xué)王懷民院士[18]首次提出云際計算概念，它以云服務(wù)提供者之間開放協(xié)作為基礎(chǔ)，通過融合多方云資源，實現(xiàn)“服務(wù)無邊界、云間有協(xié)作、資源易共享、價值可轉(zhuǎn)換”的新一代云計算模式，其參考架構(gòu)國家標(biāo)準(zhǔn)也已經(jīng)進入批準(zhǔn)階段[19]，同時云際計算連續(xù)多年依托國內(nèi)外知名會議在線下展開研討，在2020 年由國防科技大學(xué)主導(dǎo)，正式成為IEEE 云際計算國際會議.

隨著數(shù)據(jù)量的不斷增大，對算力的需求會越來越高，對計算性能的要求會逐漸提升，計算成本會隨之增加，云環(huán)境也會日趨復(fù)雜.這種趨勢下跨云環(huán)境會成為越來越多云服務(wù)使用者的必然選擇，而更加復(fù)雜的跨云環(huán)境將會不可避免地遇到新的問題.

1.2 主要任務(wù)調(diào)度算法

跨云環(huán)境下的任務(wù)調(diào)度算法是指根據(jù)當(dāng)前任務(wù)具體情況并結(jié)合環(huán)境中的所有資源，將任務(wù)分配到跨云環(huán)境中最優(yōu)資源上執(zhí)行的過程，任務(wù)調(diào)度算法本質(zhì)上是一個NP 難題[20].

跨云環(huán)境中的任務(wù)調(diào)度算法通?？梢愿鶕?jù)任務(wù)的類型將任務(wù)調(diào)度算法分為2 類：

1）獨立任務(wù)調(diào)度.獨立任務(wù)彼此之間沒有關(guān)聯(lián)關(guān)系，調(diào)度優(yōu)化的目標(biāo)通常是為了達到整個系統(tǒng)性能的最佳狀態(tài)或根據(jù)用戶的需求完成特定的調(diào)度優(yōu)化，最終將任務(wù)分配到跨云環(huán)境中的指定虛擬機即可[21].

2）工作流任務(wù)調(diào)度.工作流任務(wù)存在執(zhí)行順序，通常是所有前驅(qū)節(jié)點任務(wù)執(zhí)行完畢后，當(dāng)前任務(wù)才可以開始執(zhí)行，常用有向無環(huán)圖（directed acyclic graph,DAG）表示工作流任務(wù)，其中“節(jié)點”表示任務(wù)需要的計算過程，“邊”表示任務(wù)間的數(shù)據(jù)通信[22-23].在跨云環(huán)境中，如何調(diào)度和分配多個具有依賴關(guān)系的任務(wù)，為每個具有依賴關(guān)系的任務(wù)在跨云環(huán)境中找到合適的云平臺資源、降低資源使用成本、減少任務(wù)執(zhí)行時間是工作流任務(wù)調(diào)度優(yōu)化的重點目標(biāo).

對于跨云環(huán)境中的任務(wù)調(diào)度算法，目前已有的研究多數(shù)是以單云環(huán)境下任務(wù)調(diào)度算法為參考，根據(jù)特定目標(biāo)對其進行改進和優(yōu)化[24-25]，以滿足跨云環(huán)境的需求.表1 總結(jié)了單云環(huán)境下常見的任務(wù)調(diào)度算法，傳統(tǒng)調(diào)度算法包括先來先服務(wù)（first come first served, FCFS）、Min-Min[26]、Max-Min[27]、最小完成時間（minimum completion time, MCT）、最小執(zhí)行時間（minimum execution time, MET）、循環(huán)調(diào)度（round robin, RR）等，這類算法的思想較為簡單，通常是為了直接實現(xiàn)某種目標(biāo)而制定，算法整體易于實現(xiàn)，復(fù)雜度較低同時具有較強的實用性，現(xiàn)在多為云仿真平臺的默認(rèn)任務(wù)調(diào)度算法.但這些算法大都存在較大的局限性，并且性能不高，往往在實際的云環(huán)境中無法直接運用.蟻群優(yōu)化（ant colony optimization, ACO）[28-29]算法、粒子群優(yōu)化（particle swarm optimization, PSO）算法[30-32]、遺傳（genetic algorithm, GA）算法[33-35]、模擬退火（simulated annealing, SA）算法[36-37]、禁忌搜索（tabu search,TS）算法[38]等一般是模擬生物覓食方式或自然界中的物理現(xiàn)象，通過不斷地迭代優(yōu)化最終獲得較好的調(diào)度結(jié)果，同時這類算法也已經(jīng)在單云環(huán)境中獲得了符合調(diào)度目標(biāo)的較好的調(diào)度方案.但這類算法的參數(shù)及相關(guān)閾值的設(shè)定較為復(fù)雜，存在求解時間過長、算法復(fù)雜度較高等問題.

Table 1 Common Task Scheduling Algorithms in Single Cloud Environment表1 單云環(huán)境下常見的任務(wù)調(diào)度算法

在跨云環(huán)境中，由于資源具有異構(gòu)性且資源池中其他用戶的行為未知，任務(wù)會呈現(xiàn)較大的隨機性，同時任務(wù)的類型、數(shù)量等方面也會不斷地變化，更加復(fù)雜的環(huán)境下，任務(wù)調(diào)度會遇到新的問題和挑戰(zhàn).

2 聯(lián)盟云環(huán)境下的任務(wù)調(diào)度算法

聯(lián)盟云環(huán)境通常是指云服務(wù)供應(yīng)商彼此愿意互連其基礎(chǔ)設(shè)施以實現(xiàn)資源共享，通過管理多個云計算服務(wù)來滿足云服務(wù)使用者的需求.聯(lián)盟云支持若干個獨立云平臺合作完成同一個目標(biāo)任務(wù)[39].

文獻[40]設(shè)計了CometCloud 聯(lián)盟云架構(gòu)，該聯(lián)盟云架構(gòu)部署在3 所不同地域高校的服務(wù)器上，以成本最小化設(shè)計了調(diào)度策略并用2 個實際應(yīng)用任務(wù)進行測試.同時，利用實驗評估了處理相同任務(wù)量情況下單云環(huán)境及聯(lián)盟云環(huán)境的性能，實驗結(jié)果表明，在任務(wù)完成時間和成本優(yōu)化方面，聯(lián)盟云優(yōu)勢會更為明顯.文獻[41]針對聯(lián)盟云環(huán)境構(gòu)建了一種基于博弈論的調(diào)度方案，該方案以成本為導(dǎo)向，向納什均衡[42]解靠攏，給代理賦予了系統(tǒng)組件所需的自治程度，并加入了自組織、彈性等全局屬性.實驗結(jié)果表明，這種調(diào)度方案在面對大量任務(wù)的情況下可提供更好的伸縮性.文獻[43]提出了一種基于負(fù)載均衡的蟻群優(yōu)化（load balancing ant colony optimization, LBACO）算法，也被稱為ACOsched 算法，通過在聯(lián)盟中尋找最優(yōu)的云資源來執(zhí)行任務(wù)，從而實現(xiàn)任務(wù)的高效分配.實驗結(jié)果表明，ACOsched 算法在聯(lián)盟云中的任務(wù)完成時間有了較為明顯的縮減.由于聯(lián)盟云需要共享資源的特殊性使其無法避免法律合規(guī)等相關(guān)問題，同時較為復(fù)雜的環(huán)境也制約了聯(lián)盟云的推廣，因此除了政府及學(xué)術(shù)組織外少有用戶去使用聯(lián)盟云，這也導(dǎo)致了相關(guān)研究論文較少.

表2 總結(jié)對比了聯(lián)盟云環(huán)境下的任務(wù)調(diào)度算法.現(xiàn)有的聯(lián)盟云環(huán)境下任務(wù)調(diào)度算法，大部分會優(yōu)先根據(jù)實際應(yīng)用場景自定義聯(lián)盟云架構(gòu)，如文獻[40]中針對不同地域的服務(wù)器設(shè)計了聯(lián)盟云架構(gòu)，將該場景下的任務(wù)調(diào)度形式化為成本和最大完成時間的多目標(biāo)優(yōu)化問題，同時將多個云計算節(jié)點互聯(lián)，并通過成本決策函數(shù)的計算結(jié)果，確定何時將任務(wù)分配至聯(lián)盟云中不同的節(jié)點，優(yōu)化了任務(wù)調(diào)度的求解過程.文獻[40-43]等大都以成本、最大完成時間為首要優(yōu)化目標(biāo)，將不同場景中的調(diào)度形式化為單目標(biāo)或多目標(biāo)優(yōu)化問題，以單云環(huán)境下任務(wù)調(diào)度算法為參考，根據(jù)特定目標(biāo)需求對算法進行改進和優(yōu)化[43]，實現(xiàn)在聯(lián)盟云環(huán)境下任務(wù)的高效分配.但這些研究并不會只考慮單一的任務(wù)調(diào)度問題，同時會提出聯(lián)盟云環(huán)境下相關(guān)資源管理、數(shù)據(jù)安全、隱私保護、互操作協(xié)議標(biāo)準(zhǔn)等服務(wù)管理方法，最終實現(xiàn)跨云資源的高效利用[44-45].綜合來看，目前聯(lián)盟云環(huán)境下的任務(wù)調(diào)度研究還不充分，對于共享資源的接口標(biāo)準(zhǔn)、異構(gòu)資源的統(tǒng)一管理等問題還需要深入探討和解決.

Table 2 Comparison of Task Scheduling Algorithms in Federated Cloud Environment表2 聯(lián)盟云環(huán)境下任務(wù)調(diào)度算法對比

3 多云環(huán)境下的任務(wù)調(diào)度算法

3.1 異構(gòu)公有云環(huán)境下的任務(wù)調(diào)度算法

異構(gòu)公有云環(huán)境是由多個不同的IaaS 云服務(wù)供應(yīng)商組成，該環(huán)境下各個云服務(wù)供應(yīng)商相互獨立且互不通信，云服務(wù)使用者需要通過不同的API 將云資源整合或者根據(jù)需求構(gòu)建新的架構(gòu)統(tǒng)一管理云資源.異構(gòu)公有云環(huán)境主要有4 個方面的優(yōu)勢：

1）避免供應(yīng)商鎖定.統(tǒng)一管理多個不同的IaaS云服務(wù)供應(yīng)商使得云服務(wù)使用者擁有多個選擇，避免因某一個供應(yīng)商鎖定而中斷服務(wù).

2）多元化的地理位置.目前，業(yè)界較為領(lǐng)先的云服務(wù)供應(yīng)商已在全球不同，范圍內(nèi)部署建立了數(shù)據(jù)中心.但由于不同國家、地域的法律規(guī)定要求不同，使得云服務(wù)供應(yīng)商無法在所有區(qū)域建立相同的數(shù)據(jù)中心，因此異構(gòu)公有云環(huán)境可以融合多個地域的云服務(wù)提供商，為云服務(wù)使用者提供性能良好且合規(guī)的服務(wù).

3）受外界影響因素較小.近年來，云服務(wù)中斷事件頻發(fā)，單云環(huán)境易受到此類影響，而使用不同云服務(wù)提供商的資源能夠很好地規(guī)避此類情況，同時可以防止因監(jiān)管或法律因素引起的服務(wù)停止，也能在不同地域備份數(shù)據(jù)保證數(shù)據(jù)的完整性和安全性.

4）成本降低.云服務(wù)使用者可以根據(jù)自身需求，結(jié)合各個云服務(wù)供應(yīng)商提供的資源價格來制定更加靈活的經(jīng)濟策略，在滿足自身需求的同時降低使用成本.

文獻[46]提出了一種基于成本最優(yōu)的二進制整數(shù)規(guī)劃算法（binary integer program, BIP），該算法以最小化公有云的成本為基礎(chǔ)，通過二進制整數(shù)規(guī)劃選取成本最優(yōu)的資源進行分配，為異構(gòu)公有云環(huán)境中的任務(wù)調(diào)度提供了易于實現(xiàn)的方案.實驗結(jié)果表明，該算法在成本最小化、可行性和可伸縮性方面都表現(xiàn)得非常好.文獻[47]針對異構(gòu)公有云環(huán)境下的任務(wù)調(diào)度問題，提出了一種基于遺傳算法的任務(wù)調(diào)度算法，該算法采用適應(yīng)度函數(shù)求導(dǎo)和變異的思想，最終以任務(wù)完成時間來評估算法的整體性能.文獻[48]提出了一種基于異構(gòu)公有云環(huán)境的局部關(guān)鍵路徑算法，該算法在異構(gòu)公有云環(huán)境下為任務(wù)調(diào)度過程中部分關(guān)鍵路徑分配子截止時間，從而最大限度地降低工作流任務(wù)的總執(zhí)行成本.文獻[49]提出了一種改進的遺傳算法，其目的是為當(dāng)前任務(wù)在異構(gòu)公有云環(huán)境下找到合適的云資源配置.通過考慮各個云服務(wù)提供商在價格和功能上的不同，以滿足云服務(wù)使用者和應(yīng)用程序的需求.文獻[50]構(gòu)建了一種基于地理位置分布的異構(gòu)公有云環(huán)境服務(wù)組合模型，同時提出了一種具有改進交叉和變異算子的遺傳算法，用于QoS 服務(wù)組合（響應(yīng)時間、成本、可靠性），允許用戶根據(jù)自己的偏好選擇最優(yōu)組合方案.文獻[51]提出了一種新的云代理方法，該方法基于調(diào)度預(yù)測模型，該模型能預(yù)測異構(gòu)公有云環(huán)境中的最低價格，最終為云服務(wù)使用者提供資源的最佳部署建議.文獻[52]提出了一種基于異構(gòu)云環(huán)境下的資源優(yōu)化機制，在此機制上又提出了2 種在線動態(tài)資源分配算法，算法根據(jù)實際任務(wù)執(zhí)行的更新信息來動態(tài)調(diào)整資源分配.實驗結(jié)果表明，所提算法的任務(wù)完成時間和能耗都有了明顯的減少.文獻[53]提出了一種異構(gòu)公有云環(huán)境下的多目標(biāo)任務(wù)調(diào)度算法.實驗結(jié)果表明，該算法在最大完成時間、總成本和云資源平均利用率等性能指標(biāo)上表現(xiàn)較好，同時也實現(xiàn)了最大完成時間和成本之間的平衡.文獻[54]提出了一種基于異構(gòu)公有云環(huán)境下多目標(biāo)科學(xué)工作流調(diào)度算法，該算法在滿足可靠性約束的前提下，使工作流的最大完成時間和成本最小化.該算法基于粒子群優(yōu)化算法（PSO），考慮了任務(wù)執(zhí)行位置和數(shù)據(jù)傳輸順序.文獻[55]設(shè)計了一種基于異構(gòu)公有云環(huán)境的工作流調(diào)度架構(gòu)，該架構(gòu)包括了應(yīng)用隊列、可靠性分析、任務(wù)執(zhí)行成本估算、計劃與調(diào)度、多云系統(tǒng)互聯(lián)等模塊，并設(shè)計了工作流調(diào)度算法，目的是為了提高應(yīng)用程序的執(zhí)行可靠性并降低其成本.實驗表明，在該架構(gòu)下的工作流調(diào)度算法在成本和可靠性方面優(yōu)于現(xiàn)有算法.文獻[56]構(gòu)建了一個多目標(biāo)分布式調(diào)度模型，該模型包括總時間、成本、云吞吐量、能耗、資源利用率和負(fù)載均衡6 個目標(biāo).在該模型中又提出了一種基于正弦函數(shù)的多目標(biāo)智能算法來解決任務(wù)調(diào)度問題，該算法考慮了種群多樣性策略在種群中的變化趨勢與正弦函數(shù)相似.實驗結(jié)果表明，該算法具有良好的調(diào)度效率，提高了系統(tǒng)的安全性，同時該工作為解決物聯(lián)網(wǎng)中數(shù)據(jù)處理的難題提供了一種新的思路.文獻[57]設(shè)計了一種新的基于軟件定義的工作流代理，該代理能夠用于跨多個軟件定義的異構(gòu)數(shù)據(jù)中心部署工業(yè)工作流任務(wù)，同時自動化任務(wù)發(fā)放、數(shù)據(jù)發(fā)放和資源發(fā)放.同時提出了一種基于遺傳算法的自適應(yīng)工業(yè)工作流調(diào)度算法，該算法能夠利用多種軟件定義的云數(shù)據(jù)中心資源.實驗結(jié)果表明，該算法既提高了綠色能源利用率，又降低了成本.文獻[58]提出了一種基于預(yù)算約束的異構(gòu)多云環(huán)境動態(tài)任務(wù)調(diào)度算法，該算法分別提出了2 個版本，第2 版在第1 版的基礎(chǔ)上對算法進行了優(yōu)化和改進.實驗結(jié)果表明，算法的第2 版優(yōu)于第1 版，同時也從最大完工時間的角度證明了算法的有效性.

表3 對異構(gòu)公有云環(huán)境中的任務(wù)調(diào)度算法進行了總結(jié)，可以看出大部分的算法都是依托代理或自行設(shè)計的架構(gòu)，以最大完成時間和成本為主要優(yōu)化目標(biāo)，將不同場景中的調(diào)度建模為單目標(biāo)或多目標(biāo)優(yōu)化問題來進行求解.由于異構(gòu)公有云的特殊性，成本會成為任務(wù)調(diào)度過程中首要考慮的因素，因此存在部分研究將成本優(yōu)化作為算法的重點，通過改進單云環(huán)境下任務(wù)調(diào)度算法來適配異構(gòu)公有云環(huán)境，雖然此方法解決了部分特定場景下的任務(wù)調(diào)度問題，但忽略了任務(wù)調(diào)度的其他評價指標(biāo)，未能實現(xiàn)任務(wù)的高效分配.近年來的研究如文獻[55]為異構(gòu)公有云環(huán)境下的任務(wù)調(diào)度提供了更有價值的參考，文獻[55]中提出的架構(gòu)已經(jīng)最大限度地接近了實際的云環(huán)境，為解決異構(gòu)公有云環(huán)境下的任務(wù)調(diào)度問題提供了較為新穎的解決思路；文獻[56]中基本囊括了異構(gòu)公有云環(huán)境下任務(wù)調(diào)度的主要性能評價指標(biāo)，優(yōu)化目標(biāo)全面，整個系統(tǒng)可靠性強，為該問題的研究提供了更加全面的參考；文獻[59-62]研究了異構(gòu)公有云環(huán)境下的資源調(diào)度等相關(guān)問題，通過文獻[55-56, 59-62]可以發(fā)現(xiàn)資源調(diào)度和任務(wù)調(diào)度密不可分，在新環(huán)境下資源調(diào)度問題的有效解決也會給任務(wù)調(diào)度研究提供新的思路.

Table 3 Comparison of Task Scheduling Algorithms in Heterogeneous Public Cloud Environment表3 異構(gòu)公有云環(huán)境下任務(wù)調(diào)度算法對比

由于異構(gòu)公有云的表述過于復(fù)雜，一般研究中都不會刻意區(qū)分，只是將其稱作“多云”環(huán)境.而“多云”的界定較為模糊，且相關(guān)研究的側(cè)重不一導(dǎo)致此類研究與實際環(huán)境差距較大.近年來公有云的快速發(fā)展使得異構(gòu)公有云環(huán)境正在不斷成為云服務(wù)使用者的最新選擇，但不難發(fā)現(xiàn)目前在該環(huán)境下的調(diào)度問題研究還存在不少困難有待解決.

3.2 公有云、私有云混合環(huán)境下的任務(wù)調(diào)度算法

公有云、私有云混合環(huán)境是目前市場的主流選擇，學(xué)術(shù)界的諸多跨云任務(wù)調(diào)度研究都以此環(huán)境為主，該環(huán)境能同時兼顧公有云和私有云的優(yōu)點，實現(xiàn)難度相對較小.公有云、私有云混合環(huán)境主要有3 個方面的優(yōu)勢：

1）數(shù)據(jù)安全.公有云、私有云混合環(huán)境可以利用公有云多地域的特點，為數(shù)據(jù)提供跨多地域的數(shù)據(jù)備份，同時可以利用私有云獨有的數(shù)據(jù)安全性為數(shù)據(jù)提供最為可靠的保障.

2）彈性擴展.公有云環(huán)境的算力較高，可以有效解決私有云在特殊情況下瞬時算力不足的情況，給云服務(wù)使用者提供了更好的服務(wù)保障.

3）成本降低.公有云的接入降低了云服務(wù)使用者購買IT 的成本，同時云服務(wù)使用者可以根據(jù)需求和公有云的資源價格將任務(wù)選擇分配到公有云還是私有云上，實現(xiàn)了成本的有效降低.

文獻[63]提出了一種混合云環(huán)境下截止時間約束的任務(wù)調(diào)度算法，該算法將最早截止時間優(yōu)先算法進行改進優(yōu)化，算法考慮了計算和數(shù)據(jù)傳輸成本，以及網(wǎng)絡(luò)帶寬限制.實驗結(jié)果表明，該算法能夠很好地適合于規(guī)模較大的混合云環(huán)境.文獻[64]提出了一種混合云優(yōu)化成本調(diào)度算法，該算法先將工作流調(diào)度到私有云上，估算工作流完成時間，之后從公有云租用合適的資源并將其聚合到私有云，以便在截止時間內(nèi)提供足夠的處理能力來執(zhí)行工作流.如果超過截止時間，則選擇優(yōu)先級最高的任務(wù)調(diào)度到能夠確保工作流在截止時間之前完成的、且價格最低的公有云上.文獻[65]提出了一種基于任務(wù)級別的調(diào)度算法，該算法能夠按級別在公有云上尋找最佳資源以節(jié)省成本，并在截止時間內(nèi)能完成工作流任務(wù)的執(zhí)行.算法中還提出了一種工作流的子截止時間的概念，即工作流中單個任務(wù)的截止時間.文獻[66]提出了2 種兼顧最大完成時間和成本的混合云工作流調(diào)度算法.首先提出了一種單目標(biāo)工作流調(diào)度算法，解決在截止時間約束下最小化執(zhí)行成本的單目標(biāo)優(yōu)化問題.然后又提出了一種多目標(biāo)工作流調(diào)度算法，同時解決最小化執(zhí)行成本和最大完成時間的多目標(biāo)優(yōu)化問題.實驗結(jié)果表明，該算法可以更好地實現(xiàn)成本和完成時間的權(quán)衡.文獻[67]提出了一種啟發(fā)式的任務(wù)調(diào)度算法，該算法以任務(wù)調(diào)度的安全性和截止時間作為約束，優(yōu)化了任務(wù)完成數(shù)量和成本.該算法一方面優(yōu)先分配消耗公共云資源最大的任務(wù)，將其分配給本地集群中處理能力最強的服務(wù)器；另一方面如果在本地資源不足的情況時，租用性價比較高的新虛擬機來解決該問題.實驗結(jié)果表明，在未到達截止時間前，該算法的性能較好.文獻[68]提出了一種時間任務(wù)調(diào)度算法，該算法基于綠色數(shù)據(jù)中心和公有云構(gòu)成的混合云環(huán)境，在延遲約束下對任務(wù)進行調(diào)度.綠色數(shù)據(jù)中心的電能是由太陽能、風(fēng)能等綠色能源提供，隨著時間的變化，數(shù)據(jù)中心會產(chǎn)生收益.實驗結(jié)果表明，對比已有的多種算法，該算法能夠獲得更大的利潤，同時也能很好地適應(yīng)綠色數(shù)據(jù)中心和公有云構(gòu)成的混合云環(huán)境.文獻[69]提出了一種基于遺傳算法的單目標(biāo)任務(wù)調(diào)度算法，該算法在交叉、選擇和控制調(diào)節(jié)參數(shù)方面進行了改進.文獻[69]在單目標(biāo)任務(wù)調(diào)度算法的基礎(chǔ)上又提出了一種改進的多目標(biāo)調(diào)度算法，該算法結(jié)合了NSGA-Ⅱ算法中基于帕累托最優(yōu)的快速排序的方法.實驗結(jié)果表明，這2 種算法都能在混合云環(huán)境下有效提升任務(wù)調(diào)度的性能.

表4 對文獻[63-69]中公有云、私有云混合環(huán)境下的任務(wù)調(diào)度算法進行了對比總結(jié)，可以看出與聯(lián)盟云環(huán)境及異構(gòu)公有云環(huán)境下的任務(wù)調(diào)度算法相同，公有云、私有云混合環(huán)境下大部分的算法都是以單云環(huán)境下任務(wù)調(diào)度算法為參考，根據(jù)應(yīng)用場景中的不同需求將調(diào)度問題抽象成為單目標(biāo)或多目標(biāo)優(yōu)化問題并結(jié)合實際環(huán)境對參考算法進行改進和優(yōu)化.公有云、私有云混合環(huán)境在實際應(yīng)用中較為廣泛，成本是該環(huán)境下任務(wù)調(diào)度需要考慮的首要因素，現(xiàn)有的研究中大部分算法都以成本作為優(yōu)化目標(biāo)對任務(wù)調(diào)度進行求解.但在實際應(yīng)用中，私有云上的資源大都是安全性需求較高的內(nèi)部資源，任務(wù)調(diào)度過程中更應(yīng)該關(guān)注云服務(wù)使用者對于安全性的需求，同時環(huán)境中的其他影響因素如能耗、資源利用率、可靠性、負(fù)載均衡等性能指標(biāo)也應(yīng)當(dāng)考慮在內(nèi)并進行深入的研究和討論.

Table 4 Comparison of Task Scheduling Algorithms in Public Cloud and Private Cloud Hybrid Environment表4 公有云、私有云混合環(huán)境下任務(wù)調(diào)度算法對比

4 總結(jié)與展望

目前，針對單云環(huán)境下的任務(wù)調(diào)度算法研究較為充分，不少國內(nèi)外學(xué)者已經(jīng)提出了性能較好的調(diào)度算法并在真實的云環(huán)境中得到了驗證.但由于單云環(huán)境存在架構(gòu)瓶頸、資源上限、易被供應(yīng)商鎖定等問題，現(xiàn)已無法滿足龐大的數(shù)據(jù)量及日益增長的服務(wù)需求.跨云環(huán)境的提出有效地解決了這些問題，目前國內(nèi)外學(xué)者針對跨云環(huán)境從跨云資源管理架構(gòu)、跨云資源調(diào)度、跨云任務(wù)調(diào)度等方面已經(jīng)開展了多年的討論研究并取得了一定的進展，但跨云環(huán)境是對云計算資源的重組和聚合，資源在跨云環(huán)境中呈現(xiàn)了異構(gòu)性、分散性、復(fù)雜性和多樣性的特點，這使得任務(wù)調(diào)度的難度大大增加，部分特定場景的需求仍然得不到滿足，跨云環(huán)境下的任務(wù)調(diào)度算法還需要不斷進行深入地研究.

本文以跨云環(huán)境為出發(fā)點介紹了跨云環(huán)境的不同分類，在此分類下對任務(wù)調(diào)度算法進行了整理分析，通過梳理觀察得出3 個方面的建議：

1）現(xiàn)有任務(wù)調(diào)度算法未能有效考慮跨云架構(gòu)的特點，普適性不強.跨云環(huán)境下的任務(wù)調(diào)度算法研究目前主要集中于異構(gòu)公有云環(huán)境及公有云、私有云混合的環(huán)境，其中公有云、私有云混合的環(huán)境是目前市場的主流選擇.由于跨云環(huán)境較為復(fù)雜，現(xiàn)有的研究大部分是根據(jù)具體需求將多種云資源合并，在此基礎(chǔ)上考慮任務(wù)調(diào)度，而從構(gòu)建跨云架構(gòu)角度出發(fā)考慮任務(wù)調(diào)度問題的研究很少，這導(dǎo)致任務(wù)調(diào)度算法僅能在特定的環(huán)境中運行，雖有一定的參考價值但普適性不強.

未來研究中，可以從構(gòu)建普適性較強的跨云架構(gòu)角度出發(fā)，以更好的擴展性將更多的云資源甚至邊緣資源整合[70-71]，以統(tǒng)一的API 屏蔽底層基礎(chǔ)設(shè)施的差異，并在此基礎(chǔ)上提出更為有效的任務(wù)調(diào)度算法.

2）現(xiàn)有任務(wù)調(diào)度算法以改進單云環(huán)境下任務(wù)調(diào)度算法為主，創(chuàng)新性不足.跨云環(huán)境下任務(wù)調(diào)度算法研究正在不斷深入，現(xiàn)有的研究多數(shù)是以單云環(huán)境下任務(wù)調(diào)度算法作為參考，再結(jié)合跨云環(huán)境中新的需求進行改進、優(yōu)化，雖然能夠解決部分問題但這些算法在跨云環(huán)境中并不能全部適用，無法與其他算法進行對比，缺少一定的針對性和創(chuàng)新性.

未來研究中，可以針對跨云環(huán)境的特點，結(jié)合未在跨云環(huán)境中使用過的強化學(xué)習(xí)、模糊排序等算法，提出更新穎、更高效、更實用的跨云環(huán)境下任務(wù)調(diào)度算法.

3）現(xiàn)有任務(wù)調(diào)度算法優(yōu)化目標(biāo)較少且評價指標(biāo)不完善，無法準(zhǔn)確評估算法性能.現(xiàn)有的跨云環(huán)境下任務(wù)調(diào)度算法多是以成本及最大完成時間作為優(yōu)化目標(biāo)，雖然在跨云環(huán)境中取得了一定的效果，但未考慮環(huán)境中諸如可靠性、能耗等其他因素，優(yōu)化目標(biāo)過于單一且缺少多維度評價指標(biāo).

未來研究中，可結(jié)合實際應(yīng)用環(huán)境，將任務(wù)的執(zhí)行時間、完成時間、資源利用率、可靠性、成本、網(wǎng)絡(luò)吞吐量、可伸縮性能、能耗等優(yōu)化參數(shù)考慮在內(nèi)，增加對應(yīng)優(yōu)化目標(biāo)，更加全面地考慮環(huán)境中影響算法性能的因素，提出跨云環(huán)境下任務(wù)調(diào)度算法的多維度評價指標(biāo)，更加全面地驗證算法的性能，保證任務(wù)調(diào)度算法的高效性.

隨著國家新基建政策的實施，云計算基礎(chǔ)設(shè)施將得到更加有力地發(fā)展和支持，云計算與邊緣計算、物聯(lián)網(wǎng)等新興技術(shù)的深度融合，將使跨云環(huán)境成為更多云服務(wù)使用者的選擇，研究和提出更具實用性的跨云環(huán)境下任務(wù)調(diào)度算法更貼近解決現(xiàn)實問題.未來跨云環(huán)境會愈加復(fù)雜，跨云環(huán)境下任務(wù)調(diào)度算法將會迎來更多的挑戰(zhàn).

作者貢獻聲明：唐續(xù)豪撰寫論文；劉發(fā)貴提出了撰寫方面的建議；王彬?qū)φ撐倪M行了修改，并負(fù)責(zé)部分文獻的整理分類；李超對論文進行了修改及審閱校對；蔣俊對論文的總體架構(gòu)提出了意見，并對論文進行了審閱校對；唐泉對論文進行了修改及審閱校對；陳維明和何鳳文對論文進行了審閱校對并提供了實際參考案例.