容錯實(shí)時(shí)任務(wù)調(diào)度的DSPN建模與分析

周 悅, 王 勛, 郭 威

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

容錯實(shí)時(shí)任務(wù)調(diào)度的DSPN建模與分析

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

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

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

確定與隨機(jī)Petri網(wǎng)；容錯；實(shí)時(shí)；任務(wù)調(diào)度

0 引言

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

1 任務(wù)模型

按照任務(wù)執(zhí)行的優(yōu)先級和周期性，容錯實(shí)時(shí)系統(tǒng)通常將任務(wù)集Task分為4類，即Task={Tas,Tps,Tpas,Tap}。任意任務(wù)τ，τ∈Task，其中：

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

圖1 容錯實(shí)時(shí)任務(wù)調(diào)度過程DSPN模型

Tps為具有容錯需求的緊急高優(yōu)先級周期任務(wù)集；

Tpas為具有容錯需求非緊急低優(yōu)先級周期任務(wù)集；

Tap為無容錯需求的非周期任務(wù)集。

本文Task中的所有任務(wù)相互獨(dú)立，優(yōu)先級依次為Tas、Tps、Tpas和Tap，即Tas優(yōu)先級最高。

2 容錯實(shí)時(shí)任務(wù)調(diào)度過程DSPN模型

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

由圖1可見，本DSPN模型：

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

(2)有效地描述了高優(yōu)先級任務(wù)的搶占行為和任務(wù)恢復(fù)執(zhí)行過程，即正在執(zhí)行的低優(yōu)先級任務(wù)首先進(jìn)入中斷保護(hù)狀態(tài)，此時(shí)待處理的高優(yōu)先級任務(wù)將搶占低優(yōu)先級任務(wù)的處理機(jī)資源從而被調(diào)度執(zhí)行，直到高優(yōu)先級任務(wù)執(zhí)行完成，恢復(fù)處理機(jī)為空閑狀態(tài)；低優(yōu)先級任務(wù)將再次占用處理機(jī)資源，從斷點(diǎn)處繼續(xù)執(zhí)行，直至任務(wù)完成。變遷Tas-pas、Tas-ap、Tps-ap、Tas-ps、Tps-pas和Tpas-ap發(fā)生表示高優(yōu)先級任務(wù)搶占低優(yōu)先級任務(wù)，變遷Tback-X發(fā)生表示任務(wù)X恢復(fù)中斷；

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

3 實(shí)驗(yàn)仿真研究

假設(shè)任務(wù)截止期等于任務(wù)周期，處理機(jī)故障的處理與斷點(diǎn)恢復(fù)不占用處理機(jī)資源,混合實(shí)時(shí)任務(wù)集為表1。

表1 混合實(shí)時(shí)任務(wù)集實(shí)例

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

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

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

3.1 無故障情況

在處理機(jī)無故障情況下，將本文具有故障容錯的搶占式實(shí)時(shí)任務(wù)調(diào)度算法與文獻(xiàn)[8]中無搶占容錯調(diào)度相比較，任務(wù)調(diào)度性能如圖2～3所示。

圖2 處理機(jī)利用率

圖3 任務(wù)錯失率

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

3.2 發(fā)生故障情況

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

圖4 處理機(jī)利用率

圖5 任務(wù)錯失率

由圖4～5可見，隨著非周期任務(wù)Tap平均釋放時(shí)間間隔的減小，處理機(jī)利用率不斷增加，無故障容錯與具有故障容錯調(diào)度算法的處理機(jī)利用率在相同任務(wù)負(fù)載情況下基本相同；而對于任務(wù)錯失率，無故障容錯調(diào)度算法的高于具有故障容錯調(diào)度算法的，這是因?yàn)楫?dāng)處理機(jī)產(chǎn)生故障時(shí)，無故障容錯調(diào)度算法將終止當(dāng)前執(zhí)行的任務(wù)，導(dǎo)致任務(wù)錯失率增加；而具有故障容錯調(diào)度算法將對當(dāng)前執(zhí)行的任務(wù)進(jìn)行容錯，降低任務(wù)錯失率。

4 結(jié)論

本文應(yīng)用確定與隨機(jī)Petri網(wǎng)DSPN，針對處理機(jī)系統(tǒng)的4種具有不同優(yōu)先級和故障容錯需求的實(shí)時(shí)任務(wù)，并考慮處理機(jī)故障的發(fā)生與恢復(fù)，構(gòu)建了具有故障容錯的搶占式實(shí)時(shí)任務(wù)調(diào)度過程DSPN模型，有效地描述了任務(wù)調(diào)度執(zhí)行過程、高優(yōu)先級任務(wù)搶占和低優(yōu)先級任務(wù)中斷及恢復(fù)行為、處理機(jī)出現(xiàn)故障及容錯任務(wù)調(diào)度的行為。仿真實(shí)驗(yàn)結(jié)果從處理機(jī)利用率和任務(wù)錯失率兩個方面表明所構(gòu)建DSPN模型的有效性，以及具有容錯任務(wù)調(diào)度算法在處理機(jī)利用率相同的情況下可以有效的降低任務(wù)錯失率。這些工作為網(wǎng)絡(luò)環(huán)境下復(fù)雜處理機(jī)實(shí)時(shí)任務(wù)調(diào)度的建模奠定了基礎(chǔ)，也為復(fù)雜并行任務(wù)的形式化建模與分析提供了一種有效的方法。

[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的資源配置優(yōu)化模型與方法[J].沈陽工業(yè)大學(xué)學(xué)報(bào),2013,35(6)：667-671.

[5] 熊曾剛，楊 揚(yáng). 基于Petri網(wǎng)的兩階段網(wǎng)格任務(wù)調(diào)度模型與分析[J]. 通信學(xué)報(bào)，2009, 30(8)： 69-77.

[6] 趙 彬，王 淖，王高才.云計(jì)算環(huán)境下的節(jié)能任務(wù)調(diào)度策略的隨機(jī)Petri網(wǎng)分析[J].計(jì)算機(jī)科學(xué)，2015, 42(8)：112-117.

[7] 張海濤，艾云峰. 基于Petri網(wǎng)的分布式實(shí)時(shí)嵌入式系統(tǒng)調(diào)度的建模[J],計(jì)算機(jī)工程, 2006, 32(18)：6-8.

[8] 陳 艾，周學(xué)海，王 峰,等，面向能耗優(yōu)化的容錯實(shí)時(shí)系統(tǒng)任務(wù)調(diào)度模型研究[J]，小型微型計(jì)算機(jī)系統(tǒng)，2007，28(11): 2056-2061.

[9] 呂曉明,黃考利, 連光耀. 基于時(shí)間Petri網(wǎng)的并行測試任務(wù)過程建模及驗(yàn)證技術(shù)研究[J]. 計(jì)算機(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。

國家自然科學(xué)基金重點(diǎn)項(xiàng)目(51439004);上海市科委科技項(xiàng)目(14DZ1205500;14DZ2250900)。

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

1671-4598(2017)01-0107-04

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

TP391

A