首页> 正文

实时系统最差情况执行时间分析的研究

2020-11-22阅读(814)

实时系统最差情况执行时间分析的研究

论文摘要

与非实时系统不同，实时系统的正确性不仅要求输出结果在逻辑上正确，而且要求输出结果必须在规定的时间范围内产生。时间对于实时系统具有至关重要的意义。分析实时程序最差情况执行时间（Worst-Case Execution Time，WCET）的目的是，在程序或者程序片段投入使用之前获得其最差情况的执行时间估值。事先获知任务的WCET估值是实时系统调度及可调度性分析的前提，也是检查实时系统的性能是否满足要求的依据。获得WCET估值的常用方法是静态分析方法。静态分析方法在分析处理器特性的基础上，计算执行程序代码所占用的处理器时间上限（upper bound）。WCET分析要求安全和尽可能精确。精确的WCET估值能够节省资源。为了得到精确的WCET估值，需要获得针对WCET分析的程序流信息，例如循环的迭代范围。自动分析程序的流信息是自动分析程序WCET的关键。论文针对WCET分析方法展开了深入研究，重点研究了程序流信息的自动分析方法，包括：分析程序变量取值范围的方法和获得针对WCET分析的程序流信息的方法；基于程序模式（mode）的WCET分析方法。程序轨迹是程序的一个节点序列。当输入参数值在一定范围内变化时，程序可沿固定的轨迹执行，该轨迹对应程序的一个模式。在每个程序模式下，我们可以计算出一个WCET值。如果事先得知程序按照哪个模式运行，那么根据此模式计算的WCET值比不区分模式所计算的WCET值更精确。本文研究了自动分析程序模式的方法以及基于模式的WCET分析方法；面向对象程序的WCET分析方法。用面向对象技术进行分析、设计和编码是实时系统领域的发展趋势，但面向对象多态性却使程序的WCET分析难以进行。本文研究了具有多态特征的面向对象程序的WCET分析方法；实时系统测试中修正插装断言引起的程序时间变化的方法。为了充分测试实时程序，需要对被测程序进行插装以便获知程序的内部状态。然而，程序插装会使原有程序的时间行为发生改变。本文研究了精确计算插装断言的执行时间以及修正程序测试时间变化的方法。论文的主要创新点包括：1．系统地提出了一个基于抽象解释和通用单调数据流框架的分析程序变量取值范围的方法。该方法不仅能够保证分析的正确性，而且能够提高分析的迭代速度。在程序变量取值范围分析的基础上，提出了自动计算用于WCET分析的程序流信息的方法，该方法用于计算循环迭代范围、循环中路径和基本块的迭代范围、标识不可行路径。该方法为精确的WCET分析提供了保证。2．通过使用程序切片技术和面向路径的测试数据生成技术，提出了一种自动确定程序模式的方法。针对现代RISC处理器，提出了自动计算程序模式的WCET的方法；针对CISC处理器，提出了一种生成程序带条件的WCET符号表达式的方法。3．通过把UMI设计信息用于程序的WCET分析，提出了一个解决面向对象程序的多态性所导致的不确定性问题的方法。在要求说明关联角色多重性的基础上，通过建立关联关系到其程序表示的对应关系，计算了多态循环的迭代范围，确定了虚类函数调用对应的各个具体类调用，从而能够自动计算具有多态特征的面向对象程序的WCET。4．设计并实现了WCET分析的工具原型WCETAnalyzer。该工具能够自动分析C／C++程序针对WCET分析的程序流信息和程序模式，确定多态循环的迭代范围以及其中虚类函数调用和具体类调用的对应关系，并根据用户要求计算一个程序模块或者整个程序的WCET。5．利用WCET分析技术和原型工具WCETAnalyzer，提出了一个自动计算插装前后程序时间的变化，并根据变化的时间修正程序测试时间的方法。实验结果表明，本文的方法提高了WCET、分析的精度，扩大了WCET分析的适用范围。由于这些方法是自动的，因此它们具有良好的工业应用前景。

论文目录

  • 中文摘要
  • ABSTRACT
  • 第一章 绪论
  • §1.1 实时系统、嵌入式系统和程序WCET
  • §1.2 获取程序WCET的方法
  • §1.3 WCET分析的定义、要求和组成
  • §1.4 处理器体系结构特征与WCET分析
  • §1.5 WCET分析的研究现状和存在的问题
  • §1.6 论文的主要工作
  • §1.7 论文结构
  • 第二章 WCET分析技术
  • §2.1 程序流事实分析
  • 2.1.1 流事实表示
  • 2.1.2 手工标注方法
  • 2.1.3 直接计算
  • 2.1.4 抽象解释方法
  • 2.1.5 模式和情节
  • 2.1.6 块计数方法
  • 2.1.7 路径簇（Path Clustering）方法
  • §2.2 执行时间模型
  • 2.2.1 高速缓存
  • 2.2.2 流水线
  • 2.2.3 高速缓存和流水线的计算
  • §2.3 WCET 计算
  • 2.3.1 基于树的计算
  • 2.3.2 基于路径的计算
  • 2.3.3 IPET方法
  • 2.3.4 母函数方法
  • 2.3.5 符号化表示
  • §2.4 小结
  • 第三章 基于抽象解释和单调通用数据流框架的程序流分析
  • §3.1 WHILE 语言和通用单调数据流分析框架
  • 3.1.1 WHILE语言
  • 3.1.2 通用单调数据流框架及其迭代求解
  • 3.1.3 加宽操作符（widening operator）和收窄操作符（narrowing operator）
  • §3.2 基于通用单调数据流框架的值范围传播
  • 3.2.1 作为格的值范围
  • 3.2.2 值范围运算
  • 3.2.3 值范围分析
  • 3.2.4 测试节点产生的范围
  • 3.2.5 值范围的加宽和收窄操作及分析
  • 3.2.6 典型程序的复杂度分析
  • §3.3　值范围分析的正确性证明
  • 3.3.1 正确性定义
  • 3.3.2 伽罗华连接（Galois connection）
  • 3.3.3 值范围传播的加宽和收窄操作的正确性证明
  • 3.3.4 状态集合SS的分析
  • 3.3.5 值范围分析的伽罗华连接
  • 3.3.6 值范围传播的正确性证明
  • §3.4 导出程序流信息
  • 3.4.1 循环界限
  • 3.4.2 导出循环不可行路径和循环路径的执行次数
  • 3.4.3 导出可行路径和基本块的迭代范围
  • 3.4.4 分析举例
  • §3.5 程序流信息在WCET分析中的应用
  • §3.6 过程间分析
  • 3.6.1 扩充WHILE语言语法
  • 3.6.2 带有过程的数据流分析框架
  • 3.6.3 不同作用范围变量的分析
  • 3.6.4 带有过程的数据流分析举例
  • §3.7 从WHILE语言到C语言
  • 3.7.1 语法
  • 3.7.2 类型和表达式
  • 3.7.3 语句
  • §3.8 实验
  • §3.9 小结
  • 第四章　基于程序模式的WCET分析
  • §4.1 程序模式与WCET分析
  • §4.2 预备知识
  • §4.3 模式相关程序切片
  • 4.3.1 确定依赖输入变量
  • 4.3.2 依赖输入谓词切片
  • 4.3.3 产生模式相关切片的所有路径
  • §4.4 产生模式的输入条件
  • 4.4.1 导出谓词函数的线性算术表达式
  • 4.4.2 构造线性约束系统
  • 4.4.3 线性约束系统求解
  • §4.5 RISC处理器上指定模式的WCET分析
  • 4.5.1 分析方法
  • 4.5.2 缓存分析和计算
  • §4.6 实验结果
  • §4.7 符号化WCET分析方法
  • 4.7.1 基于分支执行频率的WCET计算方法
  • 4.7.2 包含依赖输入分支程序的WCET分析方法
  • §4.8 符号化WCET分析举例
  • §4.9 小结
  • 第五章 面向对象程序的WCET分析
  • §5.1 面向对象程序WCET分析中的问题和解决方法
  • §5.2 利用设计信息确定多态性的不确定性
  • 5.2.1 UML中的关联关系及其表示
  • 5.2.2 多态循环的识别
  • 5.2.3 利用UML中的关联关系分析程序结构
  • 5.2.4 实验验证
  • §5.3 面向对象程序的数据流分析
  • §5.4 实验方法和结果
  • 5.4.1 结构分析
  • 5.4.2 基本块迭代
  • 5.4.3 指令执行时间
  • §5.5 相关工作比较
  • §5.6 小结
  • 第六章 WCET自动分析工具原型WCETANAIXZER
  • §6.1 WCETANALYZER 的功能、要求和系统结构
  • §6.2 PARSER
  • §6.3 AIANALYZER
  • §6.4 MODEANALYZER
  • §6.5 OOANALYZER
  • §6.6 TIMEANALYZER
  • 6.6.1 源程序代码和目标代码的对应
  • 6.6.2 Alpha 21064处理器
  • 6.6.3 基本块执行时间的计算
  • 6.6.4 硬实时与软实时的计算
  • §6.7 小结
  • 第七章 基于WCET分析的实时系统轨迹修正
  • §7.1 测试预言与测试轨迹获取
  • §7.2 程序流信息
  • 7.2.1 监控程序确定的程序流
  • 7.2.2 插入点和检测点
  • §7.3 插装断言的时间分析和修正
  • 7.3.1 插装断言对目标系统的时间影响分析
  • 7.3.2 插装断言的构造
  • 7.3.3 插装断言的时间计算
  • 7.3.4 目标系统的时间计算和修正
  • §7.4 示例
  • §7.5 小结
  • 结束语
  • 致谢
  • 参考文献
  • 作者在学期间取得的学术成果

    • 相关论文文献

    • [1].基于GPRS的快递投递实时系统设计与实现[J]. 软件导刊 2017(10)
    • [2].可信分布式实时系统的面向方面的形式化方法[J]. 硅谷 2011(24)
    • [3].实时系统调度算法综述[J]. 计算机与数字工程 2014(12)
    • [4].带数据约束的概率实时系统的验证[J]. 计算机科学 2017(S1)
    • [5].一种分布式实时系统的资源管理体系结构[J]. 广东工业大学学报 2008(01)
    • [6].生产实时系统在装备制造业中的应用[J]. 汽车实用技术 2019(17)
    • [7].基于生产实时系统在线仿真技术探讨[J]. 电力信息化 2008(09)
    • [8].一种基于知识图谱的实时系统语义约束性实现方法[J]. 小型微型计算机系统 2019(12)
    • [9].汽车移动互联平台的实时系统设计与实现[J]. 工业控制计算机 2017(10)
    • [10].面向无人实时系统的的软件开发与验证方法[J]. 电脑编程技巧与维护 2020(04)
    • [11].基于实时系统的控制算法测试系统设计[J]. 船舶工程 2019(S2)
    • [12].异构的动态分布式实时系统的面向方面的形式化方法[J]. 现代计算机(专业版) 2008(12)
    • [13].面向方面的MDA在分布式实时系统中的应用[J]. 现代计算机(专业版) 2009(04)
    • [14].一种非实时系统灾备资源利用方法的研究[J]. 软件产业与工程 2013(03)
    • [15].基于RFID的Web实时系统构建与实现[J]. 现代计算机(专业版) 2008(09)
    • [16].基于责任策略的非严格实时系统形式化研究[J]. 计算机工程 2014(08)
    • [17].基于RTX实时系统测角方法的研究[J]. 宇航计测技术 2013(03)
    • [18].基于IF的实时系统验证[J]. 计算机时代 2009(04)
    • [19].实时系统任务调度策略研究[J]. 航空计算技术 2018(02)
    • [20].开放式实时系统双层调度框架的一种改进方案[J]. 计算机应用 2009(06)
    • [21].分布式实时系统任务调度算法的设计和实现[J]. 中国测试技术 2008(06)
    • [22].基于反馈控制的开放式实时系统自适应调度算法设计与实现[J]. 计算机科学 2008(09)
    • [23].基于着色时间Petri网的实时系统的形式验证[J]. 计算机科学 2008(07)
    • [24].适用于偶发实时系统的过载控制策略[J]. 计算机工程 2019(06)
    • [25].嵌入式虚拟化实时系统的研究与应用[J]. 机电信息 2019(24)
    • [26].浅谈实时中间件技术[J]. 科技视界 2014(18)
    • [27].开放式实时系统资源共享环境下的调度方法分析[J]. 小型微型计算机系统 2012(11)
    • [28].嵌入式分布实时系统自适应资源管理架构[J]. 计算机测量与控制 2012(02)
    • [29].PI实时系统在脱硫DCS中的应用[J]. 仪器仪表用户 2009(02)
    • [30].首届IEEE泛媒体计算国际会议在兰州大学举办[J]. 中国教育网络 2008(09)

    标签：;  ;  ;  ;  ;  ;  ;  ;  

    实时系统最差情况执行时间分析的研究
    下载Doc文档

    猜你喜欢

    © 2024 毕速过 版权所有 鄂ICP备12018319号-5