對等網絡環境下多目標任務容錯調度方法研究

秦軼翚，馬 濤

(北京聯合大學，北京 100011)

1 引言

容錯技術在安全系統中具有較為重要的地位，會直接影響網絡系統的可靠性，而容錯調度方法可以將多目標任務劃分為多個版本來實現目標容錯調度，這是目前比較流行的容錯方法。有效的容錯調度可以最大程度地提升網絡系統性能，使其具有靈活性、可靠性與可調度性等優點。但是研究表明，對等網絡環境下多目標任務容錯調度方法是一種NP(非確定性完全問題)，即在對等網絡環境下對任務調度是沒有最優線性時間的復雜調度方法，因此在現實應用中，通常會利用接近最優方法來完成這類調度問題。但由于處理器數量的實時變換，網絡系統內會隨時出現一些故障，這些故障不僅是硬件故障，還包括軟件故障，而任務在任何情況下都要在其時限到達前完成，因此，需要為對等網絡環境提供一種存在容錯能力的任務調度方法。

針對上述問題，本文通過PB(軟件容錯)方法劃分任務的主、副版本，使后期的任務分配能夠更加清晰、安全，隨后通過擬定任務模型與故障模型，來確定時限與任務開始的時間，最后依靠自適應策略擬定啟發式多目標任務容錯分配策略，對對等網絡環境下的多目標任務進行容錯調度。

2 對等網絡環境下多目標任務容錯調度

2.1 任務模型構建

對等網絡環境是通過多種有限帶寬網絡經過處理器互連組成的，其需要多種控制回路一起運行，每一種控制回路都會以固定頻率輸出，能夠實現很多功能，例如空集運算、數據收集或控制輸出等。這些功能之間都存在一定的關聯，也相互干擾，因此，可以將一種控制回路描述成一個回路任務，為了實現對等網絡的多種控制功能，就需要使用多種不同類型的處理器進行任務調度，對等網絡系統描述如下所示：

1)一種對等網絡系統能夠表示成一種處理器的集合

Ω={Pr1，Pr2，…，PrM}(M≥2)

(1)

由于系統中[1]處理器類型不同，同種任務在不同處理器中的運行時間也各不相同，因此，需要引入運行時間向量

τiC={τiC(1)，τiC(2)，…，τiC(M)}

(2)

其中，τiC為τi在Prj內的運行時間。

2)處理器Prj的工作能力系數表明同種任務在處理器Prj中的運行速度，運算結果如下式所示

(3)

其中，τi·C(nor)與τi·C(Prj)分別代表τi在普通處理器內的運行時間與在Prj內的運行時間，普通處理器即在每一種處理器內挑選一種處理器進行處理，挑選出的處理器其處理效率被擬定成1。

使用PB方法進行容錯處理[2]，每一種任務都需要擁有各自獨立的主、副版本，同時這些版本會分配到不同的處理器內運行，因為系統故障出現的概率較小，一般都是先運行主版本[3]，所以任務主版本就起到了決定系統控制性能的作用。通過IC方式對任務主版本進行處理，任務主版本能夠完成很多功能，例如精準度控制運算、更新顯示、數據收集、輸出控制或優化等，其存在運行時間長和結構復雜的特性，任務副版本只需要完成一些必要的功能，例如控制運算、數據收集或[4]輸出控制等，其有著運行時間短和架構簡單的特性。

3)對等網絡系統內的任務集是S={τ1，τ2，…，τN}(N≥2)，τi代表第i個回路任務，將其描述成一種四元組：

τi=(T，d，tp，tb)

(4)

其中，T代表收集樣本的周期；d代表任務的時間限制；tp代表主版本；tb代表副版本。tp與tb能夠表示成三元組即

tp=tb(C，A，Pr)

(5)

其中，C與A分別代表相應版本的運行時間和所在處理器的運行時間。設定τi·tp·C(Prj)與τi·tb·C(Prj)分別代表τi的主版本與副版本在Prj內的運行時間，由于τi·tp的結構較為復雜且運行時間較長，因此更容易產生軟件故障[5]，而τi·tb結構簡單且運行時間較短，因此擬定其能正確運行任務。本文主要針對對等網絡環境，將系統的樣本收集周期控制在一定的取值范圍，將滿足系統控制要求的最大采樣周期表示為Tmax。

實際上，每一種控制回路之間不會出現孤立問題[6]，但為了實現先進控制，需要在控制回路之間添加優點約束，比如串級系統的外回路需要在內回路運行之前實現，所以就需要添加有限關聯矩陣[7]R=(ri，j)N×N，其中，ri，j代表τi與τj之間存在的優先約束關聯，τi，j的取值為1或0，如果τi需要在τj開始之前完成，則ri，j=1，反之ri，j=0。

4)一般情況下，處理器的控制平均值是通過主版本所在處理器的運行時間與總時間的平均值選取的，其計算方式如下式所示

(6)

擬定的調度方法基于以下假設：擬定對等網絡環境內處理器總量與[8]回路任務的總量是固定的；設定回路任務的周期和時限是同等的。

2.2 故障模型構建

對等網絡內處理器都可能產生故障，同時由于系統的漏洞，每一種任務也都可能出現運行失敗的問題，所以本文在處理容錯問題之前，先構建故障模型，提升任務調度的成功率。

1)軟件故障與硬件故障是不會同時出現的，即在某時刻，網絡系統中只會產生一個處理器出現故障或一種軟件出現故障，每一種處理器在某時刻最多會產生一種軟件故障，在下一個故障出現之前，主版本運行失敗的任務，都會使用它們的副版本成功運行[9]。

2)由于硬件冗余策略可以實現對永久硬件故障的容錯，所以設定硬件與軟件的故障都存在一定的持續時間，這些故障只會影響到相應處理任務，每一種故障都是獨立存在的。

3)處理器故障即fail-stop模式，能夠描述成處理器的正常運行或故障運行狀態。

4)一個處理器出現故障，這個故障能夠被其它處理器檢測，軟件的故障也能夠實時被處理器檢測出來。

2.3 任務的主版本與副版本容錯可調度條件

對等網絡環境下任務調度需要先確定一種任務何時在哪一個處理器上運行。為了讓系統也具有容錯能力，所有實時任務都會擬定主版本與副版本，它們會分配到不同的處理器內，網絡系統會先運行主版本，假如主版本正確運行，那么副版本就不需要運行，但如果主版本所處的處理器產生故障時，那么該任務在其它處理器內的副版本就會運行，實時任務與[10]調度方法應滿足以下條件：

1)任務主版本與副版本運行時間的總和不能超過其時限，即：

max{τi·tp，C(j)+τitb·C(m)}

≤τi·P(j≠m)，?τi∈Sh

(7)

2)一個任務的主版本與副版本分配在不同的處理器內，同時它們的運行時間不可以重疊，即

{τi·tρ·Pr≠τi·tb·Pr}(τi·tρ·Tstart+τi·tρ·C(τi·tρ·Pr))≤τi·tb·Tstart，?τi∈Sh

(8)

3)主版本的實現需要滿足下式

τi·tρ·C(τi·tρ·Pr)≤τi·tρ·D

≤τi·P-τi·tb·C(τi·tb·Pr)，?τi∈Sh

(9)

為了使任務滿足容錯條件，通過擬定實時任務主版本與副版本不同的開始時間與時限方法[11]，對于?τi∈Sh，其主版本τhi·tp任務開始時間擬定成任務τhi的到達時間，其時限擬定成τhi·tp·D≤τhi·P-τhi·tb·C(τhi·tb·Pr)。通常來說，任務τhi在τhi·tp·D中完成，假如處理器τhi·tb·Pr出現故障，同時τhi·tp沒有在其時限前完成，那么系統會通知處理器τhi·tb·Pr調度相應的副版本。針對任務的副版本，擬定其開始運行的時間為處理器τhi·tb·Pr被通知調度τhi·tp的時間，同時其時限擬定成τhi·P-τhi·tp·D，這能夠確保τhi在其時限之前完成。假如主版本運行正確，那么通知處理器τhi·tb·Pr取消對τhi·tp的調度。

針對上述構建的任務模型，擬定每一種實時任務的主版本和任務時限的比例是同等的，即

τhi·tp·D=Δτhi·d=τhi·P

(10)

其中，Δ代表一種常數，0<Δ<1，則存在

τhi·tp·D=τhi·d-τhi·tb·D=(1-Δ)τhi·P

(11)

基于上式，可以得到任務集Sh與Ss在處理器集Ω內容錯可調度的充分條件。

2.4 多目標任務的容錯調度算法實現

多目標任務容錯調度即NP難題，一般會通過啟發式方法對其進行解次優解，本文使用自適應策略構建多目標任務容錯調度策略，調度的原則即：任務調度到該任務完成最早的處理器中，并將同一多目標任務的主、副版本分配到不同的處理器內。

估算任務在處理器上需要消耗的時間，具體分成兩種情況：

1)針對τi·tp，假如rk，i=0(k=1，…，n且k≠i)，其在處理器Prj內的完成時間通過式(12)進行運算

τi·tp·F(Prj)=τi·F(Prj)+τi·tp·C(Prj)

(12)

其中，τi代表分配至Prj內，同時在調度序列內位于τi·tp前方的任務；τi·F(Prj)代表τi在Prj內完成的時間。假如rk，i=1(k=1，…，n且k≠i)，那么其在Prj內完成的時間通過式(13)進行計算。

τi·tρ·F(Prj)=t+τi·tρ·C(Prj)，t

=max{τi·F(Prj)，τk·tρ·F(Prj)}

(13)

2)針對τi·tρ，在Prj內完成的時間通過式(14)進行計算。

τi·tρ·F(Prj)=t+τi·tb·C(Prj)，t

=max{τl·F(Prj)，τk·tρ·F(Prj)}

(14)

其中，τl代表在Prj內，且在調度序列中處于τi·tρ前方的最后一個任務。

多目標任務容錯分配：

1)設定任務的固定數量，每一個任務的主、副版本在正常處理器中運行的時間，處理器數量，每一個處理器的運行效率系數，設定任務調度的序列。

2)使k=1。

4)如果k=2N，使k=k+1，同時迭代(3)、(4)，反之結束。

如果R≤Tmax，那么多目標任務的所有版本都可以在Tmax運行之前完成，而回路任務的周期與時限是相同的，所以回路任務的主、副版本都能夠在時限結束之前完成運行，因此任務是可調度可容錯的。

3 仿真研究

為了證明本文方法的實用性，擬定仿真來測試本文方法的性能。

3.1 實驗環境

本文使用CloudSim模擬對等網絡，所有網絡主機存在一個CPU，為了體現處理能力的異構性，參數能夠分成1000、1500或2000MIPS。所有對等網絡都安裝一個性能為200、300或400MIPS的核心。本文擬定對等網絡開始運行與創造一個虛擬對等網絡的時間分別是：90s與15s。實驗內存在10000個多目標任務到達對等網絡內，擬定其到達服從平均間隔的時間是1/λ的泊松分布，1/λ代表[1/λ0，1/λ0+2]之間的均衡分布。任務的運算量在1×105，2×105范圍內均勻分布。截止期是di=ai+deadlineTime，deadlineTime服從均勻分布，U(baseDeadline，4baseDeadline)。

3.2 實驗結果分析

通過一組實驗來表明節點數對本文方法的影響，實驗結果如圖1所示。

圖1 不同節點數量下的任務調度成功率

通過圖1能夠看出，在節點數量增加之后，本文方法的調度成功率會隨之升高，這是因為，在節點總量上升之后，對等網絡的運行能力也會逐漸上升，其會添加更多的節點，這些節點可以存儲更多的回路任務，從圖1還能夠看出，除了節點為4的這種低資源情況外，普遍調度成功率都是隨著每一節點數量增加而迅速上升，這是因為本文方法能夠通過降低任務的等級來提升任務調度的成功率。

通過一組實驗來表明節點數對本文方法性能的影響，實驗結果如圖2所示。

圖2 不同節點數量下任務等級平均值

通過圖2能夠看出，在節點總量較低的情況下，本文方法會降低多目標任務的處理等級，這是因為在節點總量較低時，系統會出現負載過重的問題，這時方法就會通過降低任務級別來提高任務的調度成功率，而在節點總量逐漸上升之后，也會逐漸提升多目標任務的等級，這就證明節點數量增加之后，系統的處理能力也會隨之增強，為任務提供更高的處理級別，因此得出結論，本文方法具有很強的自適應性，不會因為節點數量較低，而出現停滯運行的問題。

4 結論

為了使任務調度不被系統故障所影響，本文提出對等網絡環境下多目標任務容錯調度方法，通過擬定啟發式多目標任務容錯分配策略對任務進行容錯調度。但是本文方法存在一定的針對性，只能單一地針對任務容錯進行調度，雖然能夠順利完成調度任務，但也增加了調度過程的計算量，因此下一步需要研究的課題為：在本文方法的基礎上添加故障檢測系統，依靠檢測系統提前獲取精確的故障區域同時進行處理，從而節省大量的任務調度時間與計算量。