汲洋弘康，王飞——基于Mealy机的实时系统调度方法.doc

基于Mealy机的实时系统调度方法 汲洋弘康，王飞（华侨大学 信息科学与工程学院，福建 厦门 361021） 摘 要：为了得到实时并发系统的最优运行路径，的最优调度方法。P-time Petri网建模的实时系统，并用Mealy机建立其中库所及其对应时间，满足非死锁、非阻塞特性下的最优路径。基于这种方法，P-time Petri网的最优合法序列，软硬件资源。 关键词：实时系统；Mealy机；P-Petri网；调度TP271.8 文献标识码：A Real-time Scheduling Method Based on Mealy Machine Ji Yanghongkang，Wang Fei(College of Information Science and Engineering，Huaqiao University，Xiamen 361021,China) Abstract：In 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 etri 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对实时系统进行建模分析的方法[7]中的建模方法，首先，对P-TPN中不同的网结构进行分类。之后，对网中库所及其对应的时间约束关系进行分析，保证系统的正常运行。最后，将这种关系通过有限自动机进行建模，直观的得到系统最优合法激发序列，从而为解决通过建模的实时系统寻求最优主干路经的问题[8] ，提出了一种简单可行的方法，在应用上有利于对并发的实时系统（如柔性制造系统）进行调度分析。 2 基本概念 2.1Mealy机 Mealy机[3]它的输出不仅取决于当前状态，还取决于下一个输入值。同时，Mealy机可以转化成一个有向的状态转移图，通过图形化的描述，更直观的得到满足系统所需要特性的各种条件。 2.2P-time Petri nets Petri网是描述离散事件系统的数学模型Petri-nets（TPN）是为了解决PN中某些没办法被很好描述的约束而提出的，它是一个用来证明和详述并发系统的形式化工具[9]。禁止TPN中那些会超过终止期限的变迁发生对于系统正常运行非常重要[10]。使用TPN可以允许在其组成部分的执行期间上引入时间约束，而P-TPN则是在其库所上引入了静态时间区间[11]。 定义[7] P-TPN的形式化定义由一个给定，其