2011-9第九课、嵌入式实时操作系统.ppt

1、,1,嵌入式系统 AnIntroductiontoEmbeddedSystem 第九课 嵌入式实时操作系统 浙江大学计算机学院 陈天洲 2011.4.27 2011夏学期，周三下午1-3节，周四晚上1-3节 玉泉曹光彪西501,2,课程大纲,实时系统简介 嵌入式实时调度 嵌入式实时操作系统,实时系统概念,实时系统定义 能够在指定或者确定的时间内完成系统功能和外部或内部、同步或异步时间做出响应的系统。 POSIX 1003.b定义:指系统能够在限定的响应时间内提供所需水平的服务 实时系统的正确性 不仅仅依赖于计算的逻辑结果 而且依赖于结果产生的时间 两个特点 响应时间限定 可预知 两个能力 在事

2、先先定义的时间范围内识别和处理离散事件的能力 系统能够处理和储存控制系统所需要的大量数据,3,实时系统的分类1,按任务到达分 周期性的系统 周期性任务periodic 任务必须在每个周期内完成一次 可以在周期开始时启动，也可以在周期开始以后启动 必须在周期结束前完成 非周期性系统 非周期性任务(aperiodic) 任务到达没有规则的时间要求 必须有一个启动时间或完成时间,4,多任务,实时任务 周期任务 偶发任务 非周期任务 非实时任务 实时任务要求要满足时限 非实时任务要求要使其响应时间尽可能短,5,实时系统的分类2,按实时性分（时间约束性） 硬实时系统-灾难后果 指应用的时间需求能够得到完

3、全满足，否则就造成重大安全事故，甚至造成重大的生命财产损失和生态破坏 航空航天、军事、核工业等 软实时系统-性能下降 应用虽提出时间需求，但实时任务偶尔违反这种需求对系统运行及环境不会造成严重影响 视频点播（Video-On-Demand，VOD）、监控系统、信息采集系统 调度算法 通用系统中以大吞吐量为目标 实时系统 满足时间的正确性 提供高度动态的，满足在线需求的，适应性的实时调度,6,实时系统的特点：时间约束性time constraint,是最基本的目标 系统应该能够提供对时间正确性进行指定的方法 系统提供一种指定时间尺度的方法 通用系统的延时不能满足 截止时间、时限（deadline

4、 ） 实时系统的任务具有一定的时间约束 时间约束是任何实时系统都固有的约束,7,相关定义,时限(deadline) 一个时间界限。它要求一个任务在该时刻之前完成 任务执行时间 一个任务从启动到完成所花费的时间。 分为平均任务执行时间和最坏任务执行时间 实时系统中一般指最坏任务执行时间，考虑了可能的等待、阻塞等最不利的情况 任务余量(laxity) 时限减去任务执行时间所得的值，反映了系统工作的从容程度 紧时间约束(tight time constraint) 在满足任务时限的同时，留给系统的时间比较紧张。由任务的余量小而引起 松时间约束(loose time constraint) 与紧时限概

5、念相反,指在满足任务时限的同时,留给系统的时间比较宽松,8,时限粒度(deadline granularity) 任务从启动时刻到时限之间的时间 当这个值较小时，称为时限粒度小(或小粒度时限)，反之称为时限粒度大(或大粒度时限) 强实时(hard real-time)任务 强时限任务，要求该任务在时限之前完成,否则其结果将失去可用性 弱实时(soft real-time)任务 弱时限任务，若该任务不能在时限到来之前完成,其结果的可用性将逐渐下降 关键任务(critical tasks) 任务的重要程度，若任务在时限之前不能完成，则会产生灾难性后果 时限的严格性(strictness of de

6、adline) 当一个任务的完成超过时限时,所得到结果的可用性程度,9,实时系统分类3,实时过程控制系统 系统实时地从外界获得被控系统的当前状态，进行预定的处理，根据处理结果对外界被控系统进行及时控制，使其处于要求的状态下 实时过程控制系统的模型是一个反馈环结构 实时信息处理系统 系统仅从外界系统中获得当前状态并进行相应处理 不直接控制外界系统的变化,10,实时系统的特点：可预测性predictability,系统能够对实时任务的执行时间进行判断，确定是否能够满足任务的时限要求 是实时系统的重要性能要求 嵌入式系统的两个可预测性 硬件延迟的可预测性 软件系统的可预测性 应用程序的响应时间是可预

7、测的，即在有限的时间内完成必须的工作 操作系统的可预测性，即实时原语、调度函数等运行开销应是有界的，以保证应用程序执行时间的有界性 资源约束 指多个实时任务共享有限的资源时，必须按照一定的资源访问控制协议进行同步，以避免死锁和高优先级任务被低优先级任务堵塞的时间（即优先级倒置时间）不可预测,11,实时系统的可靠性reliability,可靠性已成为衡量实时系统性能不可缺少的重要指标。 采用静态分析和保留资源的方法及冗余配置，使关键任务的要求总能满足，系统在最坏情况下能正常工作或避免损失 稳定性 嵌入式的要求：强稳定性，弱交互性 容错 大部分针对硬件的容错，也有软件容错 分布式应用 多机共享资源

8、，共同完成一个任务 困难 网络的实时性：保证网络传输时间是有界和可预测的 分布式系统的调度：负载平衡、信息传送、减少开销、任务粒度划分等,12,实时系统的结构,CPU 高运算速度 IO 实时时钟的同步 高速中断处理、高I/O吞吐率、合理的处理器和I/O设备的拓扑连接 高速可靠的和有时间约束的网络通信 可靠性 体系结构支持的出错处理 体系结构的依赖性 体系结构支持的调度、操作系统 实时编程 实时编程就是使用汇编语言、安排中断优先级、写驱动程序等 或采用Ada语言，FORTH语言 分布式的实时数据库,13,实时系统与通用系统的区别,通用系统- “劫富济贫” 方便用户管理计算机资源 追求系统资源最大

9、利用率 实时系统- “劫贫济富” 调度的实时性 响应时间可确定性 高可靠性,14,性能衡量标准,对传统的通用系统 大的系统吞吐量 合理的响应速度 对每个系统用户相对公平的进行计算资源的分配,实时系统 实时的数据吞吐 取代了吞吐量 对硬实时应用的优先响应 取代了恰当的反应速度 系统的计算资源和其他外设资源必须优先满足实时应用的要求 取代了公平,15,衡量指标,系统响应时间(System response time ) 系统发出处理要求到系统给出应答信号的时间 任务切换时间(Context-switching time) 任务之间切换而使用的时间; 中断延迟(Interrupt latency t

10、ime ) 计算机接收到中断信号到操作系统作出响应，并完成换道转入中断服务程序的时间 两个主要评价实时性的指标 最大中断禁止时间+任务切换时间,16,谬误,“实时”等于“快速” X 实时不意味着时间约束是微秒或纳秒，而首先要求的是可预测性 速度越快的系统，实时应用领域越广，实时性越好 强实时任务等于关键任务 X 强实时任务是紧时限任务 X 强实时任务等同于小粒度时限任务 X,17,18,课程大纲,实时系统简介 嵌入式实时调度 嵌入式实时操作系统,实时调度算法分类,周期任务 优先级调度 非优先级调度 非周期任务调度,19,周期任务的调度算法：优先级调度,基于优先级的调度 不事先计算任务的调度表，

11、而是在作业释放以后，给它们分配优先级，并按照优先级次序把作业放入就绪队列 分为两种 固定优先级算法 为每个任务中的所有作业分配相同的优先级 每个周期任务的优先级相对于其他任务来说是固定不变的 动态优先级算法 给每个任务的单个作业分配不同的优先级 作业释放并完成时，任务的优先级相对于其他任务的优先级要发生变化 大多数实用调度算法会给单个任务分配固定的优先级 每当作业释放并准备进入就绪队列时，就给作业分配优先级,20,速度单调算法,速度单调算法（Rate Monotonic，RM算法） 1973年，最著名，算法简单、有效、便于实现 属于固定优先级算法 任务假定 工作由定期任务组织，任务是周期性的

12、任务的相对时限等于它的周期 任务时间定长度 算法思想：使用频率高的优先级高,21,时限单调算法,时限单调算法（Deadline Monotonic），DM算法 属于固定优先级算法 设计思想 按照任务的相对时限来分配优先级 相对时限越短，优先级越高 蜕化 如果每个任务的相对时限与它的周期成正比，则RM算法与DM算法一致 当相对时限是任意的时候，DM算法表现最好 此时DM算法有时有可能产生可行的调度表，RM算法缺不可以 如果DM算法不能产生可行的调度表，RM算法肯定也不能,22,EDF算法,最早时限优先算法，截止期优先调度算法，Earliest Deadline First，EDF 是使用最多的一

13、种动态优先级调度算法 按照作业的绝对时限为其分配优先级 对于具有任意释放时间和时限的作业集J，当作业允许抢占，但作业并不竞争资源时，当且仅当J存在可行的调度时，EDF算法才能够在单处理器上产生一个可行的调度 EDF算法是任务级/作业级动态优先级算法 一旦作业按照所分配的优先级被放入就绪队列，它相对于队列中其他作业的次序就是固定的,23,LST算法,最小空闲时间优先算法（Least Slack Time First，LST）、最短空闲时间优先算法（ Least Laxity First，LLF） 属于动态优先级算法 按照空闲时间分配优先级 空闲时间为已执行过的时间长度 每次在新作业释放时，调度程

14、序检查所有就绪作业的空闲时间 将新作业和现有作业重新排序 空闲时间越小，优先级越高 LST需要监视所有就绪作业的空闲时间 只要作业间空闲时间相对发生变化，调度程序就要向作业重新分配优先级,24,扩展,以上均属于单处理器调度，本课程不介绍多处理器调度 参见并行计算与多核程序设计、多核计算课程内容 分布式实时调度 以RMS为基础的广义RMS调度 以风车调度Sr为基础的DSr调度,25,静态优先级vs动态优先级,RMS算法 处理器利用率低 在最坏的情况下处理器的利用率要小于69% 一般情况下也要小于88% 处理非周期任务较难。 EDF算法 利用率接近于1 负载过载的可靠性、可预测性与稳定性较差,26

15、,周期任务的调度算法：非优先级算法,反向EDF算法，又称为最迟释放时间算法，Latest Release Time, LRT 非优先级驱动的算法 设计思想 当调度的目标是满足作业的时限时，早于必须的时间完成任一作业没有好处 可能会因为某种原因想推迟强实时作业的执行 将释放时间当作时限，将时限当作释放时间 从后面调度作业，按照“优先级驱动”的方式，从时限最迟的作业开始调度，直到当前时间,27,非周期实时调度算法,非周期作业调度算法和偶发作业调度算法（aperiodic job and sporadic job scheduling algorithms） 根据每个新到达的偶发作业的执行时间和时限

16、，调度程序决定接收还是拒绝这个作业 如果作业被接受，调度程序调度该作业，使得该作业能够及时完成，同时不会使周期性任务和前面已接收的偶发作业错过其时限 关键：如何进行接收测试以及如何调度已接收的偶发作业 调度程序试图尽可能快地完成每一个非周期作业 关键：在不引起周期性任务和已接受的偶发作业错过其时限的前提下,28,基于RMS 的非周期任务的调度,思想 将非周期任务转化成周期任务 再利用RMS算法进行调度 两种实现 延迟服务器算法 随机服务器算法 延迟服务器算法 用一个或几个专用的周期任务执行所有非周期任务 有固定优先级 执行时间称为预算 随机服务器算法 类似延迟服务器算法，差别在于 在预算消耗T

17、s时间之后再补充预算,29,其他非周期性调度算法,最优的非周期性调度算法 使位于非周期性作业队列头部的非周期性作业响应时间最小 或使得按给定排队规则排列的非周期性作业的平均响应时间最小 空闲挪用算法（slack stealing algorithm） 利用周期性作业和偶发作业的可用空闲时间，以尽早完成本次非周期性作业 保证周期性作业不会因为非周期性作业错过时限 采用中断方式，也可以使用优先级驱动(更复杂) 轮询算法 轮询程序周期性的在轮询周期的整数倍时刻就绪可执行，并且按照给定的优先级驱动算法被调度 当轮询程序执行时，检查非周期作业队列，如果队列非空，就执行位于队列头的作业 带宽保留服务器算法

18、（bandwidth preserving algorithm） 改进的轮询算法 非周期性作业队列必须非空 服务器为非周期性作业保留资源 将非周期性任务与周期性任务一起调度,30,31,课程大纲,实时系统简介 嵌入式实时调度 嵌入式实时操作系统,嵌入式实时操作系统基本功能,操作系统基本功能 略 嵌入式操作系统可以分为两类 面向控制、通信等领域的实时操作系统,如windriver公司的vxworks、isi的psos、qnx系统软件公司的qnx、ati的nucleus等 面向消费电子产品的非实时操作系统，这类产品包括个人数字助理（pda）、移动电话、机顶盒、电子书、webphone等。 WinC

19、E、VxWorks、C/OS-等运用较广 Linux 作为通用操作系统开发的，linux核心在实时处理能力上先天不足 改造后能在一定程度上成为实时操作系统,32,RTOS,开源,eCos Fiasco (L4 clone) FreeRTOS Phoenix-RTOS Nut/OS Prex RTAI RTEMS RTLinux SHaRK TRON Project Xenomai RT-Thread,不开源,Ardence RTX BeOS ChorusOS DNIX DMERT embOS (Segger) INTEGRITY ITRON LynxOS MERT MicroC/OS-II M

20、QX RTOS 6 Nucleus OS-9 OSE OSEK/VDX OSEKtime PDOS Phar Lap ETS,33,PikeOS Portos pSOS QNX RMX RSX-11 RT-11 RTOS-UH RTXC Salvo RTOS SINTRAN III Symbian OS ThreadX VRTX VxWorks Windows CE nOS UNIX-RTR REX HP-1000/RTE,实时操作系统的设计和实现 首要目标是提供保证实时性的方法 一系列的经典问题的针对实时系统的解决方案 实现操作系统的低开销 保证内核以及其他关键的可重入性 嵌入式实时操作系统

21、RTOS中的相关概念 占先式内核 可重入 优先级反转,34,占先式/剥夺式,实时操作系统可分为可抢占型和不可抢占型两类 占先式内核preemptive 最高优先级的任务一旦就绪，总能得到CPU的控制权。 高优先级的就绪任务可以打断正在执行的较低优先级的任务，进入执行态；被抢占的较低优先级任务进入就绪任务队列，等待下一次调度。 非占先式内核 non-preemptive 内核要求每个任务自我放弃CPU的所有权。 中断可以使一个高优先级的任务由挂起状态变为就绪态，但中断服务以后控制权还是回到原来被中断的那个任务，直到该任务主动放弃CPU的使用权。 更高优先权的任务不能打断正在执行的较低优先权的任务

22、，直到较低优先权任务主动放弃CPU的控制权,35,36,抢占式（preemptive） 当系统响应时间很重要时，要使用抢占式（preemptive）内核 最高优先级的任务一旦就绪，总能得到CPU的控制权。 当优先级高的任务进入了就绪态，当前任务的CPU使用权就被剥夺了，或者说被挂起了，那个高优先级的任务立刻得到了CPU的控制权。 中断服务以后控制权不是回到原来被中断了的那个任务,而是高优先级任务得到CPU使用权,抢占式调度,37,抢占式任务切换过程,38,非抢占式调度,非抢占式（non-preemptive） 非占先式调度法也称作合作型多任务（cooperative multitasking）

23、，各个任务彼此合作共享一个CPU。 中断服务可以使一个高优先级的任务由挂起状态变为就绪状态。但中断服务以后控制权还是回到原来被中断了的那个任务，直到改任务主动放弃CPU的使用权时，那个高优先级的任务才能获得CPU的使用权。,39,非抢占式任务切换过程,抢占式调度vs非抢占式调度,抢占式调度 优点是实时性好、反应快，调度算法相对简单，可优先保证高优先级任务的时间约束 缺点是上下文切换多 非抢占式调度 优点是上下文切换少 缺点是一般情况下，处理器有效资源利用率低，可调度性不好 通用内核 调度策略：优先级调度、时间片轮转调度 调度方式：抢占式、不可抢占式、选择可抢占式 时间片：定长时间片与变长时间片

24、 商业上销售的实时内核都是抢占式内核,40,可重入性,可重入性 reentrancy 可重入型函数可以被一个以上的任务调用，而不必担心数据的破坏。 可重入型函数任何时候可以被中断，一段时间后又可以执行，而相应的数据不会丢失。 可重入型函数只使用局部变量，即变量保存在CPU寄存器中或堆栈中。 在并行运行环境中非常重要 可重入型函数 不可重入型函数 嵌入式软件尽量写成可重入函数,41,优先级反转/优先级倒置,高优先级的任务在申请已经被低优先级任务占据的资源时，高优先级被迫进入等待态，如果有一个中优先级的任务一直在执行，则高优先级将无法执行,42,两个解决方法 优先级继承（priority inhe

25、ritance） 设S为正占用着某项共享资源的进程P以及所有正在等待占用这个资源的进程的集合； 找出这个集合中的优先级最高者，其优先级为P 把进程P的优先级设置成P 优先级封顶（priority ceiling） 设S为所有可能竞争使用某项共享资源的进程的集合。事先为这个集合规定一个优先级上限p，使得这个集合中所有进程的优先级都小于p。注意p并不一定是整个系统中的最好优先级。 在创建保护该项资源的信号量或互斥量时，将p作为一个参数。 每当有进程通过这个信号量或互斥量取得共享资源时，就将此进程的优先级暂时提高到p，一直到释放该项资源的时候才恢复其原有的优先级,43,RTOS基本结构,实时多任务c

26、ore 任务管理 多任务和基于优先级的任务调度 定时器 系统的实时时钟服务，以及各个定时任务的调入等 Mem 管理系统的内存资源，如DRAM,ROM,FLASHRAM等 资源管理 管理系统的各种资源如系统的各种设备，端口，中断等； 事件和消息管理 管理各种系统级的事件，如实时中断响应，各种异常等；任务间同步和通信（信号量和邮箱等）以及各种系统消息和应用程序之间的通讯,44,操作系统实时性 一方面是多大程度上充分发挥硬件潜力，即综合速度快慢的问题； 另一方面同时也是反映的速度在多大的程度上得到保证的问题。,45,中断延迟（Interrupt Latency） 中断不可嵌套 LINUX的Botto

27、m Half 中断可嵌套：优先级中断 大多微处理器不支持； LINUX不支持； UNIX支持 与指令集有关 DMA操作有关 保证系统调用的原子性有关,46,调度延迟（Scheduling Latency） 中断处理程序进程处理 一般调度算法（Round Robin）不能及时选中 基于优先级调度算法，一般能及时选中 如果目标进程优先级低呢？ 可剥夺调度和不可剥夺调度 LINUX是属于什么调度？,47,Linux既不是完全的可剥夺，也不是完全的不可剥夺,上下文切换延迟（Context Switch Latency） 大小取决于CPU和操作系统 采用MMU 不采用MMU,48,只要发生调度，就能选中

28、目标进程吗？ 根据时间片的耗用调整优先级 拉开距离，分等级 对实时进程而言，“应该没有问题”不够 要保证 是否可以不用中断、也不用调度，回到最简单的“监控程序” ? 根据实际任务情况，多任务需要调度，任务越少越简单，越建议用监控程序,49,实时操作系统IO 需要有效的中断处理能力来处理异步事件和高效的I/O能力来处理有严格时间限制的数据收发应用 系统应该有在事先定义的时间范围内识别和处理离散的事件的能力。 系统能够处理和存储控制系统所需要的大量的数据。,50,Kernel分为：微内核与单内核,微内核 (microkernel) 设计思想：内核尽量小 移植方便 有效利用内存 内核不提供操作系统相

29、关服务，而提供实现这些服务的机制 包括：进程管理、存储管理、进程间通信、中断响应框架 内核态：提供服务实现的机制部分 用户态：操作系统的服务、设备驱动、文件系统和用户界面： 一般的嵌入式操作系统都是微内核,单内核(monolithic kernel) 设计思想：内核尽量全 一个很大的进程 模块间直接调用或函数调用 内核提供完整的操作系统服务 内核态：文件系统，进程间通信，进程调度器，内存管理，设备驱动程序 用户态：应用程序 应用程序通过内核提供的“系统调用”使用操作系统提供的服务 Linux和WinCE,51,微内核是嵌入式操作系统的主流,可靠性好 不会因一个组件出现崩溃 实时性好 内核较小，改造为抢占式、可重入方便 安全性 内核小符合最小权限准则 模块多接口多导致安全降低 开发方便 小而且简单，容易理解，容易维护 各模块可以独立开发 系统配置灵活方便 性能差 系统调用需