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

秦軼翚，馬 濤

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

1 引言

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

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

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

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

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

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

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

(1)

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

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

(2)

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

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

(3)

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

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

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

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

(4)

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

tp=tb(C，A，Pr)

(5)

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

實(shí)際上，每一種控制回路之間不會(huì)出現(xiàn)孤立問題[6]，但為了實(shí)現(xiàn)先進(jìn)控制，需要在控制回路之間添加優(yōu)點(diǎn)約束，比如串級(jí)系統(tǒng)的外回路需要在內(nèi)回路運(yùn)行之前實(shí)現(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)一般情況下，處理器的控制平均值是通過主版本所在處理器的運(yùn)行時(shí)間與總時(shí)間的平均值選取的，其計(jì)算方式如下式所示

(6)

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

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

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

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

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

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

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

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

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

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

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

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

(7)

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

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

(8)

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

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

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

(9)

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

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

τ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)容錯(cuò)可調(diào)度的充分條件。

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

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

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

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

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

(12)

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

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

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

(13)

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

τ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ρ前方的最后一個(gè)任務(wù)。

多目標(biāo)任務(wù)容錯(cuò)分配：

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

2)使k=1。

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

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

3 仿真研究

為了證明本文方法的實(shí)用性，擬定仿真來測(cè)試本文方法的性能。

3.1 實(shí)驗(yàn)環(huán)境

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

3.2 實(shí)驗(yàn)結(jié)果分析

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

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

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

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

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

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

4 結(jié)論

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