容錯實時任務調度的DSPN建模與分析

周 悅, 王 勛, 郭 威

(1.上海海洋大學 工程學院，上海 201306; 2.沈陽建筑大學 信息與控制工程學院，沈陽 110168;3.上海深淵科學工程技術研究中心，上海 201306)

容錯實時任務調度的DSPN建模與分析

周 悅1,2，3, 王 勛2, 郭 威3

(1.上海海洋大學 工程學院，上海 201306; 2.沈陽建筑大學 信息與控制工程學院，沈陽 110168;3.上海深淵科學工程技術研究中心，上海 201306)

復雜系統的形式化描述對新系統的設計以及現有系統的改進與評價都具有十分重要的作用;針對處理機系統容錯實時混合任務調度，提出采用確定與隨機Petri網進行建模與性能分析;首先，根據任務執行的優先級、周期性、容錯性和實時性，將任務分為四類；然后，采用DSPN對任務調度執行過程，不同優先級任務搶占式調度，處理機故障及故障恢復過程進行建模，由此構成處理機系統容錯實時任務調度過程的DSPN模型；最后，仿真實驗結果表明，在負載相同情況下，處理機利用率基本相同，且具有容錯的實時任務調度算法可以有效地降低任務錯失率;容錯實時任務調度DSPN模型可以為復雜任務調度系統的Petri網建模與分析奠定了基礎，并為實際工程應用提供了理論指導。

確定與隨機Petri網；容錯；實時；任務調度

0 引言

容錯實時控制系統是能夠在確定時間內執行計算或者處理任務，并對外部的異常事件進行及時響應的計算機控制系統，已經被廣泛應用于航空航天、水下機器人、工業控制等領域，具有十分嚴格的實時性和可靠性要求。隨著實時系統應用復雜性的增加，如何保證在系統出現故障的情況下，仍然能夠滿足系統的實時性要求，己經成為目前實時系統研究和設計的新挑戰[1-3]。隨著容錯實時調度算法的研究與應用，對其建模與分析備受國內外諸多學者的關注。Petri(deterministic and stochastic petri net, DSPN)網具有對復雜系統結構和邏輯行為的建模及仿真能力，被廣泛應用至系統流程建模和優化中[4]。熊曾剛等針對P2P模式的網格任務調度采用著色Petri網進行建模與分析[5]；趙彬等針對云計算異構服務器集群環境下的高能耗問題提出一種最小能耗優先的任務調度策略，并采用隨機Petri網進行建模和分析[6]；張海濤等提出了一種基于資源的時間Petri網模型，該模型采用固定優先級的搶占式調度，即將任務的優先級附著到變遷上，從而實現單處理機任務調度的建模[7]；陳艾等提出利用Petri網對處理機瞬時故障及恢復進行建模，并在故障恢復過程引入檢查點技術，提高了任務實時性[8]；呂曉明采用Petri網對任務的調度和行為進行了分析[9]。確定與隨機Petri網DSPN特別適于描述和分析具有確定與隨機時延的復雜系統的動態行為[10]，為此本文采用DSPN構建搶占式的容錯實時任務調度模型，特別是描述了高優先級任務搶占低優先級任務、處理機出現故障情況下的斷點保護與恢復過程，為高性能容錯實時系統任務調度與性能分析奠定基礎。

1 任務模型

按照任務執行的優先級和周期性，容錯實時系統通常將任務集Task分為4類，即Task={Tas,Tps,Tpas,Tap}。任意任務τ，τ∈Task，其中：

Tas為具有容錯需求的緊急非周期任務集；

圖1 容錯實時任務調度過程DSPN模型

Tps為具有容錯需求的緊急高優先級周期任務集；

Tpas為具有容錯需求非緊急低優先級周期任務集；

Tap為無容錯需求的非周期任務集。

本文Task中的所有任務相互獨立，優先級依次為Tas、Tps、Tpas和Tap，即Tas優先級最高。

2 容錯實時任務調度過程DSPN模型

具有容錯的搶占式任務調度將根據是否有故障發生、處理機忙閑狀態、任務優先級，來決定待處理隊列的任務τ是否搶占執行還是等待，以及任務被中斷執行后是否恢復執行。假設非周期任務Tas和Tap到達的時間間隔服從指數分布，由隨機時間變遷Tarrive-as和Tarrive-ap描述；周期性任務Tps和Tpas的到達時間間隔具有周期性，由確定時間變遷Tarrive-ps和Tarrive-pas描述。圖1為具有故障容錯的搶占式任務調度過程DSPN模型。

由圖1可見，本DSPN模型：

(1)有效地描述了任務執行調度過程需要經過任務隨機(或周期)到達、等待、處理執行，及完成釋放資源4個階段。庫所Pp中含有token表示處理機為空閑狀態，庫所Pexe-X中含有token時表示任務X正在執行，變遷Tmicro-X的參數表示任務X執行的時鐘粒度，庫所Pexe1-X和Pexe2-X中含有的token數量描述了任務執行的剩余時間和已經執行時間，庫所Pstate-X含有Token時表示任務X沒有被高優先級任務搶占，弧權值ωX描述了任務執行所需要時鐘粒度的倍數，變遷Texe-X發生表示任務X執行結束釋放處理機資源；

(2)有效地描述了高優先級任務的搶占行為和任務恢復執行過程，即正在執行的低優先級任務首先進入中斷保護狀態，此時待處理的高優先級任務將搶占低優先級任務的處理機資源從而被調度執行，直到高優先級任務執行完成，恢復處理機為空閑狀態；低優先級任務將再次占用處理機資源，從斷點處繼續執行，直至任務完成。變遷Tas-pas、Tas-ap、Tps-ap、Tas-ps、Tps-pas和Tpas-ap發生表示高優先級任務搶占低優先級任務，變遷Tback-X發生表示任務X恢復中斷；

(3)有效地描述了故障出現時，若處理機空閑，將保持空閑狀態直至故障解除；否則，若處理機正在執行的任務具有容錯需求，則故障出現時中斷該任務的執行過程并設置斷點保護，直到處理機故障解除，恢復任務故障前的執行狀態；若正在執行的任務無容錯需求，則當故障出現時，終止該任務的執行過程。庫所Pf和Pr中含有Token時分別表示處理機出現故障和正常狀態，二者通過兩個服從指數分布的隨機時間變遷Tf和Tr的發生相互轉換；處理機在執行任務時發生故障，無容錯任務τap通過觸發變遷Tstop1-ap和Tstop2-ap終止任務執行，及觸發Tstop3-ap釋放處理機資源；具有容錯的任務τas、τps和τpas分別通過與測試弧相連的變遷Tpause1-as、Tpause1-ps、Tpause1-pas將庫所Pstate和Pexe中的Token移入對應的庫所Ppause中，其中Ppause含有Token時表示任務由于處理機故障而處于中斷保護狀態；當處理機故障解除，庫所Ppause中的Token通過使變遷Tpause2-as、Tpause2-ps或Tpause2-pas發生，使得任務可以恢復故障前的狀態繼續執行，即完成處理機故障結束后斷點任務恢復的過程。

3 實驗仿真研究

假設任務截止期等于任務周期，處理機故障的處理與斷點恢復不占用處理機資源,混合實時任務集為表1。

表1 混合實時任務集實例

其中：表1非周期任務Tas和Tap的周期是指其釋放時間間隔服從指數分布的均值。

DSPN模型的有關時間變遷參數(單位ms)分別為：指數時間變遷Tarrive-ap和Tarrive-as的時間分布均值為27ms和18ms，變遷Tf和Tr的時間分布均值為1 500ms和3ms；確定時間變遷Tarrive-ps和Tarrive-pas的時間間隔為70ms和15ms，Tmicro-X的時間間隔為1ms。

利用仿真軟件WinTTPN對所建立的故障容錯實時任務調度DSPN模型進行仿真實驗研究。若任務均在截止期內執行完成，則滿足任務的實時性。任務執行時間超出截止期或由于處理機故障致使任務不能有效完成，則為任務執行出錯，由任務錯失率(任務執行出錯的次數與任務執行次數的比值)衡量。

3.1 無故障情況

在處理機無故障情況下，將本文具有故障容錯的搶占式實時任務調度算法與文獻[8]中無搶占容錯調度相比較，任務調度性能如圖2～3所示。

圖2 處理機利用率

圖3 任務錯失率

由圖2～3可見，本文調度算法與文獻[8]調度算法均隨著非周期任務Tap平均釋放時間間隔的減少，即任務負載的增加，處理機利用率不斷增加，此時每個任務無論是否存在搶占，其占用資源利用率相同，所以在相同任務負載情況下兩種算法的處理機利用率基本相同，表明所建DSPN模型的有效性；隨著Tap釋放時間間隔減小至最長執行時間，處理機因無法承受過大的任務負載，導致任務執行超出截止期而出錯，此時處理機利用率迅速增加，其錯失率也在最長執行時間處出現大于0，并隨著Tap釋放時間間隔的減小，任務錯失率不斷增加；由于文獻[8]中任務不存在搶占過程，任務錯失率會隨著Tap釋放時間間隔的減小而明顯高于本文任務調度算法。

3.2 發生故障情況

針對本文任務集，對比分析無故障容錯調度算法與具有故障容錯調度算法下的處理機利用率與任務錯失率，如圖4～5所示。

圖4 處理機利用率

圖5 任務錯失率

由圖4～5可見，隨著非周期任務Tap平均釋放時間間隔的減小，處理機利用率不斷增加，無故障容錯與具有故障容錯調度算法的處理機利用率在相同任務負載情況下基本相同；而對于任務錯失率，無故障容錯調度算法的高于具有故障容錯調度算法的，這是因為當處理機產生故障時，無故障容錯調度算法將終止當前執行的任務，導致任務錯失率增加；而具有故障容錯調度算法將對當前執行的任務進行容錯，降低任務錯失率。

4 結論

本文應用確定與隨機Petri網DSPN，針對處理機系統的4種具有不同優先級和故障容錯需求的實時任務，并考慮處理機故障的發生與恢復，構建了具有故障容錯的搶占式實時任務調度過程DSPN模型，有效地描述了任務調度執行過程、高優先級任務搶占和低優先級任務中斷及恢復行為、處理機出現故障及容錯任務調度的行為。仿真實驗結果從處理機利用率和任務錯失率兩個方面表明所構建DSPN模型的有效性，以及具有容錯任務調度算法在處理機利用率相同的情況下可以有效的降低任務錯失率。這些工作為網絡環境下復雜處理機實時任務調度的建模奠定了基礎，也為復雜并行任務的形式化建模與分析提供了一種有效的方法。

[1]DevarajR，SarkarA,etal.Adesignfixtosupervisorycontrolforfault-tolerantschedulingofreal-timemultiprocessorsystemswithaperiodictasks[J].InternationalJournalofControl, 2015, 88(11): 2211-2216.

[2]GaoZW，DingSX,etal.Real-timefaultdiagnosisandfault-tolerantcontrol[J].IEEETransactionsonIndustrialElectronics, 2015，62(6)：3752-3756.

[3]LakshmisowjanyaM，SwethaA,etal.Faulttolerantscheduling-dualredundancyinanautomotivecruisecontrolsystem[J].AdvancesinIntelligentSystemsandComputing, 2015, 337: 497-504.

[4] 劉艷秋，謝 萌，丁偉祥. 基于RCEPN的資源配置優化模型與方法[J].沈陽工業大學學報,2013,35(6)：667-671.

[5] 熊曾剛，楊 揚. 基于Petri網的兩階段網格任務調度模型與分析[J]. 通信學報，2009, 30(8)： 69-77.

[6] 趙 彬，王 淖，王高才.云計算環境下的節能任務調度策略的隨機Petri網分析[J].計算機科學，2015, 42(8)：112-117.

[7] 張海濤，艾云峰. 基于Petri網的分布式實時嵌入式系統調度的建模[J],計算機工程, 2006, 32(18)：6-8.

[8] 陳 艾，周學海，王 峰,等，面向能耗優化的容錯實時系統任務調度模型研究[J]，小型微型計算機系統，2007，28(11): 2056-2061.

[9] 呂曉明,黃考利, 連光耀. 基于時間Petri網的并行測試任務過程建模及驗證技術研究[J]. 計算機測量與控制,2012，20(5):1313-1314.

[10]ChenH,ZhouCJ,etal.ModellingtheprotocolstackinNCSwithdeterministicandstochasticPetrinet[J].InternationalJournalofSystemsScience, 2011, 42(6): 1057-1064.

DSPN Modeling and Performance Analysis of Fault-tolerant Real-time Task Scheduling

Zhou Yue1,2,3, Wang Xun2, Guo Wei3

(1.College of Engineering Science and Technology, Shanghai Ocean University, Shanghai 201306, China; 2.School of Information and Control Engineering, Shenyang Jianzhu University, Shenyang 110168, China; 3.Engineering Research Center of Hadal Science and Technology, Shanghai 201306, China)

Formalized description of the complicated system has the extremely vital role to design the new system, improve and evaluate the existed system. A detailed DSPN(Deterministic and Stochastic Petri Net) model and performance analysis of fault-tolerant real-time hybrid task scheduling in processor system is presented in this paper. Firstly, the tasks are divided into four kinds based on their priority, period, fault tolerance and real-time. Secondly, the behavior of scheduling execution of tasks, preempting resource of the higher priority tasks, interrupting and resuming of tasks, occurring and recovering of failure in processor system is accurately described by DSPN, and then the model of fault-tolerant real-time task scheduling of processor is constructed. Finally, the simulation results demonstrate that the utilization of processor is same at the same load, and the fault-tolerant real-time task scheduling algorithm can effectively reduce the task miss ratio. The DSPN model constructed can analyze the quantitative performance metrics of the fault-tolerant real-time task scheduling, which not only will be useful for constructing the Petri net model for complex processor system, but also be helpful for engineers and researchers.

deterministic and stochastic petri net；fault-tolerant；real-time；task schedule

2016-06-01；

2016-08-19。

國家自然科學基金重點項目(51439004);上海市科委科技項目(14DZ1205500;14DZ2250900)。

周 悅(1970-)，女，上海人，教授，研究生導師，主要從事海洋裝備控制技術，網絡化控制等方向的研究。

1671-4598(2017)01-0107-04

10.16526/j.cnki.11-4762/tp.2017.01.031

TP391

A