汲洋弘康，王飞――基于Mealy机的实时系统调度方法.doc
汲洋弘康，王飞――基于Mealy机的实时系统调度方法.doc
基于 Mealy 机的实时系统调度方法 汲洋弘康，王飞，余婷 （华侨大学 信息科学与工程学院，福建 厦门 361021） 摘 要：为了得到实时并发系统的最优运行路径，本文提出了一种基于 Mealy 机建模的最优调度方法。通 过分析以 P-time Petri 网建模的实时系统，并用 Mealy 机建立其中库所及其对应时间的关系，得到了在满足 系统非死锁、非阻塞特性下的最优路径。基于这种方法，可获得 P-time Petri 网的最优合法序列，为解决工 业生产中软硬件资源的节约以及效率问题提供思路。 关键词：实时系统；Mealy 机；P-time Petri 网；调度 中图分类号: TP271.8 文献标识码：A Real-time Scheduling Method Based on Mealy Machine Ji Yanghongkang，Wang Fei，Yu Ting (College of Information Science and Engineering，Huaqiao University，Xiamen 361021,China) Abstract：In this paper, in order to get the optimal path of real-time concurrent systems, an optimal scheduling method based on Mealy machine was proposed. Through analyzing on the real-time system with P-time Petri nets model and modeling the relationship between the place and its corresponding time with Mealy machine, the optimal path satisfied with non-deadlock and non-blocking was obtained. Based on this method, the Optimal Legal Firing Sequence of P-time Petri nets can be obtained, and provided new way to solve the industrial production of soft hardware resources saving and efficiency problem. Key words：real-time system；Mealy machine；P-time Petri nets；scheduling 1 引言 在实时领域中，调度分析是一个非常重要的研究方向，自从20世纪70年代Liu和Layland 提出调度分析模型以来，研究人员针对不同的系统计算模型和不同的调度策略提出了大量的 调度分析方法[1]。与此同时，有限自动机理论也脱颖而出，由于很多实际过程都可以抽象为 离散事件动态系统过程，合理利用有限自动机理论进行建模是实现过程自动化的关键[2][3]。 近年来，虽然结合离散事件系统模型进行调度分析的方法越来越多[4][5][6]，然而在对实时系 统进行调度时，无论是自动机还是Petri网都很容易陷入死锁或阻塞的状态。 由于Petri网所提供的理论信息非常丰富，因此被应用于计算机科学、控制科学、系统科 学的交叉领域，有着广泛地应用前景。文献[4]为了寻找Petri网的最优激发序列，结合最优原 则和线性规划，提出了一种避免死锁的改进方法。文献[5]针对半导体制造系统，提出了基 于分层着色时间Petri网模型的分时段优化调度方案，克服了模型规模膨胀的缺陷。文献[7]针 对实时系统的Petri网建模问题，提出了 “Firing instant notion”，给出了满足安全性的P-TPN 对实时系统进行建模分析的方法，但并未涉及算法的分析。 基金项目：国家自然科学基金项目（61203040）；福建省自然科学基金项目（2011J01352）。 E-mail:jyhk2012@163.com；feiw545@163.com 解决Petri网模型中主干路径的寻优问题，有利于对复杂系统进行分析，决定了系统的性 能。本文基于文献[7]中的建模方法，首先，对P-TPN中不同的网结构进行分类。之后，对网 中库所及其对应的时间约束关系进行分析，保证系统的正常运行。最后，将这种关系通过有 限自动机进行建模，直观的得到系统最优合法激发序列，从而为解决通过建模的实时系统寻 求最优主干路经的问题[8] ，提出了一种简单可行的方法，在应用上有利于对并发的实时系 统（如柔性制造系统）进行调度分析。 2 基本概念 2.1 Mealy 机 Mealy 机[3]是一种带输入输出的有限状态自动机，它的输出不仅取决于当前状态，还取 决于下一个输入值。同时，Mealy 机可以转化成一个有向的状态转移图，通过图形化的描述， 能够更直观的得到满足系统所需要特性的各种条件。 2.2 P-time Petri nets Petri网（PN）也是描述离散事件系统的数学模型。time Petri-nets（TPN）是为了解决PN 中某些没办法被很好描述的约束而提出的，它是一个用来证明和详述并发系统的形式化工具 [9]。禁止TPN中那些会超过终止期限的变迁发生，对于系统正常运行是非常重要的[10]。使用 TPN可以允许在其组成部分的执行期间上引入时间约束，而P-TPN则是在其库所上引入了静 态时间区间[11]。 定义1[7] P-TPN的形式化定义由一个二元组 ( Nr ; I ) 给定，其中： 1) Nr 是普通的Petri网； 2) I =[ai ,bi ]， bi ³ ai ，定义为在库所中一个静态操作时间区间，只有当token在对应的 区间 [ai ,bi ] 中时，token在这个库所的输出变迁上才被认为是使能的。因此，当它的操 作时间最终变为 bi 时，它就不得不离开这个库所。在这个时间 bi 后，这个token将会失 去活性，并且不再考虑这个变迁的使能，从而导致系统阻塞。 此时认为没有隔离的库所。本文的研究不考虑权值函数，即设每个弧线上的权值皆为1。 需要注意的是，对于多个库所对应同一个输出变迁的情况，只有这些库所中都包含一个有活 性的token，它们的输出变迁才能被激发；而对于多个库所对应同一个输入变迁的情况，一 旦这个变迁触发，每个库所都能获得一个token。实际上，每个token还存在一个动态区间， 来描述系统在整个正常运行过程中的总和时间区间[11]。 2.3 Petri网的有界性和安全性 定义2[12] 设 N =(S,T ; E,M 0 ) 为一个Petri网， sÎ S 。若存在正整数 B ，使得 " M Î R (M 0 ) : M (s) £ B ，则称库所 s 为有界的（bounded），并称满足此条件的最小正整 数 B 为库所 s 的界，记为 B(s) 。即 B(s) =min{B " M Î R(M 0) : M (s) £ B} 当 B(s) =1时，则称库所 s 为安全的（safe）。 3 用Mealy机建立时间关系模型 在P-TPN中，库所上的时间问题是本质研究对象[7]，其不仅要考虑token在库所中的活性， 还要考虑使系统正常运行的时间约束。本文基于文献[7]中的安全Petri网模型，分析其库所及 其对应时间约束的关系。通过将 Petri网的变迁转换成Mealy机的输出集合 D ，并把时间约束 边界作为Mealy机的输入集合 S ，可以简单直观的得到主干路径的调度结果。 在本节中，基于一个token，通过库所和变迁的个数，对P-TPN网状结构进行分类，可以 得到如下五种情况： 1.库所和变迁一一对应 2.一个库所对应多个变迁 3.多个库所对应一个变迁 4.一个变迁对应多个库所 图1 5.多个变迁对应一个库所 P-TPN的五种分类情况 其中，多个库所与多个变迁相互对应的情况，可以分解成上述五种情况，且第5种情况 由于缺少token，需要与其他情况相结合才有意义。又因为情况2、5组合所形成的Petri网在 选择变迁时具有不确定性，故在本文中不予以考虑。在基于一个token的前提下，将情况1看 作串联型结构，将情况3、4结合为一个并联型结构，便可以确定一个库所只对应一个输出变 迁，对此进行以下分析。 3.1 3.1.1 用Mealy机表示P-TPN的运行序列 串联结构的P-TPN 一 个 有 界 的 P-TPN ， N=( Nr ; I ) ， 其 中 Nr =(P,T,E ) ， P ={P｜ i i =0,1,2,3...n}， T ={t｜ j j =0,1,2,3...n- 1}， I =[ai ,bi ]。此时只有一个token在 P0 ，且对于任意的 Pi 只有 一个与其对应的输入变迁 ti-1 和输出变迁 ti ，则在这个Petri网运行过程中转移状态与时间极 值的关系可以转化成一个Mealy机： A =(Q,S,d ,q0 ,D,j ) ，其中状态 Q 为 P 的幂集， S ={ai ,b｜ i i =0,1,2,3...n}， d (qi , ai ) =qi+1 U d (qi ,bi ) =qi+1 ， D={ti |i =0,1,2,3...n- 1}， j (qi ,ai )=ti Uj (qi ,bi )=ti 。 由定义1可知，在 Pi 中的token必须于 [ai ,bi ] 这个时间段内向下一个变迁转移，故可以用 S 来表示所选择的时间点集合。由于时间点的不确定性使得所得到的输入集合 S 包含许多 元素，从而在进行相关描述时导致状态空间爆炸问题。因此，针对本文所考虑的最优调度序 列， 在进行分析时简化不同时间点所产生的影响， 用时间约束边界作为Mealy机的输入集合 S 。 根据定义1，对应于这种结构的P-TPN模型，假定系统可以正常运行，即每个库所对应的变 迁都可以触发，则可用Mealy机中的 Q 表示网中的库所， d 表示由库所中的token在时间极点 处进行的转移， j 表示当前库所对应的输出变迁。此时，可得到用于描述库所及其对应激发 时间关系的Mealy机，如图2所示： P0 [a0,b0] P1 [a1,b1] t0 a0/t0 tn-1 a1/t1 b1/t1 P1 b0/t0 Pn [an,bn] t1 P1 P0 Pn-1 [an-1,bn-1] 状态空间爆炸: 此时最后一步 有2n条路径 a1/t1 b1/t1 图2 串联型结构的P-TPN模型及其对应的Mealy机状态转移图 因为任意有界的Petri网都可以用相应的有限自动机来模拟Error! Reference source not found.。当P-TPN描述那些时间问题变得本质的系统时，由于库所 Pi 中的token只能在 [ai ,bi ]这 个 区 间 段 内 发 生 ， 那 么 其 变 迁 只 是 为 了 进 一 步 体 现 状 态 转 移 的 路 径 Error! Reference source not found.。因此，可以用区间极点作为输入集合 S ，各库所对应的输 出变迁作为输出集合 D ，构造带输出的Mealy机模型，描述系统中各个环节静态区间极点的 线性组和，即此时系统正常运行总时间为： én n ù ëi =0 i =0 û ts Î êå ai ,å bi ú 那么，所构造的Mealy机的输出就对应着原T-TPN的正常运行序列。 3.1.2 并联结构的P-TPN P1 [a1,b1] P3 [a3,b3] P0 [a0,b0] t1 tf t0 t2 P2 [a2,b2] 图3 P4 [a4,b4] 并联结构的P-TPN模型 因为 P0 在经过变迁 t0 后， P1 、 P2 中都会含有token，即可认为系统从状态 {P0}经过时间 T0 Î [a0 ,b0 ]过渡到状态 {P1, P2}，其之后对应两个变迁 t1 和 t2 ，此时便有以下2种情况： （1） [a1,b1]I [a2 ,b2 ] ¹ Æ ，设 [a1,b1]I [a2 ,b2 ] =[a2 ,b1] ，此时 t1 可以先触发到达状 态 {P3, P2}，再触发 t2 到达状态 {P3, P4}，或 t2 先触发， t1 后触发;也可以考虑在交集内 tt 12 同时触发，直接到达状态 {P3, P4}，此时可以将其状态与时间的关系转换成如下图： P0 {P3,P4} a2-a1/t2 {P3,P2} a2/{t1,t2} {P3,P4} {P3,P4} a1/t1 {P1,P2} {P1,P2} b2-a1/t2 {P3,P2} {P3,P4} a2-b1/t2 {P ,P } a0/t0 a0/t0 3 4 b /{t ,t } 2 1 2 b1/t1 P0 或 b2-b1/t2 {P3,P4} {P1,P2} b2/t2{P1,P4} a2/{t1,t2} b0/t0 b0/t0 {P3,P4} {P1,P4} … {P1,P2} {P3,P4} a1/t2 b2/{t1,t2} 图4 图3中并联结构的P-TPN模型满足 [a1,b1]I [a2 ,b2 ] ¹ Æ 时对应的Mealy机状态转移图 可见，在分时触发的情况下，其状态图形非常复杂，且还要考虑输入小于零所导致无法 触发的情况。通过上图可以知道，左右两种构造情况，所描述的时间线性组合是一致的； （2） [a1,b1]I [a2 ,b2 ] =Æ ，若 a2 >b1 ，则 t1 先触发到达状态 {P3, P2}，则可能的变迁 激发序列就是 t0tt 1 2 ；若 a1 >b2 ，则 t2 先触发到达状态 {P1, P4}，则可能的变迁激发序列就是 t0t2t1 ，用Mealy机描述如图5所示： a2/t2 P0 {P3,P4} a2>b1,t1先触发 {P ,P } 3 2 {P3,P4} a1/t1 {P1,P2} b2/t2 {P3,P2} a2/t2 a0/t0 {P3,P4} b1/t1 b2/t2 {P3,P4} {P1,P2} b2/t2{P1,P4} a1/t1 {P3,P4} b /t 0 0 {P1,P4} b /t 1 a1/t2 1 a1/t1 a1>b2,t2先触发 b1/t1 {P3,P4} {P3,P4} {P3,P4} 图5 图3中并联结构的P-TPN模型不满足 [a1,b1]I [a2 ,b2 ] ¹ Æ 时对应的Mealy机状态转移图 通过上面的分析可知，P-TPN中多个库所对应同一输入变迁的情况，反映到自动机上的 对应状态时，可以用这几个库所的并集来表示。 由于在P-TPN中，控制系统运行的是存于库所中的活性token，在经过同一变迁时，可以 同时进入两个不同的库所中，同样的进程反映到自动机上时，只是一个状态向另一个状态的 转移。如果不对库所进行合并，而是分成两种状态，就会出现非确定型自动机，这与所述的 P-TPN相悖，故对库所进行正确的合并可以有效的还原原系统中时间与转移状态之间的关系。 同时，本文研究的重点是，在满足系统正常运行（非死锁，非阻塞）的前提下，利用已 有的P-TPN构建反映变迁最优激发顺序的自动机模型， 而不是寻找与原系统严格等价的模型。 3.1.3 特殊并联型结构的P-TPN 对于如图6的并发系统，只能让其中一个库所中的token进入等待，避免产生死锁。 P1 [a1,b1] t1 P3 [a3,b3] t3 P5 [a5,b5] P0 [a0,b0] t0 tf Pcontrol P2 [a2,b2] 图6 t2 P [a ,b ] 4 4 4 t4 P [a ,b ] 6 6 6 带控制环节的P-TPN模型 设此时满足 [a1,b1]I [a2 ,b2 ] ¹ Æ ，当变迁 t1 和 t2 同时触发时，为了争夺在 Pcontrol 中的 唯一资源（token），就会造成 P1P2 互相等待的现象，使得系统陷入死锁状态[7]。因此，面对 这样的情况，在同一时刻时，只能激活变迁 t1 或 t2 ，令其中一个库所中的token进入等待的 状态。其对应的Mealy机状态转移图如图5，若不对其进行简化，则会在第五次转移时生成32 个不同情况的 {P5, P6}，从而加大了对系统进行分析的难度。 3.2 满足约束 通过上述方法，虽然可以构造出反映反映变迁激发顺序的自动机模型，但并不能保证构 造出来的模型不会发生死锁，阻塞等情况。为了使得系统正常运行，需要对各个静态区间进 行讨论，采用递归的思想，简化对系统正常运行所要满足约束的描述。因此，这里对使系统 陷入死锁、阻塞以及使token失去活性的激发序列进行排除，根据原有P-TPN的模型，有以下 三种情况： 1) 如图2所示的串联型，只需满足每个库所中的token都在使能区间内触发转移就可以保证 系统正常运行； 2) 如图3所示的并联型，要满足到达最终变迁 tf 前每条直线型支路的总区间的交集不为空， 即 [a1 +a3,b1 +b3]I [a2 +a4 ,b2 +b4 ] ¹ Æ，之后每条直线型的约束满足（1）； 3) 如图6所示的存在控制环节的并发系统，要先满足与控制环节相连的每条支路都安全运 { }{ } 行，避免死锁，即 [a1 +a3,b1 +b3]I [a2 ,b2 ] U [a1,b1]I [a2 +a4 ,b2 +b4 ] ¹ Æ。最 后满足（2）。 在直线型结构中，若token在经过每个库所时都保持活性，则系统一定可以正常运行， 且这也是系统正常运行的基础；在分支型结构中，多条支路对应同一 tf 的情况，根据定义1 可以知道， tf 之前的库所中都要存在一个没有失去活性的token，这个 tf 才能被激发。由于， 各支路在到达 tf 前相对独立，互不影响，为了使系统正常运行，就需要考虑每条支路到达 tf 前的库所时所用的时间总和，以及可以在这个库所中存活的时间。当存在控制器时，与控制 器相连的可并发环节就类似于两条互不影响的直线型，如图6中变迁 t1 、 t2 不能同时触发， 这就必定会让某条支路上的token陷入等待的状态，且在等待中这个token不能失去活性，此 时其局部最小值为这两条支线上与控制器相连环节的区间极小值的总和，即： tmin =a1 +a3或a2 +a4 4 实时系统的调度方法 找出系统的约束条件，虽然可以得到反映系统正常运行时间的自动机模型，但通过图2 n- 1 可知，即使是最简单的直线型，构造成自动机模型时也会使得状态激增到： 2i å i =0 +1 。 基于文献[7]的研究，为了得到较简单的形式，本文采用动态规划的思想，在满足使系 统正常运行的条件下，通过对系统进行并行考虑并简化模型，可以缓解状态空间爆炸的问题。 4.1 并行考虑 在上述图3中，其最短时间为各支路可运行时间交集的最小值。设 a1 +a3