15.嵌入式系统中的实时调度PPT资料36页

嵌入式系统中的实时调度陈虎tommychen74yahoo参考文献C.M.Krishna,Real-TimeSystems,Mcgraw-Hill,2019什么是实时系统一般而言具有实时性能的控制系统是实时系统。实时表示一个非常短的时间间隔“timegap”（也可以认为表示时间框架“timeframe”或者时间窗口“timewindow”），具有“立即”之含义。当计算机进行实时处理时，要求在接收到数据的同时执行操作并输出计算结果，不能超出计算机系统所能容忍的时限。实时系统的定义IEEE（美国电气电子工程师协会）给出的实时系统定义是“那些正确性不仅取决于计算的逻辑结果，也取决于产生结果所花费的时间的系统”。这就是说，实时系统运算能力具有及时与正确的双重特征。本教程给出的实时系统（Real-TimeSystem）定义是：对外来事件能在限定的响应时间内做出预定质量处理的计算机系统。实时系统的主要特点及时响应外部发生的随机任务请求在规定的时间内完成任务任务执行的时间限制类型和类型间关系•截止时间(finishtime)•任务执行预设时间(budgettime)•一个任务的截止时间通常大于任务执行预设时间实时系统的关键因素计算机系统的实时性能主要由操作系统和运行在操作系统上的应用软件决定，对于无操作系统的计算机则由控制程序决定。具有实时性能的操作系统称为实时操作系统(Real-TimeOperatingSystem,RTOS)实时系统与非实时系统的例子实时系统典型例子•民用飞机的导航系统•汽车的防刹车抱死系统(ABS)非实时系统典型例子•银行数据查询处理系统•视频播放系统•图像扫描•文字识别系统提高实时性能的因素以下几种途径常常用来提高应用系统实时性能•尽量采用硬件处理•优化微处理器的中断机制•采用简单的单线程循环程序•采用基于实时操作系统的复杂多线程操作实时系统的属性和指标实时系统的两个基本属性•可预测性和可靠性实时系统的实时性能主要根据其RTOS的三个主要指标来衡量•响应时间(responsetime)•吞吐量(throughput)•生存时间(survivaltime)响应时间计算机从识别一个外部事件到做出响应的时间RTOS响应时间的具体指标是：•中断延迟时间（InterruptLatency）•任务切换时间（TaskSwitchingLatency）响应时间(续)两个时间指标的计算公式是：•中断延迟时间=TCloseINT+TDoISR+TSaveReg+TStartServiceTCloseINT：关中断的最长时间TDoISR：开始执行中断服务子程序的第一条指令的时间TSaveReg：保存CPU内部寄存器的时间TStartService：内核进入中断服务函数的执行时间•任务切换时间：TtoDoBTaskTime–TtoPauseATaskTimeTtoDoBTaskTime：开始执行B任务的时刻TtoPauseATask：暂停执行A任务的时刻响应时间(续)任务的切换时间就是CPU从停止一个任务的执行切换到另一个任务所需时间VxWorks是实时嵌入式系统，内核为Wind。下表给出了eCos操作系统内核实时响应时间参考数据硬件测试环境中断延迟时间任务切换时间ARM7TDMI（20MHz）22.10ms49.14msStrongARM（221.2MHz）3.25ms1.85msIntelXcale（600MHz）1.87ms0.87ms实时系统的分类根据响应性能分•硬实时系统系统未能在时限内就某一事件做出响应而失败，并且该失败被认为是一种全面的系统失败，则可以认为该系统是一个硬实时（hardreal-time）系统。•软实时系统非硬实时的实时系统可以归类为软实时系统。在一个软实时（softreal-time）系统中，存在时限指标，但是如果输出响应超过时限，一般不会造成严重后果。硬实时系统和软实时系统时限效益效益损失效益损失(a)硬实时时限效益示意图(b)软实时时限效益示意图时间时间事件触发时间事件触发时间时限时限实时系统的分类(续)按照响应时间的快慢分类：•强实时系统：其响应时间在毫秒级或微秒级•普通实时系统：其响应时间一般几秒•弱实时系统：其响应时间一般在数十秒一个例子——汽车自动驾驶V：汽车速度S：汽车发现红灯时的距离minSSDVVSSminSmin：最小刹车距离求从发现红灯信号到开始刹车的最大响应时间D实时系统中的任务模型1212...NNeeeUPPP周期性实时系统•系统中任务数目固定——N•每个任务必须按照一定的周期执行——Pi•每个任务的执行时间固定——ei•处理器器利用率非周期性实时系统周期性实时系统的例子两个任务T1和T2•T1的周期为10ms，执行时间为3ms•T2的周期为6ms，执行时间为1ms任务T1任务T2306121824301020CPU上的执行过程起始时间完成时间(Deadline)任务的执行实时系统调度静态表驱动•在系统开始时就已经确定了所有任务的实行时间静态优先级——可剥夺式•每个任务有固定的优先级•当优先级高的任务需要执行时，可以打断当前正在执行的低优先级任务动态优先级•每个任务的优先级可以动态变化周期性实时任务调度的基本结构执行就绪休眠任务的状态就绪-执行•如果当前有新的任务就绪，则比较正在执行任务和新任务的优先级，选择优先级高的任务执行，低优先级任务回到就绪状态。执行-休眠•当前周期性任务执行结束，根据下一个周期开始时间确定休眠时间，启动定时器休眠-执行•当休眠定时器时间到，将到时的任务加入到就绪任务队列中，并进行优先级选择。单调速率调度(RateMonotonic,RM)静态优先级可剥夺策略每个任务的优先级取决于起任务执行周期周期越短的任务优先级越高RM算法的例子PeTask120.5Task262.0Task3102.0三个任务的参数问题1：谁的优先级最高？问题2：CPU的运行图？012345678T1T2T1T1T1T2T3T3Task1,2,3Task1,2,3Task1,3Task1，2T2Task2,3Task2,3Task3Task3Task2RM算法的基本结论12122(21)eeUPPRM算法是一个最优的静态调度策略•如果有其它静态调度策略可以完成一个任务集合的调度，则RM算法也可以完成如果有两个任务，其执行时间分别为e1,e2,执行周期分别为P1,P2，如果满足则这两个任务是RM算法可以调度的如果有N个任务，其执行时间分别为e1,e2,…,eN执行周期分别为P1,P2,…,PN,如果满足则这N个任务是RM算法可以调度的11212...(21)NNNeeeUNPPP问题PeTask131Task242Task361下述两个任务集合是否是RM可调度的，如果是请完成10ms内的调度过程，如果不是请说明理由处理器利用率小于多少时，RM算法总是可以调度的？PeTask131Task2102Task3102EarlierDeadlineFirst(EDF)调度策略可剥夺的动态优先级调度策略任务的优先级取决于它的Deadline离Deadline越近的任务优先级越高EDF算法的例子到达时间执行时间DeadlineTask101030Task24310Task358253个非周期任务0246810121416T1T2T3Task2Task3Task1T1EDF的基本结论EDF算法是一个优化的单处理器调度算法•如果有一个动态调度算法能完成实时调度，则EDF算法必然可以•如果EDF算法不能完成一个任务集合的实时调度，则不存在其它的动态调度算法来完成实时调度。在周期性实时系统中，如果每个任务的相对Deadline都等于其周期，则只要总的处理器利用率小于1，EDF算法都可以调度。RM和EDF比较考虑以下任务集合，可以使用RM调度吗？可以使用EDF调度吗？如果可以请画出12个时间单位的任务调度图。PeTask131Task242Task361优先级反转在多任务系统中，可能出现高优先级任务等待低优先级任务的情况！T1等待T2优先级继承如果有高优先级任务等待低优先级任务的资源，则低优先级任务可以暂时获得高优先级RM算法特征的证明12122(21)eeUPP如果有两个任务T1,T2，其执行时间分别为e1,e2,执行周期分别为P1,P2，如果满足则这两个任务是可以调度的Case1211PPP212110PePPP22212,max1PePeeP22,max1121112121211()PePeeeUePPPPPPT1T1T1T1T2T2T20P12P1P221211minPePPPUU=0Case2211PPP211211PPePPP22112,max1()PePeeP2,max121122112122112111()eeeePPPUePPPPPPPPPT1T1T1T1T2T2T20P12P1P221211minPePPPUU0P1eU2211PPPP1Umin=0LastResult1222min2121121111()()PPPPUPPPPPPPP21,1,01PIfIfP22min2min2minmin2111210(1)2(21)fIffUIffdUffdffUUTheoremaboutRM1(21)nUnAnysetofnperiodtasksthatfullyutilizestheprocessorunderRMmusthaveaprocessorutilizationofatleast1lim(21)ln20.693nnn