第二章 实时系统的特征及其任务 计算机学院 潘薇 panwei117@qq.com.

Presentation on theme: "第二章 实时系统的特征及其任务 计算机学院 潘薇 panwei117@qq.com."— Presentation transcript:

1 第二章 实时系统的特征及其任务 计算机学院 潘薇

2 引言 在这一章，主要讨论两个问题： 对于实时系统而言，哪一种性能度量指标是最合 适的？这些指标一定要不同于通用计算机的性能 度量指标吗？ 在给定源代码和目标结构的情况下，工程师们如 何估计程序在最坏情况下的运行时间呢？

3 实时系统的性能度量指标 实时系统通常应用于关键性应用之中，因此在投 入运行之前必须进行仔细的设计和有效性验证。 性能度量指标的选择非常重要，对是否能正确描 述系统的性能起着决定性的作用。

4 实时系统的性能度量指标 出于实用性的考虑，性能度量指标必须简明。即 是说，必须用非常少的几个，最好是一个，性能 度量指标来描述。 选取的指标必须表达系统性能中的那些重要特性， 而忽略掉不重要的。 如：如果我们选用完成任务的平均响应时间作为 指标，意味着我们忽略了响应时间的方差。

5 实时系统的性能度量指标 例2.1:考虑两个系统A 和B，响应时间分布概率 如图。 显然A系统的可预测性更 好，但是响应时间稍微 慢一些。 如果选用平均响应时间 作为性能度量指标，哪 个系统的性能更好？如 果选用响应时间的方差 作为指标呢？

6 实时系统的性能度量指标 例2.2:考察这样的例 子：用户在终端输入 数据，然后看到输入 在显示屏上显示出来。 如果这之间的延迟不 可察觉，比如5微秒和 10微秒，那么对用户 而言系统表现都是可 以接受的。 但是如果延迟越来越显著，用户觉察到的系统性能会越来越差，在某一点后基本下降到0。

7 实时系统的性能度量指标 例2.3:寻呼机中使用的计算机功能相当简单，所 以响应速度不是系统性能的决定性因素。而由于 寻呼机依靠电池供电工作，计算机的电力消耗就 成了一个更为重要的性能指标。 很多情况下，即使存在准确反映用户觉察到的性 能指标，对系统的评价还是由具体的应用决定的。

8 实时系统的性能度量指标 例2.4:考察2个系统C和D。C有一个矩阵处理单 元，在4个时钟周期内可以完成2个256*256的 矩阵乘法运算，除了矩阵运算，其他运算在两个 系统中消耗的时钟周期是一样的，但是D的时钟 频率是C的2倍。 如果选用平均响应时间作为性能指标，如何评价 这两个系统性能的好坏呢？ 哪个系统好取决于具体的应用软件，如果包含大 量矩阵运算显然C好些，反之则D好些。 一个听起来很合理的性能度量指标可能会起到误 导的作用。

9 实时系统的性能度量指标 例2.5:通常人们采用MIPS来作为计算机运算速 度的性能指标。考虑系统E和F，E有一个简单指 令集，平均每条指令需要1.2个时钟周期；F有一 个典型的主机指令集，由很多复杂指令组成，平 均每条指令需要1.8个时钟周期。2个系统的时钟 频率一样。系统E比F要快1.5倍么？ 显然不对。同样的一条程序语句，在E中可能需 要翻译成4条指令，但是在F中可能只需要2条指 令就能完成。对用户而言，他可能觉得F更快。 用户觉察到的性能与很多因素相关，以至于绝大 多数情况下都难以找到一个很完美的度量指标。

10 传统的性能评测 传统的性能评测标准主要有： 可靠性：表示的是在任意给定时间段内系统部发生失效的概率。 可用率：系统运行时间的比率。 吞吐量：单位时间内系统能处理的平均指令数。

11 传统的性能评测 这些传统指标对界定清晰的硬件故障状态非常有效 但对实时系统来说，故障集不仅由硬件状态决定，还受当前处理器之间的任务分配和调度方法的影响。 因此这些指标不适合用于实时系统的评测。

12 可运行性 可运行性是对传统评测标准的改进，它明确的将“实时计算机系统的性能应该与其控制的过程所引起的作为结果的性能密切相关”这一事实考虑在内。 这个控制过程被定义为几个实现的层次，表现为用户看到的几个不同的性能级别。 每个性能层次与某个特定的控制任务的集合的执行相关。

13 可运行性 为了实现每个控制任务，要求实时计算机系统运行一系列的控制算法。 实时计算机的可运行性就定义为计算机系统到达各个实现层次的概率。

14 可运行性 在性能分级视图中，每一层视图由上一层视图的需求驱动，并接收下一层视图的输入。每个下层视图总比上层的更加详细。

15 可运行性 视图0表示就状态变量而言的受控过程，受控过程可以让用户区分不同的性能级别。 视图1表示更详细的受控过程的任务，需要满足一定的时间限制，并完成每个级别的性能要求。 视图2表示满足视图1中的每个控制过程任务的详细的算法描述。 视图3列出满足视图2所需要的硬件结构、操作系统以及应用软件的属性。

16 可运行性 例2.6分析一架民用飞机在飞行中的着陆过程。 这架飞机有一套自动着陆系统，在设备完备的机场即使是零可见度的天气都能安全降落。 如果着陆过程开始时，自动着陆系统出现故障，并且目标机场在低可见度条件下飞机只能改降其他机场。 假设在飞机飞行可达范围内总可以找到可见度合适的机场进行手动降落。假设只要飞机的手动降落装置不出故障，就不使用自动降落的方法。 如果在自动降落的过程中，装置失效的话，飞机将坠毁。

17 可运行性 用户关心的实现层次如下： A0——在指定的机场安全降落 A1——改降其他机场，并安全降落 A2——降落过程坠毁 这可以转化为视图0的二维状态描述(a0,b0)

18 可运行性 分析视图1，操作环境是目标机场的天气情况，需要运行的控制任务是自动降落特性。视图1的状态可以表示为(a1,b1,c1)

19 可运行性 每个状态出现的概率取决于天气、机械构件的状态和计算机系统的状态。视图2关心的是计算机的控制范畴，因此可以表示为单变量

20 可运行性 我们没能描述的只有指定机场的天气状况。设天气变量如下： 那么什么是可运行性呢？就是指向量(p(A0),p(A1),p(A2))，其中p(Ai)表示计算机运行的足够好，确保能够达到实现层次Ai的概率。

21 可运行性 通过视图中的映射关系来推导P(A0) 层次A0只要系统处于视图0处于状态(0,0) 视图1处于状态集{(0,0,0),(0,1,0),(0,2,0),(1,0,0)} 视图2 ，需要(w,a2)Є{(0,0),(0,1),(0,2),(1,0)}并且c1=0 于是P(A0)=P(w=0)P(c1=0)+P(w=1)P(b1=0)P(c1=0)

22 可运行性 视图0的目标是指定的用户 视图1的目标是控制工程师，他应该知道运行什么样的控制任务以及这些任务的deadline 视图2关注的是计算机的能力 视图3关注的是硬件、操作系统、应用软件 视图2和视图3属于计算机设计师研究的领域

23 可运行性 计算机的可运行性不仅取决于计算机系统，还取决于那些不可控的因素。 例如机械故障、天气情况，都将影响计算机系统的可运行性。 这是由于实现层次是在一个对用户有意义的水平上定义的，什么导致了将要到达的实现层次与用户无关。 对用户而言，机械故障造成的飞机坠毁和自动着陆过程中计算机计算失误导致的飞机坠毁同样严重。

24 估计程序运行时间 由于实时系统应当满足deadline，能够精确估计程序的运行时间是非常重要的。 估计任何给定程序的执行时间是一个非常困难的任务，也是当前研究的焦点。它取决于以下积分因素： 源代码：经过仔细调整和优化的源代码执行时所需要的时间将更少。

25 估计程序运行时间 编译器：编译器把源代码转换成机器代码，这种转换并不是唯一的。同样代码不同编译器得到的机器码运行时间并不一致。 机器的体系结构：机器体系结构的很多方面都能影响执行时间，CPU和内存、I/O设备之间的交互、CPU寄存器的数量、缓存的大小等等。 操作系统：操作系统决定任务调度和内存管理的效率，这两者都对执行时间有重要的影响。

26 估计程序运行时间 这些因素能够以非常复杂的方式互相影响。 为了获得较为准确的执行时间的范围，我们需要精确的计算这些互相作用。 这样的计算非常难以进行，因为它需要分析程序执行的方方面面，以及每一个任务与别的任务的互相作用。

27 源代码分析 考虑一段非常简单的代码 L1: a=b*c; L2: b=d+c; L3: d=a-f; 这是一段顺序执行代码，一旦控制权转移到L1，那么就会依次执行L1、L2、L3，然后退出。 那么总的执行时间是 TALL=T(L1)+T(L2)+T(L3)

28 源代码分析 L1: a=b*c; T(L1)将取决于编译器为它所生成的机器码。例如，L1可能被翻译成下面的序列： L1.1: 得到变量c的地址 L1.2: 取得变量c的值 L1.3: 得到变量b的地址 L1.4: 取得变量b的值 L1.5: 相乘 L1.6: 保存到变量a 执行这些指令所需要的时间取决于机器的体系结构。

29 源代码分析 假设机器非常简陋，不使用命令管道，只有一个I/O端口能够访问内存，那么执行时间为 T(L1)=Σ T(L1.i) 事实上，这个等式成立还基于一系列的假设： 假定机器在这段时间里只被用来执行这些指令 假定变量b和变量c不存在与CPU的寄存器里

30 源代码分析 另外，由于不同指令的数据存在依赖，单个指令的执行时间估计并不精确。 在很多的机器中，乘法操作需要的时间是不确定的，取决于相乘的两个数本身，如果事先不知道这些数字是多少，那么我们只能给出一个范围宽松的估计。

31 源代码分析 假定有下面的一个循环： L4: while (P) do L5: Q1; L6: Q2; L7: Q3; L8: end while; 显然，除非我们知道这个循环要执行多少次，否则我们根本没有办法估计运行时间。 因此，我们至少需要知道循环迭代次数的上限和下限。

32 源代码分析 考虑下面的分支语句： L9: if B1 then S1； else if B2 then S2; else if B3 then S3; else S4; end if;

33 源代码分析 代码的执行时间将取决于条件B1、B2、B3中哪一个为真。 当B1为真时，执行时间为 T(B1)+T(S1)+T(JMP) 当B1为假但B2为真时，执行时间为 T(B1)+T(B2)+T(S2)+T(JMP) …… 如果tl(i)和tu(i)是情况i的时间估计的下限和上限，那么总的时间估计的上下限应该是 min(tl(i)) 和 max(tu(i))

34 源代码分析 预处理器生成编译过的汇编语言代码并划分出代码块进行分析。分析器对输入的源程序进行分析。程序计时器维持一张执行时间的表。循环界限模块获得系统中各种循环迭代次数的界限。结构分析器分析结构对时间的影响。代码预测模块估计执行时间，再交由时间表模块来计算最后的结果。

35 流水线操作的说明 传统的冯·诺依曼计算机模型假定是顺序执行的，一条指令被获取、解码，然后执行。只有当这些都完成了以后，才会进行下一条指令。 大多数的现代计算机并不遵循冯·诺依曼模型，引入了流水线操作，这可以同时处理不同指令的不同部分。

36 流水线操作的说明 在处理流水线机器的时候，很多复杂度是由于计算机同时处理的不同指令之间的相互依赖所引起的。 例如，如果指令i需要指令j的输出，那么i和j就不能采用流水线操作并行执行。 复杂度的另外两个来源是条件分支和中断。 如果可能有中断发生，那么最坏情况下的执行时间需要把中断处理时间计算在内。

37 流水线操作的说明 在CPU判断是否执行某个分支之前，条件分支的条件必须被计算估值。在无条件分支已经出现，但是系统尚不知道分支是否被执行时，可能有下面的操作： 停止预取指令，直到条件已经被估值为止； 猜测分支是否会被执行，并且按照这个猜测来取指令。 第一种方案显然降低了性能，因此通常会采用第二种方案，最坏情况也就是猜测错误，重新取指令。

38 两级命令管道 第一级管道从主存储器获取指令并且把它们写到预取指缓冲器；第二级管道处理别的任何事情，包括操作数的读或者写操作以及运算。 两级操作都可能访问内存，但需要等待上一个操作结束才可以进行。

39 两级命令管道 我们假定第二级本身也不是流水线化的，任何时候它都最多只能执行一个指令。 我们假定第二级如果需要访问内存会与第一级管道进行握手，会有一个单时钟周期的时延。 下面我们先定义一些符号： ni——Ii的不包括内存访问的执行时间。 vi——Ii的操作码的字节数。 ri——Ii需要读取的数据内存的个数。 wi——Ii需要写入的数据内存的个数。

40 考虑下面的五指令顺序执行代码段。假定一次内存访问需要4个处理器时钟周期。
两级命令管道 考虑下面的五指令顺序执行代码段。假定一次内存访问需要4个处理器时钟周期。 指令 不包括内存访问的执行时间 指令的操作码字节数 需要读取的内存字节数 需要写入内存的字节数 I1 10 2 I2 4 1 I3 3 I4 I5 5

41 由于v1=2，I1的获取时间是时刻0——时刻8 (4*2=8)，I1的执行时间是时刻8——时刻18。
指令 不包括内存访问的执行时间 指令的操作码字节数 需要读取的内存字节数 需要写入内存的字节数 I1 10 2 I2 4 1 两级命令管道 由于v1=2，I1的获取时间是时刻0——时刻8 (4*2=8)，I1的执行时间是时刻8——时刻18。 由于v2=1， I2的获取时间是时刻8——时刻12，I2的执行时间是时刻18——时刻22。

42 由于v3=3，I3的获取时间是时刻12——时刻24，I3的执行时间是时刻24——时刻34。
指令 不包括内存访问的执行时间 指令的操作码字节数 需要读取的内存字节数 需要写入内存的字节数 I1 10 2 I2 4 1 I3 3 两级命令管道 由于v3=3，I3的获取时间是时刻12——时刻24，I3的执行时间是时刻24——时刻34。

43 指令 不包括内存访问的执行时间 指令的操作码字节数 需要读取的内存字节数 需要写入内存的字节数 I4 2 I5 5 两级命令管道 由于v4=2，I4的获取时间是时刻24——时刻32，由于r4=2，因此I4的第二级需要访问内存取数据，但是这时I5的第一级已经开始取指令了，因此I4的执行时间是时刻34(32+4)——时刻47(32+4+4*2+2+1)。

44 指令 不包括内存访问的执行时间 指令的操作码字节数 需要读取的内存字节数 需要写入内存的字节数 I4 2 I5 5 两级命令管道 时刻36——时刻47，第一级获取单元被禁止访问内存，所以I5的获取时间是时刻32——时刻36，时刻47——时刻51，执行时间是时刻51——时刻56 。

45 高速缓冲存储器 高速缓冲存储器是用来改善处理器和主存储器的时钟周期的广泛不一致性对于程序运行的影响。 然而它也影响我们得到良好的运行时间界限。 一次访问所需要的时间取决于要访问的内容是不是存在于高速缓冲器里，如果是，那么访问时间就是缓冲访问时间，否则就需要访问主存储器，称为cache miss，这个时间将大的多。

46 高速缓冲存储器 预测一次给定的数据访问是否会导致高速缓冲故障相关困难。 因为缓冲器中的内容不容易被预测到，它们是缓冲器大小、组织和替代策略，以及CPU访问顺序的函数。 因此，为了精确判断一个数据是否在缓冲器中，我们需要知道访问缓冲器的顺序。在大多数情况下，精确的预测访问顺序是不可能的。

47 高速缓冲存储器 我们事先无法知道程序将在分支处如何进行，也无法每一个分支都跟踪，因为这是呈指数增长的。 另外，当发生任务抢占的时候，被抢占的任务的数据可能被换出缓冲器。 当然，我们总可以假定每一次缓冲器的访问都发生cache miss，从而得到最差情况的估计，但这是非常不准确的。

48 高速缓冲存储器 用于实时系统的策略性内存分配的高速缓冲器正是用于解决这个问题的。 这样的缓冲器被分成一些独立的部分和一个共享的区域，当一个关键性任务开始执行的时候，它被分配一个或者几个独立的缓冲区，并具有独享的权利，从而保证即使产生抢占，其数据也不会被覆盖而产生cache miss。

49 虚拟内存 虚拟内存是导致执行时间不确定的主要因素。 在任何可能的情况下，尽量避免使用虚拟内存。