嵌入式系统中的实时调度课件.ppt
嵌入式系统中的实时调度,陈虎tommychen74yahoo,参考文献,C. M. Krishna, Real-Time Systems, Mcgraw-Hill, 2019,什么是实时系统,一般而言具有实时性能的控制系统是实时系统。实时表示一个非常短的时间间隔“time gap”（也可以认为表示时间框架“time frame”或者时间窗口“time window”），具有“立即”之含义。当计算机进行实时处理时，要求在接收到数据的同时执行操作并输出计算结果，不能超出计算机系统所能容忍的时限。,实时系统的定义,IEEE（美国电气电子工程师协会）给出的实时系统定义是“那些正确性不仅取决于计算的逻辑结果，也取决于产生结果所花费的时间的系统”。这就是说，实时系统运算能力具有及时与正确的双重特征。本教程给出的实时系统（Real-Time System）定义是：对外来事件能在限定的响应时间内做出预定质量处理的计算机系统。,实时系统的主要特点,及时响应外部发生的随机任务请求在规定的时间内完成任务任务执行的时间限制类型和类型间关系截止时间(finish time)任务执行预设时间(budget time)一个任务的截止时间通常大于任务执行预设时间,实时系统的关键因素,计算机系统的实时性能主要由操作系统和运行在操作系统上的应用软件决定，对于无操作系统的计算机则由控制程序决定。具有实时性能的操作系统称为实时操作系统(Real-Time Operating System, RTOS),实时系统与非实时系统的例子,实时系统典型例子民用飞机的导航系统汽车的防刹车抱死系统(ABS)非实时系统典型例子银行数据查询处理系统视频播放系统图像扫描文字识别系统,提高实时性能的因素,以下几种途径常常用来提高应用系统实时性能尽量采用硬件处理优化微处理器的中断机制采用简单的单线程循环程序采用基于实时操作系统的复杂多线程操作,实时系统的属性和指标,实时系统的两个基本属性可预测性和可靠性实时系统的实时性能主要根据其RTOS的三个主要指标来衡量 响应时间(response time)吞吐量(throughput)生存时间(survival time),响应时间,计算机从识别一个外部事件到做出响应的时间 RTOS响应时间的具体指标是：中断延迟时间（Interrupt Latency）任务切换时间（Task Switching Latency）,响应时间(续),两个时间指标的计算公式是：中断延迟时间 = TCloseINT + TDoISR + TSaveReg + TStartServiceTCloseINT ：关中断的最长时间TDoISR ：开始执行中断服务子程序的第一条指令的时间TSaveReg ： 保存CPU内部寄存器的时间TStartService ：内核进入中断服务函数的执行时间任务切换时间： T to Do B Task Time T to Pause A Task TimeT to Do B Task Time ： 开始执行B任务的时刻T to Pause A Task ：暂停执行A任务的时刻,响应时间(续),任务的切换时间就是CPU从停止一个任务的执行切换到另一个任务所需时间VxWorks是实时嵌入式系统，内核为Wind。下表给出了eCos操作系统内核实时响应时间参考数据,实时系统的分类,根据响应性能分硬实时系统系统未能在时限内就某一事件做出响应而失败，并且该失败被认为是一种全面的系统失败，则可以认为该系统是一个硬实时（hard real-time）系统。 软实时系统非硬实时的实时系统可以归类为软实时系统。在一个软实时（soft real-time）系统中，存在时限指标，但是如果输出响应超过时限，一般不会造成严重后果。,硬实时系统和软实时系统时限效益,实时系统的分类(续),按照响应时间的快慢分类：强实时系统：其响应时间在毫秒级或微秒级普通实时系统：其响应时间一般几秒弱实时系统：其响应时间一般在数十秒,一个例子汽车自动驾驶,V：汽车速度S：汽车发现红灯时的距离,V,S,Smin,Smin：最小刹车距离求从发现红灯信号到开始刹车的最大响应时间D,实时系统中的任务模型,周期性实时系统系统中任务数目固定N每个任务必须按照一定的周期执行Pi每个任务的执行时间固定ei处理器器利用率非周期性实时系统,周期性实时系统的例子,两个任务T1和T2T1的周期为10ms，执行时间为3msT2的周期为6ms，执行时间为1ms,任务T1,任务T2,30,6,12,18,24,30,10,20,CPU上的执行过程,起始时间,完成时间(Deadline),任务的执行,实时系统调度,静态表驱动在系统开始时就已经确定了所有任务的实行时间静态优先级可剥夺式每个任务有固定的优先级当优先级高的任务需要执行时，可以打断当前正在执行的低优先级任务动态优先级每个任务的优先级可以动态变化,周期性实时任务调度的基本结构,就绪执行如果当前有新的任务就绪，则比较正在执行任务和新任务的优先级，选择优先级高的任务执行，低优先级任务回到就绪状态。执行-休眠当前周期性任务执行结束，根据下一个周期开始时间确定休眠时间，启动定时器休眠-执行当休眠定时器时间到，将到时的任务加入到就绪任务队列中，并进行优先级选择。,单调速率调度(Rate Monotonic, RM),静态优先级可剥夺策略每个任务的优先级取决于起任务执行周期周期越短的任务优先级越高,RM算法的例子,三个任务的参数,问题1：谁的优先级最高？问题2：CPU的运行图？,0 1 2 3 4 5 6 7 8,T1,T2,T1,T1,T1,T2,T3,T3,T2,RM算法的基本结论,RM算法是一个最优的静态调度策略如果有其它静态调度策略可以完成一个任务集合的调度，则RM算法也可以完成如果有两个任务，其执行时间分别为e1, e2, 执行周期分别为P1, P2，如果满足 则这两个任务是RM算法可以调度的如果有N个任务，其执行时间分别为e1, e2,eN 执行周期分别为P1, P2,PN,如果满足 则这N个任务是RM算法可以调度的,问题,下述两个任务集合是否是RM可调度的，如果是请完成10ms内的调度过程，如果不是请说明理由处理器利用率小于多少时，RM算法总是可以调度的？,Earlier Deadline First (EDF) 调度策略,可剥夺的动态优先级调度策略任务的优先级取决于它的Deadline离Deadline越近的任务优先级越高,EDF算法的例子,3个非周期任务,0 2 4 6 8 10 12 14 16,T1,T2,T3,T1,EDF的基本结论,EDF算法是一个优化的单处理器调度算法如果有一个动态调度算法能完成实时调度，则EDF算法必然可以如果EDF算法不能完成一个任务集合的实时调度，则不存在其它的动态调度算法来完成实时调度。在周期性实时系统中，如果每个任务的相对Deadline都等于其周期，则只要总的处理器利用率小于1，EDF算法都可以调度。,RM和EDF比较,考虑以下任务集合，可以使用RM调度吗？可以使用EDF调度吗？如果可以请画出12个时间单位的任务调度图。,优先级反转,在多任务系统中，可能出现高优先级任务等待低优先级任务的情况！,T1等待T2,优先级继承,如果有高优先级任务等待低优先级任务的资源，则低优先级任务可以暂时获得高优先级,RM算法特征的证明,如果有两个任务T1, T2，其执行时间分别为e1, e2, 执行周期分别为P1, P2，如果满足 则这两个任务是可以调度的,Case 1,T1,T1,T1,T1,T2,T2,T2,0 P1 2P1 P2,=0,Case 2,T1,T1,T1,T1,T2,T2,T2,0 P1 2P1 P2,0 P1,e,U,1,Umin,=0,Last Result,Theorem about RM,Any set of n period tasks that fully utilizes the processor under RM must have a processor utilization of at least,
