嵌入式系统中的实时调度课件

嵌入式系统中的实时调度陈虎tommychen74yahoo嵌入式系统中的实时调度陈虎1参考文献C.M.Krishna,Real-TimeSystems,Mcgraw-Hill,2019参考文献C.M.Krishna,Real-TimeS2什么是实时系统 一般而言具有实时性能的控制系统是实时系统。实时表示一个非常短的时间间隔“timegap”（也可以认为表示时间框架“timeframe”或者时间窗口“timewindow”），具有“立即”之含义。当计算机进行实时处理时，要求在接收到数据的同时执行操作并输出计算结果，不能超出计算机系统所能容忍的时限。什么是实时系统 一般而言具有实时性能的控制系统是实时系统。3实时系统的定义IEEE（美国电气电子工程师协会）给出的实时系统定义是“那些正确性不仅取决于计算的逻辑结果，也取决于产生结果所花费的时间的系统”。这就是说，实时系统运算能力具有及时与正确的双重特征。本教程给出的实时系统（Real-TimeSystem）定义是：对外来事件能在限定的响应时间内做出预定质量处理的计算机系统。实时系统的定义IEEE（美国电气电子工程师协会）给出的实时系4实时系统的主要特点及时响应外部发生的随机任务请求在规定的时间内完成任务任务执行的时间限制类型和类型间关系截止时间(finishtime) 任务执行预设时间(budgettime)一个任务的截止时间通常大于任务执行预设时间实时系统的主要特点及时响应外部发生的随机任务请求5实时系统的关键因素计算机系统的实时性能主要由操作系统和运行在操作系统上的应用软件决定，对于无操作系统的计算机则由控制程序决定。具有实时性能的操作系统称为实时操作系统(Real-TimeOperatingSystem,RTOS)实时系统的关键因素计算机系统的实时性能主要由操作系统和运行在6实时系统与非实时系统的例子实时系统典型例子民用飞机的导航系统汽车的防刹车抱死系统(ABS)非实时系统典型例子银行数据查询处理系统视频播放系统图像扫描文字识别系统实时系统与非实时系统的例子实时系统典型例子7提高实时性能的因素以下几种途径常常用来提高应用系统实时性能尽量采用硬件处理优化微处理器的中断机制采用简单的单线程循环程序采用基于实时操作系统的复杂多线程操作提高实时性能的因素以下几种途径常常用来提高应用系统实时性能8实时系统的属性和指标实时系统的两个基本属性可预测性和可靠性实时系统的实时性能主要根据其RTOS的三个主要指标来衡量响应时间(responsetime)吞吐量(throughput)生存时间(survivaltime)实时系统的属性和指标实时系统的两个基本属性9响应时间计算机从识别一个外部事件到做出响应的时间RTOS响应时间的具体指标是：中断延迟时间（InterruptLatency）任务切换时间（TaskSwitchingLatency）响应时间计算机从识别一个外部事件到做出响应的时间10响应时间(续)两个时间指标的计算公式是：中断延迟时间=TCloseINT+TDoISR+TSaveReg+TStartService TCloseINT

：关中断的最长时间

TDoISR：开始执行中断服务子程序的第一条指令的时间

TSaveReg：保存CPU内部寄存器的时间

TStartService：内核进入中断服务函数的执行时间任务切换时间：TtoDoBTaskTime–TtoPauseATaskTime TtoDoBTaskTime：开始执行B任务的时刻

TtoPauseATask

：暂停执行A任务的时刻响应时间(续)两个时间指标的计算公式是：11响应时间(续)任务的切换时间就是CPU从停止一个任务的执行切换到另一个任务所需时间VxWorks是实时嵌入式系统，内核为Wind。下表给出了eCos操作系统内核实时响应时间参考数据硬件测试环境中断延迟时间任务切换时间ARM7TDMI（20MHz）22.10ms49.14msStrongARM（221.2MHz）3.25ms1.85msIntelXcale（600MHz）1.87ms0.87ms响应时间(续)任务的切换时间就是CPU从停止一个任务的执行切12实时系统的分类根据响应性能分硬实时系统 系统未能在时限内就某一事件做出响应而失败，并且该失败被认为是一种全面的系统失败，则可以认为该系统是一个硬实时（hardreal-time）系统。软实时系统 非硬实时的实时系统可以归类为软实时系统。在一个软实时（softreal-time）系统中，存在时限指标，但是如果输出响应超过时限，一般不会造成严重后果。实时系统的分类根据响应性能分13硬实时系统和软实时系统时限效益硬实时系统和软实时系统时限效益14实时系统的分类(续)按照响应时间的快慢分类：强实时系统：其响应时间在毫秒级或微秒级普通实时系统：其响应时间一般几秒弱实时系统：其响应时间一般在数十秒实时系统的分类(续)按照响应时间的快慢分类：15一个例子——汽车自动驾驶V：汽车速度S：汽车发现红灯时的距离VSSminSmin：最小刹车距离求从发现红灯信号到开始刹车的最大响应时间D一个例子——汽车自动驾驶V：汽车速度VSSminSmin：最16实时系统中的任务模型周期性实时系统系统中任务数目固定——N每个任务必须按照一定的周期执行——Pi每个任务的执行时间固定——ei处理器器利用率非周期性实时系统实时系统中的任务模型周期性实时系统17周期性实时系统的例子两个任务T1和T2T1的周期为10ms，执行时间为3msT2的周期为6ms，执行时间为1ms任务T1任务T2306121824301020CPU上的执行过程起始时间完成时间(Deadline)任务的执行周期性实时系统的例子两个任务T1和T2任务T1任务T230618实时系统调度静态表驱动在系统开始时就已经确定了所有任务的实行时间静态优先级——可剥夺式每个任务有固定的优先级当优先级高的任务需要执行时，可以打断当前正在执行的低优先级任务动态优先级每个任务的优先级可以动态变化实时系统调度静态表驱动19周期性实时任务调度的基本结构就绪<->执行如果当前有新的任务就绪，则比较正在执行任务和新任务的优先级，选择优先级高的任务执行，低优先级任务回到就绪状态。执行->休眠当前周期性任务执行结束，根据下一个周期开始时间确定休眠时间，启动定时器休眠->执行当休眠定时器时间到，将到时的任务加入到就绪任务队列中，并进行优先级选择。周期性实时任务调度的基本结构就绪<->执行20单调速率调度(RateMonotonic,RM)静态优先级可剥夺策略每个任务的优先级取决于起任务执行周期周期越短的任务优先级越高单调速率调度(RateMonotonic,RM)静态优先21RM算法的例子PeTask120.5Task262.0Task3102.0三个任务的参数问题1：谁的优先级最高？问题2：CPU的运行图？012345678T1T2T1T1T1T2T3T3Task1,2,3Task1,2,3Task1,3Task1，2T2Task2,3Task2,3Task3Task3Task2RM算法的例子PeTask120.5Task262.0Tas22RM算法的基本结论RM算法是一个最优的静态调度策略如果有其它静态调度策略可以完成一个任务集合的调度，则RM算法也可以完成如果有两个任务，其执行时间分别为e1,e2,执行周期分别为P1,P2，如果满足则这两个任务是RM算法可以调度的如果有N个任务，其执行时间分别为e1,e2,…,eN

执行周期分别为P1,P2,…,PN,如果满足则这N个任务是RM算法可以调度的RM算法的基本结论RM算法是一个最优的静态调度策略23问题PeTask131Task242Task361下述两个任务集合是否是RM可调度的，如果是请完成10ms内的调度过程，如果不是请说明理由处理器利用率小于多少时，RM算法总是可以调度的？PeTask131Task2102Task3102问题PeTask131Task242Task361下述两个任24EarlierDeadlineFirst(EDF)调度策略可剥夺的动态优先级调度策略任务的优先级取决于它的Deadline离Deadline越近的任务优先级越高EarlierDeadlineFirst(EDF)调25EDF算法的例子到达时间执行时间DeadlineTask101030Task24310Task358253个非周期任务0246810121416T1T2T3Task2Task3Task1T1EDF算法的例子到达时间执行时间DeadlineTask1026EDF的基本结论EDF算法是一个优化的单处理器调度算法如果有一个动态调度算法能完成实时调度，则EDF算法必然可以如果EDF算法不能完成一个任务集合的实时调度，则不存在其它的动态调度算法来完成实时调度。在周期性实时系统中，如果每个任务的相对Deadline都等于其周期，则只要总的处理器利用率小于1，EDF算法都可以调度。EDF的基本结论EDF算法是一个优化的单处理器调度算法27RM和EDF比较考虑以下任务集合，可以使用RM调度吗？可以使用EDF调度吗？如果可以请画出12个时间单位的任务调度图。PeTask131Task242Task361RM和EDF比较考虑以下任务集合，可以使用RM调度吗？可以使28优先级反转在多任务系统中，可能出现高优先级任务等待低优先级任务的情况！T1等待T2优先级反转在多任务系统中，可能出现高优先级任务等待低优先级任29优先级继承如果有高优先级任务等待低优先级任务的资源，则低优先级任务可以暂时获得高优先级优先级继承如果有高优先级任务等待低优先级任务的资源，则低优先30RM算法特征的证明如果有两个任务T1,T2，其执行时间分别为e1,e2,执行周期分别为P1,P2，如果满足则这两个任务是可以调度的RM算法特征的证明如果有两个任务T1,T2，其执行时间分别31Case1T1T1T1T1T2T2T20P12P1P2<=0Case1T1T1T1T1T2T2T2032Case2T1T1T1T1T2T2T20P12P1P20