容错实时任务调度的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