面向數控系統的容錯實時調度算法研究

丁萬夫 郭銳鋒 秦承剛

1.中國科學院研究生院,北京,100039

2.中國科學院沈陽計算技術研究所,沈陽,110004

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

0 引言

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

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

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

本文首先建立了數控系統混合任務調度的模型,提出了一種具有容錯功能的實時調度算法FT—MT,在此基礎上給出了該算法的偽代碼描述以及實例研究,最后進行了調度算法的仿真實驗。

1 系統、任務及容錯模型

從任務組成來看,數控系統是一個典型的混合任務系統。其任務主要包括實時周期任務、實時突發任務和非實時任務。根據任務的關鍵度不同,又可將實時周期任務分為有容錯需求的實時周期任務和無容錯需求的實時周期任務。

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

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

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

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

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

定義5 替代版本在其截止期內的最遲開始時間稱為該替代版本的臨界點。

本文研究的前提條件:

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

(2)在運行過程中,規定替代版本具有最高的優先權,實時突發任務的優先權高于實時周期任務的優先權,而非實時任務具有最低的優先權。

2 問題描述

2.1 Basic算法介紹

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

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

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

2.2 Basic算法存在的問題

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

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

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

3 混合任務集的容錯調度算法FT—M T

3.1 FT—MT算法

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

3.1.1 主版本重新執行規則

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

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

主版本重新執行規則:當且僅當主版本Pij的執行時間Ci小于或者等于OTRij,主版本Pij才可以重新執行,否則系統撤銷Pij的執行。

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

3.1.2 主版本優先級提升規則

為了驗證優先級提升規則的有效性,再來看一個例子 。給定任務集 Γfrp={τ1,τ2},參數 τ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的周期較短,根據RM調度規則,系統將選擇 P11運行。P11在時刻 1.5運行完畢,所以系統撤銷了A11。在時刻1.5,P21開始執行,假設P21在時刻1.5發生錯誤。由于在時刻2.5沒有其他就緒的任務,并且 P21的OTR21為1.5,等于 P21的執行時間,根據Kernel算法重新執行規則,系統將重新執行P21。在時刻3,P12就緒,由于P12的優先級高于 P21,所以P12搶占 P21開始運行。因為時刻4是替代版本A21的通知時間,而替代版本的優先級高于所有主版本的優先級,所以A21搶占 P12開始運行。在時刻 5,A21運行完畢,又因為時刻5是A12的通知時間,所以系統撤銷了P12,轉而運行A12。

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

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

如圖6所示,在時刻3,雖然 P12已經就緒,根據FT—MT算法的優先級提升規則,P12無法搶占P21,因此,P21可以繼續執行,并在時刻3.5運行完畢,同時系統撤銷A21。在時刻3.5,P12開始運行,并在時刻 5運行完畢,A12也被系統撤銷。可以看到,增加優先級提升規則后的FT—MT算法進一步提高了主版本的完成率。

3.2 算法FT—MT的描述

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

3.3 舉例

本節以數控系統中的混合任務調度為例說明FT—MT算法的調度過程。為簡化分析,假設混合任務集中包括四個任務,其中兩個實時周期任務,一個實時突發任務和一個非實時任務。各任務的參數描述如表1所示。

表1 任務參數

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

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

4 仿真實驗

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

具體實驗環境如下:

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

軟件平臺:REDHAT7.0

實時內核:Linux—2.4.20+RTAI3.1

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

表2 任務類型及所占比例

4.1 仿真實驗1

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

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

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

4.2 仿真實驗2

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

5 結束語

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

[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]陳宇,熊光澤.基于資源回收的容錯最早時限優先調度[J].系統工程與電子技術,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,等.硬實時系統中基于軟件容錯的動態調度算法[J].軟件學報,2005,16(1):101-107.

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

[6]姚鑫驊,傅建中,陳子辰,等.面向數控系統的優化調度算法及容錯策略研究[J].計算機集成制造系統,2007,13(4):768-776.