面向數(shù)控系統(tǒng)的容錯實(shí)時調(diào)度算法研究

丁萬夫 郭銳鋒 秦承剛

1.中國科學(xué)院研究生院,北京,100039

2.中國科學(xué)院沈陽計算技術(shù)研究所,沈陽,110004

3.沈陽高精數(shù)控技術(shù)有限公司,沈陽,110171

0 引言

作為先進(jìn)制造業(yè)的核心技術(shù)之一,數(shù)控技術(shù)的飛速發(fā)展,對實(shí)時計算提出了更高的要求。數(shù)控系統(tǒng)不僅需要保證位置控制、速度控制等實(shí)時周期性任務(wù)在規(guī)定的時限內(nèi)完成,也要保證系統(tǒng)急停、參數(shù)調(diào)整等實(shí)時突發(fā)性任務(wù)的及時響應(yīng),而且在系統(tǒng)出現(xiàn)軟硬件故障時,仍要保證系統(tǒng)安全正確地運(yùn)行。因此,數(shù)控系統(tǒng)必須具有嚴(yán)格的時間確定性以及高度的可靠性。

目前,容錯實(shí)時調(diào)度算法的計算模型可以分成兩類:非精確計算模型[1-2]和軟件容錯模型[3-6]。在非精確計算模型中,每個任務(wù)由兩部分組成:強(qiáng)制部分(mandatory part)和可選部分(optional part)。該模型中的調(diào)度算法首先保證強(qiáng)制部分按時完成,使得該任務(wù)的輸出滿足最低的需求,同時盡可能多地執(zhí)行可選部分,以提高計算結(jié)果的精確性。非精確計算模型要求執(zhí)行的任務(wù)具有單調(diào)性,即中間結(jié)果的精度不隨執(zhí)行時間的延長而下降,而數(shù)控系統(tǒng)則要求任務(wù)輸出結(jié)果具有確定性的精度,因此該模型很難應(yīng)用于數(shù)控系統(tǒng)。根據(jù)容錯方式不同,軟件容錯模型又可分為主/替代版本模型[3-5]和回卷恢復(fù)模型[6],前者是一種基于軟件冗余的容錯技術(shù)。每個任務(wù)由兩個版本組成:主版本(primary version)和替代版本(alternate version)。其中主版本計算時間較長,計算結(jié)果較為精確,但不保證程序完全正確地運(yùn)行,而替代版本計算時間較短,只提供可接受的精度要求,但能夠保證程序完全正確地運(yùn)行,且兩者只要求完成一個即可?；鼐砘謴?fù)模型是一種基于時間冗余的容錯技術(shù)。在任務(wù)的執(zhí)行過程中,每隔一定時間把任務(wù)的狀態(tài)保存到可靠存儲介質(zhì)上(保存的狀態(tài)稱作檢查點(diǎn)),而當(dāng)系統(tǒng)發(fā)生故障時,回卷恢復(fù)模塊讀取保存的檢查點(diǎn)文件,使得任務(wù)從該狀態(tài)繼續(xù)執(zhí)行,把損失降低到檢查點(diǎn)時刻到故障發(fā)生時刻這段時間內(nèi)所做的計算。

在有關(guān)軟件容錯模型最新的研究成果中,文獻(xiàn)[3]中提出了BCE算法,為軟件容錯模型提供了一種有效的實(shí)時調(diào)度策略。BCE算法包括Basic、CAT和 EIT三個子算法。在該算法中,主版本的預(yù)測精度是影響調(diào)度性能的關(guān)鍵。BCE利用CAT算法預(yù)測主版本的可執(zhí)行性,但是當(dāng)處理器利用率較高時BCE算法的調(diào)度性能很差。為了提高任務(wù)可執(zhí)行性的預(yù)測精度,避免任務(wù)早期的失敗對后續(xù)任務(wù)的影響,文獻(xiàn)[4]提出了PKSA和CUBA算法。PKSA在BCE的基礎(chǔ)上,通過K次試探性檢測改進(jìn)了對主版本可執(zhí)行性的預(yù)測。CUBA算法則通過基于變動處理器利用率的試探性檢測提高預(yù)測的準(zhǔn)確性。文獻(xiàn)[5]提出了DPA和EDPA算法。兩種算法利用預(yù)測表對主版本的可執(zhí)行性進(jìn)行精確預(yù)測,盡可能地減少處理器時間浪費(fèi),為主版本提供更多的調(diào)度時間。由于上述算法只能調(diào)度單一類型的周期任務(wù),因此均不適用于數(shù)控系統(tǒng)多種類型混合的任務(wù)調(diào)度。針對這一問題,文獻(xiàn)[6]將人工智能領(lǐng)域的啟發(fā)式搜索算法引入混合任務(wù)集優(yōu)化調(diào)度研究,提出了最佳優(yōu)先調(diào)度BF(Best First)算法來解決任務(wù)集的實(shí)時調(diào)度問題。在此基礎(chǔ)上,提出了基于回卷恢復(fù)模型的容錯調(diào)度策略,以提高數(shù)控系統(tǒng)運(yùn)行的可靠性。但是該算法是基于時間冗余的容錯機(jī)制,需要額外的運(yùn)行開銷,即在每個檢查點(diǎn),不僅需要對當(dāng)前任務(wù)的執(zhí)行狀態(tài)(包括任務(wù)的數(shù)據(jù)變量和上下文環(huán)境)進(jìn)行保存,而且還需要對任務(wù)執(zhí)行結(jié)果的正確性進(jìn)行測試,結(jié)果正確才可以保存此時的狀態(tài)信息。可見,該算法容錯時間開銷較高,大大降低了系統(tǒng)資源利用率。

本文首先建立了數(shù)控系統(tǒng)混合任務(wù)調(diào)度的模型,提出了一種具有容錯功能的實(shí)時調(diào)度算法FT—MT,在此基礎(chǔ)上給出了該算法的偽代碼描述以及實(shí)例研究,最后進(jìn)行了調(diào)度算法的仿真實(shí)驗(yàn)。

1 系統(tǒng)、任務(wù)及容錯模型

從任務(wù)組成來看,數(shù)控系統(tǒng)是一個典型的混合任務(wù)系統(tǒng)。其任務(wù)主要包括實(shí)時周期任務(wù)、實(shí)時突發(fā)任務(wù)和非實(shí)時任務(wù)。根據(jù)任務(wù)的關(guān)鍵度不同,又可將實(shí)時周期任務(wù)分為有容錯需求的實(shí)時周期任務(wù)和無容錯需求的實(shí)時周期任務(wù)。

定義1 有容錯需求的實(shí)時周期任務(wù)集合Γfrp={τi},i=1,2,…,n,其中 n為該類任務(wù)的總數(shù)。 ?τi∈ Γf rp由一個無限的作業(yè)序列 τi={τi1,τi2,…}構(gòu)成,其中第 j個作業(yè)τij可用六元組表示為 :τij=(Ti,Ri,Pij,Aij,Ci,),其中 Ti為作業(yè)的周期,Ri為作業(yè)的到達(dá)時間,Pij和Aij分別為τij的主版本和替代版本,Ci和分別為Pij和Aij的執(zhí)行時間,且Ci≥。

定義2 無容錯需求的實(shí)時周期任務(wù)集合Γnfrp={τi},i=n+1,n+2,…,n+m,其中 m 為該類任務(wù)的總數(shù)。?τi∈Γnfrp由一個無限的作業(yè)序列 τi={τi1,τi2,…}構(gòu)成 ,其中第 j個作業(yè)τij只有一個運(yùn)行版本,可用四元組表示為:τij=(Ti,Ri,Aij,),其中Ti為作業(yè)的周期,Ri為作業(yè)的到達(dá)時間,Aij為τij的運(yùn)行版本,為Aij的執(zhí)行時間。

由定義1和定義2可知,實(shí)時周期任務(wù)集合Γrp可表示為 Γfrp與 Γnfrp的并集 ,即 Γrp=Γfrp∪Γnfrp={τ1,τ2,...,τn+m}。在本文中 ,規(guī)定所有實(shí)時周期任務(wù)在周期開始時已準(zhǔn)備就緒,而周期的結(jié)束時刻為任務(wù)的截止期。

定義3 實(shí)時突發(fā)任務(wù)集合Γap={Si},i=1,2,…,n。 ?Ai∈ Γap可用三元組表示為:Si=(Ci,Ri,Di),其中Ci為執(zhí)行時間,Ri為到達(dá)時間,Di為任務(wù)的截止期。

定義4 非實(shí)時任務(wù)集合 Γnr={Ni},i=1,2,…,n。 ?Ni∈ Γnr可用二元組表示為:Ni=(Ci,Ri),其中Ci為任務(wù)的執(zhí)行時間,Ri為任務(wù)的到達(dá)時間。

定義5 替代版本在其截止期內(nèi)的最遲開始時間稱為該替代版本的臨界點(diǎn)。

本文研究的前提條件:

(1)本容錯模型僅考慮單處理機(jī)系統(tǒng)的軟件錯誤。由于主版本提供了更為精確的計算結(jié)果,因此調(diào)度算法將盡可能多地執(zhí)行主版本,而當(dāng)主版本不能在替代版本的開始時間之前完成時,則必須執(zhí)行替代版本,以保證任務(wù)在其截止期之前能夠獲得可以接受的計算結(jié)果。

(2)在運(yùn)行過程中,規(guī)定替代版本具有最高的優(yōu)先權(quán),實(shí)時突發(fā)任務(wù)的優(yōu)先權(quán)高于實(shí)時周期任務(wù)的優(yōu)先權(quán),而非實(shí)時任務(wù)具有最低的優(yōu)先權(quán)。

2 問題描述

2.1 Basic算法介紹

文獻(xiàn)[3]提出了一種基于RM算法的軟件容錯模型,該模型的核心算法是Basic算法。運(yùn)行前,Basic算法為替代版本預(yù)先分配執(zhí)行區(qū)間,使得替代版本在其截止期內(nèi)盡可能地推遲執(zhí)行,從而為主版本的完成提供了最大的可執(zhí)行時間。運(yùn)行時,所有的主版本都在余下未被分配的區(qū)間內(nèi)執(zhí)行。對于是否執(zhí)行替代版本,主要有兩種可能:

(1)如果主版本在其替代版本的通知時間到來之前運(yùn)行完畢,系統(tǒng)將撤銷替代版本,然后調(diào)整相應(yīng)受影響的其他替代版本的時間間隔,并計算新的通知時間。

(2)如果主版本在其替代版本的通知時間到來時沒有完成,系統(tǒng)將撤銷該主版本,其替代版本開始運(yùn)行。

2.2 Basic算法存在的問題

在RM算法下,考慮一個包含兩個實(shí)時周期任務(wù)的任務(wù)集合 Γfrp={τ1,τ2},參數(shù) τij=(Ti,Ri,Pij,Aij,Ci,)分別是(5,0,P1j,A1j,2,1)和(6,0,P2j,A2j,2,2),因此 HP=LCM(5,6)=30。如圖1所示,在區(qū)間[0,30],兩個任務(wù)的通知時間分別是 v1j=4,9,14,19,24,29(j=1,2,…,6)和v2j=3,10,16,22,27(j=1,2,…,5)。這種為替代版本分配通知時間的方法稱為反向速率單調(diào)(backwards—RM)算法。

下面介紹Basic算法存在的主要問題。圖2所示為該任務(wù)集的運(yùn)行情況。在時刻0,具有較高優(yōu)先級的主版本P11就緒并開始執(zhí)行,假設(shè)P11由于軟件錯誤在時刻2失敗,所以預(yù)留給A11的區(qū)間[4,5]不能被撤銷。在時刻2,P21開始運(yùn)行,在時刻3,A21的通知時間到了,由于替代版本的優(yōu)先級高于所有主版本的優(yōu)先級,因此,A21搶占P21執(zhí)行。同理,在接下來的區(qū)間[4,5]和[5,6],系統(tǒng)分別運(yùn)行 A11和A21。在時刻 6,P12和P22同時就緒,由于P12的周期較P22短,所以系統(tǒng)執(zhí)行P12。假設(shè)P12在時刻8執(zhí)行完畢,那么分配給A12的區(qū)間[9,10]就不再需要,系統(tǒng)撤銷了A12。接著P22開始執(zhí)行并且在時刻10執(zhí)行完畢,所以A12也被系統(tǒng)撤銷。在時刻10,P13開始運(yùn)行,假設(shè)P13在時刻12發(fā)生錯誤,P23在時刻12被選擇運(yùn)行,并在時刻14運(yùn)行完畢。由于P13出錯,所以 A13不可以被撤銷,在時刻14,A13開始執(zhí)行。

觀察圖2可以發(fā)現(xiàn),在時刻12,雖然P13執(zhí)行失敗,但仍有足夠的時間使得P13重新執(zhí)行一次,這反映了Basic算法的局限性。

3 混合任務(wù)集的容錯調(diào)度算法FT—M T

3.1 FT—MT算法

針對數(shù)控系統(tǒng)的混合任務(wù)調(diào)度以及高可靠性的特點(diǎn),本文提出一種基于軟件容錯模型的實(shí)時調(diào)度算法 FT—MT(fault tolerance for mixed tasks),該算法在系統(tǒng)運(yùn)行前預(yù)先分配替代版本的執(zhí)行區(qū)間,使得替代版本在其截止期內(nèi)盡可能地推遲執(zhí)行,從而為主版本的完成提供了最大的可執(zhí)行時間。系統(tǒng)在運(yùn)行過程中以替代版本的臨界點(diǎn)作為主版本新的截止期,按照速率單調(diào)算法調(diào)度所有的主版本。如果主版本在其替代版本的臨界點(diǎn)之前運(yùn)行完畢,系統(tǒng)將撤銷替代版本,否則系統(tǒng)將撤銷該主版本,開始執(zhí)行替代版本,以保證在任務(wù)截止期之前能夠獲得可接受的計算結(jié)果。通過主版本重新執(zhí)行規(guī)則以及優(yōu)先級提升規(guī)則來盡最大努力地提高主版本的完成率,以改善輸出結(jié)果的計算精度。

3.1.1 主版本重新執(zhí)行規(guī)則

如圖3所示,通知時間為vij的主版本Pij在時刻t開始執(zhí)行,在時刻t′執(zhí)行失敗,假設(shè)在區(qū)間[t,vij]內(nèi),有λ個已經(jīng)被分配出去的區(qū)間{Ii|i=1,2,…,λ}。

定義6 重新執(zhí)行可獲得時間OTR(obtainable time for re—execution)定義如下:

主版本重新執(zhí)行規(guī)則:當(dāng)且僅當(dāng)主版本Pij的執(zhí)行時間Ci小于或者等于OTRij,主版本Pij才可以重新執(zhí)行,否則系統(tǒng)撤銷Pij的執(zhí)行。

如圖4所示,在時刻 12,P13出錯,由于OTR13=2,等于P13的執(zhí)行時間,根據(jù)FT—M T算法的重新執(zhí)行規(guī)則,系統(tǒng)在時刻12重新執(zhí)行P13。P13在時刻14運(yùn)行完畢,A13被系統(tǒng)撤銷。在時刻14,由于只有P23就緒,系統(tǒng)將選擇P23運(yùn)行。在這個例子中,通過重新執(zhí)行主版本P13,使得P13和P23都順利完成,提高了主版本的完成率,改善了輸出結(jié)果的計算精度。

3.1.2 主版本優(yōu)先級提升規(guī)則

為了驗(yàn)證優(yōu)先級提升規(guī)則的有效性,再來看一個例子 。給定任務(wù)集 Γfrp={τ1,τ2},參數(shù) τij=(Ti,Ri,Pij,Aij,Ci,)分別是(3,0,P1j,A1j,1.5,1)和(5,0,P2j,A2j,1,1),因此 HP=LCM(3,5)=15。如圖5所示,在時刻 0,P11與 P21都已就緒,由于P11的周期較短,根據(jù)RM調(diào)度規(guī)則,系統(tǒng)將選擇 P11運(yùn)行。P11在時刻 1.5運(yùn)行完畢,所以系統(tǒng)撤銷了A11。在時刻1.5,P21開始執(zhí)行,假設(shè)P21在時刻1.5發(fā)生錯誤。由于在時刻2.5沒有其他就緒的任務(wù),并且 P21的OTR21為1.5,等于 P21的執(zhí)行時間,根據(jù)Kernel算法重新執(zhí)行規(guī)則,系統(tǒng)將重新執(zhí)行P21。在時刻3,P12就緒,由于P12的優(yōu)先級高于 P21,所以P12搶占 P21開始運(yùn)行。因?yàn)闀r刻4是替代版本A21的通知時間,而替代版本的優(yōu)先級高于所有主版本的優(yōu)先級,所以A21搶占 P12開始運(yùn)行。在時刻 5,A21運(yùn)行完畢,又因?yàn)闀r刻5是A12的通知時間,所以系統(tǒng)撤銷了P12,轉(zhuǎn)而運(yùn)行A12。

在上例中,由于P12搶占了 P21,這導(dǎo)致兩個主版本都未能按時完成。為了解決這個問題,需要給FT—MT算法增加一條新的規(guī)則,即優(yōu)先級提升規(guī)則,來保證重新執(zhí)行的任務(wù)不會被高優(yōu)先級任務(wù)搶占。但是注意,提升之后的優(yōu)先級仍然不會高于替代版本的優(yōu)先級。

主版本優(yōu)先級提升規(guī)則:假設(shè)主版本Pij出錯前和出錯后的優(yōu)先級分別是pi和api,且api≥pi,如果?m,n使得 Pmn∈Γ,那么 Pmn可以搶占Pij(當(dāng)且僅當(dāng)Pmn的優(yōu)先級pm大于api)。

如圖6所示,在時刻3,雖然 P12已經(jīng)就緒,根據(jù)FT—MT算法的優(yōu)先級提升規(guī)則,P12無法搶占P21,因此,P21可以繼續(xù)執(zhí)行,并在時刻3.5運(yùn)行完畢,同時系統(tǒng)撤銷A21。在時刻3.5,P12開始運(yùn)行,并在時刻 5運(yùn)行完畢,A12也被系統(tǒng)撤銷?？梢钥吹?增加優(yōu)先級提升規(guī)則后的FT—MT算法進(jìn)一步提高了主版本的完成率。

3.2 算法FT—MT的描述

文獻(xiàn)[3]提出的CAT算法和EIT算法能夠進(jìn)一步提高Basic算法的性能。算法FT—MT調(diào)用CAT算法預(yù)測主版本的可執(zhí)行性,如果該主版本滿足可執(zhí)行的條件,則執(zhí)行該主版本,否則,取消該主版本。當(dāng)處理器處于空閑狀態(tài)時,算法FT—MT調(diào)用EIT算法提前執(zhí)行替代版本,為其他主版本留出更多的調(diào)度時間。如圖6所示,在區(qū)間[7.5,9]內(nèi),由于既沒有就緒待執(zhí)行的主版本,也沒有通知時間已到的替代版本,使得處理器處于空閑狀態(tài)。顯然,通過將FT—MT算法和EIT結(jié)合,當(dāng)處理器處于空閑狀態(tài)時,系統(tǒng)就可以提前執(zhí)行替代版本,從而避免了處理器空閑的情況。圖7給出了F T—MT算法的偽代碼。

3.3 舉例

本節(jié)以數(shù)控系統(tǒng)中的混合任務(wù)調(diào)度為例說明FT—MT算法的調(diào)度過程。為簡化分析,假設(shè)混合任務(wù)集中包括四個任務(wù),其中兩個實(shí)時周期任務(wù),一個實(shí)時突發(fā)任務(wù)和一個非實(shí)時任務(wù)。各任務(wù)的參數(shù)描述如表1所示。

表1 任務(wù)參數(shù)

首先按照反向速率單調(diào)算法為替代版本分配執(zhí)行區(qū)間。在區(qū)間[0,30],替代版本的臨界點(diǎn)分別是v1j={4,9,14,19,24,29}(j=1,2,…,6)和v2j={3,10,16,22,27}(j=1,2,…,5)。

下面介紹FT—MT算法的調(diào)度過程。圖8所示為該任務(wù)集的運(yùn)行過程。在時刻0,具有較高優(yōu)先級的主版本P11就緒并開始執(zhí)行,假設(shè)P11由于軟件錯誤在時刻2失敗,所以預(yù)留給A11的區(qū)間[4,5]不能被撤銷。在時刻2,P21開始運(yùn)行,在時刻3,A21的臨界點(diǎn)到了,由于替代版本的優(yōu)先級高于所有主版本的優(yōu)先級,因此,A21搶占P21執(zhí)行。同理,在接下來的區(qū)間[4,5]和[5,6],系統(tǒng)分別運(yùn)行A11和A21。在時刻6,P12和P22同時就緒,由于P12的周期較P22短,所以系統(tǒng)執(zhí)行P12。假設(shè)P12在時刻8執(zhí)行完畢,那么分配給A12的區(qū)間[9,10]就不再需要,系統(tǒng)撤銷了A12。接著P22開始執(zhí)行并且在時刻10執(zhí)行完畢,所以A12也被系統(tǒng)撤銷。在時刻10,P13開始運(yùn)行,假設(shè)P13在時刻12發(fā)生錯誤,由于OTR13=C13=2,等于P13的執(zhí)行時間,根據(jù)FT—MT算法的重新執(zhí)行規(guī)則,系統(tǒng)在時刻12重新執(zhí)行P13。P13在時刻14運(yùn)行完畢,A13被系統(tǒng)撤銷。在時刻14,P23和實(shí)時突發(fā)性任務(wù)S1同時就緒,由于S1的優(yōu)先級較高,系統(tǒng)選擇S1運(yùn)行,在時刻14.5,S1執(zhí)行完畢。由于OTR23=1.5＜C23=2,根據(jù)FT—MT算法的首次執(zhí)行規(guī)則,系統(tǒng)撤銷P23,開始執(zhí)行N1并在時刻15執(zhí)行完畢。P14在區(qū)間[15,16]和[18,19]執(zhí)行,而 A23在區(qū)間[16,18]執(zhí)行。

4 仿真實(shí)驗(yàn)

為了對比不同調(diào)度算法的容錯能力,本文定義了兩個衡量容錯算法性能的指標(biāo):主版本成功率(success rate of primary,SRP)和任務(wù)成功率(success rate of tasks,SRT)。SRP是主版本的實(shí)際完成數(shù)量與主版本總數(shù)量的比值,該指標(biāo)衡量容錯調(diào)度算法輸出結(jié)果的計算精度。SRT是任務(wù)的實(shí)際完成數(shù)量與任務(wù)總數(shù)量的比值,該指標(biāo)衡量容錯算法對于混合任務(wù)的調(diào)度性能。

具體實(shí)驗(yàn)環(huán)境如下:

硬件平臺:Intel(R)Pentium(R)M,1.73GHz,512MB

軟件平臺:REDHAT7.0

實(shí)時內(nèi)核:Linux—2.4.20+RTAI3.1

本次仿真實(shí)驗(yàn)共模擬了1000組任務(wù)集,每組任務(wù)集包括100個任務(wù),任務(wù)集中各種任務(wù)的類型及所占比例如表2所示。對于任意給定的任務(wù)τi,其周期 Ti,截止期Di,執(zhí)行時間Ci和替代版本的執(zhí)行時間以及任務(wù)集的錯誤率f p都是隨機(jī)產(chǎn)生的,但需要滿足Di=Ti≥Ci≥2＞0且f p＞0。

表2 任務(wù)類型及所占比例

4.1 仿真實(shí)驗(yàn)1

本實(shí)驗(yàn)測試了FT—MT算法在不同的處理機(jī)利用率U下SRP值的變化情況。該實(shí)驗(yàn)測試了f p=0.05、fp=0.1和 fp=0.15三種情況下FT—MT算法的SRP值,如圖9所示,結(jié)果表明:

(1)當(dāng)處理機(jī)利用率U低于55%時,FT—MT算法的SRP值始終保持在100%,即所有的主版本都能在其替代版本的臨界點(diǎn)到來之前運(yùn)行完畢。

(2)隨著處理機(jī)利用率U的增加(高于55%),對于不同 f p值,FT—MT算法的SRP值逐漸減少,且任務(wù)集的錯誤率 fp越大,SRP值下降得越快。這是因?yàn)閁值越大,表明任務(wù)主版本的資源需求越大,因此所能完成主版本的數(shù)量就越少,而 fp越大,即主版本出錯的概率越大,導(dǎo)致所能完成主版本的數(shù)量越少。

4.2 仿真實(shí)驗(yàn)2

本實(shí)驗(yàn)比較了FT—MT和BF兩種算法在處理混合任務(wù)集時的調(diào)度性能,實(shí)驗(yàn)中錯誤率 f p的變化范圍是[0.05,0.25],處理機(jī)利用率U的變化范圍是[0.01,0.9]。如圖10所示,兩種算法的任務(wù)成功率SRT值都表現(xiàn)出了一種由高到低的趨勢。比較圖10a和圖10b可以發(fā)現(xiàn),在容錯能力方面FT—MT算法明顯優(yōu)于BF算法。這是因?yàn)锽F算法的容錯機(jī)制是基于時間冗余的,需要額外的運(yùn)行開銷,即不管主版本是否發(fā)生錯誤,系統(tǒng)都需要保存每個檢查點(diǎn)的狀態(tài)信息,導(dǎo)致當(dāng)錯誤率和處理機(jī)利用率都較高時任務(wù)的成功率很低,而FT—MT算法在主版本不發(fā)生錯誤時,不需要額外的運(yùn)行開銷,只有當(dāng)主版本無法完成時才執(zhí)行替代版本以達(dá)到容錯目的,因此使得主版本運(yùn)行正確的概率大大增加。

5 結(jié)束語

作為實(shí)時系統(tǒng)的一種典型應(yīng)用,數(shù)控系統(tǒng)有其自身的要求。除了具有嚴(yán)格的實(shí)時性以及高度的可靠性之外,數(shù)控系統(tǒng)還需要進(jìn)行多種類型任務(wù)并存的混合任務(wù)調(diào)度。本文首先分析了不同容錯模型的特點(diǎn),提出了基于主/替代版本的軟件容錯實(shí)時調(diào)度算法(FT—MT),通過推遲替代版本在其截止期內(nèi)的執(zhí)行,提高了主版本的完成率,改善了系統(tǒng)輸出結(jié)果的計算精度,同時增加了主版本的可執(zhí)行規(guī)則,提高了主版本可執(zhí)行性的預(yù)測精度,有效減少了浪費(fèi)的處理機(jī)時間。FT—MT算法實(shí)現(xiàn)簡單,運(yùn)行開銷小,資源利用率高,能為系統(tǒng)提供容錯支持,完全滿足數(shù)控系統(tǒng)對實(shí)時性及可靠性的要求。

[1]Zhang Y X,Fang G H,Wang Y.A Feedback—driven Online Scheduler for Processes with Imprecise Computing[J].Journal of Software,2004,15(4):616-623.

[2]陳宇,熊光澤.基于資源回收的容錯最早時限優(yōu)先調(diào)度[J].系統(tǒng)工程與電子技術(shù),2003,25(10):1274-1277.

[3]Han C C,Shin K G,Wu J.A Fault—tolerant Scheduling Algorithm for Real—time Periodic Tasks with Possible Software Faults[J].IEEE Transactions on Computers,2003,52(3):362-372.

[4]李慶華,韓建軍,AAEssa,等.硬實(shí)時系統(tǒng)中基于軟件容錯的動態(tài)調(diào)度算法[J].軟件學(xué)報,2005,16(1):101-107.

[5]劉東,張春元,李瑞,等.軟件容錯模型中的容錯實(shí)時調(diào)度算法[J].計算機(jī)研究與發(fā)展,2007,44(9):1495-1500.

[6]姚鑫驊,傅建中,陳子辰,等.面向數(shù)控系統(tǒng)的優(yōu)化調(diào)度算法及容錯策略研究[J].計算機(jī)集成制造系統(tǒng),2007,13(4):768-776.