实时系统.ppt

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

1、实时系统实时调度算法之报告人：陆王博2006 年 2 月 9日由我的设计课题所引出系统中断描述表系统软件结构图中断函数中断函数中断向量中断向量功能描述功能描述优优先先级级CD_INT0 xFFE6HART载波侦测中断地址12MODBUS_timer_int0 xFFE4MODBUS定时中断地址 13HART_timer_int0 xFFE2HART定时中断地址14UART0_int0 xFFD6SCI0中断地址17UART1_int0 xFFD4SCI1中断地址18Signal A:Modbus发送缓冲区满；Signal B:Modbus接收缓冲区满；Signal C:HART接收缓冲区满；S

2、ignal D:HART发送缓冲区满；一、实时系统的分类二、实时系统的几个重要概念三、时钟驱动调度 时间片轮转调度算法 四、优先级驱动调度 （一）静态调度算法RM算法 DM算法 （二）动态调度算法EDF算法 LLF算法五、调度算法总结一、实时系统的分类 根据所解决问题的性质根据所解决问题的性质：静态调度、动态调度静态调度、动态调度 根据任务是否可以被抢占：抢占式调度、非抢占式调度 根据任务的实时性要求：硬实时调度、软实时调度 根据实时系统运行环境：单处理机调度、多处理机调度 根据调度器的体系结构：集中式调度、分布式调度 三种常用的实时调度方法：时钟驱动调度、加权轮转调度和优先级驱动调度。加权轮

3、转调度方法主要用于调度高速交换网络的实时通信。周期（Ti）周期任务所具有，表示任务周期性执行的间隔时间。执行时间（Ci）指任务占用CPU的时间。由于每次执行的软件 环境的差异性，导致任务在各次具体执行过程中的计算时间不同，因此通常用最坏情况下的执行时间来表示。就绪时限（Ri）任务具备了可执行条件的时刻。相位（i）任务第一次就绪的时刻。截止时限（截止期）有绝对截止时限（di）和相对截止时限（Di）两种表示方法。绝对截止时限（di）是任务必须完成的时刻。相对截止时限（Di）是任务所允许的最大响应时间。Di=di Ri CPU利用率执行时间（Ci）与周期（Ti）之比，是衡量算法优 劣的重要参数。二、

4、实时系统的几个重要概念描述一个任务的两种方法：用（i，Ti，Ci，Di）来描述一个任务。例如，（1，10，3，6）是一个周期任务，它的相位是1，周期是10，执行时间是3，相对时限是6。因此，该任务在时刻1第一次就绪，到时刻7必须执行完毕；第二次就绪在时刻11，到时刻17必须执行完毕，依次类推。CPU利用率为0.3。只用（Ti，Ci）来描述一个任务。例如，（10，3），它表示默认相位为0，周期为10，执行时间为3，默认相对时限等于其周期。因此，该任务在时刻0第一次就绪，到时刻10必须执行完毕；第二次就绪在时刻10，到时刻20必须执行完毕，依次类推。CPU利用率为0.3。三、时钟驱动调度 时间片轮

5、转调度算法 时间片轮转调度算法的适用情况：当两个或多个就绪任务具有相同的优先级，且它们是就绪任务中优先级最高的任务时；时间片的选择：时间片太大，时间片轮转调度就没有意义；时间片太小，任务切换过于频繁，处理器开销大，真正用于 运行应用程序的时间将会减小。四、优先级驱动调度 很多经典的调度算法都是基于优先级的，分静态优先级调度和动态优先级调度，在静态优先级调度中，系统任务序列的周期、截止时限、执行时间、CPU利用率等时间特性参数都是己知的，系统任务执行的顺序都可以计算出来。比较经典的静态实时调度算法有速率单调(Rate Monotonic RM)调度算法和单调截止期限(Deadline Monol

6、ithicDM)调度算法。在动态优先级调度中，任务的优先级是可变的，它基于一个有序的优先级序列，这个序列是按照任务的某一个时间特性参数如截止时限、紧急程度或周期而排列的，在运行过程中，这个序列的优先级会由于任务的运行改变时间特性参数而发生变化。比较经典的动态实时调度算法有最早截止期优先(Earliest Deadline FirstEDF)调度算法和最低松弛度优先(Least Laxity First LLF)调度算法。（一）静态调度算法RM算法 速率单调(Rate Monotonic-RM)调度最早是在1973年由Liu和Layland 提出的。它是基于任务的周期给任务指定优先级。RM算法是

7、基于如下假设的基础上进行分析的：所有任务都是周期任务；任务的相对截止时限等于周期；任务在每个周期内的执行时间都相等，为一个常量；任务间没有通信，也不需要同步；任务在执行的任何位置都能被抢占，不存在临界区。对于 RM 调度算法，优先级最高的任务是周期最短的任务，优先级次高的任务是周期次短的任务，依次类推。当有多个任务可供执行时，周期最短的任务首先得到服务。如果把任务的优先级描绘成关于它们速率的函数，其结果是一个单调递增函数，因此称作速率单调调度。（一）静态调度算法RM算法 满足RM算法调度可行性的充分条件如下：给定任务集S=P1,P2,Pn，每个任务都有一个固定周期Tn和执行时间Cn，如果这个任

8、务集的CPU利用率满足下面的条件：(Cn任务Pn执行时间；Tn任务Pn周期)则该任务集用RM算法调度是可行的，RM调度对任务集S是一个可行调度。这里L(n)表示n个任务的CPU 利用率的最小上界，当时，整个任务集的负载小于L(n)时，RM算法调度是可行的，但是当任务集的负载大于L(n)时，并不能判定RM 算法的可行性。（一）静态调度算法RM算法例:有3个周期任务，P1=(4，1)，P2=(10，2)，P3=(20，5)。P1的优先级最高，因为它的速率最高（即周期最短）。P2的优先级次之，P3的优先级最低。首先证明RM调度算法的可行性：可以看出，这3个任务的CPU总利用率小于RM的上界(0.70

9、.779)，因此可以断定，如果使用RM调度，系统的所有任务可以得到成功调度。任务P1，P2，P3的RM调度图（一）静态调度算法DM算法 时限单调(DM)算法是在RM算法之后发展起来的一种固定优先级调度算法。在DM调度算法中，任务优先级由任务时限来决定，时限宽度越小，优先级别越高；时限宽度越长，优先级别越低。采用任务时限作为任务优先级别是基于这种思想：时限宽度越小的任务，越需要紧急处理，否则导致任务越过其时限而得不到调度，从而影响系统的实时性。例：有3个任务：P1=(50，50，25，100)，P2=(0，62.5，10，20)，P3=(0，125，25，50)，这三个任务的CPU利用率分别是0

10、.5，0.16，0.2。总利用率是0.86。按照DM算法，P2的优先级最高，P1的优先级最低。如图（a），所有的任务满足它们的时限。图(a)任务P1，P2，P3的DM调度高低（一）静态调度算法DM算法图(b)任务P1，P2，P3的RM调度 在本例中，若采用RM调度算法，则P1优先级最高，P3优先级最低。如图(b)，P2的第二次执行超出了截止时限，P3的第二次执行也超出了截止时限，由此看出，RM调度算法不能胜任这个系统。P1=(50，50，25，100)，P2=(0，62.5，10，20)，P3=(0，125，25，50)高低（二）动态调度算法EDF算法 最早截止期优先(Earliest Dea

11、dline FirstEDF)调度算法是动态调度中最经典的算法之一，它按照任务的截止时限为其分配优先级。截止时限越短，优先级越高。与DM调度不同的是，EDF调度的任务的优先级是随着时间而变的，在每一个可调度时刻，都根据其最早截止时限，动态地改变任务的优先级。判定EDF调度算法可行性的充分必要条件：给定任务集，当且仅当这个任务的CPU利用率满足下面的条件时：(Cn任务Pn执行时间；Tn任务Pn周期)该任务集用EDF算法调度是可行的。（二）动态调度算法EDF算法 下面给出一个EDF的例子，有两个任务：A=(20，10)，B=(50，25)，由于A的截止期(20)小于B的截止期(50)，所以A的优先

12、级比B高，最先得到执行，两个任务的EDF调度时序如下图。在A1、A2到达的时刻，他们的优先级都比B高，抢占B1；但在A3到达的时刻，由于B1的截止期比A3的短，优先级反转，A3未能成功抢占B1。从EDF调度时序可以看出CPU利用率是100。任务A，B，C的EDF调度图（二）RM算法和EDF算法比较 RM 和EDF 都是相当常见的实时调度算法，RM 和EDF 哪一种调度策略更好，这取决于用户自己的标准。RM是一种静态的调度算法，它的优点是：系统中任务确定，任务的调度次序也就确定，这样使得调度算法工作量比较小，系统开销比较小，可以保证所有进程的截止时限都可以满足，这种优先级固定的调度策略比较适用于

13、高安全性系统；RM的缺点是：CPU利用率较低，不灵活，缺少对系统运行过程中突发事件的实时处理能力，需要事先考虑系统中各种可能出现的情况。对同步周期性任务而言，是一种性能比较好的调度算法。EDF是一种动态调度算法，可以实现很高的CPU利用率，可以调度RM不能合理调度的任务集，具有效率高、容易计算和推断的优点，但是它的系统开销比较大，很难诊断出即将过载的可能性，因此EDF比较适用于软实时系统。（二）RM算法和EDF算法比较RM EDF（1 ）针对RM和EDF的缺陷，提出一种基于权重的RM和EDF相结合的混合优先级调度，对于系统中的每个实时任务，都具有RM和EDF两个部分优先级，系统事先为这两个部分

14、优先级指定一个权重系数，每个部分优先级与其对应的权重系数相乘后，再合起来组成任务的真正优先级，调度程序按照这个真正的优先级去调度各个实时任务。如此一来，系统可以按照用户需要实施不同的调度，当EDF对应的权重系数为零时，系统便使用RM调度算法；当RM对应的权重系数为零时，系统使用EDF调度算法；当需要适中选择时，可以选择其恰当的权重系数。此方法起到折衷RM和EDF调度算法的作用，通过权重的调整，可以灵活地实现RM和EDF调度算法的结合。EDF算法致命的弱点：EDF算法虽然能对可调度负载进行优化，但是它不能解决过载问题。发生过载时，EDF性能就会急剧退化。EDF只考虑截止期，没有考虑到任务执行的时

15、间，当一个任务由于截止期的临近被调度，然而此时任务执行所需要的时间已超出了截止期，即任务就算被调度也来不及在截止期前完成，那么该任务的执行已没有意义，不仅导致任务夭折，又浪费了CPU资源。最低松弛度优先(Least Laxity First LLF)调度算法可以弥补EDF的这个不足，具有在重负载的情况下，工作较好的优点。它是根据任务紧急(或松弛)的程度，来确定任务的优先级，任务的紧急程度越高，为该任务所赋予的优先级就越高，以使之优先执行。一个任务的松弛度定义为:Laxity=Deadline time CPU time needed Current time 可以明显的看出，截止期（deadl

16、ine time）在先的任务不一定被最先执行。如果laxity的值为0，则表明这个任务应该立即执行。（二）动态调度算法LLF算法（二）动态调度算法LLF算法 LLF 算法从理论上分析，具有在重负载的情况下，工作较好的优点，具有在调度时能判断出任务是否能被调度的问题，避免任务夭折，使过载问题得以解决的能力。但是，由于等待执行任务的空闲时间是严格递减的，其等待执行的缓急程度也随时间越来越紧急，因此在系统执行过程中，等待任务随时可能会抢占当前执行的任务。LLF算法造成任务之间的频繁切换或称为颠簸(thrashing)现象较为严重，颠簸现象增大了系统开销，并限制了LLF算法的应用，使得其实用性大为降低

17、。五、调度算法总结 上述各种算法都各具优势，但同时也存在不足。比如，RM 算法，是许多实时系统常用的一种静态调度方法。这种算法被广泛地应用于任务周期性执行并且各个任务之间不需要同步的场合，能够在较低的开销条件下保证任务运行时的优先级。但它的CPU利用率比较低，且对于突发事件不能作出及时的响应。EDF算法克服了RM的利用率限制，也可以处理周期与非周期的任务，而且在资源需求中它们可以方便地反映调用的变化，但它也不可避免会产生任务夭折现象，当系统过载时，性能急剧下降。那么，在实际应用中，我们可以针对系统的要求和侧重点的不同，选取不同的调度算法，也可以根据情况，组合其中的两种或多种算法，达到取其优势，去其弊端的效果。祝大家新年快乐！