TMSVL语言及其在实时系统验证上的应用

来源 :西安电子科技大学 | 被引量 : 0次 | 上传用户:fuiegfiusbkufbakuefg
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
MSVL(Modeling,Simulation and Verification Language)是一种时序逻辑程序设计语言,是投影时序逻辑(Projection Temporal Logic,PTL)的可执行子集。MSVL主要用于形式化建模、仿真和验证并发系统以及交互式系统,但其不能有效地建模和表达实时系统中的时间约束和中断等行为以及和时间相关的性质,使其在实时系统中应用受到限制。本文对MSVL语言进行扩展,得到了可以建模实时系统的语言TMSVL(Timed MSVL),并为TMSVL开发了解释器(模型检测工具)。使用TMSVL实现了对单速率调度(Rate-monotonic Scheduling,RMS)算法、基于μC/OS-Ⅲ的实时系统、基于ROS(Robot Operating Systems)的人工智能系统以及多级中断系统的建模、仿真和验证。本文围绕定义TMSVL语言的逻辑、TMSVL语言的语义、工具实现以及对TMSVL语言的应用展开,主要工作概括如下:第一,针对PTL不能定义连续时间中的时间约束和强制终止或者超时的问题扩展PTL,从而得到其基于时间的扩展形式TPTL(Timed PTL)。TPTL主要从以下三方面扩展PTL:(1)在PTL中引入代表时间的变量T和代表时间长度的变量Ts来建模实时系统的时间,二者的取值均为非负实数;(2)定义时间约束操作符来限制被约束公式的时间长度,它可以描述连续时间概念下的时间约束;(3)定义cut操作符来描述强制终止或者超时。接着,本文给出并证明了 TPTL中包含时间约束和cut操作符的公式的逻辑规则。TPTL的提出为定义实时系统建模语言从而验证实时系统提供了形式化(模型)语义。第二,为了建模、仿真和验证实时系统,本文使用TPTL定义了扩展的MSVL语言,即TMSVL。TMSVL不仅包括了MSVL中的所有语句,还包含了建模实时系统的时钟语句、cut语句、延时语句、超时语句和中断语句。本文证明了所有的TMSVL语句都可以转化为范式,并给出了TMSVL语句转化范式的方法。定义了TMSVL语言的操作语义,给出了表达式的求值规则和扩展语句的语义等价规则,并通过证明TMSVL语言操作语义和模型语义的一致性来确保操作语义的正确性。使用TMSVL语句,可以建模实时系统中的延时、定时响应、任务截止时间、强制终止、超时和中断等时间约束行为。第三,为了自动化实时系统的建模、仿真和验证过程,本文基于TMSVL语言的操作语义,开发了TMSVL解释器。该工具通过扩展MSVL解释器而得到,使其支持了对时钟语句、cut语句、延时语句、超时语句和中断语句的词法分析、语法分析以及语义分析。该解释器具有三种工作模式(建模、仿真和验证):在建模模式下,可以得到程序的带标记的范式图(Labeled Normal Form Graph,LNFG),它描述了程序的状态空间;在仿真模式下,可以得到程序的一条执行路径;在验证模式下,可以验证系统是否满足给定性质。TMSVL解释器为模型检测实时系统提供了新的工具支持。第四,在实时系统的设计中,确保任务的实时性以及中断处理的安全性是一项关键且复杂的工作。本文以经典调度算法RMS为例,将TMSVL语言应用到基于RMS算法的任务集的可调度性检测上。该方法提供了检测RMS算法可行性的充分必要条件,而且可以解决一系列任务集的可调度性检测问题。此外,本文将提出方法应用到基于μC/OS-Ⅲ的实时系统的可靠性验证上。以基于μC/OS-Ⅲ的实时系统为研究案例,分别使用TMSVL建模了包含多任务同步的实时系统和包含中断的多任务实时系统,并成功地验证了这些系统中任务的实时性以及系统的安全性。接着,本文研究了如何将TMSVL语言及其模型检测方法应用到建模和验证基于ROS的人工智能系统上。最后,本文研究了如何使用TMSVL形式化建模多级中断系统。基于TMSVL中的基本中断语句,给出了建模多级中断系统的方法。该方法为多级中断系统提供了形式化语义,使得可以对这类系统进行模型检测,从而形式化验证其实时性和安全性。
其他文献
复杂系统遍及自然、社会和技术领域。建立刻画复杂系统的模型是认知、预测、控制和同步复杂系统的基础。对于大多数复杂系统,只有有限的复杂动力学表征数据可用。因此,如何从表征数据构建刻画复杂系统的模型成为当代复杂系统研究的一个核心问题。作为系统建模的技术基础,优化算法辅助建模成为大数据时代下复杂系统建模研究的核心之一。针对设计复杂系统智能建模算法所遇到的难点,本文以模糊认知图和复杂网络为工具,人工智能技术
保密通信一直是信息技术领域的研究热点,近年来,互联网和移动通信的发展对保密通信的安全性提出了更高的要求.作为一类典型的非线性系统,混沌系统因其生成的状态信号具有初值敏感性、非周期性、为随机性、类噪声性等复杂的动力学特征,表现出了高度的不可预测性及天然的隐蔽性,正好符合保密通信的安全需求.混沌同步是实现保密通信的前提,但现有的同步方法和控制技术仍有待改进完善.另外,在实际应用中,系统的不确定性和外界
近几年系统的维修建模得到了研究者的极大关注。研究的系统主要分为单部件系统,两部件系统和多部件系统。可修模型的最优替换策略主要有基于系统的工作时间或系统的失效次数的单变量策略以及基于工作时间和失效次数的二元策略。系统的退化过程一般用几何过程描述,即用几何过程描述系统的连续工作时间和修理时间。本文引入扩展的几何过程描述系统连续的工作时间和修理时间,克服了几何过程的严格单调的缺点。考虑了修理工在系统工作
近年来,随着激光技术以及光场调控技术快速发展,各种具有新颖特性的有形电磁波束及结构光束受到了研究人员的广泛关注,本文以高阶时域有限差分方法FDTD(2,4)为基础,重点研究了FDTD算法中有形波束的重构。在传统FDTD方法的基础上使用四阶中心差分,对旋度算符中的空间一阶偏导数进行近似,获得了改善的数值色散以及网格各向异性特性。在此基础上,实现了高阶FDTD中基模高斯波束、高阶贝塞尔波束的重构,研究
碳纳米管(CNT)具有高强度、高刚度、低密度和高横纵比等优异的力学性能,被认为是一种具有广阔应用前景的复合材料增强体。功能梯度材料(FGM)由于其组分含量在一定的空间方向上是连续变化的,其力学特性在空间上也是连续变化的。为了进一步提高CNT增强体对复合材料宏观力学性能的增强效果,功能梯度分布形式被应用到CNT增强复合材料中。功能梯度CNT增强复合材料(FG-CNTRC)结构通常以梁、板或壳的形式存
两块可分凸优化问题在科学与工程中有很多重要应用,乘子交替方向法(ADMM)和Peaceman-Rachford分裂方法(PRSM)是求解该类问题的经典算法.PRSM的收敛性仅在目标函数的凸性下无法保证,但是由于进行了两次乘子更新,PRSM的数值效果优于ADMM.众所周知,传统ADMM和PRSM均以增广拉格朗日函数为效益函数,当子问题求解较为困难时,线性化技术被广泛使用.在增广拉格朗日函数的基础上,
越来越多的光学应用技术涉及到粒子的光散射特性计算与分析。针对不同的粒子,研究者提出并发展了各种光散射理论和计算方法。不同的理论模型和计算方法具有不同的适用范围,目前仍面临的挑战之一是大尺寸非球形粒子的光散射计算问题。对于形态复杂且尺寸远大于入射光波长的粒子,现有的解析理论(如米理论、广义米理论、德拜级数展开)和数值算法(如离散偶极子近似、时域有限差分、T矩阵)不再适用。而几何光学近似(GOA)方法
复杂系统广泛存在于现实世界中,是21世纪的重点研究课题之一,具有重要的实际应用背景和理论研究意义。通过将复杂系统看作是由系统中的多个个体(节点)以及个体间关系所组成的网络系统,复杂网络成为了描述和理解复杂系统的重要工具和方法。目前关于复杂网络的研究存在于多个领域,如数学,物理学,计算机科学,生物学以及社会学等等。对于自然界中的各类复杂网络系统来说,同步不仅仅是一种普遍且典型的聚集性行为,也是复杂网
具有线性约束和可分结构的凸优化模型在半定规划、图像处理、压缩感知、机器学习等领域应用广泛.如何充分利用问题的可分结构,设计有效且收敛的求解算法是最优化领域的一个热门课题.交替方向乘子法(ADMM)由于简单、易于实现以及适用范围广等优点成为应用最广泛的算法之一,并由此掀起了研究一阶分布式算法的热潮.本文针对三种不同结构的可分凸优化问题,基于ADMM和算子分裂算法基本框架设计一阶算法,并系统研究它们的
反应扩散方程(系统)的时空传播已被广泛关注和研究,因为它能够很好地描述和解释众多自然现象,如物种入侵和疾病传播等.行波解和整体解是时空传播理论的重要组成部分,对其研究具有理论意义和应用价值.需要指出的是,目前源于两个行波的整体解已有较多的结果,然而源于三个或三个以上行波的整体解的研究结果还十分有限,尤其是关于环境齐次反应扩散系统和环境非齐次扩散方程的源于三个行波的整体解的研究未曾见到任何结果,因此