嵌入式系统-实时系统.ppt

《嵌入式系统-实时系统.ppt》由会员分享，可在线阅读，更多相关《嵌入式系统-实时系统.ppt（43页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、嵌入式系统实时理论嵌入式系统实时理论Song Guanghua21实时系统概述实时术语实时系统概述实时术语n作业（job）l能够被系统调度和执行的工作单元n任务（task）l共同提供某种系统功能的一组相关作业n活动资源（active resource）l作业执行时占用的资源：比如CPU、网络、磁盘n释放时间（release time）l在这一时刻，作业可以开始执行n时限（deadline）l作业必须在给定的时间点之前完成，这一时间点即是时限n响应时间（response time）l作业从释放到完成的时间长度n相对时限（relative deadline）l作业的最大允许响应时间n绝对时限（ab

2、solute deadline）l作业的释放时间加上相对时限n定时约束（timing constraint）l对作业的定时行为所施加的约束Song Guanghua3实时系统概述定时约束实时系统概述定时约束n对于一个给定的时限，如果计算任务没有完成，有三种情况：n强定时约束l当不能满足定时约束或时限被认为是致命错误时，这个定时约束就是强定时约束n弱定时约束l同样不希望作业的执行延迟l个别弱时限的延迟不会造成严重的后果l随着延迟的作业的增多，系统整体性能会变差价值价值时限时限时限价值Song Guanghua4实时系统概述实时系统定义实时系统概述实时系统定义nPOSIX 1003.b定义l指系统

3、能够在限定的响应时间内提供所需水平的服务n一个实时系统必须满足的条件l计算机必须在一个给定的时间期限之前完成计算任务n硬实时系统l如果计算机没有能够及时的交付计算结果，那么由这个计算机控制的系统就会发生灾难性的后果l具有强定时约束n软实时系统l对计算任务有时限要求，但该时限要求的延迟不会引起严重的后果l一般不需要证明系统确实满足实时性能要求l具有弱定时约束Song Guanghua52实时系统参考模型处理器和资源n处理器l如果两个处理器功能相同并且可以交换使用，那么就可以认为它们是同一类型-例如：对称多处理器系统中的多CPUl通常在关注作业调度、同步和处理器利用率时，不区分处理器类型n资源l被

4、动资源l如内存、序列号、信号量和锁Song Guanghua6实时系统参考模型时间参数n通常假定强实时作业和任务的许多参数总是已知的l例如系统中任务的个数-在许多嵌入式系统中，只要系统处于一种操作模式下，其任务个数就是固定的-当系统的操作模式改变时，任务个数也会改变，在新模式下的任务数也应该是已知的l对于任务个数会改变的系统，系统必须维护所有已有强实时任务的信息，包括个数n作业的参数l时间参数：说明作业的定时约束和行为l互连参数：描述作业如何依赖于其他作业以及其他作业如何依赖于它l功能参数：说明作业的内在属性l资源参数：说明其资源要求Song Guanghua7实时系统参考模型时间参数（2）n

5、释放时间、绝对时限与相对时限都是时间参数l用ri，di，Di表示n作业的可行间隔l作业Ji的释放时间和绝对时限之间的时间间隔（ri，di）n释放时间抖动（release-time jitter）l假设ri在一定范围ri-，ri+内波动-ri-：最早释放时间-ri：最晚释放时间l如果每个作业的实际释放时间可以用其最早或者最晚释放时间近似代替，则说作业有固定的释放时间n释放时间间隔（inter-release time）l作业流中两个连续作业的释放时间的间隔Song Guanghua8实时系统参考模型时间参数（3）n偶发作业（sporadic job）或非周期作业（aperiodic job）l某

6、些作业的释放时间在产生它们的事件发生之前是不知道的l随机时刻释放l随机分布的概论A(x)：作业的释放时间在x或者x之前的概率n到达时间（arrival time）或者到达时间间隔（inter-arrival time）l当一个非周期作业释放时称为到达lA(x)是到达时间分布或者到达时间间隔分布Song Guanghua9实时系统参考模型时间参数（4）n执行时间eil在Ji独自执行并且其所需要的资源都具备的情况下，完成Ji的执行所需要的时间l取决于作业的复杂度和处理器速度，与作业如何调度无关n完成任务需要的实际时间会发生变化lei在范围ei-,ei+-ei-：Ji的最小执行时间-ei+：Ji的最

7、大执行时间l通常假定所有强实时作业的ei-和ei+都是已知的l实际执行时间是未知的Song Guanghua10实时系统参考模型周期性任务模型n周期性任务模型l适用于确定性工作负荷l准确性会随着释放时间抖动的增加以及执行时间的变动而变弱n周期任务（period task）l如每个计算或者数据传输按照规则的或者半规则的时间间隔反复不断的执行，以便为系统提供某个功能，就将之建模为周期任务l周期任务是一系列的作业Tin对于Til周期pi-是Ti中相连的作业的释放时间间隔之中的最小长度l执行时间（execution time）ei-是Ti中所有作业的最大执行时间Song Guanghua11实时系统参

8、考模型周期性任务模型（实时系统参考模型周期性任务模型（2 2）nTi的相位l每个任务Ti的第一个作业Ji,1的释放时间ri,1l定义为i=ri,1l具有相同相位的任务称为同相n超周期（hyper-period）lH表示pi的最小公倍数l每个超周期中作业（最大）个数N为l对于周期为3、4、10的三个周期任务，超周期长度为60，N=41n任务Ti的利用率uil周期为pi，执行时间为ei的完全周期性任务保持处理器忙的时间比率lui=ei/pin总利用率l系统中所有任务的利用率之和Song Guanghua12实时系统参考模型周期性任务模型（实时系统参考模型周期性任务模型（3 3）n在t时刻释放的Ti

9、中的作业必须在t之后的Di个时间内完成l经常假定，对所有的任务，每个作业在每个周期的开始都是释放的、就绪的并且必须在周期结束之前完成nDi可以取任意值，并且可以小于pin非周期任务l任务中的作业要么是弱时限的要么没有时限n对于模型中的非周期任务，作业的执行时间也是随机分布变量l服从概率分布B(x)Song Guanghua13实时系统参考模型优先约束和数据依赖实时系统参考模型优先约束和数据依赖n作业间的数据和控制依赖关系可能限制了作业的执行次序n优先约束（precedence constraints）l如果要按照某种次序限制作业的执行，称作业具有优先约束l如果作业可以按照任意次序执行，称作业是

10、独立的（independent）n优先次序关系（precedence relation）l作业之间的先后约束关系l如果Jk在Ji执行完成之前不能开始执行，则称Ji是Jk的前任（predecessor），Jk是Ji的后继（successor）l用偏序关系表示为JiJkl如果JiJk并且没有其他作业Jj使得JiJjJk，则称Ji是Jk的直接前任（immediate predecessor），Jk是Ji的直接后继（immediate successor）l如果Ji和Jk既没有关系JiJk，也没有关系JkJi，则它们是独立的n就绪（ready）l当一个有前任的作业在其释放时间或者释放时间之后，且其所有

11、的前任都已经完成，该作业才能就绪Song Guanghua14实时系统参考模型优先约束和数据依赖（实时系统参考模型优先约束和数据依赖（2 2）n前趋图（precedence graph）l采用有向图表示的优先约束关系l顶点对应于作业，有向边对应于优先约束关系n任务图（task graph）l扩展了的前趋图l顶点表示作业，用一对数字来表示它们的可行间隔，边表示作业间的依赖关系n数据依赖l如果作业Jk消费Ji所产生的数据或者作业Ji向Jk发消息，则产生数据依赖Song Guanghua15实时系统参考模型其他依赖关系n时间依赖关系l时间距离（temporal distance）-两个作业完成时间的

12、差值-如果要求两个作业之间的时间距离不能超过某个有限值，则称它们有时间距离约束nAND/OR优先约束l如果一个作业必须等待所有直接前任作业的完成，这样的作业称为AND作业，依赖关系为AND优先约束l如果一个作业的一个或者一些直接前任已经完成，那么只要此作业在释放时间或者释放时间之后就可以开始执行，这样的作业称为OR作业Song Guanghua16实时系统参考模型功能参数n抢占（preemption）l当更紧急作业到达时，当前执行的任务被暂停，处理器被交给更紧急的作业，当更紧急的作业完成后，处理器再返还给原先的任务恢复执行l如果一个作业的执行在任何时候都可以被挂起以便让给其他作业执行，随后又可

13、以在挂起点被恢复执行，则该作业是可抢占的（preemptible）l如果一个作业必须从头到尾的执行，中途不能中断，则称该作业是不可抢占的（nonpreemptible）n作业的重要性（importance）l一个用于指明作业相对于其他作业的重要性的整数l作业越关键，重要性越大Song Guanghua17实时系统参考模型任务的资源参数和资源的参数实时系统参考模型任务的资源参数和资源的参数n资源的抢占性l如果限制一个资源的每个单元必须串行使用，则该资源为不可抢占的,否则就是可抢占的n采用资源图表示资源的配置l所有的处理器和资源都有顶点对应l顶点的属性是资源的参数-资源的类型-资源数量l边表示资源

14、之间的关系Song Guanghua18实时系统参考模型调度等级n调度程序（scheduler）l根据所选择的一组调度算法和资源访问控制协议来对作业进行调度和资源分配，实现这些算法的模块称为调度程序n调度的正确性（correctness）l调度程序产生唯一有效的调度n可行调度（feasible）l如果所有的作业能满足其时限要求，称为可行调度n可调度的（schedulable）l如果使用一个调度算法，调度程序总能产生可行调度，则称根据此调度算法的作业集合是可调度的n最优的（optimal）l当给定作业集合有可行调度时，如果一个强实时调度算法，总能产生可行调度，则此调度算法是最优的n作业的延迟l作

15、业的完成时间与时限的差-作业提前完成，延迟就是负值-作业完成晚了，延迟就是正值Song Guanghua193实时调度算法时钟驱动调度n时钟驱动（clock-driven）l是指在系统开始执行之前，选择一些特定的时刻，在这些时刻决定哪一个作业在何时执行n在典型的使用时钟驱动调度方法的系统里，所有强实时作业的参数都是固定的并且是已知的l作业的调度表脱机计算并被保存，在运行时使用l调度程序在每一个调度决策时刻调度作业运行l运行时开销可被最小化n适用于基本具有可确定性的系统l在可确定性的框架下还可以存在少量非周期作业和偶发作业Song Guanghua20实时调度算法基于优先级调度n基于优先级的调度

16、l不事先计算任务的调度表，而是在作业释放以后，给它们分配优先级，并按照优先级次序把作业放入就绪队列n固定优先级算法l为每个任务中的所有作业分配相同的优先级l每个周期任务的优先级相对于其他任务来说是固定不变的n动态优先级算法l给每个任务的单个作业分配不同的优先级l作业释放并完成时，任务的优先级相对于其他任务的优先级可能会发生变化n大多数实用调度算法会给单个任务分配固定的优先级l每当作业释放并准备进入就绪队列时，就给作业分配优先级Song Guanghua21实时调度算法速率单调算法n速率单调算法（Rate Monotonic），RM算法l1973年，著名实时调度算法l固定优先级算法l假定任务是周

17、期性的l假定任务的相对时限等于它的周期n基于任务的周期分配任务优先级l周期越短，优先级越高l任务的速率与其周期成反比l速率越高，优先级越高Song Guanghua22Task SetSong Guanghua23Periodic Task Timing Diagram周期任务调度算法有效性：RM调度算法要求：Song Guanghua24实时调度算法时限单调算法n时限单调算法（Deadline Monotonic），DM算法l固定优先级算法n按照任务的相对时限来分配优先级l相对时限越短，优先级越高n如果每个任务的相对时限与它的周期成正比，则RM算法与DM算法一致n当相对时限是任意的时候，DM

18、算法表现好l此时DM算法有可能产生可行的调度表，RM算法却不行l如果DM算法不能产生可行的调度表，RM算法肯定也不能Song Guanghua25实时调度算法EDF算法n最早时限优先算法，截止期优先调度算法，Earliest Deadline First，EDFl动态优先级算法n按照作业的绝对时限为其分配优先级n对于具有任意释放时间和时限的作业集J，当作业允许抢占，但作业并不竞争资源时，当且仅当J存在可行的调度时，EDF算法才能够在单处理器上产生一个可行的调度nEDF算法是任务级/作业级动态优先级算法l一旦作业按照所分配的优先级被放入就绪队列，它相对于队列中其他作业的次序就是固定的vRMS算法

19、对处理器利用率的下限有限制，在最坏的情况下处理器的利用率要算法对处理器利用率的下限有限制，在最坏的情况下处理器的利用率要小于小于69%，一般情况下也要小于，一般情况下也要小于88%，而且处理非周期任务较难。，而且处理非周期任务较难。v对于对于EDF算法，利用率比算法，利用率比RMS大为提高接近于大为提高接近于1，但负载过载时的可靠性、，但负载过载时的可靠性、可预测性与稳定性较差可预测性与稳定性较差Song Guanghua26实时调度算法反向EDF算法n又称为最迟释放时间算法（Latest Release Time,LRT）l当调度的目标是满足作业的时限时，早于必须的时间完成任一作业没有好处l

20、可能会因为某种原因想推迟强实时作业的执行n将释放时间当作时限，将时限当作释放时间l从后面调度作业，按照“优先级驱动”的方式，从时限最迟的作业开始调度，直到当前时间n这是一个非优先级驱动的算法Song Guanghua27实时调度算法LST算法n最小空闲时间优先算法（Least Slack Time First，LST）l动态优先级算法n按照空闲时间分配优先级l空闲时间为已执行过的时间长度l每次在新作业释放时，调度程序检查所有就绪作业的空闲时间l将新作业和现有作业重新排序l空闲时间越小，优先级越高nLST需要监视所有就绪作业的空闲时间l只要作业间的空闲时间相对发生变化，调度程序就要向作业重新分配

21、优先级Song Guanghua28实时调度算法非周期实时调度算法n非周期作业调度算法和偶发作业调度算法（aperiodic job and sporadic job scheduling algorithms）l根据每个新到达的偶发作业的执行时间和时限，调度程序决定接收还是拒绝这个作业l如果作业被接受，调度程序调度该作业，使得该作业能够及时完成，同时不会使周期性任务和前面已接收的偶发作业错过其时限-关键：如何进行接收测试以及如何调度已接收的偶发作业l调度程序试图尽可能快地完成每一个非周期作业-关键：在不引起周期性任务和已接受的偶发作业错过其时限的前提下n最优的非周期性调度算法l如果一个非周期

22、性作业调度算法能够使位于非周期性作业队列头部的非周期性作业响应时间最小，或者能够使得按照给定排队规则排列的非周期性作业的平均响应时间最小Song Guanghua29实时调度算法非周期实时调度算法（实时调度算法非周期实时调度算法（2 2）n空闲挪用算法（slack stealing algorithm）l利用周期性作业和偶发作业的可用空闲时间l前提是保证周期性作业不会因为非周期性作业错过时限l采用中断方式，也可以使用优先级驱动，但是更为复杂n轮询算法l轮询程序周期性地在轮询周期的整数倍时刻就绪可执行，并且按照给定的优先级驱动算法被调度l当轮询程序执行时，检查非周期作业队列，如果队列非空，就执行

23、位于队列头的作业Song Guanghua30实时调度算法非周期实时调度算法（实时调度算法非周期实时调度算法（3 3）n带宽保留服务器算法（bandwidth preserving algorithm）l改进的轮询算法l非周期性作业队列必须非空l服务器为非周期性作业保留资源l将非周期性任务与周期性任务一起调度Song Guanghua314实时调度算法资源访问控制协议资源访问控制协议n资源访问控制协议（resource access-control protocol）管理以下行为l何时、何条件下准许对每个资源的请求l如何调度那些请求资源的作业n优先级逆转l由作业间的资源竞争产生的优先级逆转l由

24、于资源基于不可抢占策略分配给作业，因而当作业发生冲突时，即使两个作业的执行都是可抢占的，较高优先级的作业也可能被较低优先级的作业阻塞l如果没有良好的资源访问控制，优先级逆转的持续时间可能会无限长Song Guanghua32实时调度算法不可抢占的临界区协议不可抢占的临界区协议n不可抢占的临界区协议（Nonpreemptive Critical Section Protocol,NPCS）l作业一旦拥有某资源，便不可被抢占nNPCS最重要的优点是简单l不需要预先了解任何有关作业资源需求的知识nNPCS的缺点l所有作业都会被其他拥有某些资源的较低优先级的作业所阻塞n最高限度优先级协议（ceilin

25、g priority protocol）l改进的NPCSl当所有作业的资源需求都已知时，令拥有资源的作业以所有请求该资源的作业的最高优先级执行Song Guanghua33实时调度算法基本的优先级继承协议n基本的优先级继承协议调度规则l在处理器上，就绪的作业根据其当前优先级以优先级驱动方式可抢占地进行调度l每个作业J在其释放时间t的优先级等于它的分配优先级n分配规则l当一个作业J在时刻t请求资源R时-如果R空闲，就将R分配给J，直至J释放该资源为止-如果R不空闲，就拒绝这个请求，且阻塞Jn优先级继承规则l当请求资源的作业J被阻塞时，阻塞J的作业Jl将继承J的当前优先级l作业Jl将按其继承优先级

26、执行，直至释放资源RSong Guanghua34Priority InversionnDuration of a priority inversion depends on unpredictable actions of other unrelated tasksSong Guanghua35Priority InheritancenLower-priority task inherits the priority of any higher priority task pending on a resource they shareSong Guanghua36实时调度算法基本的优先级继

27、承协议（实时调度算法基本的优先级继承协议（2 2）n继承阻塞（inheritance block）l由优先级继承产生的阻塞n传递阻塞（transitively block）l由于作业J1阻塞J2，J2又阻塞了J3l优先级继承是可传递的n优先级继承协议无法防止死锁n优先级继承协议无法将作业的阻塞时间减低至最少Song Guanghua375实时应用数字控制n实时系统嵌入于传感器与执行部件l如引擎、刹车闸、飞行器等l上述对象的状态由传感器监视，由执行部件改变对象的状态n采样数据系统l通过周期采样，将模拟传感器读出结果数字化，然后在每个周期执行相应的控制规律计算，再通过计算结果激活执行部件l采样周期

28、选择：通过采样周期的选择，对计算时间与精度进行折中l多频率系统：通过多输入输出控制系统，为对象建立多维的状态Song Guanghua38实时应用高层控制n复杂控制系统控制器组织具有多层次l底层控制器直接控制物理对象，计算简单并几乎是确定的，计算周期从毫秒到秒不等l高层控制器的输出是底层控制器的参考输入，可能非常复杂和多变，计算周期可能是分甚至小时n制导与控制l通过秒级控制器完成制导和路径规划l大量的计算脱机完成，在制导过程中仅有相对简单并确定的时间攸关计算n实时命令与控制l需要实时的人工交互，键盘等人工交互的操作频率可能需要高于10HzSong Guanghua39实时应用信号处理n处理的带

29、宽要求l实时信号处理往往在每个采样周期计算一个或者多个输出n雷达系统l雷达信号处理：通过大范围的波束扫描进行覆盖，信号处理的吞吐量也很高l跟踪：通过对反射信号的处理，判断新目标的位置和速度l门控：通过测量值判断是否是有效的轨迹l数据结合：解决数据赋值模糊的问题l复杂度和定时需要：通过控制器修改信号处理参数，有效抑制干扰，辨别目标Song Guanghua40实时应用实时数据库实时数据库n实时数据库所维护的数据具有容易过时的特点l股票行情报价系统l轨迹记录数据库l实时文件系统n实时数据库l1实时一致性l2实时稳定性l3.实时容错性n设计目标l首先是对事务定时限制的满足n基本原则l宁要部分正确而及

30、时的信息，也不要绝对正确但过时的信息n系统性能指标l满足定时限制的事务的比率l要求必须确保硬实时事务的截止期，必要时宁肯牺牲数据的准确性与一致性n软实时事务满足截止期的比率相对较高，但要100满足截止期很难或几乎不可能Song Guanghua41n实时数据库相关技术的实现l实时数据库中的基本事件-实时性来源于事件的触发，即事件驱动l事件的定义与运算、维护和事件表达式l基于组件的模块化体系l被动式内核结构-将各核心模块尽量独立，即便-特定模块出现故障系统也可以自动重新启动该模-块并且将系统恢复到故障前的状态l高效数据存取技术-(1)快速位号检索-(2)访问同步和数据共-(3)高速数据读写l事务调度模式Song Guanghua42实时应用多媒体应用多媒体应用n多媒体应用l计算密集型的过程l实时需要依赖于要求的视频和音频的质量l保持口型同步的需要：视频帧和相应的音频数据单元的时间同步，即如果视频是一个讲话人，他的口型看上去应该能够合理运动以产生伴音END