实时系统程序最差情况执行时间(WCET)分析概述1姬孟洛1齐治昌1李书浩21(国防科技大学计算机学院长沙410073)2(并行与分布处理国家重点实验室长沙410003)【摘要】事先获知系统中程序最差情况的执行时间(Worst-CaseExecutionTime,WCET)是设计和验证实时系统调度及可调度性分析的前提，也是确定周期性任务是否满足其性能目标从而发现系统性能瓶颈的基础。本文概述了程序WCET的分析方法，描述了WCET分析的定义和组成，重点总结其中的程序流事实分析方法，并指出程序流事实分析存在的问题和WCET分析的研究热点。【关键词】程序流事实分析，最差情况执行时间WCET分析，实时系统，软件工程;AnOverviewofWorstCaseExecutionTime(WCET)AnalysisJIMeng-Luo1QIZhi-Chang1LiShuhao21(DepartmentofComputerScience,NationalUniversityOfDefenseTechnology,Changsha410073)2(ParallelandDistributiveProcessingofNationalLaboratory,Changsha410003)AbstractThepurposeofWorst-CaseExecutionTime(WCET)analysisistoprovidea-prioriinformationabouttheworstpossibleexecutiontimeofaprogramorpieceofaprogrambeforeusingtheminasystem.Whendesigningandverifyingreal-timesystems,WCETestimatescanbeusedtoperformschedulingandschedulabilityanalysis,todeterminewhetherperformancegoalsaremetforperiodictasks,tocheckthatinterruptshavesufficientlyshortreactiontime,tofindperformancebottlenecks,andsoon.InthispaperweoverviewtheanalysismethodsofWCETanalysis,describeitscomponents,andsummarizetheanalysismethodsofprogramflowfactanalysisinWCETanalysis.WepointouttheprobleminprogramflowfactanalysisandtheresearchhotspotinWCETanalysis.KeywordsWorst-CaseExecutionTimeanalysis,Real-TimeSystem,SoftwareEngineering1国家自然科学基金(No.60303013)资助姬孟洛：国防科技大学计算机学院博士生，研究方向：实时系统分析，面向对象设计；齐治昌：教授，研究方向：软件工程，计算机教育。李书浩：硕士，研究方向：软件工程。联系人：姬孟洛，email：jmluo@nudt.edu.cn.通讯地址：长沙国防科技大学计算机学院博士生队1引言实时系统与其它应用系统的不同之处在于其正确性具有更加严格的标准。实时系统的正确性不仅取决于它所产生的输出，同时还取决于输出产生的时间。实时系统的结果只有在规定的时间范围内完成时才是有效的。当没有在规定的时间范围内完成时，轻则降低系统的性能（弱实时系统），重则引起灾难性的后果（强实时系统）。因此，事先获取系统中每个任务最差情况下的执行时间WCET2对实时系统的时序分析具有特别重要的意义。事实上，事先得知系统中任务的WCET既是进行调度及可调度性检测的前提，又是系统设计中软硬件界限划分的一个依据，同时还是确定周期性任务是否满足其性能目标,从而发现系统性能瓶颈的基础。WCET分析值必须安全和精确(tightness)，前者保证不能低估最差执行时间，后者要求提供可接受的高估值。获取程序的WCET是实时系统的一个重要研究领域，也是最近十多年来的一个研究热点[1]。从1986年发表第一篇有关WCET的文献[2]开始，到目前为止，几乎所有比较发达的国家都有研究机构从事这方面的研究，比较著名的有美国Florida州立大学、Princeton大学、奥地利的Vienna技术大学、瑞典的Uppsala大学、英国的York大学以及韩国国立大学等。WCET分析包括动态度量、静态分析和混合方法共三种方法。动态度量方法就是直接运行程序以测量（measure）程序的执行时间，目前使用的有随机方法、基于遗传算法的进化方法（EvolutionMethod）、模拟退火方法和统计方法。动态度量方法很难保证所得到结果是安全的，尤其是对现代高性能处理器。静态分析方法根据程序的流信息，针对运行程序的处理器特性估算出程序的WCET。因为程序的流信息通常是非常复杂的，而处理器尤其是现代处理器（比如高速缓存和超级流水线）的特性也很复杂，所以静态分析和计算也会变得非常复杂。但静态分析方法能够保证得到的结果是安全的，而且能够不运行程序就获得结果，从而成为WCET分析研究的主流[1]。...