基于排隊論和時間需求分析法的實時系統時間行為分析

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

關鍵詞：實時任務模型； 可延期服務器； 時間需求分析法； M/M/1/K排隊模型；可調度性

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

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

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

1先進飛機配電系統主處理機實時任務模型

1．1先進飛機配電系統主處理機任務劃分

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

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

a）初始化任務。進行系統初始化，開機自檢，建立并啟動多任務，完成系統初始操作后，退出執行。

b）電網狀態采集任務。周期訪問ELMC和BPCU等智能終端，獲得電網狀態數據。

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

d）電網狀態分析任務。根據實時數據庫中各種終端的狀態數據判斷系統的運行情況，進行故障診斷，并產生相應的故障恢復操作序列。

e）負載方程解算任務。根據實時數據庫中的當前電網狀態解算負載供電請求方程和負載控制方程，產生對負載的控制指令。

f）飛機電網狀況上傳任務。接收公共設備管理系統的指令上傳當前飛機電網狀態、故障以及恢復的時間、位置和可能的原因。

g）機內自檢測任務。周期性地進行PSP系統自檢，向公共設備管理系統報告工作狀況。

由于接收公共設備管理系統指令的時刻對于PSP來說是隨機發生的，且對于保證飛機電網正常供電來說，上傳狀態數據相對于其他任務是次要的。上述任務集中飛機電網狀況上傳任務是非周期執行的弱實時任務，其余任務皆為周期執行的強實時任務。

1．2先進飛機配電系統主處理機實時任務模型建立

為便于定量分析該混合任務系統的可調度性等實時性能指標，先對任務的時間參數進行建模：

為了獲得更好的任務時間行為可預測性，減小系統調度開銷，PSP采用固定優先級的靜態調度算法——RMS算法調度周期任務。該算法主要是解決單一處理器上的多任務調度問題。其基本思想是：基于任務的周期設置其優先級，周期越短，任務的優先級越高；再根據任務優先級高低調度執行。

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

4PSP任務集的實際調度測試結果

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

5分析結果的進一步思考

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

6結束語

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

參考文獻：

[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]王強，王宏安，金宏，等.實時系統中非定期任務調度算法綜述[J].計算機研究與發展，2004，41(3):385-387.

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

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

[6]唐應輝，唐小我.排隊論基礎與分析技術[M].北京:科學出版社，2006:57-61.

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

[8]趙選民，徐偉，師義民，等.數理統計[M].2版.北京:科學出版社，2003:165-171.

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