©2020-2024 ioDraw All rights reserved,
Privacy Policy
WCET：Worst Case Execution Time——最坏情况执行时间
* 在实时嵌入式系统设计中，为了保证系统运行安全，需要验证系统是否满足时限——任务必须在截止期之前完成，否则实时系统会出错。
* 衡量嵌入式实时性的指标：任务的最坏情况执行时间。
* 在对硬实时系统进行设计时，需要在系统实际运行之前对系统的时间特性进行完整的验证，来确保系统在运行过程中时间特性不会被破坏——时间特性验证。
* 实时系统的时间特性必须在系统级进行验证，即只有系统的每一个部分以及整个系统都满足实时性要求，这个系统才满足。
* 衡量系统实时性的重要的参数是任务的最坏情况执行时间（Worst Case Execution Time）。
* WCET为任务的实时调度，任务的优先级仲裁，资源的冲突仲裁以及任务间通信提供依据，是确保系统安全运行的可信基础。
* WCET分析方法包括：动态测量、静态分析和混合方法三种。
*
动态测量：在目标环境中实际地运行任务，通过测量任务的执行时间，加上各种统计方法来估计程序的WCET。理论上，通过测量的方法来获取程序的WCET，必须向任务输入所有可能的参数，保证程序运行完所有可能的执行路径，而实际程序的输入参数空间往往非常巨大，输入所有参数来运行程序通常是不可行的，即使可行也需要消费很长的时间。——因此，在有限样本的情况下，动态度量很难保证所得的结果的安全性，尤其是对于现代的高性能处理器。
*
静态分析方法根据程序的流信息，针对目标处理器的特性估算出程序的WCET。由于程序流信息非常复杂，且现代处理器（高速缓存和流水线）的特性也很复杂，因此静态分析和计算也变得非常复杂。但是程序静态分析方法由于能够保证所得到的结果是安全的，且能够不运行程序就得到结果，从而成为WCET分析研究的主流技术，但是静态分析方法往往会高估程序的WCET实际值。
当前静态WCET分析方法从3个方面展开研究：控制流分析、底层分析和计算方法。
（1）控制流分析：从程序的源代码或目标代码出发，通过分析程序的逻辑结构、语法、语义等信息来获取程序所有可能的执行路径（执行流）。控制流分析不考虑程序的执行环境的硬件特性，主要集中在程序控制流信息的提取、程序逻辑结构的呃呃表示、控制流信息的表示与转换、循环上界的确定、不可行和隐藏路径发现等。
（2）底层分析：又称执行时间建模，主要考虑缓存、流水线等处理器体系结构对程序执行时间的影响，现代计算机体系结构多采用上述特性来提高处理器性能，而这些特性的引入使处理器执行命令的行为越来越不可预测，这与实时系统的可预测性特征相反。执行时间建模时对目标处理器的各种加速特性进行建模。
（3）计算方法：WCET分析的最后阶段是结合控制流分析和底层分析来进行计算，最终得到WCET的估计值。计算方法可分为：基于树（Tree-Based）方法、基于路径（Path-based）方法和隐藏路径枚举技术IPET方法。
*
混合方法：将静态分析和动态测量相结合，该方法有两种，一种是在测量的基础上得到WCET，此时测量的是程序片段，比如基本块；另一种是在程序静态分析的基础上进行测量，例如首先找到可能导致WCET的程序路径，然后测量该路径的WCET。
<>WCET分析存在的问题
*
高性能微处理器的使用增加了时序分析的难度。高性能处理器采用深层流水线、缓存、乱序执行和分支预测等技术来提高处理器的性能。在过去，执行时间是常量。而现在，随着采用深层流水线、缓存和其他各种预测概念的微处理器，导致各个指令的执行时间差异很大，指令执行时间成为了变量，同意指令的执行时间因为指令的出现位置不同也不同了，增加了时序分析的难度。
*
微系统结构分析：执行时间界限能否确定、确定的界限能否精确，很大程度上依赖计算机系统结构。而计算机系统结构相互依赖，无法对单个组件进行分析，也无法以简单方式来实施执行时间惩罚，而需要进行整体结构分析，带来了更高的复杂性并增加了资源需求。多核处理器存在L2
Cache和总线共享，造成多核访问冲突，同时针对多个线程相互交互，某一线程访问共享变量将导致处理器耗费一定时间维护L1
Cache数据的一致性，这都给多核嵌入式软件WCET分析带来不确定性。
*
多核实时嵌入式系统的任务执行过程必须遵守某种任务分配策略。当系统中有多个处理器可执行同一任务时，该策略决定将任务分配给哪一个处理器。在动态调度算法的模型中，为了描述任务分配这一动态行为，任务与处理器之间的映射关系必须能够动态地建立和调制，而建立动态映射关系模型是很困难的。实际应用中，存在多个任务并行执行，且多个任务之间存在相互通信，因此研究多和嵌入式软件的WCET，必须解决基于多核、多任务的调度问题，即确定各个任务分别在哪个核上运行、何时开始运行。
<>时序分析
从本质上说，WCET分析就是搜索一条穿过程序的最长路径。可以看做是构建加权图并查找其中的最长路径问题。图的节点：基本块（直线代码的最长序列）等程序片段，图的边：控制流，节点权重：程序片段执行时间的上限，边权重：遍历计数的界限。因此提出了一种针对静态时序分析的类标准系统结构。
* 控制流重建读取要分析的二进制可执行文件，重建其控制流，并将其转换为中间程序表示形式
* 值分析以静态方式确定寄存器和内存位置中存储的值。
* 循环界限分析来确定算术指令的执行时间