副版本優先級可提升的全局容錯調度算法

彭 浩 韓江洪 魏振春 衛 星

（合肥工業大學計算機與信息學院 合肥 230009）（hanjh＠hfut．edu．cn）

副版本優先級可提升的全局容錯調度算法

彭 浩 韓江洪 魏振春 衛 星

（合肥工業大學計算機與信息學院 合肥 230009）（hanjh＠hfut．edu．cn）

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

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

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

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

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

本文的研究建立在以下假設的基礎上：

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

2）在一次作業的生命周期內只會出現一次故障，這一假設在容錯調度領域被廣泛采用［5，9－10，12］；

3）故障持續時間很短，即是瞬態故障［13－14］；

4）系統的硬件平臺為同構多處理器平臺，處理器速度相同，并共享存儲器．

1 任務模型和相關定義

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

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

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

定義1．任務τi在時間區間A內的負載是指在該時間區間內τi作業的累積運行時間長度．

定義2．高優先級任務τi在時間區間A內對作業Jk產生的干擾負載是指τi釋放的作業處于運行狀態而Jk處于就緒狀態但不能運行的累積時間長度．

定義3．在時間區間A內作業Jk受到的累積干擾負載是指在該區間內所有高優先級任務產生的干擾負載的總和．

定義4．在時間區間A內作業Jk受到的干擾是指在區間內Jk處于就緒狀態但得不到運行的累積時間長度．

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

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

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

2 可調度性測試

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

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

2．1 可調度性分析

假設被測試任務為τk．τk可調度要求：1）τk無故障時可以在截止期前正確響應；2）τk發生故障時可以在截止期前正確響應．其中前者又包含其他任務發生故障和沒有任務發生故障2種情況．

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

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

2．2 系統中無故障

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

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

Fig．2 Release pattern for calculating the upper bound of workload．圖2 產生最大負載的作業釋放模式

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

其中Ni表示可以在L內完整運行作業的數量，min（CPi，L＋RNFi－CPi－Ni×Ti）表示帶出作業產生的最大負載；

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

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

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

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

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

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

2．3 其他任務發生故障

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

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

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

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

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

2．4 自身發生故障

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

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

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

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

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

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

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

3 副版本優先級分配

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

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

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

4 仿 真

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

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

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

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

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 總 結

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

［1］Gaska T，Werner B，Flagg 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）（丁萬夫，郭銳鋒，秦承剛，等．硬實時系統中基于軟件容錯模型的容錯調度算法［J］．計算機研究與發展，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）（朱萍，陽富民，涂剛，等．一種可行的分布式硬實時容錯調度算法［J］．軟件學報，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）（謝國琪，李仁發，劉琳，等．異構分布式系統DAG可靠性模型與容錯算法［J］．計算機學報，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，FTGS－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

國家自然科學基金項目（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）

關鍵詞 多處理器；容錯調度；全局調度；硬實時系統；優先級提升