论文部分内容阅读
构造一个实时系统的时候,安全性和程序最坏情况执行时间(WCET)是必需的,为了给出WCET估计值,必须同时考虑到系统的软件特性和硬件特性。传统的方法是通过在目标平台上实际执行程序来得到估计值的,但是这种方法既容:易出错,也不能保证估计结果的正确性。另一种方法是静态估计程序的WCET值,该方法必须考虑到所有可能的程序流和硬件特性的作用。在静态估计方法中有三种常用WCET分析方法,它们分别是隐藏路径列举技术(IPET)、基于路径(Path-based)的计算方法和基于树(Tree-based)的计算方法。 本文主要提出两种基于路径的计算实时程序最坏情况执行时间的方法,这两种方法首先检测程序中存在的分支约束,然后将程序中存在的分支约束信息转化为程序流程控制图(CFG图)中结点之间的语义冲突,并按照结点对的形式保存在相应的冲突数组里,在接下来的WCET计算阶段通过边搜索程序执行路径边检测冲突数组里保存的已有的冲突关系以便在搜索路径的同时排除非可行执行路径,提高搜索的效率,最终在可行执行路径集中选择具有最大执行时间的执行路径。与以往的方法相比,本文的方法既避免了穷举所有执行路径(其中包括可行执行路径和非可行执行路径)带来的复杂度,也不需要在排除非可行执行路径之后重新回到流程控制图(CFG图)源结点重新搜索执行路径,而是在检测冲突的同时适当地调整流程控制图(CFG图)并更新当前路径即可。 本文在给出这两种方法详细说明的同时也给出了它们对于标准实验程序的实验结果,并与其他方法做一个比较,实验证明对于语句间语义依赖关系比较强的程序能够快速且有效地给出评估结果。