信息物理系统可调度性分析的执行时间优化方法
|
摘要
针对信息物理系统(CPS)中物理连续进程与计算离散进程实时交互任务集的可调度性难以准确、快速地分析,提出一种基于有限状态机(FSM)的执行器状态自动机(ASA)分析方法.首先将CPS调度性问题转换为自动机状态位置的可达性问题进行分析,定义了状态转移约束条件,并采用超致密时间模型表达全局时间信号,然后建立ASA与FMS的状态关系映射,证明ASA可达性判定问题.最后提出一种基于决策树的ASA状态集分类搜寻策略(DT-ASA*),通过Ptolemy II平台建立DT-ASA*策略模型并分析其精确性、执行时间及内存使用率,仿真结果显示系统模型预测值与实际值基本一致,但仍然存在过度匹配的现象,使用模型预测任务状态能极大减少执行时间,但同时会消耗更多内存资源.
Aiming at the problem which the tasks set schedulability is difficult to analysis accurately and quickly when real-time interaction of continuous physical process and discrete computing process in cyber physical system. A analysis method based on finite state machine( FSM) and named actor state automata is proposed. First,it translates the schedulability analysis of CPS to the reachability analysis of the state locations in automata,and the state transition constraints are defined,the superdense time model is adopted for expressing global time signal,then the status mapping relationships between ASA and FSMare established,and the decision problem of reachability is proved. Lastly,a classified search strategy of state set for ASA based on decision tree and named DT-ASA*is proposed,and analyzes its accurateness,execution time and memory usage through establishes a model in Ptolemy II,and the simulation results showthat the predicted value and actual value are basically identical,but still exists the phenomenon of excessive matching,the model can greatly reduce the execution time,but at the same time will consume more memory resources.
Aiming at the problem which the tasks set schedulability is difficult to analysis accurately and quickly when real-time interaction of continuous physical process and discrete computing process in cyber physical system. A analysis method based on finite state machine( FSM) and named actor state automata is proposed. First,it translates the schedulability analysis of CPS to the reachability analysis of the state locations in automata,and the state transition constraints are defined,the superdense time model is adopted for expressing global time signal,then the status mapping relationships between ASA and FSMare established,and the decision problem of reachability is proved. Lastly,a classified search strategy of state set for ASA based on decision tree and named DT-ASA*is proposed,and analyzes its accurateness,execution time and memory usage through establishes a model in Ptolemy II,and the simulation results showthat the predicted value and actual value are basically identical,but still exists the phenomenon of excessive matching,the model can greatly reduce the execution time,but at the same time will consume more memory resources.
引文
[1]He Ji-feng,Li Xuan-dong.Cyber-physical systems[J].Communications of CCF,2013,9(7):6-7.
[2]Yang Gang,Du Cheng-lei,Wang Yu-ying,et al.Behavior modeling and simulation verification of CPS[J].Communications of CCF,2013,9(7):16-23.
[3]Zhao Yang,Xiong Yu-hong,Edward A.Lee,et al.The design and application of structured types in ptolemy II[J].International Journal of Intelligent System,2010,25(2):118-136.
[4]Akkaya I,Derler P,Emoto S,et al.Systems engineering for industrial cyber-physical systems using aspects[J].Proceedings of the IEEE,2016,104(5):997-1012.
[5]Elena F,Pavel K,Paul P,et al.Task automata:schedulability,decid ability and undecidability[J].Information and Computation,2007,205(8):1149-1172.
[6]Gui Sheng-lin,Luo Lei,Li Yun,et al.Schedulability analysis tool for distributed real-time systems based on automata theory[J].Journal of Softw are,2011,22(6):1236-1251.
[7]Stigge M,Ekberg P,Guan N,et al.The digraph real-time task mnodel[C].Real-Time and Embedded Technology and Applications Symposium,IEEE,2011:71-80.
[8]Zhao Y,Xiong Y H,Edward A L,et al.The design and application of structured types in ptolemy II[J].International,Journal of Intelligent System,2010,25(2):118-136.
[9]Xu Hong-zhi,Li Ren-fa,Zeng Li-ning.Modeling and simulation of cyber-physical system based on ptolemy[J].Journal of System Simulation,2014,26(8):1633-1638.
[10]Ilge A.Data-driven cyber-physical systems via real-time stream analytics and machine learning[D].University of California,Berkeley,2016.
[11]Zhang Jing,Chen Yao,Fan Hong-bo,et al.Control strategy of task scheduling permission in cyber-physical system[J].Computer Engineering,2017,43(4):60-66.
[12]Zhao Xing-wang,Liang Ji-yie.An attribute weighted clustering algorithm for mixed data based on information entropy[J].Journal of Computer Research Development,2016,53(5):1018-1028.
[13]Sarjoughian H S,Sundaramoorthi S.Superdense time trajectories for DEVS simulation models[C].Symposium on Theory of M odeling&Simulation:Devs Integrative M&s Symposium,Society for Computer Simulation International,2015:249-256.
[14]Wang Jian-ping,Zhang Yun-sheng,Zhang Guo,et al.Real-time semantics of state transition for embedded control systems[J].Control and Decision,2014,29(1):83-88.
[15]Maryam B,Ilge A,Ehsan K,et al.Coordinated actors for reliable self-adaptive systems[C].Proc.of Formal Aspects of Component Softw are,Besanon,France,Oct.,2016:19-21.
[1]何积丰,李宣东.信息-物理融合系统[J].中国计算机学会通讯,2013,9(7):6-7.
[2]杨刚,杜承烈,王余英,等.CPS行为建模及其仿真验证[J].中国计算机学会通讯,2013,9(7):16-23.
[6]桂盛霖,罗蕾,李允,等.基于自动机理论的分布式实时调度分析工具[J].软件学报,2011,22(6):1236-1251.
[9]徐洪智,李仁发,曾理宁.基于Ptolemy的信息物理融合系统建模与仿真[J].系统仿真学报,2014,26(8):1633-1638.
[11]张晶,陈垚,范洪博,等.信息物理融合系统任务调度权限控制策略[J].计算机工程,2017,43(4):60-66.
[12]赵兴旺,梁吉业.一种基于信息熵的混合数据属性加权聚类算法[J].计算机研究与发展,2016,53(5):1018-1028.
[14]王剑平,张云生,张果,等.嵌入式控制状态转移的确定性实时语义[J].控制与决策,2014,29(1):83-88.
[2]Yang Gang,Du Cheng-lei,Wang Yu-ying,et al.Behavior modeling and simulation verification of CPS[J].Communications of CCF,2013,9(7):16-23.
[3]Zhao Yang,Xiong Yu-hong,Edward A.Lee,et al.The design and application of structured types in ptolemy II[J].International Journal of Intelligent System,2010,25(2):118-136.
[4]Akkaya I,Derler P,Emoto S,et al.Systems engineering for industrial cyber-physical systems using aspects[J].Proceedings of the IEEE,2016,104(5):997-1012.
[5]Elena F,Pavel K,Paul P,et al.Task automata:schedulability,decid ability and undecidability[J].Information and Computation,2007,205(8):1149-1172.
[6]Gui Sheng-lin,Luo Lei,Li Yun,et al.Schedulability analysis tool for distributed real-time systems based on automata theory[J].Journal of Softw are,2011,22(6):1236-1251.
[7]Stigge M,Ekberg P,Guan N,et al.The digraph real-time task mnodel[C].Real-Time and Embedded Technology and Applications Symposium,IEEE,2011:71-80.
[8]Zhao Y,Xiong Y H,Edward A L,et al.The design and application of structured types in ptolemy II[J].International,Journal of Intelligent System,2010,25(2):118-136.
[9]Xu Hong-zhi,Li Ren-fa,Zeng Li-ning.Modeling and simulation of cyber-physical system based on ptolemy[J].Journal of System Simulation,2014,26(8):1633-1638.
[10]Ilge A.Data-driven cyber-physical systems via real-time stream analytics and machine learning[D].University of California,Berkeley,2016.
[11]Zhang Jing,Chen Yao,Fan Hong-bo,et al.Control strategy of task scheduling permission in cyber-physical system[J].Computer Engineering,2017,43(4):60-66.
[12]Zhao Xing-wang,Liang Ji-yie.An attribute weighted clustering algorithm for mixed data based on information entropy[J].Journal of Computer Research Development,2016,53(5):1018-1028.
[13]Sarjoughian H S,Sundaramoorthi S.Superdense time trajectories for DEVS simulation models[C].Symposium on Theory of M odeling&Simulation:Devs Integrative M&s Symposium,Society for Computer Simulation International,2015:249-256.
[14]Wang Jian-ping,Zhang Yun-sheng,Zhang Guo,et al.Real-time semantics of state transition for embedded control systems[J].Control and Decision,2014,29(1):83-88.
[15]Maryam B,Ilge A,Ehsan K,et al.Coordinated actors for reliable self-adaptive systems[C].Proc.of Formal Aspects of Component Softw are,Besanon,France,Oct.,2016:19-21.
[1]何积丰,李宣东.信息-物理融合系统[J].中国计算机学会通讯,2013,9(7):6-7.
[2]杨刚,杜承烈,王余英,等.CPS行为建模及其仿真验证[J].中国计算机学会通讯,2013,9(7):16-23.
[6]桂盛霖,罗蕾,李允,等.基于自动机理论的分布式实时调度分析工具[J].软件学报,2011,22(6):1236-1251.
[9]徐洪智,李仁发,曾理宁.基于Ptolemy的信息物理融合系统建模与仿真[J].系统仿真学报,2014,26(8):1633-1638.
[11]张晶,陈垚,范洪博,等.信息物理融合系统任务调度权限控制策略[J].计算机工程,2017,43(4):60-66.
[12]赵兴旺,梁吉业.一种基于信息熵的混合数据属性加权聚类算法[J].计算机研究与发展,2016,53(5):1018-1028.
[14]王剑平,张云生,张果,等.嵌入式控制状态转移的确定性实时语义[J].控制与决策,2014,29(1):83-88.