對等網(wǎng)絡(luò)環(huán)境下多目標任務(wù)容錯調(diào)度方法研究

秦軼翚，馬 濤

(北京聯(lián)合大學，北京 100011)

1 引言

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

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

2 對等網(wǎng)絡(luò)環(huán)境下多目標任務(wù)容錯調(diào)度

2.1 任務(wù)模型構(gòu)建

對等網(wǎng)絡(luò)環(huán)境是通過多種有限帶寬網(wǎng)絡(luò)經(jīng)過處理器互連組成的，其需要多種控制回路一起運行，每一種控制回路都會以固定頻率輸出，能夠?qū)崿F(xiàn)很多功能，例如空集運算、數(shù)據(jù)收集或控制輸出等。這些功能之間都存在一定的關(guān)聯(lián)，也相互干擾，因此，可以將一種控制回路描述成一個回路任務(wù)，為了實現(xiàn)對等網(wǎng)絡(luò)的多種控制功能，就需要使用多種不同類型的處理器進行任務(wù)調(diào)度，對等網(wǎng)絡(luò)系統(tǒng)描述如下所示：

1)一種對等網(wǎng)絡(luò)系統(tǒng)能夠表示成一種處理器的集合

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

(1)

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

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

(2)

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

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

(3)

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

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

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

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

(4)

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

tp=tb(C，A，Pr)

(5)

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

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

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

(6)

擬定的調(diào)度方法基于以下假設(shè)：擬定對等網(wǎng)絡(luò)環(huán)境內(nèi)處理器總量與[8]回路任務(wù)的總量是固定的；設(shè)定回路任務(wù)的周期和時限是同等的。

2.2 故障模型構(gòu)建

對等網(wǎng)絡(luò)內(nèi)處理器都可能產(chǎn)生故障，同時由于系統(tǒng)的漏洞，每一種任務(wù)也都可能出現(xiàn)運行失敗的問題，所以本文在處理容錯問題之前，先構(gòu)建故障模型，提升任務(wù)調(diào)度的成功率。

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

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

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

4)一個處理器出現(xiàn)故障，這個故障能夠被其它處理器檢測，軟件的故障也能夠?qū)崟r被處理器檢測出來。

2.3 任務(wù)的主版本與副版本容錯可調(diào)度條件

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

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

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

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

(7)

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

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

(8)

3)主版本的實現(xiàn)需要滿足下式

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

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

(9)

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

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

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

(10)

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

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

(11)

基于上式，可以得到任務(wù)集Sh與Ss在處理器集Ω內(nèi)容錯可調(diào)度的充分條件。

2.4 多目標任務(wù)的容錯調(diào)度算法實現(xiàn)

多目標任務(wù)容錯調(diào)度即NP難題，一般會通過啟發(fā)式方法對其進行解次優(yōu)解，本文使用自適應(yīng)策略構(gòu)建多目標任務(wù)容錯調(diào)度策略，調(diào)度的原則即：任務(wù)調(diào)度到該任務(wù)完成最早的處理器中，并將同一多目標任務(wù)的主、副版本分配到不同的處理器內(nèi)。

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

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

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

(12)

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

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

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

(13)

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

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

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

(14)

其中，τl代表在Prj內(nèi)，且在調(diào)度序列中處于τi·tρ前方的最后一個任務(wù)。

多目標任務(wù)容錯分配：

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

2)使k=1。

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

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

3 仿真研究

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

3.1 實驗環(huán)境

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

3.2 實驗結(jié)果分析

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

圖1 不同節(jié)點數(shù)量下的任務(wù)調(diào)度成功率

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

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

圖2 不同節(jié)點數(shù)量下任務(wù)等級平均值

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

4 結(jié)論

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