实时系统WCET分析方法.doc

WCET相关概念及其分析方法 实时系统，POSIX 1003.b 作了这样的定义：指系统能够在限定的响应时间内提供所需水平的服务。而一个Donald Gillies 提出的更加为大家接受的定义是：一个实时系统是指计算的正确性不仅取决于程序的逻辑正确性，也取决于结果产生的时间，如果系统的时间约束条件得不到满足，将会发生系统出错。 实时系统根据其对于实时性要求的不同，可以分为软实时和硬实时两种类型。硬实时系统指系统要有确保的最坏情况下的服务时间，即对于事件的响应时间的截止期限是无论如何都必须得到满足。比如航天中的宇宙飞船的控制等就是现实中这样的系统。其他的所有有实时特性的系统都可以称之为软实时系统。如果明确地来说，软实时系统就是那些从统计的角度来说，一个任务能够得到有确保的处理时间，到达系统的事件也能够在截止期限到来之前得到处理，但违反截止期限并不会带来致命的错误，像实时多媒体系统就是一种软实时系统。 一个计算机系统为了提供对于实时性的支持，它的操作系统必须对于 CPU 和其他资源进行有效的调度和管理。在多任务实时系统中，资源的调度和管理更加复杂。 由实时系统的定义不难看出，实时系统与其它应用系统的不同之处在于其正确性具有更加严格的标准。实时系统的正确性不仅取决于它所产生的输出，同时取决于输出产生的时间。实时系统的结果只有在规定的时间范围内完成才是有效的。当没有在规定的时间范围内完成时，轻则降低系统的性能(弱实时系统) ，重则引起灾难性的后果(强实时系统) 。因此，事先获取系统中每个任务最差情况下的执行时间WCET(有时也需要知道最好情况下的执行时间(Best Case Execution Time ，BCET) ，因为BCET的分析和应用与WCET 基本相同，故统称为WCET。) 对实时系统的时序分析具有特别重要的意义。事实上，事先得知系统中任务的WCET 既是进行调度及可调度性检测的前提，又是划分系统设计中软硬件界限的一个依据，同时还是确定周期性任务是否满足其性能目标，从而发现系统性能瓶颈的基础。WCET 分析值必须安全和精确( tightness) ，前者保证不能低估最差执行时间，后者要求提供可接受的高估值。获取程序的WCET 是实时系统的一个重要研究领域，是最近10 多年来的一个研究热点。 WCET分析的定义 公认的WCET 分析的定义是由P. Puschner 和A. Burns给出的[1] :WCET 分析是指计算给定应用程序代码片断执行时间的上限,这里代码片断执行时间定义为执行代码片断所花费的处理器时间。 从上述定义能够看出: ①WCET 的分析结果是实际WCET 值的上界,这里不要求完全精确; ②分析得到的时间是运行程序占有的处理器时,这里不考虑上下文切换引起的时间,也没有考虑整个应用程序甚至系统的WCET ,考虑的只是不间断运行一个程序所占用的处理器时间; ③这个时间显然和程序代码片断以及处理器特征有关。 WCET的三种分析方法： WCET 分析包括动态度量、静态分析和混合方法共3 种方法[1]。动态度量方法就是直接运行程序以测量(measure) 程序的执行时间,目前使用的有随机方法、基于遗传算法的进化方法( Evolution Method) 、模拟退火方法和统计方法。动态度量方法很难保证所得到结果是安全的,尤其是现代高性能处理器，并且执行的输入量非常大的情况下。 静态分析方法根据程序的流信息,针对运行程序的处理器特性估算出程序的WCET。因为程序的流信息通常是非常复杂的,而处理器尤其是现代处理器(比如高速缓存和超级流水线) 的特性也很复杂,所以静态分析和计算也会变得非常复杂。但静态分析方法能够保证得到的结果是安全的,而且能够不运行程序就获得结果,从而成为WCET 分析研究的主流。 混合方法就是既包括静态分析也包括动态度量的方法。该方法或者首先对程序进行分析,根据分析结果进行测试,或者先度量,然后在度量的基础上静态计算程序的WCET 值。 静态WCET分析的介绍 静态分析的主要目标是把分析限制在小的程序块而不是整个的执行通路上。通常静态分析针对的只是一个基本的代码块，或者是基本代码块的简单序列。把执行通路划分成数个代码块会降低测量的时间，因为有些公用的代码块只需要测量一次即可。 从大的角度来看，静态WCET分析大概需要三个步骤。流分析决定所有可能的路径，同时用图或者语法树来描述这些路径。时间分析，得到基本块的执行时间，这一过程包括两个步骤：历史依赖机制（缓存和支路预测）的分析，这一步也被叫做全局分析；局部分析，计算基本块的执行时间。最后，把各个基本块的执行时间按照图或者语法树描述的执行路径相加再加上额外的时间来获取整个的WCET。 WCET分析的基本思路： 为了得到精确