信息物理系统可调度性分析的执行时间优化方法

张 晶，陈 垚，孙 俊，范洪博

(昆明理工大学 信息工程与自动化学院，昆明 650500)

1 概 述

信息物理系统(Cyber-Physical System，CPS)通过软件的计算进程控制外部环境的物理进程，并由一系列传感器组件与网络节点完成搜集环境信息、系统间通信、反馈控制等任务.为了获取精确的环境信息并做出实时反应，根据具体的不同任务，系统需要自动调整计算逻辑与资源配置，采用针对性的调度策略，实现计算世界与物理世界的高效融合[1].CPS系统的连续物理系统与离散计算系统相互作用、互相影响[2]，其中计算进程由包含独立控制线程、可异步传递消息与交流的执行器(Actor)通过输入、输出含有特定信息的事件信号实时控制物理实体.然而物理环境的时间变量为连续信号，而计算系统为离散信号.计算进程若要控制物理进程，需要将物理连续变量由微分不变式计算得到一个收敛于离散变量中对应的不动点收敛函数，求解该不动点即可使系统内外环境在时间度量与表示上保持一致[3].

由于设计的不同需求，CPS系统的开发必须考虑系统时间信号、事件价值、执行周期、资源消耗等约束条件，使开发过程可以得到一个详实的性能评估与描述.对于CPS在复杂环境下的任务执行要求，系统能否完成调度任务就显得异常重要，这就要求对其可调度性进行验证，而CPS物理进程与计算进程实时交互过程中，对其任务集的可调度性进行直接验证非常困难，为此需要在保证系统正确性的前提下，能准确分析可调度性的方法[4].此前，时间自动机被广泛用于测试实时系统的调度性.其中Elena F等人[5]提出了一种称为任务自动机的实时系统模型，其异步流程定位于自动机状态位置，从而表达出任务到达与依赖模式.桂盛霖等人[6]实现了一种支持分布式系统任务实时调度分析工具SCT，其分析结果精确但分析时间偏长.M Stigge等人[7]基于有向图模型提出一种pseudo-polynomial调度算法，对不同模型的工作类型、执行条件与循环结构的表达方式进行优化.然而这些方法并没有提及计算世界与物理世界深度交互时，系统的调度性如何转换为自动机的可达性进行判定.

本文考虑在上述技术研究的基础上，定义多元的CPS系统任务调度约束，以超致密时间模型(Superdense Time Model，SDT)计算离散变量不动点并表达系统全局时间信号.提出一种基于有限状态机(Finite State Machine，FSM)的执行器状态自动机(Actor State Automata，ASA)分析方法对CPS调度性进行分析，并基于此方法，提出一种基于决策树的ASA状态集分类搜寻策略(A classified search strategy of state set for ASA based on decision tree，DT-ASA*).最后通过PtolemyII平台[8，9]建立模型，分析系统模型的精确性与性能.

2 系统模型

CPS系统由物理设备与计算系统组合而成，通过传感器、制动器与网络节点相互作用.如图1所示，计算系统在PtolemyII平台仿真时被定义为一种基于面向执行器(Actor-oriented)的并发性模型与通信交流策略构成的并发计算模型(Model of Computation，MoC)[10]，利用事件驱动结构，通过异步回调操作(asynchronous callbacks) 函数可将所有事件信号按事件时间戳顺序处理.

图1 基于面向执行器模型的基本等级架构Fig.1 Basic level architecture based on actor-oriented model

2.1 CPS系统执行约束条件

·SA是执行器A状态集合，且SA≠Ø；

基于面向执行器的并发计算模型，是一种具有层次感的程序组件组成的系统模型，不同层次的模型或同一层次的组件通过执行器进行通信，其方式即通过输入、输出端口接收或送出执行事件.

定义2.(事件)事件信号标签为一个五元组E=，其中：

·C代表事件所处信道集合，其单值子集c代表某个输入行为或输出行为，并且{e1，e2|e1∈Ein∨e2∈Eout}，则f(sinit，e1，cin)=u(sinit，e1)×e2，其中e2∈cout；

·Φe是事件e∈E的约束条件集合；

·T是执行器处理事件的系统全局时间；

·SE是事件E的状态集合，se∈SE是事件e的时间戳确定的事件状态.

由于不同的设计需求，CPS的事件考虑多种约束条件，如Φe=δe×Re×Ve.

δe为事件时间戳所确定的时序约束，时序约束内部元素是时钟集合X⊆T到非负实数+的映射，并且是系统预计执行器处理事件e的时间，即：；t是系统当前运行时间，y为影响参数[11].

Re为执行事件e所消耗的资源，该约束由事件等待时产生的能耗，执行任务的消耗，及是否正常执行等因素决定.令de为事件e截至时间，re为事件就绪准备被执行的时间，εe为完成处理fA任务的时间，对于当前时间t∈T，事件e处于等待时间或执行时间有如下状态：

(a)runninge=(re

(b)readye=((t=re∧t

(c)suspende=(t≤re∨(t

(d)sleepe=(t

Ve为事件价值量约束，由事件e产生的数据质量Qe与对应的执行器A的信息冗余度χA决定，H(A)为执行器A输出事件时的信息熵[12]，满足：

2.2 全局时间信号的表达

CPS中计算进程为离散的，物理进程为连续的，若T为任意小常数的倍数，则无法表达其语义，故不能以时钟计数表达执行器输出事件的时间戳排序.考虑集合×代替+作为时钟集合X⊆T的映射，表示执行器处理事件的系统全局时间T，此时时间值为数组(∂，n)∈T，其中∂为时间长度，n为离散时间瞬间的某一序列值[13].

定义3.超致密时间(SDT)表示为(∂，n)∈(T=×)，∂∈表示离散步长，n∈表示离散步数.若(∂，n)≥ (∂′，n′)，则有∂≥∂′∨(∂=∂′∧n≥n′).对于SDT有如下性质[14]：

·对于(∂，n)在集合T上有如下的下降集：

·T的下降集由T本身表示；

定理1.在超致密时间中，若Y为实时规则集合，Y′为非实时规则集合，对于∀e∈E，当且仅当∃t∈(∂，n)，有(e，t)∈Y，则e∈Y′.

证明：1)根据定义3，(∂，n)∈T，则T的下降集为Ζ[∂，n]或Ζ(∂，n)，其中，若∂∈，则T的下降集为Ζ(∂，∞).故若∃t∈(∂，n)，使得(e，t)∈Y，说明e的执行序列为排序的.

2)若t为任意实数值的时间序列，则∃(e，t)∈Y，若∃q∈，使X内部元素x为q的整数倍，则∃n∈，0≤i′≤i，使xi=xi′+nq.由t∈(∂，n)，得ti=ni∂.由于存在延迟，故总有q′≤q，使∂i-∂i′=nq′≤nq，由证明1)可知(ti-ti′)与∂i-∂i′满足相同约束Φe，故构造(e，(∂，n))作用于执行器，其事件输出路径满足与输出Cr=f×u相同的运行路径.故当(e，t)∈Y，有e∈Y′.

得证.

2.3 带约束条件的执行器行为

对于集合H(A，E)，有如下属性：

·e∈E为执行器A在time(∂，n)控制下的输出事件：

(a)∃e=ep为周期事件(periodic events)，其输出事件时间间隔p1为固定常数；

(b)∃e=ea为非周期事件(aperiodic events)，其输出事件时间间隔p2是以需求确定的最小下界;

·若∀se∈SA，E=sleepe∨suspende，则执行器A的执行周期p→∞；

·执行器A中任意事件e顺序执行的必要条件为∀t=(e，(∂，n))≥p(me，(∂，n))|m=1，2，，…，n-1}，即每个事件由状态readye→runninge需要前n-1个事件执行完成才能开始；

·执行器A中任意事件e必须满足Φe=δe×Re×Ve.

图2 执行器内部状态转移任务示例图Fig.2 Sample figure of state transition tasks in an actor

3 执行器状态自动机

3.1 有限状态机语义

系统状态被定义为在某个特定的时刻，系统对应的条件状况.状态变量表示为s∈Σ，Σ为系统所有可能状态的集合，有限状态机(FSM)是一种Σ为有限集合的状态机，在FSM中，系统行为被表达为状态集合，并在其中通过某种规则管理各个状态间的转移.

定义4.(有限状态机)有限状态机为六元组<Σ，CI，CO，s0，Δ，F>，其中：

·Σ为状态机内所有可能状态的集合；

·CI为函数：CI=Cin→Ein∪{absent}，{absent}表示信道Cin可用；

·CO为函数：CO=Cout→Eout∪{absent}；

·s0为初始状态，s0∈Σ；

·Δ为变量值；

·F为函数：F=Σ×CI×Δ→Σ×CO×Δ.

对于一个确定的有限状态机，若任意状态，最多有一个输入值可以激活一个转移，则称其具有确定性；若任意状态，每个输入值都至少能激活一个转移，则称其为可接受的.状态间的转移为有限状态空间离散动态与输入到输出的映射.

FSM可并列异步组合，对于a、b状态机组合成的c状态机，其执行过程中有如下语义：

1)c的响应为a或b其中的一个的响应，并且选择是不确定的；

2)c的响应可能为a或b其中的一个的响应，也可能为a、b的共同响应，并且选择是不确定的，执行结果可能导致没有响应；

3)c的响应如何决定，由外部环境选择.

如图3为一组并列异步组合FSM，通过不同约束条件(guard)选择转移状态.其中，状态b可分层为状态c与状态d，当处于状态b时表示处于状态c或状态d.框图3-Ⅱ为框图3-Ⅰ的等效表示.

图3 并列异步组合FSM示例图Fig.3 Sample figure of side-by-side composition FSM

3.2 执行器状态自动机语义

本节定义一种带约束条件有限状态机的特定子类，命名为执行器状态自动机，与以往技术原理相同，本文采用基于自动机理论，将系统可调度性问题转换为可达性问题进行分析.带约束条件有限状态机为<Σ，E，L，L0，X，Φ，Δ，f>，与上述符合含义相同的，Σ为状态机内所有可能状态的集合，E是有限事件集合，L为位置的有限集合L0为初始位置集合，并有L0⊆L，X⊆T为时钟集合，Φ为E的约束条件集合，Δ为变量值，f为状态转移函数.

定义5.(执行器状态自动机)执行器状态自动机为十二元组<Σ，E，L，L0，ρ，σ，X，δ，R，V，Δ，f>，其中：

·Σ为状态机内所有可能状态的集合，存在Σre表示可执行状态集，Σerr表示不可执行状态集，并且Σre，Σerr∈Σ；

·E为有限事件集合，存在E=En∪Ew，En为内部事件集合，Ew为外部事件集合，其行为与定义3第1子句(c)相符；

·L为位置的有限集合，存在L=Lbasic∪Lcom，其中Lbasic为基础位置集合，Lcom为异步组合位置集合；

·L0⊆Lbasic为初始位置集合；

·l0，l1∈Lcom，e∈E，s∈Σ，l1=l0(s×e)→ρ(l0)，∀l∈Lcom，ρ(l)表示l的子位置，而ρ-1(l)表示l的父位置；

·σ={&&，‖，Ø}表示每个位置间的关系，若父子位置为&&关系，则∀l1=ρ(l0)=Sact，其中Sact表示活跃状态，若父子位置为‖关系，则只存在一个l1=ρ(l0)=Sact，&&关系与‖关系组合成的位置集合为Lcom，对于L0⊆Lbasic=Ø说明其没有父子关系的位置；

·时钟集合X⊆time(∂，n)为时钟集合，满足超致密时间表达：(∂，n)∈(T=×)；

·δ×R×V为约束条件，其定义与2.1节对δe、Re及Ve的描述相符；

·Δ为变量值，每个变量的值域都为有限的；

·f=Σ×E×L×2X×Φ(δ)×Φ(R)×Φ(V)×Δ表示状态转移关系.

3.3 执行器状态自动机判定性证明

由定义5第6子句可知，若位置l=Sact且σ(l)=||，则∃!l′∈ρ(l)使得l′=Sact；若位置l=Sact且σ(l)=&&，则∀!l′∈ρ(l)使得l′=Sact.

定理2.带约束条件有限状态机是可判定的，则执行器状态自动机一定也是可判定的.

证明：设K=<Σ，E，L，L0，X，Φ，Δ，f>为带约束条件有限状态机，按如下条件可编码为对应的特定子类K′=<Σ′，E′，L′，L0′，ρ，σ，X′，δ，R，V，Δ′，f′>：

1)K中活跃状态位置集合{L|Sact}中任意位置l∈L都对应K′中某一位置l′∈L′.若l的初始位置为L0⊆Lbasic⊆K，则l′的初始位置为L0′⊆Lbasic′⊆K′，其中E′=E；

2)K中的时钟集X对应K′中的时钟集X′，且满足X=X′，f′(δ)=f；

3)若{L|Satc，∀l∈L}对应K′中的位置l′∈L′，则状态转移关系为f′(l′)=∧{L|Satc，l∈L}f(l)；

4)若在K中有从li到lj的状态转移f(si×cin×ei)，与一组从Lm到Ln的状态转移行为集合H(A，E)⊆F，且状态为li∈{Li|Sact}，Lm∈{Li|Sact}，lj∈{Lj|Sact}，ln∈{Lj|Sact}，其中{Li|Sact}，{Lj|Sact}⊆{L|Sact}，li，lj∈Lbasic，Lm，Ln⊆L.那么在K′中同时对应状态转移f′(si′×cin′×ei′)={L|Satc}，u(si′×cin′×ei′)={Lj|Satc}，u∈F，且f′(δ×R×V)=∧E⊆H(A，E)f(Φ).

通过编码后，K中∀s∈∑=({L|Sact}，X)对应K′中某一状态s′∈∑′=(l′，X′)，并且l′={L|Sact}.若K中∃si∈∑=({Li|Sact}，Xi)可由s到达，则si在K′中对应的si′也可由s′到达.由定义6与定义7可知，执行器状态自动机的可达性是可判定的.

得证.

3.4 DT-ASA*策略

对于ASA的模型检测，需要计算ASA的可到达状态集合，检测ASA是否满足超致密时间逻辑描述的系统规格，并使用调度策略进行验证.考虑一种基于决策树的ASA状态集分类搜寻策略(A classified search strategy of state set for ASA based on decision tree，DT-ASA*)，并且在PtolemyII平台上基于此策略建模，用于分析ASA方法的精确度、执行时间及内存使用率.

DT-ASA*策略实质是个递归的过程，若在下列情况发生时产生递归返回：

1)属性集中的样本全属于同一类别，即全可达或不可达，则无需分类；

2)属性集为空，或样本属性取值完全相同，则无法分类：此情况下将此结点作为叶结点，其类别为样本中最多的类别；

3)结点内样本集为空，无法分类：此情况下将其父结点作为叶结点，其类别为样本中最多的类别.

作为每个结点划分的关键，参考著名的C4.5决策树算法，使用增益率(gain ratio)选择最优划分属性，由状态集s=中计算出信息增益高于平均水平的条件，再从中计算出增益率最高的作为此结点划分的最佳考量变量.最后检测所有可达或不可达类别的叶结点，考虑将不可达结点剪枝或归纳所有可达结点，所述策略的伪代码如算法1所示.

算法1.DT-ASA*策略

输入： 训练集K={s0,s1,…,sm}

属性集Γ={reachable,error}

1.初始化： s0={e0,I0,x0,δ0,R0,V0}

2. Re:={s0},Error=[]

3.DT-ASA*(K,Γ):

4. 生成结点node

5.while∑≠Ø

6.ifK中的样本属于同一类别reachableORerror

7. 将nodfe标记为reachableORerror

8.return

9.endifΓ=Ø

10.if或K中的样本在Γ取值相同，then

11. 将node标记为叶结点，其类别标记为K中样本最多类

12.return

13.endif

17. 选择gain_ratio(K,s)较大的属性作为最优划分属性Γ*

18.forΓ*的每个取值a*

19.为node生成一个分支

20.令Ka表示K在Γ*上取值为a*的样本子集

21.ifKa为空，then

22.将分支节点标记为叶结点，其类别标记为K中样本最多的类

23.return

24.else

25.以DT-ASA*(K,Γ、{Γ*})为分支结点

26.end

27.if存在s′属于reachableands′不属于Re

28. Re:=Re∪{s′}

29.else

30. Error.extend(s′)

31.end

DT-ASA*策略的输入为系统状态及属性集合，输出为系统状态分类后的状态属性分类集合.

测试DT-ASA*策略：本测试使用处理器为1.6GHz双核Intel Core i5，RAM为8.00GB的MacBook Air PC机，其系统为macOS Sierra，以系统自带的Python 2.7编程运行，使用加州大学伯克利分校[15]的数据集作为训练集.

由于数据需要作为4.2节所建立模型的变量输入，故测试的决策树结果为字典模式保存，其中可达状态集存入字典Re，不可达状态集存入列表Error：

>>> DT-ASA*Tree

{′states′：{‘disabled’：′error′，′act′：{′timing sequence′：{‘overrun’：′error′，′x：=0′：{′quantity of value′：{′satisfy′：{′clock constraint′：{′satisfy′：{′energy consumption′：{′equality′：{′events′：{′ready′：′reachable′，′running′：′reachable′，′suspend′：′reachable′，′sleep′：′error′}}，′low′：{′events′：{′ready′：′reachable′，′running′：′reachable′，′suspend′：′reachable′，′sleep′：′error′}}，′higher′：′error′}}，′dissatisfy′：′error′，′equality′：{′energy consumption′：{′equality′：{′events′：{′ready′：′reachable′，′running′：′reachable′，′suspend′：′reachable′，′sleep′：′error′}}，′low′：′events′：{′ready′：′reachable′，′running′：′reachable′，′suspend′：′reachable′，′sleep′：′error′}}，′higher′：′error′}}}}，′dissatisfy′：′error′}}}}}}

其中′reachable′表示可达状态，′error′表示不可达状态，事件约束条件有runninge、readye、suspende以及sleepe，时序约束若不是‘overrun’则在状态转移时重置时钟′x：=0′，约束条件集合Φe为′clock constraint′，′energy consumption′和′quantity of value′.测试结果符合数据集运行结果.

4 性能验证

4.1 建立DT-ASA*策略模型

UC Berkeley的PtolemyII平台由Edward Ashford Lee教授团队研发，用于验证包含时间和行为类型属性的组件交互过程，并支持分层设计实时嵌入式异构系统[8].本节建立的DT-ASA*策略模型，使用4.1节所述MacBook Air PC开发环境，平台版本使用PtolemyⅡ10.0.1Mac OS X版.

建立的模型如图4所示，Director为系统调度器，使用2.2节所述的SDT时间控制系统全局时间.Director调度器右侧为Δ变量值，引号左边为变量名，引号右边为变量初始值.State Model为状态产生模块，内部随机产生初始状态s0，由不同的调度策略产生状态序列并输入Modal Model模块分析检测，生成result实时反馈回State Model，使其更新更优的状态序列.Modal Model内部结构为执行器状态自动机模型，其左端输入不可达状态集列表Error.模型输出结果表现在曲线生成器reachableState与Rate中.

图4 DT-ASA*策略模型Fig.4 Model of DT-ASA* strategy

Modal Model中黑色箭头s与Error表示输入参数，result表示输出参数.虚线状态转移边为默认转移(default transition)，其优先级仅低于普通转移.加粗的边表示经历转移(history transition)，为复位转移的一种形式，目标状态会停留于它最后所处的状态或最初状态.RelationParameter为转移关系，图中以u表示，具体如下：

u1：(output：s = reachableRate)；

u2：(guard：error，output：s = 0，set：count = 0)；

u3：(guard：count < 10 && s0<= ScheOn，output：s = reachableRate，set：count = count + 1)；

u4：(guard：count < 10&& s0> ScheOn，output：s = errorRate，set：count = count + 1);

u5：(guard：!error &&s0>= ScheOff，output：s =errorRate);

u6：(output：s = 0);

u7：(guard：count < 10，output：s = errorRate，set：count + 1);

u8：(guard：error，output：s = 0，set：count = 0);

u9：(guard：!error &&s0<= ScheOff，output：s = reachableRate);

u10：(output：s = 0);

u11：(guard：count < 10，output：s = reachableRate，set：count + 1);

u12：(output：s = errorRate);

u13：(output：s = errorRate);

4.2 仿真结果

测试所涉及的调度策略包括单调速率(RM)调度策略、最早交货期(EDD)调度算法、优先级最早时限优先(EDF*)算法、Hu级调度(Hu level scheduling)算法.其中RM策略为一种简单的抢占式调度策略，为周期较小的任务分配较高的优先级；EDD算法也称为Jackson算法，它只根据时限顺序执行，与任务间相对顺序无关，时限最早的优先级最高；EDF*算法为简单的EDF改进方法，是一种支持任务到达并且将最大延迟最小化的简单优先级最优算法；Hu级调度算法为多处理器调度最简单的方法，作为关键路径(critical path)算法的一种，根据最长完成时间制定优先级图的路径.

模型中不同调度策略的状态转移都处于执行状态或就绪状态间相互转换.首先不使用Modal Model产生的result进行反馈，而由不同的调度策略直接将状态序列输入reachableState得到实际值，然后使用4.2节描述的系统模型，将结果输入reachableState与Rate得到预测值，通过对比得到DT-ASA*策略模型的精确性.分析结果如图5(a)-图5(d)所示.对比获得实际状态序列与预测状态序列的执行时间以及内存使用率，结果如表1所示.

图5 DT-ASA*策略模型的精确性分析Fig.5 Analysis of accurateness for DT-ASA* strategy Model

由图5所示，使用调度策略实际产生30次状态转移，在图5(a)与图5(b)中，DT-ASA*策略模型能很好地预测出最终状态转移次数，其中可达不可达图为DT-ASA*策略得出的二分类结论，即在迭代过程中，若当前位置为可达状态输出1.0，若为不可达状态则输出0.0.状态序列图与可达不可达图互相对应，明显看出，位置状态为1.0时，状态转移过程中增加状态序列，位置状态为0.0时，状态转移停滞，直到搜索到下一可达状态.图5(c)、图5(d)与图5(a)、图5(b)相似，预测值与实际值基本一致，但可以看出在状态序列稳定后，图5(c)、图5(d)的预测值要比实际值略高，即仍然存在过度匹配的现象.

表1 DT-ASA*策略模型的性能分析Table 1 Analysis of performance for DT-ASA* strategy Model

分析不同测试算法在系统模型中的性能，将算法在模型中得到实际值的执行与得到预测值的执行分别运行20次，得到平均执行时间与平均内存使用率.由表1所示，可以看出4种不同的调度策略在模型中的执行情况，其中迭代次数为图5中横坐标的迭代次数.当使用DT-ASA*策略模型时，对于RM调度策略，执行时间提高33.33%，同时多消耗45.16%内存资源；对于EDD调度算法，执行时间提高45.32%，同时多消耗23.53%内存资源；对于优先级EDF算法，执行时间提高37.01%，同时多消耗45.95%内存资源；对于Hu级调度算法，执行时间提高33.80，同时多消耗32.56%内存资源.

表2 关键符号列表Table 2 Key compliance list

由仿真结果可以得出结论，DT-ASA*策略模型所得到的预测值与实际值基本一致，但仍然存在过度匹配的现象，需要进一步改进，虽然使用模型预测任务状态能极大减少执行时间，但同时也会消耗更多内存资源.

5 总 结

本文针对CPS系统可调度性分析问题.首先定义了CPS系统执行约束条件，然后以SDT表达系统全局时间，在定义了带约束条件的执行器行为后，提出了一种基于有限状态机的执行器状态自动机分析方法，并对执行器状态自动机判定性问题进行证明.最后提出一种基于决策树的执行器状态自动机状态集分类搜寻策略，通过可包含时间和行为类型属性组件交互过程进行验证的PtolemyII平台建立策略模型.通过仿真得出结论，该策略得到的预测值基本符合实际值，并且明显降低执行时间，但策略仍然存在不足，例如会消耗更多内存资源以及存在过度匹配的现象，需要在今后的工作中加以改进.