Computer Engineering and Applications ›› 2024, Vol. 60 ›› Issue (12): 303-313.DOI: 10.3778/j.issn.1002-8331.2303-0262

• Engineering and Applications • Previous Articles     Next Articles

Design Optimization for Active-Polling and Event-Driven Software State Machine

SUN Laiping, YU Yi, CHU Pengzi   

  1. 1.Key Laboratory of Road and Traffic Engineering of the Ministry of Education, Tongji University, Shanghai 201804, China
    2.Maglev Transportation Engineering Research and Development Center, Tongji University, Shanghai 201804, China
    3.Shanghai Shentong Metro Group Co., Ltd., Shanghai 201103, China
  • Online:2024-06-15 Published:2024-06-14

状态轮询和事件驱动的软件状态机设计优化

孙来平,虞翊,楚彭子   

  1. 1.同济大学 道路与交通工程教育部重点实验室,上海 201804
    2.同济大学 磁浮交通工程技术研究中心,上海 201804
    3.上海申通地铁集团有限公司,上海 201103

Abstract: It is well recognized that the flexibility of state machine design brings developers high efficiency and convenience, but it also introduces three typical problems: the output errors caused by the state logic and timing dependence, the huge load of computing caused by the historical data caching, and the uncontrollable outputs caused by the close-coupling between states. The problems still exist in software detail design and coding. Without changing state machines’ functionalities and following principles of constraint conditions, the paper carries out an equivalent transformation of state machine from both time-complexity and cyclomatic complexity dimensions. The transformation forms a general process of optimization, involves merging or splitting the original state and decision condition, recombining the split or merged state according to the metamodel definition, and adding the transition condition. An optimization algorithm is proposed for three typical problems, the algorithm is used to test the state machine before and after optimization, and the feasibility of the algorithm is verified from the time-complexity and cyclomatic complexity. The practical meaning of the study is that it provides an applicable method for software detail design and refactoring especially in the area of real-time control systems or safety critical systems.

Key words: software state machine, graph isomorphism, state equivalence, time complexity, cyclomatic complexity

摘要: 状态机设计的灵活性在给开发人员带来高效与便利的同时,也带来三类较典型的问题:由于状态逻辑和时序依存导致的输出错误,由于历史数据缓存导致的状态机计算量庞大的问题,以及由于状态跃迁耦合导致的输出不可控问题。目前这三类问题在软件详细设计和编码中仍然存在。在状态机功能不改变、在有限状态机设计约束条件下从时间复杂度和圈复杂度两个维度对状态机进行等价转换,即将原状态和判定条件进行合并或拆分,根据元模型定义对拆分或合并后的状态进行重组,添加跃迁条件,提出优化的一般性过程。进而针对三类典型问题给出优化算法,用同一算法分别对优化前后的状态机进行测试,并从时间复杂度和圈复杂度两方面验证了优化算法的可行性。该研究的实用价值在于为实时控制和安全苛求系统软件设计或重构提供了一种优化的方法。

关键词: 软件状态机, 图同构, 状态等价性, 时间复杂度, 圈复杂度