云環境下結合改進粒子群優化與檢查點技術的容錯調度算法

孫默辰 邵清

摘 要：云計算環境中任務執行容易受資源故障影響，導致調度效率與成功率降低。針對該問題，提出一種結合改進粒子群優化與檢查點技術的容錯調度算法。通過改進粒子群優化算法進行全局搜索，尋找粒子群最優解，以保證任務獲取最優資源，減少調度復雜度;同時通過設置檢查點，使失效任務從檢查點繼續執行，實現任務動態恢復，提高調度可靠性。仿真實驗表明，與傳統算法相比，當任務數量不斷增加時該算法可提高任務執行成功率，縮短任務執行時間。

關鍵詞：云計算;任務調度;容錯;粒子群優化;檢查點技術

DOI：10. 11907/rjdk. 191566 開放科學（資源服務）標識碼（OSID）：

中圖分類號：TP312文獻標識碼：A 文章編號：1672-7800（2020）002-0007-05

英標：Fault-tolerant Scheduling Algorithm Based on Improved Particle Swarm Optimization in Cloud Environment

英作：SUN Mo-chen，SHAO Qing

英單：（School of Optical-Electrical and Computer Engineering，University of Shanghai for Science and Technology，Shanghai 200093，China）

Abstract：Task execution is susceptible to resource failures in cloud computing environment which leads to a reduction in scheduling efficiency and success rate. In order to solve this problem， a fault-tolerant scheduling algorithm based on improved particle swarm optimization and checkpoint technology is proposed. Firstly， the particle swarm optimization algorithm is used for global search to find the optimal solution， and it will ensure that the task gets the optimal resources and reduces the complexity of the task scheduling. At the same time， by setting a checkpoint， the invalid task is continuously executed from the checkpoint to achieve dynamic recovery of the task and improve scheduling reliability. Simulation experiments show that as the number of tasks increases， the algorithm can improve the success rate of task execution and also shorten the task execution time when compared with the traditional algorithm.

Key Words：cloud computing; task scheduling; fault tolerance; particle swarm optimization; checkpoint technology

0 引言

在互聯網時代，信息量呈不斷增大趨勢，目前已進入大數據時代[1]。互聯網已融入公眾日常生活，但原有的計算機模式已不能滿足處理海量數據的需求[2]。為了更好地處理海量數據信息，在計算機和網絡技術基礎上，云計算作為一種新興的計算范式[3-6]，受到業界和學術界的關注。作為未來重要行業領域的主流IT應用模式，云計算將為重點行業用戶信息化建設與IT運維管理工作奠定核心基礎，并助力行業迅速發展。

云計算面對的計算任務數量龐大，任務調度和資源分配問題是決定云計算效率的重難點[7]，同時在處理數據過程中會產生大量、重要的中間數據，因此數據可靠性也是亟待解決的重點問題，即完善的容錯機制對云計算必不可少[8]。從云環境下的任務容錯調度需求出發，在確保每個任務被分配到最佳資源上的同時，盡可能減少故障對任務調度產生的影響。檢查點技術是一種常用的容錯方法，通過設置檢查點和回卷恢復機制可使失效任務重新恢復執行，從而提高調度可靠性[9]。

針對云計算任務調度與容錯技術，國內外學者進行了相應研究，并提出了很多算法，如文獻[10]分別對蟻群算法和粒子群算法（Particle Swarm Optimization，PSO）進行改進，綜合兩種算法的優勢建立一種蟻群粒子群算法，以提高云計算資源調度效率;文獻[11]提出一種多種服務質量QoS（Quality of Service）約束離散粒子群優化的任務調度算法，該算法在滿足調度截止期的情況下具有較高的可靠性，并且對Makespan性能影響較小，但是以上算法均沒有考慮系統容錯問題，導致任務調度成功率較低;文獻[12]提出一種虛擬化云平臺中的容錯調度算法，通過主副版本方法實現對物理主機的容錯，有效提高了資源利用率，但是時間成本較高;文獻[13]提出一種基于任務備份的云計算容錯調度算法，根據云計算的安全等級對任務進行備份，重新調度失效任務，具有較好的容錯性，但是資源調度效率較低。

上述算法均沒有將任務調度與容錯機制有效結合。因此本文提出一種基于改進粒子群優化與檢查點技術的容錯調度算法（FTCM-PSO），在確保每個任務被分配至最佳資源的基礎上，同時通過設置檢查點，使失效任務從檢查點繼續執行，實現任務動態恢復，提高調度可靠性。仿真實驗表明，與傳統算法相比，該算法能夠提高任務執行成功率，同時任務執行時間也有一定程度縮短。

1 問題描述

在云計算環境下任務調度指建立任務與資源之間的映射，資源處理能力越高，表明調度到該資源上的任務處理時間越短。

在一次全局分配α中，用戶提交的任務t被分配到各個資源VM中，資源負載情況和計算能力將隨之變化，僅通過查看資源配置參數無法正確呈現資源性能變化，為了正確展示資源性能變化情況，用公式（1）、公式（2）計算資源負載情況。

其中[vmi]表示資源編號，[Pi]表示資源性能參數，[L（α）i]表示某個任務開始時資源的當前負載，[Tmax（α）i]表示分配到資源[vmi]上所有任務執行完成時間，[lenti]表示分配到資源[vmi]上所有任務長度，本文用任務長度表示任務大小，[Bi]代表資源[vmi]可用帶寬，所以每當一個新任務分配到資源[vmi]上后，對應任務執行時間[Tmax（α）i]均隨之變化。此外，本文引入檢查點技術為任務調度提供容錯機制，因此對于任務[tj]在資源[vmi]上的執行時間計算公式為：

其中，[mi]表示任務[ti]的檢查點數量，[Gi]表示檢查點設置時間開銷，[δi]為故障檢測時間開銷，[Ci]為資源故障發生次數，[μi]為卷回恢復時間開銷。在任務到達資源之前，每個資源均有默認的參數，例如處理器速度、當前負載和帶寬。這些參數將被用來計算資源處理任務的能力，本文采用改進粒子群優化算法獲取適應度高的最優粒子，它代表全局最佳資源，即該資源處理任務能力最高。任務調度是建立任務與資源之間的映射，資源處理任務能力越高，表明任務執行時間越短。算法目標是找到全局最佳資源，并將任務分配到該資源上，從而減少任務執行時間。用[TVij]表示資源[vmi]對任務[tj]的處理能力，MIPSi表示處理器速度，[1-L（α）i]表示當前資源所剩負載大小。因此在云環境任務調度問題中，求最小完成時間的問題可轉化為求函數優化問題，目標函數為：

本文針對任務調度模型作出如下假設：

假設1：各任務之間沒有依賴關系，資源性能可滿足每個任務的要求。

假設2：所有任務可被完全分配。

假設3：資源是被獨占而非共享的，一個資源只能被一個任務占用。

2 算法設計

本文設計一種結合改進粒子群優化與檢查點技術的容錯調度算法。通過尋求粒子群最優解獲取最佳資源，減少調度復雜性，并在任務執行過程中設置檢查點，通過回卷恢復機制實現容錯效果。

2.1 粒子群優化方案

由于任務調度是離散問題，在應用粒子群算法時[14-15]，應使用離散的數值對粒子進行編碼，將任務調度與粒子位置、速度等結合起來。本文對粒子群算法中的粒子使用間接編碼的方式[16]。

2.1.1 速度操作算法設計

假設存在t個任務，將這t個任務分割成m個子任務，資源數量為n個，則粒子可編碼為公式（5）所示的m維向量。

其中，i表示種群中第i個個體，j表示個體的第j維，其中1≤j≤m，xij表示[1，n]范圍內的自然數。例如設置t=2，m=7，n=4。粒子可編碼為（3，4，2，1，4，2，3，1，3，4），如表1所示，每個粒子均代表一種調度方案，通過對粒子解碼可知任務分配情況。

為獲得子任務在計算資源上的分布情況，對已編碼的粒子進行相應解碼。由表1中的粒子編碼情況，對粒子進行解碼，結果如表2所示。

通過表2解碼可知，計算資源1用來執行子任務{4}，由此可知子任務{3， 6}、{1， 7}、{2， 5}，分別分配到計算資源2、3、4。

設種群規模為NP，即為系統隨機初始化NP個粒子。xij、vij表示將第j個任務分配到第i個資源上后粒子位置和速度。其中1≤i≤NP，初始化vij的值設置為[-vmax，vmax]之間的隨機數。每個粒子在更新自己速度和位置時均根據自己搜索到的歷史最佳點和群體內其它粒子搜索的歷史最佳點兩個值進行迭代更新，粒子根據公式（6）、（7）更新自己的速度和位置。

2.1.2 慣性權重設計

在速度更新公式中引入慣性權重ω[17]，通過ω的選取影響全局和局部搜索能力。

在標準粒子群算法中通常使用固定值的慣性權重ω值，但是通過閱讀大量文獻發現，當使用動態的慣性權重ω值時，改進的粒子群優化算法可以得到更好的收斂結果。在算法初期使用較大的ω值，使搜索步伐加大，隨著迭代次數的不斷增加，逐漸減小ω值，縮小搜索步伐，防止錯過最優解。因此使用一個合適的動態慣性權重值可以平衡算法的全局和局部搜索能力，使算法可以在使用最少迭代次數的同時得到最優結果。

本文對ω進行改進，使搜索過程具有非線性自適應動態調節的特點。具體公式為：

其中，tmax表示最大迭代次數，t表示當前迭代次數，ωmax和ωmin分別表示慣性權重ω的最大值、最小值，由于慣性權重ω常在[0.4， 0.9]之間變化，因此ωmax=0.9，ωmin=0.4。為了測試參數n對慣性權重ω的影響，對n取[0.5， 2.0]之間的數值進行驗證。

如圖1所示，當n較小時，隨著迭代次數的增加，ω減小速度過快，不利于后期局部搜索;當n為1時，ω呈線性變化;而當n過大時，ω較早收斂為0。實驗表明當n=1.5時，ω的變化滿足迭代后期緩慢減小的要求，因此取參數n=1.5。

2.2 檢查點設置與恢復實現

檢查點技術可定期保存任務執行狀態[18]，并在任務執行出錯后從檢查點位置恢復執行，這是故障恢復的一種重要方法，但需要合理設置檢查點，以減少任務執行開銷。

2.2.1 檢查點設置

在檢查點技術中，檢查點文件是一個重要的概念，存儲和故障后的回滾均依賴檢查點文件。為了盡量減少檢查點的設置開銷，在檢查點文件的生成過程中，檢查進程哪些部分發生了變化，如果發生了變化，則更新進程。檢查點恢復技術原理如圖2所示。

在檢查點恢復技術中，檢查點的設置間隔與任務執行總時間存在如下關系：檢查點間隔較短，則設置檢查點的代價較大，導致任務執行總時間可能變長;相反，檢查點間隔較長，則導致故障發生時從上一檢查點重新執行的時間代價較大，因此檢查點間隔的設置對任務執行的時間至關重要。本文通過等距檢查點設置算法，確保在任務執行過程中，保持檢查點間隔不變。如果任務執行時間為T，檢查點設置開銷為G，故障上限是k，采用固定檢查點間隔τ=可使任務在最壞情況下的執行時間最短。

2.2.2 恢復實現

在云計算任務調度下，任務T={t1， t2，…， tn}的配置屬性可由7元組〈Ti， Di， Ci， mi， Gi， δi， μi〉表示，其中Ti、Di、Ci分別表示任務ti的到達時間、截止時間、最壞執行時間，且Ci

基于該模型，在任務可能發生多次故障的情況下，同時考慮檢查點設置開銷、故障檢測開銷、故障恢復開銷，即任務故障響應時間的計算公式Ri（mi）為：

其中[Ri（mi）]為檢查點設置時間與故障檢測時間及故障恢復時間之和。故障恢復時間是在任務執行時間內，故障發生次數與最大故障恢復開銷的乘積。

2.3 算法流程

基于改進粒子群優化與檢查點技術的容錯調度算法流程如圖4所示。

算法步驟描述如下：

步驟1：初始化NP個粒子的位置和速度。

步驟2：通過公式（6）、公式（7），不斷更新粒子的位置和速度。

步驟3：判斷是否達到了最大迭代次數，如果達到即找到適應度高的最優粒子即最佳資源，將任務分配到該資源上;如果沒有達到，則回到步驟2。

步驟4：在最佳資源上執行任務。

步驟5：判斷任務是否完成，若任務未完成，判斷任務是否執行失敗，若任務失敗：讀取最近一次保存檢查點信息，記錄資源故障次數，從上次保存的狀態重新執行失敗任務，然后執行步驟4;若任務成功：保存檢測點信息然后繼續執行步驟4;若任務完成，記錄任務完成總時間。

步驟6：判斷所有任務是否執行完成，若未完成，執行步驟2尋找最佳資源執行任務;若完成，則結束任務。

3 實驗研究

3.1 實驗方案

首先，為驗證迭代次數對改進粒子群算法性能的影響，設定迭代次數的范圍為100～400，粒子群大小為50，記錄執行完成200個任務所需的時間和任務完成率，將兩項結果轉化成相對值在一個圖形中展示。

從圖5可知，任務完成時間的減少及任務完成率的提高表示改進粒子群優化算法性能在一定范圍內，隨迭代次數的增加逐漸提高，但當迭代次數達到300次后，兩項性能指標曲線趨于穩定，為確保完整算法性能穩定，本文設定迭代次數為300次。

其次，為了驗證本文算法性能，利用云平臺CloudSim構建實驗環境，設定20個不同執行能力的資源且每個資源下的機器數量從10～20不等。在本次實驗中，主要觀察不同任務數對算法性能的影響，即規定在一定時間范圍內執行50～300個不同大小的任務，為便于計算，假設在任務執行過程中僅發生一次故障。環境和模擬參數如表3所示。

3.2 實驗結果與分析

為了驗證本文融合檢查點技術的容錯調度算法（FTCM-PSO）的有效性，將其與基于蟻群優化的容錯調度算法（ACOwFT）[19]、基于粒子群優化的多目標任務調度算法（TSPSO）[20]進行對比分析。為了獲取更精確的測量結果，進行10次實驗后取其平均值。

由圖6可知，在任務數量較少時，因為FTCM-PSO算法設置檢查點造成的時間開銷，導致任務執行時間略高于TSPSO算法，FTCM-PSO算法與ACOwFT算法的表現相當。然而，隨著任務數量的增加，本文FTCM-PSO算法可在任務將要執行時對資源作出更好的選擇，將任務分配到最佳資源上執行，并且在執行過程中遇到資源故障時，可直接把任務進程恢復到檢查點時刻的狀態繼續運行，從而大幅縮短任務執行時間，且隨著任務數量的繼續增加，執行時間差距逐漸增大，本文算法優勢會愈加明顯。

從圖7可看出，隨著任務數量的增加，3種算法的錯失率均在增加，但是相比不具有容錯機制的TSPSO算法，其它兩種算法的錯失率相對較低，本文算法有明顯優化效果。

4 結語

為了提高云計算下任務調度算法的容錯性能，本文通過引入檢查點技術，利用檢查點設置和回卷恢復技術，縮短了任務總執行時間，提高了資源利用率。同時，在任務分配期間，通過改進粒子群優化算法的粒子搜索能力，選擇最佳資源，不但能縮短任務執行時間，還降低了任務執行錯失率。仿真實驗表明，該算法在容錯性能上優于ACOwFT算法和TSPSO算法，調度可靠性進一步提高。

參考文獻：

[1] WIN T Y， TIANFIELD H， MAIR Q. Big data based security analytics for protecting virtualized infrastructures in cloud computing[J]. IEEE Transactions on Big Data，2018，4（1）：11-25.

[2] WU J X. Thoughts on the development of novel network technology[J]. Science China（Information Sciences），2018，61（10）：144-154.

[3] 張鵬，王桂玲，徐學輝. 云計算環境下適于工作流的數據布局方法[J]. 計算機研究與發展，2013，50（3）：636-647.

[4] BUYYA R， GARG S K， CALHEIROS R. SLA-oriented resource provisioning for cloud computing： challenges， architecture， and solutions[C]. International Conference on Cloud and Service Computing， 2011：1-10.

[5] 劉永.云計算技術研究綜述[J]. 軟件導刊，2015，14（9）：4-6.

[6] 胡瑩.云計算及其關鍵技術研究[J]. 軟件導刊，2016，15（8）：159-161.

[7] MAZHAR B， JALIL R， KHALID J， et al. Comparison of task scheduling algorithms in cloud environment[J]. International Journal of Advanced Computer Science and Applications，2018，6（4）：384-390.

[8] 王勇， 劉美林， 李凱，等. 云環境下基于可靠性的均衡任務調度算法研究[J]. 計算機科學，2015，42（S1）：325-331.

[9] 楊娜， 劉靖. 融合容錯需求和資源約束的云容錯服務適配方法[J]. 計算機科學，2017，44（7）：61-67.

[10] 薩日娜. 基于蟻群粒子群優化算法的云計算資源調度方案[J]. 吉林大學學報：理學版，2017，55（6）：1518-1522.

[11] WANG Y， LIU Y G， GUO J F， et al. QoS scheduling algorithm in cloud computing based on discrete particle swarm optimization[J]. Computer Engineering，2017，43（6）：111-117.

[12] 王吉，包衛東，朱曉敏. 虛擬化云平臺中實時任務容錯調度算法研究[J]. 通信學報，2014，35（10）：171-180，191.

[13] GULER B， OZKASAP O. Efficient checkpointing mechanisms for primary-backup replication on the cloud[J]. Concurrency and Computation： Practice and Experience，2018，30（21）：e4707.

[14] ZHANG Y， YANG R. Cloud computing task scheduling based on improved particle swarm optimization algorithm[C]. IECON 2017 - 43RD Annual Conference Of The IEEE Industrial Electronics Society，2017：8768-8772.

[15] WANG Q， FU X L， DONG G F. et al. Research on cloud computing task scheduling algorithm based on particle swarm optimization[J]. Journal of Computational Methods in Sciences and Engineering，2018，8（9）：1-9.

[16] 劉志雄. 求解調度問題的粒子群算法編碼方法研究[J]. 武漢科技大學學報，2010，33（1）：99-104.

[17] LI X G， ZHU E Z， ZHANG Y W. A novel computation method for adaptive inertia weight of task scheduling algorithm[J]. Computer Research and Development，2016，53（9）：1990-1999.

[18] HE Z Z， MEN C G， LI X. Schedulability of fault-tolerant real-time system based on checkpoint interval optimization[J]. Journal of Jilin University，2014，44（2）：433-439.

[19] IDRIS H， EZUGWU A E， JUNAIDU S B， et al. An improved ant colony optimization algorithm with fault tolerance for job scheduling in grid computing systems[DB/OL]. http：//europepmc.org/backend/ptpmcrender.fcgi？accid=PMC5435234&blobtype=pdf.

[20] JENA R K. Multi-objective task scheduling in cloud environment using nested PSO framework[J]. 3RD International Conference on Recent Trends in Computing，2015，57：1219-1227.

（責任編輯：江 艷）