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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 仿 真

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

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

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

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

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

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

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

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

5 總 結(jié)

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

［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）（丁萬夫，郭銳鋒，秦承剛，等．硬實時系統(tǒng)中基于軟件容錯模型的容錯調(diào)度算法［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）（朱萍，陽富民，涂剛，等．一種可行的分布式硬實時容錯調(diào)度算法［J］．軟件學(xué)報，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可靠性模型與容錯算法［J］．計算機學(xué)報，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é)基金項目（61370088）；國家國際科技合作專項項目（2014DFB10060）；國家科技支撐計劃項目（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)鍵詞 多處理器；容錯調(diào)度；全局調(diào)度；硬實時系統(tǒng)；優(yōu)先級提升