基于排隊論和時間需求分析法的實時系統(tǒng)時間行為分析

摘要：針對目前廣泛使用的固態(tài)優(yōu)先級RMS調(diào)度策略，利用時間需求分析算法對系統(tǒng)中所有周期任務(wù)進行可調(diào)度性分析測試，保證其在臨界點仍可以滿足時限。利用排隊論中的M/M/1/K排隊系統(tǒng)，根據(jù)非周期事件接收緩沖和可延期服務(wù)器定量分析非周期事件的平均響應(yīng)時間和系統(tǒng)異步事件丟失率，使之符合系統(tǒng)要求。

關(guān)鍵詞：實時任務(wù)模型； 可延期服務(wù)器； 時間需求分析法； M/M/1/K排隊模型；可調(diào)度性

中圖分類號：TP316．2文獻標志碼：A

文章編號：1001-3695(2007)12-0106-03

實時系統(tǒng)不僅要保證邏輯的正確性，而且要在確定的時間內(nèi)提供正確的結(jié)果。如果某個實時任務(wù)沒有在要求的時限內(nèi)完成，就會導(dǎo)致嚴重后果，對于強實時系統(tǒng)甚至?xí)?dǎo)致整個系統(tǒng)崩潰。許多實時應(yīng)用系統(tǒng)涉及混合任務(wù)集的調(diào)度處理。其中任務(wù)可能具有硬截止期和軟截止期。硬截止期任務(wù)用于保證系統(tǒng)正確運行，通常是周期性的任務(wù)；軟截止期任務(wù)用于實現(xiàn)相對不太關(guān)鍵的系統(tǒng)活動，這類任務(wù)通常是非周期的，具有不確定的到達時間。任務(wù)的時間需求不同，導(dǎo)致了調(diào)度的策略和目標也不同。一般來說，混合任務(wù)集的調(diào)度目標是保證硬截止期的任務(wù)滿足其截止期。在上述前提下，在規(guī)定的平均響應(yīng)時間內(nèi)，使非周期事件的丟失率最小。本文以先進飛機配電系統(tǒng)主處理機為例，利用時間需求分析方法和M/M/1/K排隊模型分析系統(tǒng)中強實時任務(wù)的可調(diào)度性、非周期事件的響應(yīng)時間和響應(yīng)數(shù)量之間的關(guān)系。

1先進飛機配電系統(tǒng)主處理機實時任務(wù)模型

1．1先進飛機配電系統(tǒng)主處理機任務(wù)劃分

先進飛機電氣綜合控制與管理系統(tǒng)采用分布式計算機系統(tǒng)和負載智能管理技術(shù)。該系統(tǒng)是由電氣系統(tǒng)處理機(PSP)、電氣負載管理中心(ELMC)和匯流條控制器(BPCU)組成的智能化的分布控制網(wǎng)絡(luò)。其中電氣系統(tǒng)主處理機是先進飛機電氣綜合控制與管理系統(tǒng)的核心部分。其功能示意圖如圖1所示。該系統(tǒng)是典型的實時系統(tǒng)，本執(zhí)行軟件以實時操作系統(tǒng)VxWorks作為系統(tǒng)軟件，由它進行實時任務(wù)調(diào)度和資源分配管理。VxWorks是以任務(wù)為基本運行單位，并以優(yōu)先級驅(qū)動算法來調(diào)度任務(wù)，所以將PSP的功能合理劃分成若干任務(wù)并為每個任務(wù)賦予合適的優(yōu)先級是保證系統(tǒng)實時性的關(guān)鍵。

根據(jù)PSP的功能，PSP實時任務(wù)模型包括如下七個任務(wù)：

a）初始化任務(wù)。進行系統(tǒng)初始化，開機自檢，建立并啟動多任務(wù)，完成系統(tǒng)初始操作后，退出執(zhí)行。

b）電網(wǎng)狀態(tài)采集任務(wù)。周期訪問ELMC和BPCU等智能終端，獲得電網(wǎng)狀態(tài)數(shù)據(jù)。

c）實時數(shù)據(jù)庫管理任務(wù)。更新實時數(shù)據(jù)時間戳，剝離過期數(shù)據(jù)，保證實時數(shù)據(jù)庫中數(shù)據(jù)的時間、邏輯一致性。

d）電網(wǎng)狀態(tài)分析任務(wù)。根據(jù)實時數(shù)據(jù)庫中各種終端的狀態(tài)數(shù)據(jù)判斷系統(tǒng)的運行情況，進行故障診斷，并產(chǎn)生相應(yīng)的故障恢復(fù)操作序列。

e）負載方程解算任務(wù)。根據(jù)實時數(shù)據(jù)庫中的當(dāng)前電網(wǎng)狀態(tài)解算負載供電請求方程和負載控制方程，產(chǎn)生對負載的控制指令。

f）飛機電網(wǎng)狀況上傳任務(wù)。接收公共設(shè)備管理系統(tǒng)的指令上傳當(dāng)前飛機電網(wǎng)狀態(tài)、故障以及恢復(fù)的時間、位置和可能的原因。

g）機內(nèi)自檢測任務(wù)。周期性地進行PSP系統(tǒng)自檢，向公共設(shè)備管理系統(tǒng)報告工作狀況。

由于接收公共設(shè)備管理系統(tǒng)指令的時刻對于PSP來說是隨機發(fā)生的，且對于保證飛機電網(wǎng)正常供電來說，上傳狀態(tài)數(shù)據(jù)相對于其他任務(wù)是次要的。上述任務(wù)集中飛機電網(wǎng)狀況上傳任務(wù)是非周期執(zhí)行的弱實時任務(wù)，其余任務(wù)皆為周期執(zhí)行的強實時任務(wù)。

1．2先進飛機配電系統(tǒng)主處理機實時任務(wù)模型建立

為便于定量分析該混合任務(wù)系統(tǒng)的可調(diào)度性等實時性能指標，先對任務(wù)的時間參數(shù)進行建模：

為了獲得更好的任務(wù)時間行為可預(yù)測性，減小系統(tǒng)調(diào)度開銷，PSP采用固定優(yōu)先級的靜態(tài)調(diào)度算法——RMS算法調(diào)度周期任務(wù)。該算法主要是解決單一處理器上的多任務(wù)調(diào)度問題。其基本思想是：基于任務(wù)的周期設(shè)置其優(yōu)先級，周期越短，任務(wù)的優(yōu)先級越高；再根據(jù)任務(wù)優(yōu)先級高低調(diào)度執(zhí)行。

對于非周期任務(wù)，為降低非周期任務(wù)的平均響應(yīng)時間，改進非周期任務(wù)時間行為的可預(yù)測性。PSP采用的處理方法是使用延期服務(wù)器。該方法用一個或幾個專用的具有較高優(yōu)先級的周期任務(wù)執(zhí)行所有非周期任務(wù)，這種周期任務(wù)稱為可延期服務(wù)器。根據(jù)周期大小，服務(wù)器有固定優(yōu)先級，服務(wù)器的執(zhí)行時間被稱為預(yù)算，它在每個服務(wù)器周期就緒時補充。如果此時沒有掛起的非周期任務(wù)，則在本周期內(nèi)保持這些分配的執(zhí)行預(yù)算。當(dāng)有非周期任務(wù)就緒時，只要服務(wù)器有充足的預(yù)算，就可在其周期內(nèi)執(zhí)行非周期任務(wù)。其執(zhí)行預(yù)算就按照每單位時間一個的速率消耗。延期服務(wù)器可用如下模型來描述：

4PSP任務(wù)集的實際調(diào)度測試結(jié)果

圖6是利用VxWorks提供的邏輯分析儀WindView觀測繪制的系統(tǒng)任務(wù)集實際調(diào)度結(jié)果。從圖中可以看出，按照本文的調(diào)度策略，PSP任務(wù)集是可以調(diào)度的，強實時任務(wù)可以滿足各自的時限。任務(wù)延遲時間符合時間需求分析法的計算結(jié)果。在50~58 ms，PSP連續(xù)接到公共設(shè)備管理器的三組上傳指令，上傳要求的數(shù)據(jù)包最小計算時間為3×4=12 ms。飛機電網(wǎng)狀況上傳任務(wù)可延期服務(wù)器利用在40 ms時刻補充并延期的預(yù)算立即執(zhí)行。經(jīng)過四個服務(wù)器周期，在141.5 ms時刻將數(shù)據(jù)包發(fā)送完畢，響應(yīng)時間為91．5 ms，與M/M/1/K排隊模型的分析計算結(jié)果基本一致。

5分析結(jié)果的進一步思考

圖4、5中的虛曲線表示的是可延期服務(wù)器的強度降低1．5%，即10％時PSP對上位機指令的平均響應(yīng)時間和信息丟失率。由此可見，在類似于PSP的固定優(yōu)先級實時系統(tǒng)中，可延期服務(wù)器的強度對非周期任務(wù)的響應(yīng)時間的影響是比較明顯的。但根據(jù)2.2節(jié)的計算結(jié)果，可延期周期服務(wù)器的強度大小要受到強實時任務(wù)可調(diào)度性的約束。其服務(wù)強度不能太高。這主要是由于服務(wù)器的預(yù)算補充規(guī)則比較保守，下一步可以利用空閑挪用思想設(shè)計更優(yōu)化的周期服務(wù)器預(yù)算補充策略，使之能夠充分利用CPU空閑時間，進一步降低非周期任務(wù)的平均響應(yīng)時間，增加非周期事件響應(yīng)數(shù)量。

6結(jié)束語

本文以實時任務(wù)時間需求分析法和排隊論為理論分析工具，以先進飛機電氣系統(tǒng)處理機實時系統(tǒng)為分析實例，建立了該處理機的實時任務(wù)調(diào)度模型，得到了強實時任務(wù)最大執(zhí)行時間和弱實時任務(wù)平均響應(yīng)時間的數(shù)學(xué)表達形式，進而定量分析了先進飛機電氣系統(tǒng)處理機實時系統(tǒng)的實時性能指標，并根據(jù)分析結(jié)果給出了進一步提高實時性能的一種思路。

參考文獻：

[1]BUTTAZZO G， ABENI L.Adaptive workload management through elastic scheduling[J]. Real－time Systems， 2002，23(1－2):7-24.

[2]GLASS R L. Real－time software[M].[S.l.]:Prentice-Hall， 2000:72-101.

[3]王強，王宏安，金宏，等.實時系統(tǒng)中非定期任務(wù)調(diào)度算法綜述[J].計算機研究與發(fā)展，2004，41(3):385-387.

[4]劉育芳，張立臣.實時系統(tǒng)最壞執(zhí)行時間分析[J].計算機應(yīng)用研究，2005，22(11):8-10.

[5]LIUJ W S.實時系統(tǒng)[M].姬孟洛，李軍，王馨，等譯.北京:高等教育出版社，2003:100-140，163-170.

[6]唐應(yīng)輝，唐小我.排隊論基礎(chǔ)與分析技術(shù)[M].北京:科學(xué)出版社，2006:57-61.

[7]封建湖，車剛明，聶玉峰.數(shù)值分析[M].北京:科學(xué)出版社，2002:185-189.

[8]趙選民，徐偉，師義民，等.數(shù)理統(tǒng)計[M].2版.北京:科學(xué)出版社，2003:165-171.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文”