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

doi:10.3778/j.issn.1002-8331.2303-0262

Abstract

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

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

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

SUN Laiping, YU Yi, CHU Pengzi. Design Optimization for Active-Polling and Event-Driven Software State Machine[J]. Computer Engineering and Applications, 2024, 60(12): 303-313.

孙来平, 虞翊, 楚彭子. 状态轮询和事件驱动的软件状态机设计优化[J]. 计算机工程与应用, 2024, 60(12): 303-313.

References

[1] ASHBY W R, CULBERTSON J T, DAVIS M D, et al. Automata studies (AM-34)[M]. Princeton: Princeton University Press, 2016: 129-153.
[2] MEALY G H. A method for synthesizing sequential circuits[J]. Bell System Technical Journal, 1955, 34(5): 1045-1079.
[3] WAGNER F, WOLSTENHOLME P. State machine misunderstandings[J]. Computing and Control Engineering, 2004(17): 3-4.
[4] 崔玲, 张建标. 基于动态聚类的有限状态机多错误诊断[J]. 北京工业大学学报, 2021, 47(6): 607-615.
CUI L, ZHANG J B. Multiple-fault diagnosis of finite state machine based on dynamic clustering[J]. Journal of Beijing University of Technology, 2021, 47(6): 607-615.
[5] UCAN A B, SAY A C. Advice hierarchies among finite automata[J]. Information and Computation, 2022, 288: 104878.
[6] MICHALISZYN J, OTOP J. Learning infinite-word automata with loop-index queries[J]. Artificial Intelligence, 2022, 307: 103710.
[7] KUTRIB M, MALCHER A, WENDLANDT M. Input-driven multi-counter automata[J]. Theoretical Computer Science, 2021, 870: 121-136.
[8] BEIER S, HOLZER M. Nondeterministic right one-way jumping finite automata[J]. Information and Computation, 2022, 284: 104687.
[9] FAZEKAS S Z, HOSHI K, YAMAMURA A. Two-way deterministic automata with jumping mode[J]. Theoretical Computer Science, 2021, 864: 92-102.
[10] VAANDRAGER F, MIDYA A. A myhill-nerode theorem for register automata and symbolic trace languages[J]. Theoretical Computer Science, 2022, 912(12): 37-55.
[11] ARREDONDO D, LAKIN M R. Robust finite automata in stochastic chemical reaction networks[J]. Royal Society Open Science, 2021, 8(12): 211310.
[12] CZARNECKI K, HELSEN S. Classification of model transformation approaches [C]//OOPSLA’03 Workshop on Generative Techniques in the Context of MDA, 2003．
[13] BORDIHN H, HOLZER M. On the number of active states in finite automata[J]. Acta Informatica, 2021, 58(4): 301-318.
[14] GAO Z, WANG B, FENG J E, et al. Finite automata approach to reconstructibility of switched Boolean control networks[J]. Neurocomputing, 2021, 454(24): 34-44.
[15] 潘雁, 祝跃飞. 主动自动机学习中的等价查询算法优化[J].软件学报, 2023, 34(7): 3241-3255.
PAN Y, ZHU Y F. Optimization of equivalence query algorithm in active automata learning[J]. Journal of Software,2023, 34(7): 3241-3255.
[16] DENG H, YAN Y, CHEN Z Q. A matrix-based static approach to analysis of finite state machines[J]. Frontiers of Information Technology & Electronic Engineering, 2022, 23(8): 1239-1247.
[17] 伍旭东, 唐麒, 张伟, 等. 基于扩展有限状态机的SCA符合性测试方法研究[J]. 计算机工程与应用, 2021, 57(16): 263-268.
WU X D, TANG Q, ZHANG W, et al. Research on SCA compliance testing method based on extended finite state machine[J]. Computer Engineering and Applications, 2021, 57(16): 263-268.
[18] EBERT C, CAIN J. Cyclomatic complexity[J]. IEEE Software, 2016, 33(6): 27-29.
[19] RUPINDER P S, HARDEEP S. A cyclomatic complexity generalization for a composite service[J]. International Journal of Computer Theory and Engineering, 2021, 13(2): 47-49.