非实时系统典型例子
• • • • 银行数据查询处理系统 视频播放系统 图像扫描 文字识别系统
ห้องสมุดไป่ตู้
提高实时性能的因素
以下几种途径常常用来提高应用系统实时 性能
• • • • 尽量采用硬件处理 优化微处理器的中断机制 采用简单的单线程循环程序 采用基于实时操作系统的复杂多线程操作
可见硬件加速和RTOS应用是提高实时系 统的两个主要因素
实时系统的主要特点
及时响应外部发生的随机任务请求 在规定的时间范围内完成任务 任务执行的时间限制类型
• 截止时间 • 任务执行时间
• 截止时间 一个时间界限。它要求一个任务在该时刻之前完成 • 任务执行时间 一个任务从启动到完成所花费的时间。 分为平均任务执行时间和最坏任务执行时间 实时系统中一般指最坏任务执行时间，考虑了可能的等待、阻塞等最不 利的情况 • 任务余量 截止时间减去任务执行时间所得的值，反映了系统工作的从容程度 • 紧时间约束 在满足任务时限的同时，留给系统的时间比较紧张。由任务的余量小而 引起 • 松时间约束 与紧时限概念相反,指在满足任务时限的同时,留给系统的时间比较宽松
实时系统的属性和指标
实时系统的两个基本属性
• 可预测性和可靠性
实时系统的实时性能主要根据其RTOS的三 个主要指标来衡量
• 响应时间(response time) • 吞吐量(throughput) • 生存时间(survival time)
可预测性
系统能够对实时任务的执行时间进行判断，确定是否 能够满足任务的时限要求 嵌入式系统的两个可预测性 硬件延迟的可预测性 软件系统的可预测性 应用程序的响应时间是可预测的，即在有限的时间内完成必须的工作 操作系统的可预测性，即实时原语、调度函数等运行开销应是有界的 以保证应用程序执行时间的有界性 • 资源约束 指多个实时任务共享有限的资源时，必须按照一定的资源访 问控制协议进行同步，以避免死锁和高优先级任务被低优先 级任务堵塞的时间（即优先级反转时间）不可预测
基于优先级的调度
给每个任务分配一个优先级，在每次任务调度 时，调度器总是让CPU执行具有最高优先级的任务 。优先级驱动算法是事件驱动算法，即当任务所需 要的资源就绪后，会立即执行而无需等待。此算法 又称为贪心调度算法，保持工作调度算法或者列表 调度算法。
优先级调度
静态实时调度 系统在编译时就决定从就 绪任务队列选择哪个任务 来执行，即系统中实时任 务特性是事先知道的。 分为速率单调调度RMS和 截止时间单调调度DMS 动态实时调度 指调度器在运行期间才决 定选择哪个就绪任务来运 行。 分为最早截止时间优先 EDF和最小空闲时间优先 LSF
动态实时调度 最早截止时间优先算法EDF
分配给任务的优先级是根据它们当前对截止时限的 要求定的，离截止时限越短的就绪任务优先级越高 基于的模型假设 1. 所有实时任务启动时间为零 2. 任何任务不存在不可抢占的代码段，且抢占代价可 忽略 3. 任务无关，无先后次序的约束 4. 任务的相对最终完成时限与它的周期相等 5. 只有处理器的请求有意义，内存、I/O和其他资源 的请求可忽略
第二十讲 嵌入式实时操作系统
袁嵩
实时系统简介 嵌入式实时调度 嵌入式实时操作系统
一 实时系统简介
一般而言具有实时性能的控制系统是实时 系统。 实时表示一个非常短的时间间隔“time gap” （也可以认为表示时间框架“time frame” 或者时间窗口“time window”），具有“立 即”之含义。 当计算机进行实时处理时，要求在接收到 数据的同时执行操作并输出计算结果，不 能超出计算机系统所能容忍的时限。
周期性实时系统的例子
两个任务T1和T2
• T1的周期为10ms，执行时间为3ms • T2的周期为6ms，执行时间为1ms
起始时 间 任务T1 任务T2 CPU上的 执行过程 6 12 18 24 30 任务的 执行 10 完成时间 (Deadline) 20 30
二
嵌入式实时调度
实时调度算法分类 周期任务调度 优先级调度 非优先级调度 非周期任务调度
如果有N个任务，其执行时间分别为e1,e2,…,eN 执行周期分别为P1, P2,…,如果满足 1 eN e1 e 2 U = + + ... + ≤ N (2 N − 1) P1 P2 PN
则这N个任务是RMS算法可以调度的
截止时间单调调度DMS
按照任务的相对截止时间分配优先级，相对截止时 间短的优先级高。 它具有和RMS相同的优点，但 放松了对任务周期必 须等于其相对截止时间的限制。 如果每个任务的相对时限与它的周期成正比，则 RMS算法与DMS算法一致 当相对时限是任意的时候，DMS算法表现要好些， 此时DMS算法有时有可能产生可行的调度表，RMS 算法却不可以；如果DMS算法不能产生可行的调度 表，RMS算法肯定也不能.
• 中断延迟时间（Interrupt Latency） • 任务切换时间（Task Switching Latency）
响应时间
两个时间指标的计算公式是：
• 中断延迟时间 = TCloseINT + TDoISR + TSaveReg + TStartService TCloseINT ：关中断的最长时间 TDoISR ：开始执行中断服务子程序的第一条指令的时间 TSaveReg ： 保存CPU内部寄存器的时间 TStartService ：内核进入中断服务函数的执行时间 计算机接收到中断信号到操作系统作出响应，并完 成换道转入中断服务程序的时间 • 任务切换时间： T to Do B Task Time – T to Pause A Task Time T to Do B Task Time ： 开始执行B任务的时刻 T to Pause A Task ：暂停执行A任务的时刻 也就是CPU从停止一个任务执行切换到执行另一个任务所需要的时 间
• 如果有一个动态调度算法能完成实时调度，则 EDF算法必然可以 • 如果EDF算法不能完成一个任务集合的实时调度， 则不存在其它的动态调度算法来完成实时调度。
实时系统的定义
IEEE（美国电气电子工程师协会）给出的 实时系统定义是“那些正确性不仅取决于 计算的逻辑结果，也取决于产生结果所花 费的时间的系统”。这就是说，实时系统 运算能力具有及时与正确的双重特征。 本教程给出的实时系统（Real-Time System）定义是：对外来事件能在限定的 响应时间内做出预定质量处理的计算机系 统。
实时系统的关键因素
计算机系统的实时性能主要由操作系统和 运行在操作系统上的应用软件决定，对于 无操作系统的计算机则由控制程序决定。 具有实时性能的操作系统称为实时操作系 统(Real-Time Operating System, RTOS)
实时系统与非实时系统的例子
实时系统典型例子
• 民用飞机的导航系统 • 汽车的防刹车抱死系统
周期性实时任务调度的基本结 构
就绪<->执行
就绪
执行
• 如果当前有新的任务就绪，则 比较正在执行任务和新任务的 优先级，选择优先级高的任务 执行，低优先级任务回到就绪 状态。
执行->休眠
• 当前周期性任务执行结束，根 据下一个周期开始时间确定休 眠时间，启动定时器
休眠 任务的状态
休眠->执行
• 当休眠定时器时间到，将到时 的任务加入到就绪任务队列中， 并进行优先级选择。
可靠性
可靠性已成为衡量实时系统性能不可缺少的重要指 标。 采用静态分析和保留资源的方法及冗余配置，使关 键任务的要求总能满足，系统在最坏情况下能正常 工作或避免损失 一个系统的可靠性是由其组成元素共同决定的，这 些元素包括硬件、板级开发包、RTOS和应用等。
实时系统与通用系统区别
通用系统 方便用户管理计算机资 源 追求系统资源最大利用 率 实时系统 调度的实时性 响应时间可确定性 高可靠性
静态实时调度 速率单调调度(RMS)
基于嵌入式系统作了如下假设
1. 2. 3. 4. 5. 所有任务请求必须是周期性的，必须在限定时间内完成 任务之间相互独立 任务的运行时间不变即不考虑中断情况 所有非周期性任务都在特殊情况下运行 采用单处理器，任务切换时间忽略不计
速率越高，周期越短，任务的优先级越高
EDF算法的例子
3个非周期任务 到达时间 Task1 Task2 Task3 Task1 0 4 5 Task3 执行时间 10 3 8 Deadline 30 10 25
Task2
T1 0 2 4
T2 6 8 10
T3 12 14 16
T1
EDF的基本结论
EDF算法是一个优化的单处理器调度算法
RMS算法的可调度性分析
RMS算法是一个最优的静态调度策略
• 如果有其它静态调度策略可以完成一个任务集合的调度，则RMS算法也可 以完成
如果有两个任务，其执行时间分别为e1,e2 执行周期分别为P1, P2, 如果 满足
则这两个任务可被RMS算法调度
e1 e2 U = + ≤ 2( 2 − 1) P P2 1
下表给出了eCos嵌入式可配置操作系统内核实时响应 时间参考数据
硬件测试环境 ARM7TDMI（20MHz） StrongARM（221.2MHz） Intel Xcale（600MHz）
中断延迟时间 22.10 ms 3.25 ms 1.87 ms
任务切换时间 49.14 ms 1.85 ms 0.87 ms
实时系统的体系结构
实时系统的体系结构必须满足： 高运算速度 高速的中断处理 高的I/O吞吐率 合理的处理器和I/O设备的拓扑连接 高速可靠的和有时间约束的通信 体系结构支持的出错处理， 体系结构支持的调度 体系结构支持的操作系统， 体系结构支持的实时语言特性。
实时的调度理论。由于实时系统应用的特殊性，以 往通用系统中以大吞吐量为目标的调度算法必须改 进以适应实时应用的需要。主要要求是满足时间的 正确性，然后提供高度动态的，满足在线需求的， 强适应性的实时调度。 实时操作系统的设计和实现。在设计上首要目标是 提供保证实时性的方法，包括一系列的经典问题的 针对实时系统的解决方案。实现上要求操作系统的 低开销，而且必须保证内核以及其他关键部件的可 重入性。