彭 浩 韓江洪 魏振春 衛(wèi) 星

（合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院 合肥 230009）（hanjh＠hfut．edu．cn）

副版本優(yōu)先級(jí)可提升的全局容錯(cuò)調(diào)度算法

彭 浩 韓江洪 魏振春 衛(wèi) 星

（合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院 合肥 230009）（hanjh＠hfut．edu．cn）

在主副版本機(jī)制的全局容錯(cuò)調(diào)度中，副版本運(yùn)行窗口短，采用優(yōu)先級(jí)繼承策略的副版本響應(yīng)時(shí)間長(zhǎng)，容易錯(cuò)失截止期．針對(duì)副版本實(shí)時(shí)性差的問題，提出基于優(yōu)先級(jí)提升策略的全局容錯(cuò)調(diào)度算法（fault tolerant global scheduling with backup priority promotion，F(xiàn)TGS－BPP），通過賦予副版本比主版本高的優(yōu)先級(jí)，減少副版本在運(yùn)行過程中受到的干擾，縮短了副版本的響應(yīng)時(shí)間，改善了副版本的實(shí)時(shí)性，從而減少了實(shí)現(xiàn)容錯(cuò)所需的額外處理器資源．仿真結(jié)果表明，和采用優(yōu)先級(jí)繼承策略的全局容錯(cuò)調(diào)度算法相比，F(xiàn)TGS－BPP在調(diào)度相同的任務(wù)集時(shí)明顯降低了處理器資源需求．

為了滿足對(duì)計(jì)算能力不斷增長(zhǎng)的需求，多處理器芯片被越來越多的嵌入式硬實(shí)時(shí)系統(tǒng)采用，例如航空電子系統(tǒng)［1］、汽車電子系統(tǒng)［2］、工業(yè)控制系統(tǒng)［3］等．硬實(shí)時(shí)系統(tǒng)同時(shí)具有實(shí)時(shí)性和可靠性要求．實(shí)時(shí)性是指系統(tǒng)中的每個(gè)任務(wù)都必須能夠在某個(gè)固定時(shí)限內(nèi)完成設(shè)計(jì)的功能，這個(gè)時(shí)限被稱為截止期；可靠性是指系統(tǒng)可以無故障執(zhí)行設(shè)計(jì)功能的能力．有效的硬實(shí)時(shí)容錯(cuò)調(diào)度算法是滿足系統(tǒng)實(shí)時(shí)性和可靠性要求的關(guān)鍵［4－6］．

主副版本機(jī)制是實(shí)現(xiàn)容錯(cuò)調(diào)度最主要的方法［7］．在該方法中，系統(tǒng)中的每個(gè)任務(wù)有一個(gè)主版本以及一個(gè)或多個(gè)副版本，任務(wù)開始運(yùn)行時(shí)只有主版本作業(yè)就緒，副版本作業(yè)都處于掛起狀態(tài)，如果主版本出錯(cuò)，則會(huì)有一個(gè)副版本作業(yè)進(jìn)入就緒狀態(tài)并被調(diào)度運(yùn)行，該副版本作業(yè)出錯(cuò)則繼續(xù)調(diào)度下一個(gè)副版本作業(yè)，直至該任務(wù)任意一個(gè)版本的作業(yè)正確響應(yīng)，副版本作業(yè)的啟動(dòng)順序由設(shè)計(jì)人員預(yù)先確定．

和多處理器實(shí)時(shí)調(diào)度算法相同，容錯(cuò)調(diào)度算法也分為分組容錯(cuò)調(diào)度算法和全局容錯(cuò)調(diào)度算法．前者將任務(wù)分組，并保證將同一個(gè)任務(wù)的主副版本分到不同的組中，每組單獨(dú)占用一個(gè)固定的處理器，并使用單處理器實(shí)時(shí)調(diào)度算法調(diào)度每個(gè)組中的任務(wù)［5，89］；后者不固定任務(wù)的運(yùn)行位置，任務(wù)可以在處理器間遷移，調(diào)度器總是調(diào)度優(yōu)先級(jí)高的主版本或者副版本在功能完好的處理器上運(yùn)行，這樣不會(huì)出現(xiàn)有處理器空閑而任務(wù)在其他處理器上等待卻不能使用空閑處理器運(yùn)行的情況．和分組容錯(cuò)調(diào)度相比，全局容錯(cuò)調(diào)度的研究還很少，文獻(xiàn)［10］提出了基于概率模型的動(dòng)態(tài)優(yōu)先級(jí)全局容錯(cuò)調(diào)度算法EDFk，并建立了基于使用率的可調(diào)度測(cè)試．文獻(xiàn)［11］研究了基于優(yōu)先級(jí)繼承策略的固定優(yōu)先級(jí)全局容錯(cuò)調(diào)度算法FTGS．優(yōu)先級(jí)繼承策略的問題是會(huì)造成副版本實(shí)時(shí)性差，在主副版本機(jī)制的容錯(cuò)調(diào)度中主版本和副版本的截止期是相同的，而副版本作業(yè)只有在主版本作業(yè)出現(xiàn)故障之后才會(huì)進(jìn)入就緒狀態(tài)被調(diào)度運(yùn)行，因此可供副版本作業(yè)運(yùn)行的時(shí)間窗口較短，容易錯(cuò)失截止期，為了保證副版本能夠在短時(shí)間內(nèi)響應(yīng)，需要增加大量額外的處理器資源．

優(yōu)先級(jí)提升策略是解決副版本實(shí)時(shí)性差的有效方法，該策略通過賦予副版本比較高的優(yōu)先級(jí)，使副版本作業(yè)可以在較短時(shí)間內(nèi)響應(yīng)，從而滿足實(shí)時(shí)性要求．本文基于優(yōu)先級(jí)提升策略，針對(duì)固定優(yōu)先級(jí)偶發(fā)實(shí)時(shí)任務(wù)集，提出副版本優(yōu)先級(jí)可提升的全局容錯(cuò)調(diào)度算法（fault tolerant global scheduling with backup priority promotion，F(xiàn)TGS－BPP），解決主副版本機(jī)制的全局容錯(cuò)調(diào)度中副版本實(shí)時(shí)性差的問題．

本文的研究建立在以下假設(shè)的基礎(chǔ)上：

1）任務(wù)之間相互獨(dú)立，任務(wù)中沒有并行運(yùn)行的代碼，即一個(gè)任務(wù)同一時(shí)刻只能占用一個(gè)處理器；

2）在一次作業(yè)的生命周期內(nèi)只會(huì)出現(xiàn)一次故障，這一假設(shè)在容錯(cuò)調(diào)度領(lǐng)域被廣泛采用［5，9－10，12］；

3）故障持續(xù)時(shí)間很短，即是瞬態(tài)故障［13－14］；

4）系統(tǒng)的硬件平臺(tái)為同構(gòu)多處理器平臺(tái)，處理器速度相同，并共享存儲(chǔ)器．

1 任務(wù)模型和相關(guān)定義

多處理器硬實(shí)時(shí)系統(tǒng)包含1個(gè)由n個(gè)實(shí)時(shí)任務(wù)組成的偶發(fā)任務(wù)集和1個(gè)由m個(gè)同構(gòu)處理器組成的硬件平臺(tái)．任務(wù)τi（i＝1，2，…，n）包含1個(gè)主版本和1個(gè)副版本，用6元組τi＝?CPi，CBi，Di，Ti，PPi，PBi?表示．其中，CPi和CBi分別表示主、副版本的最壞情況運(yùn)行時(shí)間；Di表示相對(duì)截止期，即任務(wù)一次運(yùn)行的釋放時(shí)刻和完成時(shí)限之間的時(shí)間長(zhǎng)度；Ti表示任務(wù)相鄰2次釋放作業(yè)的最小時(shí)間間隔；PPi和PBi分別表示主、副版本的優(yōu)先級(jí)，在這里規(guī)定數(shù)值越小代表越高的優(yōu)先級(jí)，即最高優(yōu)先級(jí)為1，最低優(yōu)先級(jí)為n．在后面的章節(jié)中，不需要特別指明作業(yè)的序數(shù)時(shí)，用JPi和JBi分別表示任務(wù)τi主、副版本的一次作業(yè)，ri表示JPi和JBi的釋放時(shí)刻，di表示作業(yè)的絕對(duì)截止期，即di＝ri＋Di，分別用RPi和RBi表示τi主、副版本的最大響應(yīng)時(shí)間，用RNFi表示系統(tǒng)中無故障時(shí)τi主版本的最大響應(yīng)時(shí)間．

任務(wù)的主、副版本在某一時(shí)刻（時(shí)間觸發(fā)或事件觸發(fā)）同時(shí)分別釋放1次作業(yè)，主版本釋放的作業(yè)立刻進(jìn)入就緒狀態(tài)，副版本釋放的作業(yè)進(jìn)入掛起狀態(tài)，只有在對(duì)應(yīng)主版本作業(yè)發(fā)生故障時(shí)才會(huì)進(jìn)入就緒狀態(tài)，主版本作業(yè)正確響應(yīng)時(shí)，取消對(duì)應(yīng)的副版本作業(yè)．就緒作業(yè)進(jìn)入1個(gè)全局就緒作業(yè)隊(duì)列，調(diào)度器按照優(yōu)先級(jí)順序調(diào)度前n個(gè)（n是處理器數(shù)量）就緒作業(yè)在功能完好的處理器上運(yùn)行，作業(yè)和處理器之間沒有綁定的關(guān)系，即作業(yè)可以在任意1個(gè)處理器上運(yùn)行．在FTGS－BPP中，搶占是始終允許的，任意時(shí)刻就緒的高優(yōu)先級(jí)作業(yè)會(huì)搶占低優(yōu)先級(jí)作業(yè)，如果有多個(gè)低優(yōu)先級(jí)作業(yè)則搶占其中優(yōu)先級(jí)最低的，同時(shí)作業(yè)遷移也是始終允許的，即被搶占作業(yè)可以在另一個(gè)處理器上恢復(fù)運(yùn)行．

在后面章節(jié)的討論中，需要用到下面這些定義：

定義1．任務(wù)τi在時(shí)間區(qū)間A內(nèi)的負(fù)載是指在該時(shí)間區(qū)間內(nèi)τi作業(yè)的累積運(yùn)行時(shí)間長(zhǎng)度．

定義2．高優(yōu)先級(jí)任務(wù)τi在時(shí)間區(qū)間A內(nèi)對(duì)作業(yè)Jk產(chǎn)生的干擾負(fù)載是指τi釋放的作業(yè)處于運(yùn)行狀態(tài)而Jk處于就緒狀態(tài)但不能運(yùn)行的累積時(shí)間長(zhǎng)度．

定義3．在時(shí)間區(qū)間A內(nèi)作業(yè)Jk受到的累積干擾負(fù)載是指在該區(qū)間內(nèi)所有高優(yōu)先級(jí)任務(wù)產(chǎn)生的干擾負(fù)載的總和．

定義4．在時(shí)間區(qū)間A內(nèi)作業(yè)Jk受到的干擾是指在區(qū)間內(nèi)Jk處于就緒狀態(tài)但得不到運(yùn)行的累積時(shí)間長(zhǎng)度．

定義5．如果作業(yè)的釋放時(shí)間在時(shí)間區(qū)間之前，截止期在該區(qū)間開始時(shí)刻之后，則稱該作業(yè)為帶入作業(yè)，如圖1中的J1．分別用CI（carry－in）和NC（no carry－in）表示一個(gè)任務(wù)是否有帶入作業(yè)的情況．

Fig．1 Definitions of carry－in and carry－out job．圖1 帶入作業(yè)和帶出作業(yè)的定義

定義6．如果作業(yè)的釋放時(shí)間在區(qū)間結(jié)束時(shí)間之前、截止期在區(qū)間結(jié)束時(shí)間之后，則稱該作業(yè)為帶出作業(yè)，如圖1中的J4．

2 可調(diào)度性測(cè)試

可調(diào)度性測(cè)試是硬實(shí)時(shí)調(diào)度算法的重要組成部分，在系統(tǒng)設(shè)計(jì)階段，必須通過可調(diào)度性測(cè)試證明系統(tǒng)中運(yùn)行的實(shí)時(shí)任務(wù)集是可調(diào)度的，即在運(yùn)行過程中沒有作業(yè)會(huì)錯(cuò)失截止期．不同的硬實(shí)時(shí)調(diào)度算法安排任務(wù)運(yùn)行次序、位置的策略不同，這二者決定了可調(diào)度性測(cè)試的形式，因此需要給每種調(diào)度算法建立專屬的可調(diào)度性測(cè)試．

由于多處理器實(shí)時(shí)系統(tǒng)的臨界時(shí)刻（critical instant）還是未知的，目前的可調(diào)度性判定條件都是任務(wù)集可調(diào)度的充分而非必要條件［15］．文獻(xiàn)［16－17］分別基于響應(yīng)時(shí)間分析法（response time analysis，RTA）和截止期分析法（deadline analysis，DA）建立了多處理器實(shí)時(shí)系統(tǒng)的可調(diào)度性判定條件RTALC和DA－LC．基于響應(yīng)時(shí)間分析的可調(diào)度性判定準(zhǔn)確性更高，因此FTGS－BPP算法的可調(diào)度性測(cè)試采用這種方法，按照優(yōu)先級(jí)從高到低的順序依次判定任務(wù)集中每個(gè)任務(wù)的可調(diào)度性，如果所有任務(wù)都是可調(diào)度的，則任務(wù)集是可調(diào)度的．

2．1 可調(diào)度性分析

假設(shè)被測(cè)試任務(wù)為τk．τk可調(diào)度要求：1）τk無故障時(shí)可以在截止期前正確響應(yīng)；2）τk發(fā)生故障時(shí)可以在截止期前正確響應(yīng)．其中前者又包含其他任務(wù)發(fā)生故障和沒有任務(wù)發(fā)生故障2種情況．

假設(shè)τk的主、副版本在時(shí)刻rk各釋放一次作業(yè)JPk和JBk，τk可能遇到的故障模式有3種：1）系統(tǒng)中沒有故障發(fā)生，τk使用主版本作業(yè)JPk的計(jì)算結(jié)果，JPk的最大響應(yīng)時(shí)間RNFk就是無故障時(shí)τk的最大響應(yīng)時(shí)間；2）其他任務(wù)發(fā)生故障，τk依然使用主版本作業(yè)JPk的計(jì)算結(jié)果，JPk的最大響應(yīng)時(shí)間RPk就是τk的最大響應(yīng)時(shí)間；3）τk發(fā)生故障，即τk的主版本作業(yè)發(fā)生故障，τk使用副版本作業(yè)JBk的計(jì)算結(jié)果，JBk的最大響應(yīng)時(shí)間RBk就是τk發(fā)生故障時(shí)的最大響應(yīng)時(shí)間．

只有τk在3種故障模式下的最大響應(yīng)時(shí)間都不大于其截止期，即式（1）成立，τk才是可調(diào)度的．2．2～2．4節(jié)將詳細(xì)討論如何計(jì)算3種故障模式下的最大響應(yīng)時(shí)間．

2．2 系統(tǒng)中無故障

當(dāng)系統(tǒng)中沒有故障發(fā)生時(shí)，所有副版本作業(yè)都不會(huì)進(jìn)入就緒狀態(tài)，只有主版本作業(yè)運(yùn)行，因此調(diào)度情況和不考慮容錯(cuò)能力的調(diào)度算法類似，使用RTA－LC［16］中的方法可以計(jì)算JPk的最大響應(yīng)時(shí)間RNFk．為了便于理解，這里根據(jù)本文使用的任務(wù)模型改寫該計(jì)算方法中使用的公式，并簡(jiǎn)要敘述計(jì)算過程，這些在后面討論其他故障模式時(shí)也需要使用．

首先要計(jì)算高優(yōu)先級(jí)任務(wù)τi（PPi＜PPk）在從rk開始長(zhǎng)度為L(zhǎng)的時(shí)間窗口（后面簡(jiǎn)稱為L(zhǎng)）內(nèi)產(chǎn)生的最大負(fù)載．圖2是任務(wù)τi在L內(nèi)有帶入作業(yè)（CI）和沒有帶入作業(yè)（NC）時(shí)產(chǎn)生最大負(fù)載的釋放模式，區(qū)分這2種不同情況是為了使用限制帶入作業(yè)（limited carry－in）技術(shù)［16，18］，以提高測(cè)試準(zhǔn)確性．

Fig．2 Release pattern for calculating the upper bound of workload．圖2 產(chǎn)生最大負(fù)載的作業(yè)釋放模式

分別用WCIi（L）和WNCi（L）表示τi在有帶入作業(yè)（CI）和沒有帶入作業(yè)（NC）情況下的最大負(fù)載，使用式（2）和式（3）計(jì)算：

其中Ni表示可以在L內(nèi)完整運(yùn)行作業(yè)的數(shù)量，min（CPi，L＋RNFi－CPi－Ni×Ti）表示帶出作業(yè)產(chǎn)生的最大負(fù)載；

任務(wù)τi在L內(nèi)有帶入作業(yè)（CI）和沒有帶入作業(yè)（NC）時(shí)產(chǎn)生的最大干擾負(fù)載ICIi（L）和INCi（L）分別使用式（4）和式（5）計(jì)算：

限制τi的最大干擾負(fù)載不超過L－CPk＋1的原因在于：如果τi的最大干擾負(fù)載到達(dá)L－CPk＋1，τi釋放的作業(yè)在L內(nèi)占用一個(gè)處理器的時(shí)間已經(jīng)導(dǎo)致JPk無法在該處理器上被調(diào)度（運(yùn)行高優(yōu)先級(jí)負(fù)載不超過L－CPk的處理器才有足夠的資源運(yùn)行JPk）；而繼續(xù)增加τi的最大干擾負(fù)載會(huì)導(dǎo)致在計(jì)算最大干擾時(shí)，超過L－CPk＋1的部分被錯(cuò)誤地分配到每個(gè)處理器上，影響最終計(jì)算結(jié)果．

用Fi（L）表示τi在有帶入作業(yè)（CI）和沒有帶入作業(yè)（NC）情況下最大干擾負(fù)載的差值：

至此，通過式（7）可以計(jì)算得到所有高優(yōu)先級(jí)主版本在L內(nèi)產(chǎn)生的最大累積干擾負(fù)載Sk（L）．式（7）使用限制帶入作業(yè)（limited carry－in）技術(shù)，只允許Fi（L）項(xiàng)前m－1（m是處理器個(gè)數(shù)）大的任務(wù)有帶入作業(yè)，該技術(shù)的具體討論請(qǐng)見文獻(xiàn)［16，18］．

在L內(nèi)，JPk受到的最大干擾Ik（L）通過式（8）計(jì)算．式（8）等號(hào)的右邊表示所有高優(yōu)先級(jí)主版本產(chǎn)生的最大累積干擾負(fù)載在L內(nèi)能夠同時(shí)占用所有處理器的最密集排列，這種排列導(dǎo)致JPk就緒但無法運(yùn)行的時(shí)間最長(zhǎng)．

從RNFk（0）＝CPk開始，迭代計(jì)算式（9），直至RNFk（n＋1）＝RNFk（n），RNFk（n）即為JPk在系統(tǒng)中無故障情況下的最大響應(yīng)時(shí)間RNFk．

2．3 其他任務(wù)發(fā)生故障

假設(shè)故障任務(wù)為τf，JPk除了受到高優(yōu)先級(jí)任務(wù)主版本的干擾，還受到τf一次副版本作業(yè)JBf的干擾．高優(yōu)先級(jí)主版本的最大負(fù)載和最大干擾負(fù)載使用式（2）～（6）計(jì)算，但由于考慮了有故障發(fā)生的情況，在式（2）中應(yīng)使用考慮故障的主版本最大響應(yīng)時(shí)間RPi代替RNFi．

τf可能在任意時(shí)刻出錯(cuò)，即JBf可能在任意時(shí)刻就緒，這里對(duì)其做出最壞情況假設(shè)，即JBf在rk時(shí)刻就緒．考慮到只有優(yōu)先級(jí)高于JPk時(shí)JBf才對(duì)其產(chǎn)生干擾，JBf產(chǎn)生的最大干擾負(fù)載If（L）使用式（10）計(jì)算：

JPk受到的最大干擾Ik（L）通過式（8）計(jì)算．

從RPk，f（0）＝CPk開始，迭代計(jì)算式（12）直至RPk，f（n＋1）＝RPk，f（n），RPk，f（n）即為τf故障時(shí)JPk的最大響應(yīng)時(shí)間RPk，f．

JPk在任意一個(gè)任務(wù)（除τk之外）故障時(shí)的最大響應(yīng)時(shí)間RPk是所有RPk，f中的最大值，即：

2．4 自身發(fā)生故障

假設(shè)JBk在時(shí)刻t0就緒，即對(duì)應(yīng)主版本作業(yè)JPk在時(shí)刻t0發(fā)生故障．時(shí)刻t0越遲，JBk的響應(yīng)時(shí)間也就越遲，而JPk發(fā)生故障的最遲時(shí)間不可能晚于系統(tǒng)無故障情況下其最大響應(yīng)時(shí)間RNFk，因此假設(shè)t0＝RNFk，這對(duì)于任務(wù)τk來說是最壞情況．

將τk的主副版本作業(yè)JPk和JBk結(jié)合為一個(gè)虛擬作業(yè)J′k，J′k分成2個(gè)部分：前一部分優(yōu)先級(jí)為PPk，長(zhǎng)度為CPk；后一部分優(yōu)先級(jí)為PBk，長(zhǎng)度為CBk．J′k的運(yùn)行過程和τk的主版本作業(yè)JPk在RNFk時(shí)刻出現(xiàn)故障之后JBk就緒并完成運(yùn)行的過程相同，因此J′k的最大響應(yīng)時(shí)間R′k就是JBk的最大響應(yīng)時(shí)間．此時(shí)，求JBk最大響應(yīng)時(shí)間RBk的問題就轉(zhuǎn)化為求J′k的最大響應(yīng)時(shí)間R′k的問題．

由于J′k在運(yùn)行過程中有1次優(yōu)先級(jí)變化，使得變化前后對(duì)其產(chǎn)生干擾的任務(wù)集合不同．優(yōu)先級(jí)高于PPk、低于PBk的主版本（假設(shè)序號(hào)為i）在［rk，RNFk］內(nèi)對(duì)J′k產(chǎn)生干擾，優(yōu)先級(jí)高于PBk的主版本（假設(shè)序號(hào)為j）在［rk，R′k］內(nèi)對(duì)J′k產(chǎn)生干擾，它們的最大負(fù)載和最大干擾負(fù)載分別通過式（2）～（6）可以得到．

J′k在時(shí)間區(qū)間L內(nèi)受到的最大累積干擾負(fù)載S′k（L）通過式（14）計(jì)算．由于R′k≥RNFk＋CBk，在計(jì)算過程中L的最小取值為RNFk＋CBk，因此在式（14）中不考慮L＜RNFk的可能，以簡(jiǎn)化公式方便理解．

PPk的所有任務(wù)的Fi（L）項(xiàng)中，前m－1大的項(xiàng)的數(shù)量和．

J′k受到的最大干擾I′k（L）通過式（8）計(jì)算．

從R′k（0）＝RNFk＋CBk開始，迭代計(jì)算式（15）直至R′k（n＋1）＝R′k（n），R′k（n）即為虛擬作業(yè)J′k的最大響應(yīng)時(shí)間，也就是主版本作業(yè)發(fā)生故障的情況下JBk的最大響應(yīng)時(shí)間RBk．

3 副版本優(yōu)先級(jí)分配

在FTGS－BPP中，副版本的優(yōu)先級(jí)會(huì)影響整個(gè)實(shí)時(shí)任務(wù)集可調(diào)度性．高優(yōu)先級(jí)副版本可以在短時(shí)間內(nèi)響應(yīng)，實(shí)時(shí)性好，但是副版本優(yōu)先級(jí)過高會(huì)給其他高優(yōu)先級(jí)主版本帶來額外的干擾負(fù)載，而高優(yōu)先級(jí)主版本通常能承受的干擾相對(duì)較小，增加額外干擾負(fù)載有可能造成主版本不可調(diào)度．

本節(jié)建立一種啟發(fā)式的副版本優(yōu)先級(jí)分配算法．假設(shè)一個(gè)實(shí)時(shí)任務(wù)集的主版本已采用某種優(yōu)先級(jí)分配算法分配優(yōu)先級(jí)，例如DM（deadline monotonic），DkC等，并已按照優(yōu)先級(jí)順序排序，即PP1＝1，PP2＝2，…，PPn＝n．在初始狀態(tài)下，將副版本的優(yōu)先級(jí)都設(shè)置為對(duì)應(yīng)主版本的優(yōu)先級(jí)，并判定整個(gè)任務(wù)集的可調(diào)度性，從最高優(yōu)先級(jí)任務(wù)開始，依次檢測(cè)每個(gè)任務(wù)副版本的可調(diào)度性，對(duì)于不可調(diào)度的副版本，將其副版本提升一個(gè)優(yōu)先級(jí)，并更新再次判定該副版本和所有主版本的可調(diào)度性，不需要測(cè)試其他副版本的可調(diào)度性是因?yàn)閺牡?節(jié)的討論中可以看出，副版本的可調(diào)度性只取決于高優(yōu)先級(jí)主版本，改變副版本的優(yōu)先級(jí)對(duì)其他任務(wù)的副版本沒有影響．重復(fù)這個(gè)提升—測(cè)試過程直至副版本可調(diào)度，如果賦予副版本最高優(yōu)先級(jí)仍不可調(diào)度，或者在這個(gè)過程中有主版本被判定為不可調(diào)度，則優(yōu)先級(jí)分配失敗，不能找到能夠容錯(cuò)調(diào)度該任務(wù)集的副版本優(yōu)先級(jí)分配方案．

副版本優(yōu)先級(jí)分配算法的偽代碼描述如算法1所示，其中primaryi和backupi分別表示任務(wù)τi的主、副版本，假設(shè)任務(wù)集已按照主版本優(yōu)先級(jí)順序排序，因此任務(wù)及其主版本的下標(biāo)就等于優(yōu)先級(jí)．

4 仿 真

仿真實(shí)驗(yàn)采用調(diào)度大量隨機(jī)生成任務(wù)集的方法，以處理器需求（m）和任務(wù)集使用率（U）的比值（m?U）為評(píng)價(jià)指標(biāo)，比較FTGS－BPP和采用優(yōu)先級(jí)繼承策略的全局容錯(cuò)調(diào)度算法（FTGS－1）實(shí)現(xiàn)容錯(cuò)調(diào)度所需的處理器資源．這一方法在硬實(shí)時(shí)調(diào)度研究領(lǐng)域被廣泛采用［5，8－9，16－17］．m?U比值反映了調(diào)度算法對(duì)處理器資源的需求，數(shù)值越小表示該調(diào)度算法的調(diào)度性能越好．FTGS－1是文獻(xiàn)［12］中提出的容錯(cuò)調(diào)度算法只考慮一次故障的形式．同時(shí)，實(shí)驗(yàn)中也計(jì)算了不考慮容錯(cuò)的全局調(diào)度算法（GS）的m?U比值，從而可以比較2種容錯(cuò)調(diào)度算法為實(shí)現(xiàn)容錯(cuò)需要的額外處理器資源．

生成隨機(jī)任務(wù)集的方法如下：首先設(shè)置任務(wù)集中單個(gè)任務(wù)的使用率（C?T）上限a和任務(wù)數(shù)量n，最小釋放間隔T取［1，500］內(nèi)的隨機(jī)值，并假定任務(wù)以T為周期釋放作業(yè)，最壞情況運(yùn)行時(shí)間C?。?，aT］中的隨機(jī)值，截止期D＝T，任務(wù)的副版本簡(jiǎn)單地規(guī)定為主版本的復(fù)制．

a分別取0．2，0．3，0．4，0．5，分別使用DkC和DM算法給隨機(jī)任務(wù)集的主版本分配優(yōu)先級(jí)，在之間從低到高搜索使任務(wù)集可調(diào)度的m值（處理器個(gè)數(shù)），對(duì)每個(gè)m取值運(yùn)行一次副版本優(yōu)先級(jí)分配算法，如果成功分配優(yōu)先級(jí)則說明在該m取值下任務(wù)集是可調(diào)度的，對(duì)每組參數(shù)（a和n）重復(fù)30次實(shí)驗(yàn)，取平均值作為有效結(jié)果．實(shí)驗(yàn)結(jié)果如圖3～6所示．

從圖3～6中可以看出，不論使用DkC或DM算法分配優(yōu)先級(jí)，F(xiàn)TGS－BPP算法容錯(cuò)調(diào)度隨機(jī)任務(wù)集所需的處理器資源都明顯少于FTGS－1．和FTGS－1相比，使用DkC算法分配優(yōu)先級(jí)時(shí)，F(xiàn)TGS－BPP最多減少處理器需求17．7%（a＝0．4，n＝40），平均減少11．4%；使用DM算法分配優(yōu)先級(jí)時(shí)，F(xiàn)TGS－BPP最多減少處理器需求21．7%（a＝0．3，n＝30），平均減少12．1%．實(shí)驗(yàn)結(jié)果說明FTGS－BPP通過提升副版本優(yōu)先級(jí)，改善了副版本的實(shí)時(shí)性，從而減少了為保證副版本不錯(cuò)失截止期而需要的額外處理器資源．

Fig．3 m?Uratio when a＝0．2．圖3 a＝0．2時(shí)的m?U比值

Fig．4 m?Uratio when a＝0．3．圖4 a＝0．3時(shí)的m?U比值

Fig．5 m?Uratio when a＝0．4．圖5 a＝0．4時(shí)的m?U比值

Fig．6 m?Uratio when a＝0．5．圖6 a＝0．5時(shí)的m?U比值

5 總 結(jié)

本文基于優(yōu)先級(jí)提升策略，提出副版本優(yōu)先級(jí)可提升的全局容錯(cuò)調(diào)度算法FTGS－BPP，改善了副版本的實(shí)時(shí)性，使副版本可以在較短的運(yùn)行時(shí)間窗口內(nèi)依然不會(huì)違反截止期約束．通過生成大量隨機(jī)任務(wù)集仿真的方法，對(duì)比了FTGS－BPP和基于優(yōu)先級(jí)繼承策略的全局容錯(cuò)調(diào)度算法的調(diào)度性能，仿真結(jié)果表明，采用不同的優(yōu)先級(jí)分配算法時(shí)，F(xiàn)TGS－BPP都能夠有效減少容錯(cuò)帶來的額外處理器資源需求．

［1］Gaska T，Werner B，F(xiàn)lagg D．Applying virtualization to avionics systems—The integration challenges［C］??Proc of the 29th Digital Avionics Systems Conf．Piscataway，NJ：IEEE，2010：5．E．1－1 5．E．1－19

［2］Di Natale M，Sangiovanni－Vincentelli A L．Moving from federated to integrated architectures in automotive：The role of standards，methods and tools［J］．Proceedings of the IEEE，2010，98（4）：603 620

［3］Adyanthaya S，Geilen M，Basten T，et al．Fast multiprocessor scheduling with fixed task binding of large scale industrial cyber physical systems［C］??Proc of 2013 Euromicro Conf on Digital System Design．Piscataway，NJ：IEEE，2013：979 988

［4］Ding Wanfu，Guo Ruifeng，Qin Chengang，et al．A faulttolerant scheduling algorthm with software fault tolerance in hard real－time systems［J］．Journal of Computer Research and Development，2011，48（4）：691 698（in Chinese）（丁萬夫，郭銳鋒，秦承剛，等．硬實(shí)時(shí)系統(tǒng)中基于軟件容錯(cuò)模型的容錯(cuò)調(diào)度算法［J］．計(jì)算機(jī)研究與發(fā)展，2011，48（4）：691 698）

［5］Zhu Ping，Yang Fuming，Tu Gang，et al．Feasible faulttolerant scheduling algorithm for distributed hard－real－time system［J］．Journal of Software，2012，23（4）：1010 1021（in Chinese）（朱萍，陽富民，涂剛，等．一種可行的分布式硬實(shí)時(shí)容錯(cuò)調(diào)度算法［J］．軟件學(xué)報(bào)，2012，23（4）：1010 1021）

［6］Xie Guoqi，Li Renfa，Liu Lin，et al．DAG reliability model and fault－tolerant algorithm for heterogeneous distributed systems［J］．Chinese Journal of Computers，2013，36（10）：2019 2032（in Chinese）（謝國琪，李仁發(fā)，劉琳，等．異構(gòu)分布式系統(tǒng)DAG可靠性模型與容錯(cuò)算法［J］．計(jì)算機(jī)學(xué)報(bào)，2013，36（10）：2019 2032）

［7］Krishna C M．Fault－tolerant scheduling in homogeneous realtime systems［J］．ACM Computing Surveys，2014，46（4）：48：1 48：34

［8］Bertossi A A，Mancini L V，Menapace A．Scheduling hardreal－time tasks with backup phasing delay［C］??Proc of the 10th IEEE Int Symp on Distributed Simulation and Real－Time Applications．Piscataway，NJ：IEEE，2006：107 118

［9］Chen H M，Luo W，Wang W，et al．A novel real－time faulttolerant scheduling algorithm based on distributed control systems［C］??Proc of 2011Int Conf on Computer Science and Service System．Piscataway，NJ：IEEE，2011：80 83

［10］Berten V，Goossens J，Jeannot E．A probabilistic approach for fault tolerant multiprocessor real－time scheduling［C］?? Proc of the 20th Int Parallel and Distributed Processing Symp．Piscataway，NJ：IEEE，2006：1 10

［11］Pathan R M，Jonsson J．FTGS：Fault－tolerant fixed－priority scheduling on multiprocessors［C］??Proc of the 10th IEEE Int Conf on Trust，Security and Privacy in Computing and Communications．Piscataway，NJ：IEEE，2011：1164 1175

［12］Samala A K，Mallb R．Fault tolerant scheduling of hard realtime tasks on multiprocessor system using a hybrid genetic algorithm［J］．Swarm and Evolutionary Computation，2014，14（1）：92 105

［13］Baumann R．Soft errors in advanced computer systems［J］．IEEE Design ＆Test of Computers，2005，22（3）：258 266

［14］Koren I，Krishna C M．Fault－Tolerant Systems［M］．San Francisco，CA：Morgan Kaufmann，2007

［15］Guan N，Wang Y．Fixed－priority multiprocessor scheduling：Critical instant，response time and utilization bound［C］?? Proc of the 26th Parallel and Distributed Processing Symp Workshops ＆PhD Forum．Piscataway，NJ：IEEE，2012：2470 2473

［16］Guan N，Stigge M，Yi W，et al．New response time bounds for fixed priority multiprocessor scheduling［C］??Proc of the 30th IEEE Real－Time Systems Symp．Piscataway，NJ：IEEE，2009：387 397

［17］Davis R I，Burns A．Improved priority assignment for global fixed priority pre－emptive scheduling in multiprocessor realtime systems［J］．Real－Time Systems，2011，47（1）：1 40

［18］Lee J，Shin I．Limited carry－in technique for real－time multicore scheduling［J］．Journal of Systems Architecture，2013，59（7）：372 375

Peng Hao，born in 1984．PhD candidate in Hefei University of Technology．His main research interests include real－time system scheduling and embedded systems（superbinnitu＠aliyun．com）．

Han Jianghong，born in 1954．Professor and PhD supervisor in Hefei University of Technology．His main research interests include safety－critical industrial systems and embedded systems．

Wei Zhenchun，born in 1978．Associate professor in Hefei University of Technology．His main research interests include internet of things，wireless sensor networks，embedded system and distributed system．

Wei Xing，born in 1980．Associate professor in Hefei University of Technology．His main research interests include internet of things engineering and discrete event dynamic system．

Fault Tolerant Global Scheduling with Backup Priority Promotion

Peng Hao，Han Jianghong，Wei Zhenchun，and Wei Xing
（School of Computer and Information，Hefei University of Technology，Hefei 230009）

Fault tolerance is of great importance in hard real－time systems due to the impossibility of eliminating faults．In such a system the fault tolerant scheduling algorithm plays a critical role for achieving fault tolerance capability．In primary－backup scheme based fault tolerant global scheduling algorithms，the execution window of backup is relatively small．When priority inheritance strategy is adopted，the response time of the backup is likely too long to guarantee deadline requirement．For improving the real time property of the backup，we propose a fault tolerant global scheduling algorithm based on backup priority promotion strategy—FTGS－BPP．In FTGS－BPP，the backup has a higher priority than its corresponding primary so that during the execution the backup suffers less interference．Consequently the response time of the backup is reduced which means better real time performance．FTGS－BPP can achieve fault tolerance with less processors than the algorithms which follow priority inheritance strategy．A backup priority searching algorithm is also proposed．The simulation result shows that，compared with the fault tolerant global scheduling algorithm based on priority inheritance strategy，F(xiàn)TGS－BPP is able to reduce processor requirement significantly when scheduling the same task set．

multiprocessor；fault－tolerant scheduling；global scheduling；hard real－time systems；priority promotion

TP316．2

2014－12－17；

2015－06－09

國家自然科學(xué)基金項(xiàng)目（61370088）；國家國際科技合作專項(xiàng)項(xiàng)目（2014DFB10060）；國家科技支撐計(jì)劃項(xiàng)目（2013BAH51F01，2013BAH51F02）

This work was supported by he National Natural Science Foundation of China（61370088），the International S＆T Cooperation Program of China（2014DFB10060），and the National Key Technology R＆D Program of the Ministry of Science and Technology（2013BAH51F01，2013BAH51F02）．

魏振春（weizc＠hfut．edu．cn）

關(guān)鍵詞 多處理器；容錯(cuò)調(diào)度；全局調(diào)度；硬實(shí)時(shí)系統(tǒng)；優(yōu)先級(jí)提升