孫默辰 邵清

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

關(guān)鍵詞：云計算;任務(wù)調(diào)度;容錯;粒子群優(yōu)化;檢查點技術(shù)

DOI：10. 11907/rjdk. 191566 開放科學(xué)（資源服務(wù)）標(biāo)識碼（OSID）：

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

英標(biāo)：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 引言

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

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

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

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

1 問題描述

在云計算環(huán)境下任務(wù)調(diào)度指建立任務(wù)與資源之間的映射，資源處理能力越高，表明調(diào)度到該資源上的任務(wù)處理時間越短。

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

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

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

本文針對任務(wù)調(diào)度模型作出如下假設(shè)：

假設(shè)1：各任務(wù)之間沒有依賴關(guān)系，資源性能可滿足每個任務(wù)的要求。

假設(shè)2：所有任務(wù)可被完全分配。

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

2 算法設(shè)計

本文設(shè)計一種結(jié)合改進粒子群優(yōu)化與檢查點技術(shù)的容錯調(diào)度算法。通過尋求粒子群最優(yōu)解獲取最佳資源，減少調(diào)度復(fù)雜性，并在任務(wù)執(zhí)行過程中設(shè)置檢查點，通過回卷恢復(fù)機制實現(xiàn)容錯效果。

2.1 粒子群優(yōu)化方案

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

2.1.1 速度操作算法設(shè)計

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

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

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

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

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

2.1.2 慣性權(quán)重設(shè)計

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

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

本文對ω進行改進，使搜索過程具有非線性自適應(yīng)動態(tài)調(diào)節(jié)的特點。具體公式為：

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

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

2.2 檢查點設(shè)置與恢復(fù)實現(xiàn)

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

2.2.1 檢查點設(shè)置

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

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

2.2.2 恢復(fù)實現(xiàn)

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

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

其中[Ri（mi）]為檢查點設(shè)置時間與故障檢測時間及故障恢復(fù)時間之和。故障恢復(fù)時間是在任務(wù)執(zhí)行時間內(nèi)，故障發(fā)生次數(shù)與最大故障恢復(fù)開銷的乘積。

2.3 算法流程

基于改進粒子群優(yōu)化與檢查點技術(shù)的容錯調(diào)度算法流程如圖4所示。

算法步驟描述如下：

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

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

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

步驟4：在最佳資源上執(zhí)行任務(wù)。

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

步驟6：判斷所有任務(wù)是否執(zhí)行完成，若未完成，執(zhí)行步驟2尋找最佳資源執(zhí)行任務(wù);若完成，則結(jié)束任務(wù)。

3 實驗研究

3.1 實驗方案

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

從圖5可知，任務(wù)完成時間的減少及任務(wù)完成率的提高表示改進粒子群優(yōu)化算法性能在一定范圍內(nèi)，隨迭代次數(shù)的增加逐漸提高，但當(dāng)?shù)螖?shù)達到300次后，兩項性能指標(biāo)曲線趨于穩(wěn)定，為確保完整算法性能穩(wěn)定，本文設(shè)定迭代次數(shù)為300次。

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

3.2 實驗結(jié)果與分析

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

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

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

4 結(jié)語

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

參考文獻：

[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] 張鵬，王桂玲，徐學(xué)輝. 云計算環(huán)境下適于工作流的數(shù)據(jù)布局方法[J]. 計算機研究與發(fā)展，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] 劉永.云計算技術(shù)研究綜述[J]. 軟件導(dǎo)刊，2015，14（9）：4-6.

[6] 胡瑩.云計算及其關(guān)鍵技術(shù)研究[J]. 軟件導(dǎo)刊，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] 王勇， 劉美林， 李凱，等. 云環(huán)境下基于可靠性的均衡任務(wù)調(diào)度算法研究[J]. 計算機科學(xué)，2015，42（S1）：325-331.

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

[10] 薩日娜. 基于蟻群粒子群優(yōu)化算法的云計算資源調(diào)度方案[J]. 吉林大學(xué)學(xué)報：理學(xué)版，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] 王吉，包衛(wèi)東，朱曉敏. 虛擬化云平臺中實時任務(wù)容錯調(diào)度算法研究[J]. 通信學(xué)報，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] 劉志雄. 求解調(diào)度問題的粒子群算法編碼方法研究[J]. 武漢科技大學(xué)學(xué)報，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.

（責(zé)任編輯：江 艷）