基于Mealy机的实时系统调度方法-华侨大学学报（自然科学版）.docVIP

基于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对实时系统进行建模分析的方法，但并未涉及算法的分析。 解决Petri网模型中主干路径的寻优问题，有利于对复杂系统进行分析，决定了系统的性能。本文基于文献[7]中的建模方法，首先，对P-TPN中不同的网结构进行分类。之后，对网中库所及其对应的时间约束关系进行分析，保证系统的正常运行。最后，将这种关系通过有限自动机进行建模，直观的得到系统最优合法激发序列，从而为解决通过建模的实时系统寻求最优主干路经的问题[8] ，提出了一种简单可行的方法，在应用上有利于对并发的实时系统（如柔性制造系统）进行调度分析。 2 基本概念 2.1 Mealy机 Mealy机[3]是一种带输入输出的有限状态自动机，它的输出不仅取决于当前状态，还取决于下一个输入值。同时，Mealy机可以转化成一个有向的状态转移图，通过图形化的描述，能