《实时系统程序最差情况执行时间(WCET)分析概述.doc》由会员分享，可在线阅读，更多相关《实时系统程序最差情况执行时间(WCET)分析概述.doc（6页珍藏版）》请在金锄头文库上搜索。
1、实时系统程序最差情况执行时间(WCET)分析概述国家自然科学基金(No. 60303013 )资助姬孟洛：国防科技大学计算机学院博士生，研究方向：实时系统分析，面向对象设计；齐治昌：教授，研究方向：软件工程，计算机教育。李书浩：硕士，研究方向：软件工程。联系人：姬孟洛，email：. 通讯地址：长沙 国防科技大学计算机学院博士生队姬孟洛1 齐治昌1 李书浩21 (国防科技大学计算机学院 长沙 410073)2 (并行与分布处理国家重点实验室 长沙 410003)【摘要】事先获知系统中程序最差情况的执行时间(Worst-Case Execution Time ,WCET)是设计和验证实时系统调度
2、及可调度性分析的前提，也是确定周期性任务是否满足其性能目标，从而发现系统性能瓶颈的基础。本文概述了程序WCET的分析方法，描述了WCET分析的定义和组成，重点总结其中的程序流事实分析方法，并指出程序流事实分析存在的问题和WCET分析的研究热点。【关键词】程序流事实分析，最差情况执行时间WCET分析，实时系统，软件工程;An Overview of Worst Case Execution Time (WCET) AnalysisJI Meng-Luo1 QI Zhi-Chang1 Li Shuhao21 (Department of Computer Science, National Uni
3、versity Of Defense Technology, Changsha 410073)2 (Parallel and Distributive Processing of National Laboratory, Changsha 410003)Abstract The purpose of Worst-Case Execution Time (WCET) analysis is to provide a-priori information about the worst possible execution time of a program or piece of a progr
4、am before using them in a system. When designing and verifying real-time systems, WCET estimates can be used to perform scheduling and schedulability analysis, to determine whether performance goals are met for periodic tasks, to check that interrupts have sufficiently short reaction time, to find p
5、erformance bottlenecks, and so on. In this paper we overview the analysis methods of WCET analysis, describe its components, and summarize the analysis methods of program flow fact analysis in WCET analysis. We point out the problem in program flow fact analysis and the research hot spot in WCET ana
6、lysis.Keywords Worst-Case Execution Time analysis, Real-Time System, Software Engineering1 引言实时系统与其它应用系统的不同之处在于其正确性具有更加严格的标准。实时系统的正确性不仅取决于它所产生的输出，同时还取决于输出产生的时间。实时系统的结果只有在规定的时间范围内完成时才是有效的。当没有在规定的时间范围内完成时，轻则降低系统的性能（弱实时系统），重则引起灾难性的后果（强实时系统）。因此，事先获取系统中每个任务最差情况下的执行时间WCET有时也需要知道最好情况下的执行时间（Best-Case Execut
7、ion Time，BCET），因为BCET的分析和应用与WCET基本相同，故统称为WCET。对实时系统的时序分析具有特别重要的意义。事实上，事先得知系统中任务的WCET既是进行调度及可调度性检测的前提，又是系统设计中软硬件界限划分的一个依据，同时还是确定周期性任务是否满足其性能目标,从而发现系统性能瓶颈的基础。WCET分析值必须安全和精确(tightness)，前者保证不能低估最差执行时间，后者要求提供可接受的高估值。获取程序的WCET是实时系统的一个重要研究领域，也是最近十多年来的一个研究热点1。从1986年发表第一篇有关WCET的文献2开始，到目前为止，几乎所有比较发达的国家都有研究机构从
8、事这方面的研究，比较著名的有美国Florida州立大学、Princeton大学、奥地利的Vienna技术大学、瑞典的Uppsala大学、英国的York大学以及韩国国立大学等。WCET分析包括动态度量、静态分析和混合方法共三种方法。动态度量方法就是直接运行程序以测量（measure）程序的执行时间，目前使用的有随机方法、基于遗传算法的进化方法（Evolution Method）、模拟退火方法和统计方法。动态度量方法很难保证所得到结果是安全的，尤其是对现代高性能处理器。静态分析方法根据程序的流信息，针对运行程序的处理器特性估算出程序的WCET。因为程序的流信息通常是非常复杂的，而处理器尤其是现代处
9、理器（比如高速缓存和超级流水线）的特性也很复杂，所以静态分析和计算也会变得非常复杂。但静态分析方法能够保证得到的结果是安全的，而且能够不运行程序就获得结果，从而成为WCET分析研究的主流1。混合方法就是既包括静态分析也包括动态度量的方法。该方法或者首先对程序进行分析，根据分析结果进行测试，或者先度量，然后在度量的基础上静态计算程序的WCET值。本文研究WCET静态分析，并在下文简写为WCET分析。2 WCET分析的定义和组成2.1WCET分析的定义公认的WCET分析的定义是由P.Puschner和A.Burns给出的1：WCET分析是指计算给定应用程序代码片断执行时间的上限，这里代码片断执行时
10、间定义为执行代码片断所花费的处理器时间。从上述定义能够看出：WCET的分析结果是实际WCET值的上界，这里不要求完全精确；分析得到的时间是运行程序占有的处理器时间，这里不考虑上下文切换引起的时间，也没有考虑整个应用程序甚至系统的WCET，考虑的只是不间断运行一个程序所占用的处理器时间；这个时间显然和程序代码片断以及处理器特征有关。2.2 WCET分析的组成一般认为WCET分析包括三个组成部分3：程序流事实分析；执行时间模型的建立；基于前两项信息的WCET计算。为了得到精确的WCET分析值，需要获得程序流事实信息。流事实信息通常包括循环的最大迭代次数、递归调用的最大深度、不可行路径(infeas
11、ible path)和其它的程序流约束信息，其中不可行路径是指对任意输入数据都不可能执行的程序路径。在程序流信息中，对WCET分析影响较大的是循环的迭代次数和不可行路径。要获取程序的WCET，还需要对程序的目标代码进行分析以获得实际的时间，即建立执行时间模型，此分析也称为低层分析。对于不带cache、没有流水线的传统CISC指令，其指令的执行时间是固定的，此时低层分析就非常简单：一个代码段的执行时间就是其所对应的每条指令执行时间的累加。但对于带有高速缓存和流水线以及分支预测机制等特征的现代处理器，代码段执行时间的估算就复杂得多。高速缓存对整个程序段甚至是整个系统的执行时间都有影响，因此它是全局
12、性的，而流水线对相邻的几条指令的执行时间有影响，因此它是局部性的。流水线分析的典型方法是利用保留表4，这也是处理器体系流水线分析的常用方法。两条指令的执行时间就是它们对应的两个保留表连接之后，从第一条指令第一个阶(stage)到最后一条指令的最后一个阶之间的周期（cycle）数。典型的高速缓存的分析方法是把每条指令分为不同的访问类型，根据不同的访问类型计算缓存引起WCET。Mueller5把指令的访问类型分为4类： always miss、always hit、first miss和first hit，分别表示总是丢失、总是命中、第一次丢失和第一次命中。计算的目的在于，在给定程序流事实和执行时
13、间模型的情况下，为程序计算WCET估值。计算方法可以分为三大类3：基于路径的（path-based）、基于树的（tree-based）和隐含路径枚举的（IPET，Implicit Path Enumeration Technique）方法。在基于树的计算6中，使用为每种类型的复合程序语句定义的规则确定语句的WCET，然后通过自底向上遍历程序的语法分析树产生整个程序的WCET估值。此方法称为Time schema。Time schema方法概念简单，计算容易，但难以考虑语句间的依赖性。在基于路径的计算3457中，通过计算程序中不同路径的时间，然后查找具有最长执行时间的路径产生WCET估值。此方法
14、的特性是，可能的执行路径是明确表示或确定的。在单个循环中基于路径的方法是很自然的，但当跨越循环嵌套层次时流事实信息表示会比较困难。IPET是由Li等8提出的，首先应用于指令执行时间不变的简单处理器时间模型中，后又将此方法应用到流水线和高速缓存的计算。IPET计算使用代数和或者或逻辑约束表示程序流和执行时间。为程序中的每个基本块和程序流边赋一个时间变量（tentity）和一个计数变量（xentity），tentity表示该块或边的执行时间，xentity表示该块或边的执行次数。在满足程序的结构和可能流的约束情况下，通过最大化下列目标函数（cost function）找到WCET： IPET约束系
15、统既可以用整数线性规划技术解决（ILP），也可以用约束解决技术CSP解决。由于有可用的有效ILP解决器，ILP成为最流行的计算方法。约束解决技术允许表达更复杂的约束，但一般会花费更长的时间。需要说明的是，WCET分析的三个组成部分是相互依赖、相互影响的。举例来说，执行时间模型的不同层次对流事实的要求是不同的。3 程序流事实分析程序流事实用来确定程序可能的执行路径，也就是程序的动态行为。流事实分析的结果是诸如哪些函数得到调用、循环的迭代次数、不同的if语句之间的依赖关系等信息。因为此问题一般是计算处理，所以通常都进行简化和近似的分析。但此分析必须遵从安全的路径信息，即要考虑到所有的可行路径。流事实信息分析包括手工标柱和自动分析两种。手工标柱是用户通过与WCET工具的交互，给源程序代码添加标注(annotation)，或者在程序代码外面给出需要的信息。比如，Kirner等9通过用额外的语法来扩充C语言以定义循环的界限和路径信息，从而允许流信息进入源程序代码。Brjesson10使用C代码中的#pragmas添加标注。手工标注对程序员来说是个很大的负担，因为有时即使是一个很小的程序想标注出来也是困难的，同时手工标注容易出错。因此，最好能够通过自动流分析获取需要的信息。自动流信息分析通过分析程序代码来获取流信息，自动流分析通常获得循环的执行界限和循环中的不可行路径。下面介绍几种程序
