基于可信任度的任務調度策略研究?

邢艷芳 秦 軍

（中國傳媒大學南廣學院 南京 211172）

1 引言

隨著信息技術的快速發展和普及應用，大規模的數據處理需求日益增加，傳統的并行計算機難以提供足夠的存儲空間和計算資源進行處理，云計算技術為解決海量數據處理提供了良好的環境。Ma?pReduce 是云計算進行海量數據處理的分布式計算模型，它簡化了分布式并行程序的編寫。

MapReduce 并行編程模型改變了大規模數據集的計算方式，并且在分布式計算領域發揮著重要的作用，但是MapReduce編程模型的性能上仍然存在一些問題。MapReduce 編程模型設計的目的是用數量龐大的工作節點處理海量數據，因此這也就要求MapReduce 要能夠快速地處理發生的機器故障。在MapReduce 編程模型中，JobTracker 節點會定期ping 每個TaskTracker 節點，如果TaskTracker節點在規定時間內沒有響應信息，該節點就會被標記為失效。失效的節點上完成的所有任務都將會被設置為未執行狀態，并被分配在其他TaskTracker節點上重新執行。這種容錯機制開銷大，效率低，浪費了大量資源［1～3］。

在MapReduce 并行編程模型中，系統將Task?Tracker 節點的失效作為一種常態，即不需要特殊處理，一般情況只是將失效節點的任務調度到其他節點上執行。由于在失效的節點上所完成的Map任務都是存儲在本地磁盤上，因此所有完成的map任務都要重新執行。本文從任務調度的角度對MapReduce 的性能進行優化，提出引入節點失效恢復機制的可靠性任務調度策略。對云環境中的資源節點進行可信任度評估，建立可信任度模型，避免任務分配到可靠性低的節點，造成任務重新調度執行，浪費時間和資源［4～6］。

2 可信任度度量指標

可信任度是對系統或產品的可靠性評估的參數。一般來說可靠性是指某一系統或產品是可信任或可信賴的。對某一系統或產品而言，如果能按照用戶要求正常完成任務，就可以認為它是可靠的；但是如果它不能按照用戶的要求持續工作完成任務，那么我們就認為它是不可靠的。對任一產品而言，其可靠性越高，用戶對其的可信任度就越高。同理可知，產品可靠性越低，用戶對其的可信任度也就越低。可靠性越高的產品可以穩定工作的時間就越長。從對可靠性的定義來看，可靠性是指用戶對系統可信賴程度的一種度量，即系統在規定條件和時間內，完成用戶指定的任務，在任務運行期間不引起系統發生失效的可能性。從廣義上來說，可靠性是用戶對系統或產品主觀判斷的結果，也就是用戶對系統或產品的可信任程度。但是為了對可靠性進行量化，工業界對某一產品或系統的可靠性通過其最長無故障連續工作時間來衡量。工作時間越長，其發生故障的概率也就越高。

2.1 可信任度

可信任度是指根據用戶要求，在規定時間t內，系統完成指定任務的概率，它用一個時間函數表示：

T 代表發生故障前的工作時間。不可信任度與可信任度是互補的關系，不可信任度又稱之為失效概率，失效概率F也是一個時間函數，即

由上述定義可知，可信任度和不可信任度都是針對一定時間而說的。對同一產品或系統來說，如若工作時間不同，那么產品或系統的可信任度和不可信任的也會不一樣。

2.2 失效率

失效率是指工作到時間t 這一刻，產品或系統還沒有發生失效，在時間t 時刻以后的下一個單位時間內系統發生失效的概率。失效率是系統或產品進行可靠性分析的常用數量特征，產品或系統發生失效的概率越高，其可信任度就越低。系統或產品在正常工作的情況下，其失效率慢慢穩定時，假設系統或產品的失效率服從指數分布，可信任度和失效率的關系為

3 可信任度模型

定義1：節點模型［7］。假設云環境下的節點是異構的，N 中的每一個節點Nj性能上都存在差異。本文將要研究的節點模型刻畫為一個無向圖G（T，E），節點集合：N=｛N1，N2……，Nm｝，m 為節點個數。E 代表圖的邊集合，主要用來表示節點之間的相互聯系。對于不同的節點而言，其計算能力各有高低；同一個任務在不同的節點上的響應時間也有所不同。為了記錄任務在不同節點上的響應時間，我們用一個n*m 的矩陣RT 表示，RTij表示任務i 在節點j上的運行時間。為了表示節點之間傳遞的信息量，我們用一個m*m 階的矩陣TI 表示節點之間的通信量，其中節點a 和節點b 之間的通信量表示為TIab。在無向圖G（T，E）中，虛擬機之間彼此相互獨立，沒有依賴關系。

定義2：任務響應時間Tij是指所有任務都執行完成返回結果所花費的時間，主要包括任務等待時間WTij、任務傳輸時間CTij和任務執行時間RTij。

定義3：可信任度。本文主要從節點失效率和失效修復率兩方面考慮節點的可信任度。節點出現故障的情況主要是節點和節點之間的通信鏈路以及節點自身是否發生故障。失效恢復分布可恢復失效和不可恢復失效，通信鏈路失效是不可恢復失效。我們定義Ιk表示節點是否可恢復，如果是不可恢復失效那么Ιk為0，否則Ιk為1。

假設節點出現故障的概率和節點之間通信鏈路發生故障的概率分別服從參數為σ和ξ的泊松分布，則在時間間隔［0，t］內節點發生故障p次的概率λp(t)=e-σt/p!，同理可知通信鏈路在時間間隔［0，t］內通信鏈路失效p次的概率θp(t)=e-ξt/p!。假設節點出現故障可恢復的概率服從參數為ε的泊松分布，其中通信鏈路發生故障時不可恢復的。假設節點在時間間隔［0，t］內節點修復p 次的概率μp(t)=e-εt/p!。

定義Pj(t)為在時間間隔［0，t］內節點j 上沒有發生故障（即p=0）的概率，其概率值為

定義Cj(t)為在時間間隔［0，t］內節點a 和節點b 的通信鏈路上沒有發生故障（即p=0）的概率，其概率值為

式（7）中TIab/Netab表示節點之間在通信鏈路上的通信時間。

定義Rj(t)在時間間隔［0，t］內節點j 上沒有發生修復（即p=0）的概率，其概率值為

由上述介紹可知，節點j 完成任務i 的概率為Kij。

為了提升應用程序的并行性，一個作業往往被分割成多個任務同時在多個節點上并行執行，一個任務只在一個節點上執行，當所有任務都返回任務執行結果，則表明該作業成功完成。假設N（j）是執行任務的節點集合，那么任務的可靠性可以表示為

以任務調度可靠性最大化和任務總響應時間最小化為目標的任務調度策略是云環境中常見的任務調度模型。要使調度策略達到可靠性最高化和任務總響應時間最小化的目標，就要將目標函數設定為

由于任務總響應時間的取值要比可靠性的取值范圍大，因此將x 作為比例因子協調可靠性和時間成本所占的比例，防止時間成本控制目標函數值。

4 調度算法

根據引入失效恢復機制的可信任度模型，對蟻群模擬退火算法進行擴展，針對云環境中的任務調度問題，將考慮失效恢復機制的可信任評估模型引入蟻群模擬退火算法中，提出考慮失效恢復機制的蟻群模擬退火算法［8～9］。

ACOSA（Ant Clony Optimization Simulated Ane?alling）算法為啟發式ACO 和SA 的結合，其原理是對任務Ti和節點Nj，通過ACO找出局部最優的任務調度解，再利用SA進行局部優化，從而將任務分配到合適的異構資源節點上執行。其中ACO 在螞蟻尚未進行搜索前將初始信息素濃度設置為一常數，這樣會加大螞蟻的搜索空間［10～14］。

隨著時間的增加，信息素濃度越來越高，螞蟻就可以根據上次螞蟻走過的路徑上信息素的濃度來進行選擇合適的路徑。當任務被調度到資源節點上執行時，可信任度反映了目標資源節點提供服務的可靠程度。將可信度最大化和時間成本最小化作為目標函數，并將該函數作為ACO 的啟發函數：

引入失效恢復機制后，節點可以通過運行失效恢復程序對停止執行的任務進行恢復。基于可靠性任務調度策略的執行步驟：

1）初始化參數。設置初始溫度Tmax、最大迭代次數Itermax以及初始信息素τij。

2）構造可行解。螞蟻j根據選擇遷移規則選擇合適的節點，將選中的節點加入禁忌表中，指導所有任務都分配到合適的節點資源。

3）對信息素進行更新。當所有螞蟻都完成路徑搜索時產生局部最優解，利用局部最優解進行局部信息素的更新。

4）SA進行局部優化。根據ACO獲得的局部最優解，利用SA對局部最優解優化，得到新解

5）Metropolis 準則。根據Metropolis 準則判斷SA構造的新解是否會被接受。

6）終止準則。對當前溫度進行降溫，判斷是否滿足終止準則，若滿足則執行7），否則返回至4）。

7）全局信息素更新。根據SA 產生的候選解對全局信息素更新，迭代次數加1，若迭代次數大于Itermax，則終止所有步驟，否則返回至2）。

5 仿真實驗

針對引入失效恢復機制的可靠性任務調度策略的仿真實驗［15～17］，該策略的可靠性主要是由節點可信任度和通信鏈路的可信任度決定，根據提出的算法性能和應用任務的大小及通信/計算比Rcc（Communication to Computation Ratio）有關，因此任務類型將由通信/計算比決定，Rcc＞1 表示任務為通信密集型，0＜Rcc＜1表示任務為計算密集型。

實驗環境參數設置如下：任務Rcc分別為0.1、1、10；任務數為100，節點數為20，通信鏈路數為20。設置兩種可信任度低的節點，分別占節點總數的20%和30%，兩類節點執行失敗的概率分別為80%和50%。如圖1 和圖2 所示，分別驗證失效恢復機制的有效性和失效恢復率對任務執行時間的影響。

圖1 不同失效恢復率下任務執行成功率（不限制最大恢復次數）

圖2 不同失效率對應的任務完成時間

上述實驗證明，引入失效恢復機制確實提高了任務執行成功的概率［18～20］，表明了失效恢復機制是有效的，但是在進行失效恢復的過程中也會產生時間和資源開銷，因此要選擇合適的失效恢復概率。不同任務數的情況下，比較任務執行成功率和目標函數值的大小。比較FCFS 算法和ACOSA 算法，其中失效恢復率uk設為0.6。

圖3 不同任務數對應不同的任務執行成功率

圖4 不同任務對應的目標函數值

從圖3 中可知，任務數逐漸增加的情況下，FCFS 算法和ACOSA 算法任務執行成功率都在逐漸降低，但是引入失效恢復機制的ACOSA 算法的任務執行成功率明顯高于FCFS（First Come First Served）算法。由圖4 可知，引入失效恢復機制的ACOSA 算法的任務完成時間要小于FCFS 算法的任務完成時間。因此，可以證明引入失效恢復機制不僅可以提高任務的執行成功率，而且在選擇了合適的失效恢復率的情況下，引入失效恢復機制的ACOSA算法性能優于FCFS算法。

6 結語

針對云計算中的任務調度問題，提出基于可信任度的任務調度策略。通過引入節點失效恢復機制，在分析可信任度度量指標的基礎上構建可信任度模型，結合失效恢復機制和可信任度模型的調度策略為任務的成功執行提供了可靠性保證。仿真結果表明，引入失效恢復機制的ACOSA 算法性能優于FCFS算法。