实时系统最坏执行时间分析

实时系统开发过程中必须强调时间的重要性和支持时间的可预报性。最坏执行时间分析与可调度性分析构成了实时系统时间方面操作可信的基础。最坏执行时间分析计算任务执行时间的上界,这些任务的上界用来分配正确的CPU时间给实时任务。最坏执行时间是可调度分析工具的输入,可调度分析决定了一组任务在一个给定的目标系统下是否可调度。对最坏执行时间分析方面的研究进行了综述,给出在这一领域所取得的进展。还讨论了在最坏执行时间分析方面存在的问题,给出了将来的研究方向。

实时系统程序最差情况执行时间(WCET)的分析

事先获知系统中程序最差情况的执行时间(Worst-CaseExecutionTime,WCET),是设计和验证实时系统调度及可调度性分析的前提,也是确定周期性任务是否满足其性能目标,从而发现系统性能瓶颈的基础。本文概述了程序WCET的分析方法,描述了WCET分析的定义和组成,重点总结其中的程序流事实分析方法,并指出程序流事实分析存在的问题和WCET分析的研究热点。

一种快速程序最坏执行时间分析方法研究

给出一种带有路径冲突检测的程序最坏情况执行时间估计方法,这种方法首先检测程序中存在的分支约束,然后将程序中存在的分支约束信息转化为程序流程控制图(CFG图)中结点之间的语义冲突,并按照结点对的形式保存在相应的冲突数组里,在接下来的WCET计算阶段通过边搜索程序执行路径边检测冲突数组里保存的已有的冲突关系以便在搜索路径的同时排除非可行执行路径,最终在可行执行路径集中选择具有最大执行时间的执行路径。与以往的方法相比,在保持估计精度的前提下,本文的方法避免了穷举所有执行路径带来的复杂度,提高了搜索的效率。实验结果表明本文方法对于语句间语义依赖关系比较强的实时程序能够快速且有效地给出估计结果。

一种精确程序最坏执行时间分析方法

Java语言的动态特性使程序的最坏执行时间分析较悲观和难以预测,提出一种精确最坏执行时间分析方法,在高层分析中,引入一种标记方法,对带有标记的Java类文件进行反编译提取控制流程,得到每一个基本块中的Java字节码指令的最坏情况下的执行次数,在底层分析中,建立结合流水线和高级缓存影响的时间模型,得到每条指令所对应的执行时间,最后结合高层分析和底层分析的结果得到程序的最坏情况下的执行时间。实验表明,该方法可以使对实时Java程序的最坏情况执行时间预测更加安全和精确。

两种基于符号的最坏执行时间分析方法的比较与分析

通常的最坏执行时间分析方法只是得到一个常数,然后将这个常数应用在所有的地方,这将造成所得的值过于悲观(overpessimistic)。如果能以一个代数表达式代替,其中影响程序执行时间的一些未知值(如调用参数,运行平台参数等)都用参数来表示,然后在具体的环境中再根据具体的情况进行实例化,那么所获得的最坏执行时间将更加接近于实际的值。文章讨论了基于符号的最坏执行时间分析方法,分析了其特点,对两种基于符号的最坏执行时间分析方法进行了比较和研究,并给出了将来的研究方向。

基于MPA与静态预估的最坏执行时间分析方法

针对现有嵌入式系统最坏执行时间(WCET)的静态分析方法效率低下问题,利用最小传播算法对程序流进行分析,获得程序中每一个基本块的最小树约束,通过象征性循环上界约束对所求函数中的内部循环变量进行再次约束,并结合最小树约束获得程序的WCET表达式。使用静态预估分析方法对每一个基本块的底层指令周期进行绝对估值,将底层指令周期代入WCET表达式计算出程序最终的WCET值。实验结果表明,与基于程序控制流程图的程序执行时间静态分析方法相比,该方法在保证程序分析精度的同时,大幅提高了分析效率。

可平台迁移的最坏执行时间分析

当前的很多最坏执行时间分析工具都是针对特定的编程语言或特定的编译器的,因而缺乏平台间的迁移性,从而不能被广泛使用。介绍了一种基于Java字节码的可平台迁移的最坏执行时间分析方法。该分析方法包括两方面:一是对字节码(java bytecode)的高层分析,提取出程序数据流和控制流信息;二是对Java虚拟机的底层分析,获得虚拟机的时间模型。最后这两种分析结合得到程序的最坏执行时间。同时还探讨了将来的研究方向。

多余处理器时间回收与最坏执行时间分析

通常的最坏执行时间分析方法的结果过于悲观(overpessimistic),根据这种结果进行调度将导致资源的极大浪费。面向对象的编程语言由于具有封装、继承、多态的特点,使得按照通常的方法获得的最坏执行时间更加悲观。解决这个问题的一个办法就是限制面向对象语言这些特点的使用,但这又导致最终的实时系统不够灵活,失去了面向对象语言的优点。文章以实时JAVA系统为例,介绍了将运行中赚取时间(gaintime)的回收与最坏执行时间分析相结合的方法,这种方法既提高了资源的使用率,又保证了系统的灵活性和性能。

实时系统最坏执行时间分析及测试

程序最坏执行时间是实时系统可调度分析的基础,同时也是对系统进行性能分析,提前发现系统瓶颈的重要依据。本文首先论述了程序最坏执行时间(WCET)分析计算的主要方法,然后介绍了主要的测试工具及其应用情况,最后针对程序最坏执行时间的工程应用提出可行建议。

程序最坏执行时间极值统计方法

程序的最坏执行时间WCET是实时系统时间操作方面的可信基础,现有的WCET静态分析方法都需要对系统某种程度上的额外知识和限定性假设,导致现有的WCET分析方法本质上为偏高估计,降低了资源的利用率和系统的性能。给出一种基于极值统计的程序最坏执行时间估计新方法,采用程序执行时间的测量值作为样本,利用Gumbel分布建立程序最坏执行时间统计模型,根据测量样本序列预测执行时间的最大值,与以往的方法相比,这种方法综合体现了各种硬件特性对程序执行时间的影响,估计结果更为精确,更适合处理硬件特性和软件复杂度较高情况下的程序最坏执行时间估计。实验结果表明利用Gumbel分布建立的WCET估计模型能够快速且有效地给出实时程序的最坏执行时间估计。

基于多级一致性协议的多核处理器WCET分析方法

由于多核处理器优越的计算性能,多核处理器现已广泛应用在嵌入式实时系统中.相对于单核处理器,多核处理器存在资源共享竞争、并行任务干扰等因素,尤其是缓存(Cache)一致性问题,导致任务最坏情况执行时间(worst-case execution time,WCET)的预测更加困难.基于以上因素,提出基于多级一致性协议的多核处理器WCET分析方法.该方法针对多级一致性协议体系架构,提出多级一致性域的概念,将多核处理器的数据访问分为域内访问和跨域访问2个层次,根据Cache读写策略和MESI(modify exclusive shared invalid)一致性协议,得出一致性域内部和跨一致性域的Cache状态更新函数,从而实现多级一致性协议嵌套情况下的WCET分析.实验结果表明,在改变Cache配置参数的情况下,该方法分析结果与GEM5仿真结果的变化趋势一致,经过相关性分析,GEM5仿真结果与该方法分析结果相关性系数不低于0.98;在分析精度方面,该方法的平均过估计率为1.30,相比现有方法降低了0.78.

一种保障实时系统时间约束的处理器指令扩展

采用软硬件协同技术,通过必要的硬件语义实现资源隔离,基于高效的任务调度保障不同关键级别任务满足时间约束,是当前混合关键系统设计的有效方法之一。本研究基于时序可预测的细粒度多线程处理器FlexPRET,扩展设计实现时序指令,并分别在硬件和编译器中添加对扩展指令的支持,使得程序在代码中对最大执行时间进行时序约束语义描述。实验评测表明,所实现的扩展指令可为用户提供更精细的时序控制。

车控操作系统实时性/安全性保障技术

电子控制技术为智能网联汽车的高速发展持续赋能,车控操作系统是保障汽车电子控制软件安全、高效、实时运行的基石。随着智能网联汽车向集中式、端云融合式电子电气架构发展,车载硬件演化为多核异构处理器、弹性计算平台,车控软件向面向服务的软件架构转变,车控操作系统的架构、关键技术等也随之发展。综述了智能网联汽车用车控操作系统的发展历程与现状,对任务调度、实时性/安全性保障、形式化表征与验等基础理论和关键技术进行深入分析,阐述现有车控操作系统的技术挑战与发展趋势,为智能网联汽车的车控操作系统发展提供参考。

基于取指执行时序范畴的多核共享Cache干扰分析

在多核结构中,获得并行应用线程的安全、精确的最坏情况执行时间(worst case execution time,WCET)的最大挑战之一在于共享资源的竞争冲突检测.在共享Cache的多核处理器中,线程在共享Cache中的指令可能被其他并行线程的指令替换,从而导致了线程间在共享Cache上的干扰,因此多核结构下线程WCET需要考虑并行线程间在共享Cache上的干扰.在现有的简单地址映射干扰分析基础上,考虑了指令取指执行时序因素对干扰的影响,提出了非干扰状态的充分不必要条件,根据指令的取指执行时序范畴判断线程在共享Cache上的干扰状态.通过排除非干扰状态,可以进一步精确多核结构中线程的WCET估值.理论分析证明了该方法的有效性.实验结果表明,与当前现有的考虑执行周期和基于逻辑访问先后顺序的方法相比,基于时序方法下的WCET估值分别可以提高12%和7%的精确度.

包含依赖输入分支程序的符号化WCET分析

符号化WCET(worst-caseexecutiontime)分析是用符号表达式表示任务的最大执行时间:表达式中包含了参数.通过在运行时刻快速确定表达式值,符号化WCET分析可以更精确地估算WCET.提出了一种针对其分支直接依赖于输入数据的程序的符号化WCET分析方法.首先对Blieberger方法进行扩充,使得WCET符号表达式能够表达依赖输入分支,然后利用程序的控制依赖图对符号表达式进行化简,从而产生带条件的WCET符号表达式,即不同的条件对应不同的符号表达式.与已有方法不同,符号化WCET公式直接依赖于输入参数,使得运行时的WCET估算更加简单直接.

支持软件预取的缓存WCET分析

许多高性能嵌入式处理器都引入了多级缓存、硬件预取及软件预取等机制,为使支持软件预取的硬实时任务具有执行时间的可预测性,提出一种支持软件预取的缓存WCET分析方法.该方法对多级缓存抽象解释模型进行了软件预取语义扩展,分析了软件预取对任务的最坏情况下性能和能耗的影响.实验结果表明,该方法能够对支持软件预取的多级缓存行为进行有效分析;同时软件预取优化技术可使某些访存缺失较大的硬实时任务WCET平均减少22.9%,能耗平均降低24.1%.

基于WCET的SPM实时性管理策略

提出一种基于最坏情况执行时间(WCET)的SPM静态分配算法,该算法采用额外的WCET分析工具获得任务最坏情况执行路径(WCEP),针对最坏情况执行路径,把程序划分为全局变量、全局堆栈、指令块等节点,用包含节点和节点间关系的CFG描述应用程序,采用考虑节点间关系的算法把选中的节点分配到SPM中。仿真实验结果表明,采用该分配策略管理SPM空间比不采用SPM时的实时性提高54%左右。

基于WCET的多核共享资源冲突分析与约束研究

随着片上多核处理器在嵌入式实时系统中的应用,片上共享资源给任务的WCET分析带来诸多挑战,使得对多核共享资源冲突问题的研究变得非常重要。依据研究的目标,可以把目前已有的研究分为面向共享资源冲突分析和面向共享资源冲突约束两大类。对于面向共享资源冲突分析问题,探讨了不同共享资源冲突产生的原因,概括和比较了典型的冲突分析方法的优势和局限性;对于面向共享资源冲突约束问题,给出了其主要的研究内容,并评述和分析了几种主流的冲突约束方法。最后针对目前的研究状况指出了一些研究方向。

用于WCET静态分析的MIPS处理器建模方法研究

为获得安全而紧致的WCET估计,需要考虑执行程序的目标处理器的体系结构特征.Cache、流水线等用于提高性能的技术已经广泛地应用于现代处理器中,如果在静态分析过程中不考虑它们带来的影响,必然会导致WCET过估计.以Petri网作为模型工具,以WCET分析为应用目标构造MIPS处理器的体系结构模型,该方法讨论了各种RISC处理器中常见的体系结构特征的抽象以及它们在Petri网模型中的表示方法.通过实验验证,指令序列在Petri网模型上的模拟执行时间与指令序列在DLXView模拟器上的测试结果具有一致性,表明构建处理器的体系结构Petri网模型是一种有效的指令序列执行时间的静态分析方法.

支持指令预取的两级指令缓存WCET分析

随着嵌入式实时系统中硬件的不断发展,许多处理器具有两级指令缓存并且支持指令预取技术.指令预取技术能否在两级指令缓存结构中广泛应用,取决于两级指令缓存下支持指令预取的缓存最坏情况执行时间(WCET,Worst-Case Execution Time)能否被分析.目前虽然存在一些支持指令预取的缓存分析方法,但是它们都只能用于单层指令缓存,并不能用于多层组关联指令缓存WCET分析.通过扩展在两级指令缓存架构下缓存分析的支持指令预取的抽象语义,本文提出了基于抽象解释的支持指令预取的缓存WCET分析方法.本文分析指令预取对于L1指令缓存和L2指令缓存访存延迟和抽象缓存状态的影响,设计了支持指令预取的L1指令缓存和L2指令缓存访存延迟计算方法和缓存状态分析算法.本文实验中对不同的Benchmarks进行了分析,结果表明本文的支持指令预取的缓存WCET分析方法是有效的,在不同的指令预取度下,指令预取比没有指令预取的最坏情况下平均提升了19.3%的性能.