嵌入式系统-实时系统

嵌入式系统－实时理论SongGuanghua21实时系统概述－实时术语作业（job）能够被系统调度和执行的工作单元任务（task）共同提供某种系统功能的一组相关作业活动资源（activeresource）作业执行时占用的资源：比如CPU、网络、磁盘释放时间（releasetime）在这一时刻，作业可以开始执行时限（deadline）作业必须在给定的时间点之前完成，这一时间点即是时限响应时间（responsetime）作业从释放到完成的时间长度相对时限（relativedeadline）作业的最大允许响应时间绝对时限（absolutedeadline）作业的释放时间加上相对时限定时约束（timingconstraint）对作业的定时行为所施加的约束SongGuanghua3实时系统概述－定时约束对于一个给定的时限，如果计算任务没有完成，有三种情况：强定时约束当不能满足定时约束或时限被认为是致命错误时，这个定时约束就是强定时约束弱定时约束同样不希望作业的执行延迟个别弱时限的延迟不会造成严重的后果随着延迟的作业的增多，系统整体性能会变差价值价值时限时限时限价值SongGuanghua4实时系统概述－实时系统定义POSIX1003.b定义指系统能够在限定的响应时间内提供所需水平的服务一个实时系统必须满足的条件计算机必须在一个给定的时间期限之前完成计算任务硬实时系统如果计算机没有能够及时的交付计算结果，那么由这个计算机控制的系统就会发生灾难性的后果具有强定时约束软实时系统对计算任务有时限要求，但该时限要求的延迟不会引起严重的后果一般不需要证明系统确实满足实时性能要求具有弱定时约束SongGuanghua52实时系统参考模型－处理器和资源处理器如果两个处理器功能相同并且可以交换使用，那么就可以认为它们是同一类型例如：对称多处理器系统中的多CPU通常在关注作业调度、同步和处理器利用率时，不区分处理器类型资源被动资源如内存、序列号、信号量和锁SongGuanghua6实时系统参考模型－时间参数通常假定强实时作业和任务的许多参数总是已知的例如系统中任务的个数在许多嵌入式系统中，只要系统处于一种操作模式下，其任务个数就是固定的当系统的操作模式改变时，任务个数也会改变，在新模式下的任务数也应该是已知的对于任务个数会改变的系统，系统必须维护所有已有强实时任务的信息，包括个数作业的参数时间参数：说明作业的定时约束和行为互连参数：描述作业如何依赖于其他作业以及其他作业如何依赖于它功能参数：说明作业的内在属性资源参数：说明其资源要求SongGuanghua7实时系统参考模型－时间参数（2）释放时间、绝对时限与相对时限都是时间参数用ri，di，Di表示作业的可行间隔作业Ji的释放时间和绝对时限之间的时间间隔（ri，di）释放时间抖动（release-timejitter）假设ri在一定范围[ri-，ri+]内波动ri-：最早释放时间ri＋：最晚释放时间如果每个作业的实际释放时间可以用其最早或者最晚释放时间近似代替，则说作业有固定的释放时间释放时间间隔（inter-releasetime）作业流中两个连续作业的释放时间的间隔SongGuanghua8实时系统参考模型－时间参数（3）偶发作业（sporadicjob）或非周期作业（aperiodicjob）某些作业的释放时间在产生它们的事件发生之前是不知道的随机时刻释放随机分布的概论A(x)：作业的释放时间在x或者x之前的概率到达时间（arrivaltime）或者到达时间间隔（inter-arrivaltime）当一个非周期作业释放时称为到达A(x)是到达时间分布或者到达时间间隔分布SongGuanghua9实时系统参考模型－时间参数（4）执行时间ei在Ji独自执行并且其所需要的资源都具备的情况下，完成Ji的执行所需要的时间取决于作业的复杂度和处理器速度，与作业如何调度无关完成任务需要的实际时间会发生变化ei在范围[ei-,ei+]ei-：Ji的最小执行时间ei+：Ji的最大执行时间通常假定所有强实时作业的ei-和ei+都是已知的实际执行时间是未知的SongGuanghua10实时系统参考模型－周期性任务模型周期性任务模型适用于确定性工作负荷准确性会随着释放时间抖动的增加以及执行时间的变动而变弱周期任务（periodtask）如每个计算或者数据传输按照规则的或者半规则的时间间隔反复不断的执行，以便为系统提供某个功能，就将之建模为周期任务周期任务是一系列的作业Ti对于Ti周期pi是Ti中相连的作业的释放时间间隔之中的最小长度执行时间（executiontime）ei是Ti中所有作业的最大执行时间SongGuanghua11实时系统参考模型－周期性任务模型（2）Ti的相位每个任务Ti的第一个作业Ji,1的释放时间ri,1定义为φi=ri,1具有相同相位的任务称为同相超周期（hyper-period）H表示pi的最小公倍数每个超周期中作业（最大）个数N为对于周期为3、4、10的三个周期任务，超周期长度为60，N=41任务Ti的利用率ui周期为pi，执行时间为ei的完全周期性任务保持处理器忙的时间比率ui=ei/pi总利用率系统中所有任务的利用率之和1/niiNHpSongGuanghua12实时系统参考模型－周期性任务模型（3）在t时刻释放的Ti中的作业必须在t之后的Di个时间内完成经常假定，对所有的任务，每个作业在每个周期的开始都是释放的、就绪的并且必须在周期结束之前完成Di可以取任意值，并且可以小于pi非周期任务任务中的作业要么是弱时限的要么没有时限对于模型中的非周期任务，作业的执行时间也是随机分布变量服从概率分布B(x)SongGuanghua13实时系统参考模型－优先约束和数据依赖作业间的数据和控制依赖关系可能限制了作业的执行次序优先约束（precedenceconstraints）如果要按照某种次序限制作业的执行，称作业具有优先约束如果作业可以按照任意次序执行，称作业是独立的（independent）优先次序关系（precedencerelation）作业之间的先后约束关系如果Jk在Ji执行完成之前不能开始执行，则称Ji是Jk的前任（predecessor），Jk是Ji的后继（successor）用偏序关系表示为JiJk如果JiJk并且没有其他作业Jj使得JiJjJk，则称Ji是Jk的直接前任（immediatepredecessor），Jk是Ji的直接后继（immediatesuccessor）如果Ji和Jk既没有关系JiJk，也没有关系JkJi，则它们是独立的就绪（ready）当一个有前任的作业在其释放时间或者释放时间之后，且其所有的前任都已经完成，该作业才能就绪SongGuanghua14实时系统参考模型－优先约束和数据依赖（2）前趋图（precedencegraph）采用有向图表示的优先约束关系顶点对应于作业，有向边对应于优先约束关系任务图（taskgraph）扩展了的前趋图顶点表示作业，用一对数字来表示它们的可行间隔，边表示作业间的依赖关系数据依赖如果作业Jk消费Ji所产生的数据或者作业Ji向Jk发消息，则产生数据依赖SongGuanghua15实时系统参考模型－其他依赖关系时间依赖关系时间距离（temporaldistance）两个作业完成时间的差值如果要求两个作业之间的时间距离不能超过某个有限值，则称它们有时间距离约束AND/OR优先约束如果一个作业必须等待所有直接前任作业的完成，这样的作业称为AND作业，依赖关系为AND优先约束如果一个作业的一个或者一些直接前任已经完成，那么只要此作业在释放时间或者释放时间之后就可以开始执行，这样的作业称为OR作业SongGuanghua16实时系统参考模型－功能参数抢占（preemption）当更紧急作业到达时，当前执行的任务被暂停，处理器被交给更紧急的作业，当更紧急的作业完成后，处理器再返还给原先的任务恢复执行如果一个作业的执行在任何时候都可以被挂起以便让给其他作业执行，随后又可以在挂起点被恢复执行，则该作业是可抢占的（preemptible）如果一个作业必须从头到尾的执行，中途不能中断，则称该作业是不可抢占的（nonpreemptible）作业的重要性（importance）一个用于指明作业相对于其他作业的重要性的整数作业越关键，重要性越大SongGuanghua17实时系统参考模型－任务的资源参数和资源的参数资源的抢占性如果限制一个资源的每个单元必须串行使用，则该资源为不可抢占的,否则就是可抢占的采用资源图表示资源的配置所有的处理器和资源都有顶点对应顶点的属性是资源的参数资源的类型资源数量边表示资源之间的关系SongGuanghua18实时系统参考模型－调度等级调度程序（scheduler）根据所选择的一组调度算法和资源访问控制协议来对作业进行调度和资源分配，实现这些算法的模块称为调度程序调度的正确性（correctness）调度程序产生唯一有效的调度可行调度（feasible）如果所有的作业能满足其时限要求，称为可行调度可调度的（schedulable）如果使用一个调度算法，调度程序总能产生可行调度，则称根据此调度算法的作业集合是可调度的最优的（optimal）当给定作业集合有可行调度时，如果一个强实时调度算法，总能产生可行调度，则此调度算法是最优的作业的延迟作业的完成时间与时限的差作业提前完成，延迟就是负值作业完成晚了，延迟就是正值SongGuanghua193实时调度算法－时钟驱动调度时钟驱动（clock-driven）是指在系统开始执行之前，选择一些特定的时刻，在这些时刻决定哪一个作业在何时执行在典型的使用时钟驱动调度方法的系统里，所有强实时作业的参数都是固定的并且是已知的作业的调度表脱机计算并被保存，在运行时使用调度程序在每一个调度决策时刻调度作业运行运行时开销可被最小化适用于基本具有可确定性的系统在可确定性的框架下还可以存在少量非周期作业和偶发作业SongGuanghua20实时调度算法－基于优先级调度基于优先级的调度不事先计算任务的调度表，而是在作业释放以后，给它们分配优先级，并按照优先级次序把作业放入就绪队列固定优先级算法为每个任务中的所有作业分配相同的优先级每个周期任务的优先级相对于其他任务来说是固定不变的动态优先级算法给每个任务的单个作业分配不同的优先级作业释放并完成时，任务的优先级相对于其他任务的优先级可能会发生变化大多数实用调度算法会给单个任务分配固定的优先级每当作业释放并准备进入就绪队列时，就给作业分配优先级SongGuanghua21实时调度算法－速率单调算法速率单调算法（RateMonotonic），RM算法1973年，著名实时调度算法固定优先级算法假定任务是周期性的假定任务的相对时限等于它的周期基于任务的周期分配任务优先级周期越短，优先级越高任务的速率与其周期成反比速率越高，优先级越高SongGuanghua22TaskSetSongGuanghua23PeriodicTaskTimingDiagram周期任务调度算法有效性：11niiiCTRM调度算法要求：1/1(21)nniiiCnTSongGuanghua24实时调度算法－时限单调算法时限单调算法（DeadlineMonotonic），DM算法固定优先级算法按照任务的相对时限来分配优先级相对时限越短，优先级越高如果每个任务的相对时限与它的周期成正比，则RM算法与DM算法一致当相对时限是任意的时候，DM算法表现好此时DM算