任务管理和调度.ppt

《任务管理和调度.ppt》由会员分享，可在线阅读，更多相关《任务管理和调度.ppt（79页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、嵌入式系统设计嵌入式系统设计嵌入式系统设计嵌入式系统设计第9讲（2）任务管理和调度授课教师：电邮地址：嵌入式系统设计嵌入式系统设计嵌入式系统设计嵌入式系统设计主要内容任务调度优先级反转2023/1/嵌入式系统设计嵌入式系统设计嵌入式系统设计嵌入式系统设计3.任务调度基于优先级的可抢占调度时间片轮转调度静态调度动态调度静态调度与动态调度之间的比较2023/1/嵌入式系统设计嵌入式系统设计嵌入式系统设计嵌入式系统设计任务调度要解决的问题WHAT：按什么原则分配CPUw 任务调度算法WHEN：何时分配CPUw任务调度的时机HOW：如何分配CPUw任务调度过程（任务的上下文切换）2023/1/嵌入式系

2、统设计嵌入式系统设计嵌入式系统设计嵌入式系统设计计算机发展初期通常都要集中在计算机所在的地方，人为地以作业（job）的方式把工作内容一件一件地提交给计算机进行处理，也就不存在调度的概念随后，出现了计算机的批处理方式计算机把作业按照先来先服务的方式进行处理，体现了一种非常简单的调度概念后来出现多道程序处理方式，调度才变得复杂和重要起来2023/1/嵌入式系统设计嵌入式系统设计嵌入式系统设计嵌入式系统设计调度用来确定多任务环境下任务执行的顺序和在获得CPU资源后能够执行的时间长度。操作系统通过一个调度程序来实现调度功能。调度程序以函数的形式存在，用来实现操作系统的调度算法。w调度程序本身并不是一个

3、任务，是一个函数调用，可在内核的各个部分进行调用。调用调度程序的具体位置又被称为是一个调度点（scheduling point），调度点通常处于以下位置：w中断服务程序的结束位置；w任务因等待资源而处于等待状态；w任务处于就绪状态时等。2023/1/嵌入式系统设计嵌入式系统设计嵌入式系统设计嵌入式系统设计调度本身需要一定的系统开销，需要花费时间来计算下一个可被执行的任务。竭力使用最优调度方案往往并不是一个明智的办法w高级的调度程序通常具有不可预见性，需要花费更多的时间和资源，并且，其复杂性也增加了应用编程人员的使用难度。简单是实时内核所强调的主要特点w实用的实时内核在实现时大都采用了简单的调度

4、算法，以确保任务的实时约束特性和可预见性是可以管理的。复杂的、高级的调度算法则通常用于研究领域 2023/1/嵌入式系统设计嵌入式系统设计嵌入式系统设计嵌入式系统设计内核的主要职责就是要确保所有的任务都能够满足任务的时间约束特性要求时间约束特性来源于任务的不同需求（如截止时间、QoS等），且同一个任务在不同时候也可能具有不同的时间约束特性。w比如，机器人中用来控制行动的任务在障碍环境下行走所需要考虑的约束特性就比行走在开放环境下要多得多。能够同时适应所有情况的调度算法是不存在的。2023/1/嵌入式系统设计嵌入式系统设计嵌入式系统设计嵌入式系统设计调度算法研究从理论上来说，最优调度只有在能够完

5、全获知所有任务在处理、同步和通信方面的需求，以及硬件的处理和时间特性的基础上才能实现。w实际的应用很难实现，特别是需要获知的信息处于动态变化的情况下。w即使在这些需要的信息都是可以预见的情况下，常用的调度问题仍然是一个NP难题。w调度的复杂性将随调度需要考虑的任务和约束特性的数量呈现出指数增长。调度算法不能很好地适应系统负载和硬件资源不断增长的系统。当然，这并不意味着调度算法不能解决只有少量、定义好的任务的应用的需求。2023/1/嵌入式系统设计嵌入式系统设计嵌入式系统设计嵌入式系统设计设计调度程序时，通常需要综合考虑如下因素：CPU的使用率（CPU utilization）输入/输出设备的吞

6、吐率响应时间（responsive time）公平性截止时间这些因素之间具有一定的冲突性。比如可通过让更多的任务处于就绪状态来提高CPU的使用率，但这显然会降低系统的响应时间。调度程序的设计需要优先考虑最重要的需求，然后在各种因素之间进行折中处理。2023/1/嵌入式系统设计嵌入式系统设计嵌入式系统设计嵌入式系统设计调度算法是在一个特定时刻用来确定将要运行的任务的一组规则。从1973年Liu和Layland开始关于实时调度算法的研究工作以来（1973年，Liu和Layland发表了一篇名为“Scheduling Algorithms for Multiprogramming in a Hard

7、 Real-Time Environment”的论文），相继出现了很多调度算法和方法。对于调度方法，可以划分为以下三个主要的行为：脱机配置运行时调度先验性分析2023/1/嵌入式系统设计嵌入式系统设计嵌入式系统设计嵌入式系统设计脱机配置产生运行时调度所需要的静态信息；运行时调度在系统运行的时候根据不同的事件在各个计算之间进行切换处理；先验性分析根据静态配置信息和调度算法在运行时的行为分析确定所有的时间需求是否得到满足。各种调度算法之间的差异在于它们在上述三种行为之间的侧重点。先验性分析通过测试来确定调度方法的可行性，比如所有任务在运行时的时间约束特性是否都能得到满足。2023/1/嵌入式系统设

8、计嵌入式系统设计嵌入式系统设计嵌入式系统设计对于大量的实时调度方法而言，存在着以下几类主要的划分方法：离线（off-line）和在线（on-line）调度抢占（preemptive）和非抢占（non-preemptive）调度静态（static）和动态（dynamic）调度最佳（optimal）和试探性（heuristic）调度2023/1/嵌入式系统设计嵌入式系统设计嵌入式系统设计嵌入式系统设计离线调度和在线调度：根据获得调度信息的时机。离线调度：w运行过程中使用的调度信息在系统运行之前就确定了，如时间驱动的调度。w离线调度算法具有确定性，但缺乏灵活性，适用于那些特性能够预先确定，且不容易发

9、生变化的应用。在线调度：w调度信息在系统运行过程中动态获得，如优先级驱动的调度（如EDF，RMS等）。w在线调度算法在形成最佳调度决策上具有较大的灵活性。2023/1/嵌入式系统设计嵌入式系统设计嵌入式系统设计嵌入式系统设计抢占式调度和非抢占式调度：任务在运行过程中能否被打断的处理情况。抢占式调度：w正在运行的任务可能被其他任务所打断。非抢占式调度：w一旦任务开始运行，该任务只有在运行完成而主动放弃CPU资源，或是因为等待其他资源被阻塞的情况下才会停止运行。实时内核大都采用了抢占式调度算法，使关键任务能够打断非关键任务的执行，确保关键任务的截止时间能够得到满足。抢占式调度算法要更复杂些，且需要

10、更多的资源，并可能在使用不当的情况下会造成低优先级任务出现长时间得不到执行的情况。非抢占式调度算法常用于那些任务需要按照预先确定的顺序进行执行，且只有当任务主动放弃CPU资源后，其他任务才能得到执行的情况。2023/1/嵌入式系统设计嵌入式系统设计嵌入式系统设计嵌入式系统设计ISRLow Priority TaskHigh Priority TaskISRISR make High Priority Task ReadyISRCompletes(Return to Task)Low Priority TaskCompletes(Switch to HP Task)Interrupt Occur

11、sVector to ISRNon-PreemptiveNon-Preemptive 2023/1/嵌入式系统设计嵌入式系统设计嵌入式系统设计嵌入式系统设计ISRLow Priority Task(LPT)High Priority Task(HPT)ISRISR make High Priority Task ReadyInterrupt OccursVector to ISRISRCompletes(Switch to HP Task)HP Task Completes(Switch back to LP Task)PreemptivePreemptive 2023/1/嵌入式系统设计嵌入

12、式系统设计嵌入式系统设计嵌入式系统设计内核的可抢占性内核可抢占与不可抢占：执行内核提供的系统调用的过程中，是否可以被中断打断。可抢占内核：即使正在执行的是内核服务函数，也能响应中断，并且中断服务程序退出时能进行任务重新调度：如果有优先级更高的任务就绪，就立即让高优先级任务运行，不要求回到被中断的任务，将未完成的系统调用执行完。2023/1/嵌入式系统设计嵌入式系统设计嵌入式系统设计嵌入式系统设计内核的可抢占性不可抢占内核：不可抢占内核有两种情况内核服务函数不能被中断。系统在执行内核服务函数时处于关中断状态，不能响应外部可屏蔽中断，这样就会在一定程度上延迟中断响应时间。能被中断但是不能进行任务重

13、新调度。w系统在执行内核服务函数时可以响应中断，不会延迟中断响应时间；w但是在中断退出时不进行任务重新调度，即使在中断服务程序执行过程中有更高优先级的任务就绪，也必须回到被中断的任务将未完成的内核函数执行完后，才能让高优先级任务执行。2023/1/嵌入式系统设计嵌入式系统设计嵌入式系统设计嵌入式系统设计低优先级任务低优先级任务内核服务内核服务ISRISR高优先级任务高优先级任务时时间间(1)(1)(2)(2)(3)(3)(4)(4)(5)(5)不可抢占内核（允许中断）不可抢占内核（允许中断）2023/1/嵌入式系统设计嵌入式系统设计嵌入式系统设计嵌入式系统设计低优先级任务低优先级任务内核服务内

14、核服务ISRISR高优先级任务高优先级任务时时间间(1)(1)(2)(2)(3)(3)(4)(4)(5)(5)可抢占内核可抢占内核2023/1/嵌入式系统设计嵌入式系统设计嵌入式系统设计嵌入式系统设计静态调度和动态调度：根据任务优先级的确定时机静态调度：w所有任务的优先级在设计时就确定下来了，且在运行过程中不会发生变化（如RMS）。动态调度：w任务的优先级则在运行过程中确定，并可能不断地发生变化（如EDF）。静态调度算法适用于能够完全把握系统中所有任务及其时间约束（如截止时间、运行时间、优先顺序和运行过程中的到达时间）特性的情况。静态调度比较简单，但缺乏灵活性，不利于系统扩展；动态调度有足够的

15、灵活性来处理变化的系统情况，但需要消耗更多的系统资源。2023/1/嵌入式系统设计嵌入式系统设计嵌入式系统设计嵌入式系统设计CPU的使用率（utilization）对于给定的一组任务，这些任务所使用的整个CPU资源的比率。对于一个给定的调度算法，其CPU使用率存在着一个理论上的上限，如EDF算法的最大CPU使用率为1。可调度性（schedulability）对于给定的一组任务，如果所有任务都能满足截止时间的要求，这些任务就是可调度的。对于在线调度算法，当一个新的任务需要加入到系统中时，应进行可调度性分析w如果加入任务后会导致某些任务不能满足调度性，则该任务就不能添加到系统中去可调度性的程度可以

16、通过所有任务截止时间都能得到满足的情况下的最大CPU使用率来进行衡量。2023/1/嵌入式系统设计嵌入式系统设计嵌入式系统设计嵌入式系统设计基于优先级的可抢占调度 基于优先级的可抢占调度方式如果出现具有更高优先级的任务处于就绪状态时，当前任务将停止运行，把CPU的控制权交给具有更高优先级的任务，使更高优先级的任务得到执行。实时内核需要确保CPU总是被具有最高优先级的就绪任务所控制。当一个具有比当前正在运行任务的优先级更高的任务处于就绪状态的时候，实时内核应及时进行任务切换，保存当前正在运行任务的上下文，切换到具有更高优先级的任务的上下文。2023/1/嵌入式系统设计嵌入式系统设计嵌入式系统设计

17、嵌入式系统设计任务任务1 1任务任务2 2任务任务3 3优先级优先级高高低低时间时间任务任务2 2就绪就绪任务任务3 3就绪就绪任务任务2 2任务任务1 1抢占抢占抢占抢占任务任务3 3运行结束运行结束任务任务2 2运行结束运行结束在可抢占调度方式下的任务运行情况在可抢占调度方式下的任务运行情况在可抢占调度方式下的任务运行情况在可抢占调度方式下的任务运行情况 任务任务1 1被具有更高优先级的任务被具有更高优先级的任务2 2所抢占，然后任务所抢占，然后任务2 2又被任务又被任务3 3抢占。当抢占。当任务任务3 3完成运行后，任务完成运行后，任务2 2继续执行。当任务继续执行。当任务2 2完成运行

18、后，任务完成运行后，任务1 1才又得才又得以继续执行。以继续执行。2023/1/嵌入式系统设计嵌入式系统设计嵌入式系统设计嵌入式系统设计时间片轮转调度 时间片轮转调度（round-robin scheduling）算法当有两个或多个就绪任务具有相同的优先级，且它们是就绪任务中优先级最高的任务时，任务调度程序按照这组任务就绪的先后次序调度第一个任务，让第一个任务运行一段时间，然后又调度第二个任务，让第二个任务又运行一段时间，依次类推，到该组最后一个任务也得以运行一段时间后，接下来又让第一个任务运行。任务运行的这段时间称为时间片（time slicing）。2023/1/嵌入式系统设计嵌入式系统设

19、计嵌入式系统设计嵌入式系统设计时间片轮转调度在时间片轮转调度方式中当任务运行完一个时间片后，该任务即使还没有停止运行，也必须释放处理器让下一个与它相同优先级的任务运行，使实时系统中优先级相同的任务具有平等的运行权利。释放处理器的任务被排到同优先级就绪任务链的链尾，等待再次运行。2023/1/嵌入式系统设计嵌入式系统设计嵌入式系统设计嵌入式系统设计时间片轮转调度采用时间片轮转调度算法时，任务的时间片大小要适当选择。时间片大小的选择会影响系统的性能和效率：w时间片太大，时间片轮转调度就没有意义；w时间片太小，任务切换过于频繁，处理器开销大，真正用于运行应用程序的时间将会减小。不同的实时内核在实现时

20、间片轮转调度算法上可能有一些差异：有的内核允许同优先级的各个任务有不一致的时间片；有的内核要求相同优先级的任务具有一致的时间片。2023/1/嵌入式系统设计嵌入式系统设计嵌入式系统设计嵌入式系统设计任务任务1 1任务任务2 2任务任务3 3优先级优先级高高低低时间时间任务任务3 3就绪就绪任务任务3 3运行结束运行结束任务任务1 1任务任务2 2任务任务1 1任务任务2 2在时间片轮转调度方式下的任务运行情况在时间片轮转调度方式下的任务运行情况在时间片轮转调度方式下的任务运行情况在时间片轮转调度方式下的任务运行情况任务任务1 1和任务和任务2 2具有相同的优先级，按照时间片轮转的方式轮流执行。

21、当具有相同的优先级，按照时间片轮转的方式轮流执行。当高优先级任务高优先级任务3 3就绪后，正在执行的任务就绪后，正在执行的任务2 2被抢占，高优先级任务被抢占，高优先级任务3 3得到得到执行。当任务执行。当任务3 3完成运行后，任务完成运行后，任务2 2才重新在未完成的时间片内继续执行。才重新在未完成的时间片内继续执行。随后任务随后任务1 1和任务和任务2 2又按照时间片轮转的方式执行。又按照时间片轮转的方式执行。2023/1/嵌入式系统设计嵌入式系统设计嵌入式系统设计嵌入式系统设计静态调度静态调度算法任务的优先级需要在系统运行前进行确定。确立任务优先级的主要依据为：w执行时间。以执行时间为依

22、据的调度算法为：n最短执行时间优先（smallest execution time first）；n最长执行时间优先（largest execution time first）。w周期。以周期为依据的调度算法为：n短周期任务优先（smallest period first）；n长周期任务优先（largest period first）。2023/1/嵌入式系统设计嵌入式系统设计嵌入式系统设计嵌入式系统设计静态调度w任务的CPU使用率。任务的CPU使用率为任务计算时间与任务周期的比值。以任务的CPU使用率为依据的调度算法为：n最小CPU使用率优先（smallest task utilizatio

23、n first）；n最大CPU使用率优先（largest task utilization first）。w紧急程度。根据任务的紧急程度，以人为的方式进行优先级的静态安排。人为安排优先级比率单调调度算法2023/1/嵌入式系统设计嵌入式系统设计嵌入式系统设计嵌入式系统设计 人为安排优先级 人为安排优先级是嵌入式实时软件开发中使用得非常多的一种方法。以系统分析、设计人员对系统需求的理解为基础，确定出系统中各个任务之间的相对优先情况，并据此确定出各个任务的优先级。2023/1/嵌入式系统设计嵌入式系统设计嵌入式系统设计嵌入式系统设计webDisplaydataHandlingdataRecv1 请

24、求请求Web页面页面2 请求请求Web页面页面3 请求请求Web页面页面4 Web数据数据5 Web数据数据6 解析后的解析后的Web数据数据在一个用来实现网页浏览的应用中，可把整个应用划分为网络数据接收在一个用来实现网页浏览的应用中，可把整个应用划分为网络数据接收dataRecvdataRecv、网页数据处理、网页数据处理dataHandlingdataHandling和网页显示和网页显示webDisplaywebDisplay等三个任等三个任务。务。由于由于dataRecvdataRecv需要及时接收从网络传过来的数据，其优先级应最高；需要及时接收从网络传过来的数据，其优先级应最高；web

25、DisplaywebDisplay需要及时处理用户的输入（如停止获取当前页面或是请求新需要及时处理用户的输入（如停止获取当前页面或是请求新的页面等），其优先级应比的页面等），其优先级应比dataHandlingdataHandling高。据此，可人为地把高。据此，可人为地把dataRecvdataRecv、dataHandlingdataHandling和和webDisplaywebDisplay的优先级分别安排为的优先级分别安排为5 5、7 7、6 6（设定数字越大，任务的优先级越低）。（设定数字越大，任务的优先级越低）。2023/1/嵌入式系统设计嵌入式系统设计嵌入式系统设计嵌入式系统设计

26、比率单调调度算法 1973年，Liu和Layland在ACM上发表了题为“Scheduling Algorithms for Multiprogramming in a Hard Real-Time Environment”的论文，该论文奠定了实时系统所有现代调度算法的理论基础。比率单调调度算法（rate-monotonic scheduling algorithm，RMS）即在该论文中被提出来。2023/1/嵌入式系统设计嵌入式系统设计嵌入式系统设计嵌入式系统设计比率单调调度算法RMS是基于以下假设的基础上进行分析的：A1.所有任务都是周期任务；A2.任务的相对截止时间等于任务的周期；A3.

27、任务在每个周期内的计算时间都相等，保持为一个常量；A4.任务之间不进行通信，也不需要同步；A5.任务可以在计算的任何位置被抢占，不存在临界区。2023/1/嵌入式系统设计嵌入式系统设计嵌入式系统设计嵌入式系统设计比率单调调度算法尽管Liu和Layland把该调度算法定位于单处理器的实时任务调度，但实验证明，同样适用于分布式系统。RMS是一个静态的固定优先级调度算法：任务的优先级与任务的周期表现为单调函数关系w任务周期越短，任务的优先级越高；w任务周期越长，任务的优先级越低。RMS是静态调度中的最优调度算法w如果一组任务能够被任何静态调度算法所调度，则这些任务在RMS下也是可调度的。2023/1

28、/嵌入式系统设计嵌入式系统设计嵌入式系统设计嵌入式系统设计比率单调调度算法任务的可调度性可以通过计算任务的CPU使用率，然后把得到的CPU使用率同一个可调度的CPU使用率上限进行比较来获得。可调度的CPU使用率上限被称为可调度上限（schedulable bound）。w表示给定任务在特定调度算法下能够满足截止时间要求的最坏情况下的最大CPU使用率。可调度上限的最大值为100%，与调度算法密切相关。w对于一组任务，如果任务的CPU使用率小于或等于可调度上限，则这组任务是可被调度的；w如果任务的CPU使用率大于可调度上限，就不能保证这组任务是可被调度的，任务的调度性需要进一步的分析。2023/1

29、/嵌入式系统设计嵌入式系统设计嵌入式系统设计嵌入式系统设计比率单调调度算法在RMS中，CPU使用率的可调度范围为：上述条件是一个上述条件是一个充分条件充分条件，但不是一个必要条件：，但不是一个必要条件：如果任务的如果任务的CPUCPU使用率满足该条件，则任务是可调度的；使用率满足该条件，则任务是可调度的；但如果不满足该条件，也有可能被但如果不满足该条件，也有可能被RMSRMS所调度。所调度。2023/1/嵌入式系统设计嵌入式系统设计嵌入式系统设计嵌入式系统设计比率单调调度算法RMS的可调度的CPU使用率上限 任务数量任务数量可调度的可调度的CPU使用率上限使用率上限1120.82830.780

30、40.75750.74360.735ln22023/1/嵌入式系统设计嵌入式系统设计嵌入式系统设计嵌入式系统设计任务任务计算时间计算时间周期周期CPU使用使用率率CPU使用使用率之和率之和可调度上可调度上限限1150.200.201.0025200.250.450.8338500.160.610.784121000.120.730.76满足满足满足满足RMSRMS调度条件的任务的执行情况调度条件的任务的执行情况调度条件的任务的执行情况调度条件的任务的执行情况任务的计算时间、周期时间、任务的计算时间、周期时间、CPUCPU使用率及其使用率及其RMSRMS要求的可调度上限要求的可调度上限任务的执行

31、情况任务的执行情况2023/1/嵌入式系统设计嵌入式系统设计嵌入式系统设计嵌入式系统设计任务任务计算时间计算时间周期周期CPU使用使用率率CPU使用使用率之和率之和可调度上可调度上限限1150.200.201.0025200.250.450.83310500.200.650.784201000.200.850.76任务的计算时间、周期时间、任务的计算时间、周期时间、CPUCPU使用率及其使用率及其RMSRMS要求的可调度上限要求的可调度上限任务的执行情况任务的执行情况不满足不满足不满足不满足RMSRMS调度条件，但能够被调度执行的情况调度条件，但能够被调度执行的情况调度条件，但能够被调度执行的

32、情况调度条件，但能够被调度执行的情况2023/1/嵌入式系统设计嵌入式系统设计嵌入式系统设计嵌入式系统设计比率单调调度算法在任务比较多的情况下RMS的可调度的CPU使用率上限为ln2，如此低的CPU使用率对大多数的系统来说都是不可接受的。对于RMS来说，即使CPU的使用率小于100%，但如果大于了算法给定的可调度范围，仍有可能不能满足截止时间的要求。2023/1/嵌入式系统设计嵌入式系统设计嵌入式系统设计嵌入式系统设计比率单调调度算法RMS的不足之处还在于它假定任务是相互独立的、周期性的，且任务能够在任何计算点被抢占。在实时系统中，任务之间通常都需要进行通信和同步。Rajkumar在博士论文（

33、Synchronization in Real-Time Systems:A Priority Inheritance Approach）中基于RMS提出了可以处理任务同步的调度算法。w解决了单处理器上任务之间的同步问题。wRajkumar还解决了任务之间存在互斥执行的问题，允许任务存在临界区，在执行临界区时，任务不能被其他任务所抢占。2023/1/嵌入式系统设计嵌入式系统设计嵌入式系统设计嵌入式系统设计比率单调调度算法非周期任务的处理方式:w以后台方式执行非周期任务n效率比较低，非周期任务只有在所有周期任务都没有执行的情况下才会得到调度。w把就绪的非周期任务组织成一个队列，然后周期性地查询该

34、队列是否有非周期任务的方式来执行。n有可能出现刚查询完成，就有非周期任务就绪的情况，导致该任务等待一个轮询周期才能得到调度执行的情况。2023/1/嵌入式系统设计嵌入式系统设计嵌入式系统设计嵌入式系统设计动态调度对于静态调度，任务的优先级不会发生变化。在动态调度中，任务的优先级可根据需要进行改变，也可能随着时间按照一定的策略自动发生变化。截止时间优先调度算法 最短空闲时间优先调度算法 2023/1/嵌入式系统设计嵌入式系统设计嵌入式系统设计嵌入式系统设计截止时间优先调度算法 RMS调度算法的CPU使用率比较低，在任务比较多的情况下，可调度上限为68%。Liu和Layland又提出了一种采用动态

35、调度的、具有更高CPU使用率的调度算法截止时间优先调度算法（earliest deadline first，EDF）。在EDF中，任务的优先级根据任务的截止时间来确定：任务的绝对截止时间越近，任务的优先级越高；任务的绝对截止时间越远，任务的优先级越低。当有新的任务处于就绪状态时，任务的优先级就有可能需要进行调整。2023/1/嵌入式系统设计嵌入式系统设计嵌入式系统设计嵌入式系统设计截止时间优先调度算法同RMS一样，Liu和Layland对EDF算法的分析也是在一系列假设的基础上进行的。在Liu和Layland的分析中，EDF不要求任务为周期任务，其他假设条件与RMS相同。2023/1/嵌入式系

36、统设计嵌入式系统设计嵌入式系统设计嵌入式系统设计截止时间优先调度算法EDF算法是最优的单处理器动态调度算法，其可调度上限为100%。在EDF调度算法下，对于给定的一组任务，任务可调度的充要条件为：对于给定的一组任务，如果对于给定的一组任务，如果EDFEDF不能满足其调度性要求，则没有其他调不能满足其调度性要求，则没有其他调度算法能够满足这组任务的调度性要求。度算法能够满足这组任务的调度性要求。2023/1/嵌入式系统设计嵌入式系统设计嵌入式系统设计嵌入式系统设计截止时间优先调度算法同基于固定优先级的静态调度相比，采用基于动态优先级调度的EDF算法的显著优点在于：EDF的可调度上限为100%，使

37、CPU的计算能力能够被充分利用起来。EDF也存在不足之处：在实时系统中不容易实现；同RMS相比，EDF具有更大的调度开销，需要在系统运行的过程中动态地计算确定任务的优先级；在系统出现临时过载的情况下，EDF算法不能确定哪个任务的截止时间会得不到满足。2023/1/嵌入式系统设计嵌入式系统设计嵌入式系统设计嵌入式系统设计截止时间优先调度算法Liu和Layland提出了一种混合的调度算法：大多数任务都采用RMS进行调度，只有少量任务采用EDF调度算法。尽管混合的调度算法不能达到100%的CPU使用率，但确实综合了EDF和RMS调度算法的优点，使整个调度比较容易实现。2023/1/嵌入式系统设计嵌入

38、式系统设计嵌入式系统设计嵌入式系统设计任务任务到达时间到达时间计算时间计算时间绝对截止时间绝对截止时间T101030T24310T351025任务及其到达时间、计算时间与绝对截止时间任务及其到达时间、计算时间与绝对截止时间当任务当任务T1T1到达的时候，由于到达的时候，由于T1T1是系统中等待运行的唯一一个任务，因此是系统中等待运行的唯一一个任务，因此T1T1得到立即执行。任务得到立即执行。任务T2T2在时间在时间4 4到达，由于任务到达，由于任务T2T2的截止时间（的截止时间（1010）小于任务小于任务T1T1的截止时间（的截止时间（3030），因此任务），因此任务T2T2的优先级比的优先级

39、比T1T1高，并抢占任高，并抢占任务务T1T1得到执行。任务得到执行。任务T3T3在时间在时间5 5到达，由于到达，由于T3T3的截止时间比的截止时间比T2T2的截止时的截止时间大，因此间大，因此T3T3的优先级的优先级T2T2比低，需要等到比低，需要等到T2T2执行完成后，才能得到执行。执行完成后，才能得到执行。当当T2T2执行完成后（时间执行完成后（时间7 7），），T3T3开始执行（开始执行（T3T3的优先级比的优先级比T1T1高）。高）。T3T3运运行到时间行到时间1717，T1T1才能继续执行直到运行结束。才能继续执行直到运行结束。2023/1/嵌入式系统设计嵌入式系统设计嵌入式系统

40、设计嵌入式系统设计最短空闲时间优先调度算法 在最短空闲时间优先调度算法（least-laxity-first scheduling）中，任务的优先级根据任务的空闲时间进行动态分配：w任务的空闲时间越短，任务的优先级越高；w任务的空闲时间越长，任务的优先级越低。任务的空闲时间可通过来表示：任务的空闲时间=任务的绝对截止时间-当前时间-任务的剩余执行时间 2023/1/嵌入式系统设计嵌入式系统设计嵌入式系统设计嵌入式系统设计静态调度与动态调度之间的比较 动态调度的出现是为了确保低优先级任务也能被调度。对于所有任务都具有同等重要程度的系统比较合适；对于需要绝对可预测性的系统一般不使用动态调度：w在出

41、现临时过载的情况下，要求调度算法能够选择最紧急的任务执行，而放弃那些不太紧急的任务。w而动态调度的优先级只反映了任务的时间特性，没有把任务的紧急程度体现到优先级中去。2023/1/嵌入式系统设计嵌入式系统设计嵌入式系统设计嵌入式系统设计静态调度与动态调度之间的比较动态调度的调度代价通常都比静态调度高：动态调度在每一个调度点都需要对任务的优先级进行重新计算，静态调度中任务的优先级则始终保持不变，不需要进行计算。2023/1/嵌入式系统设计嵌入式系统设计嵌入式系统设计嵌入式系统设计4.优先级反转优先级继承协议 优先级天花板协议2023/1/嵌入式系统设计嵌入式系统设计嵌入式系统设计嵌入式系统设计理

42、想情况下高优先级任务就绪后，能够立即抢占低优先级任务而得到执行。但在有多个任务需要使用共享资源的情况下，可能会出现高优先级任务被低优先级任务阻塞，并等待低优先级任务执行的现象。优先级反转（priority inversion）：高优先级任务需要等待低优先级任务释放资源，而低优先级任务又正在等待中等优先级任务的现象。2023/1/嵌入式系统设计嵌入式系统设计嵌入式系统设计嵌入式系统设计两个任务都试图访问共享数据的情况即为出现优先级反转最通常的情况。为了保证一致性，这种访问应该是顺序进行的。w如果高优先级任务首先访问共享资源，则会保持共享资源访问的合适的任务优先级顺序；w如果是低优先级任务首先获得

43、共享资源的访问，然后高优先级任务请求获取对共享资源的访问，高优先级任务将被阻塞，直到低优先级任务完成对共享资源的访问。阻塞是优先级反转的一种形式，它使得高优先级任务必须等待低优先级任务的处理。如果阻塞的时间过长，即使在CPU使用率比较低的情况下，也可能出现截止时间得不到满足的情况。2023/1/嵌入式系统设计嵌入式系统设计嵌入式系统设计嵌入式系统设计通常的同步互斥机制为信号量（semaphore）、锁（lock）和Ada中的Rendezvous（汇合）等。为保护共享资源的一致性，或是确保非抢占资源在使用上的合适顺序，使用这些方法是非常必须的。直接应用这些同步互斥机制将导致系统中出现不定时间长度

44、的优先级反转和比较低的任务可调度性情况。2023/1/嵌入式系统设计嵌入式系统设计嵌入式系统设计嵌入式系统设计t0t0t1t2t3t4t5t6t7t8Critical section guarded by Stime123t9t0t10t11t12t13t14t15t16t18t17假设假设T1T1，T2T2，T3T3为优先级顺序降低的三个任务，为优先级顺序降低的三个任务，T1T1具有最高优先级。假具有最高优先级。假定定T1T1和和T3T3通过信号量通过信号量S S共享一个数据结构，并且，在时刻共享一个数据结构，并且，在时刻t1t1，任务，任务T3T3获获得信号量得信号量S S，开始执行临界区

45、代码。在，开始执行临界区代码。在T3T3执行临界区代码的过程中，高执行临界区代码的过程中，高优先级任务优先级任务T1T1就绪，抢占任务就绪，抢占任务T3T3而获得而获得CPUCPU资源，并在随后试图使用共资源，并在随后试图使用共享数据，但该共享数据已被享数据，但该共享数据已被T1T1通过信号量通过信号量S S加锁。在这种情况下，会期加锁。在这种情况下，会期望具有最高优先级的任务望具有最高优先级的任务T1T1被阻塞的时间不超过任务被阻塞的时间不超过任务T3T3执行完整个临界执行完整个临界区的时间。但事实上，这种区的时间。但事实上，这种阻塞时间的长度是无法预知阻塞时间的长度是无法预知的。这主要是由

46、的。这主要是由于任务于任务T3T3还可能被具有中等优先级的任务还可能被具有中等优先级的任务T2T2所阻塞，使得所阻塞，使得T1T1也需要等待也需要等待T2T2和其他中等优先级的任务释放和其他中等优先级的任务释放CPUCPU资源。资源。2023/1/嵌入式系统设计嵌入式系统设计嵌入式系统设计嵌入式系统设计任务T1的阻塞时间长度不定，可能会很长。如果任务在临界区内不允许被抢占，这种情况可得到部分解决。但由于形成了不必要的阻塞，使得这种方案只适合于非常短的临界区。比如，一旦一个低优先级任务进入了一个比较长的临界区，不会访问该临界区的高优先级任务将会被完全不必要的阻塞。2023/1/嵌入式系统设计嵌入

47、式系统设计嵌入式系统设计嵌入式系统设计Lampson在1980年发表的题为“Experiences with processes and monitors in Mesa”的论文中首先讨论关于优先级反转的问题：建议临界区执行在比可能使用该临界区的所有任务的优先级更高的优先级上。解决优先级反转现象的常用协议为：优先级继承协议（priority inheritance protocol）；优先级天花板协议（priority ceiling protocol）。2023/1/嵌入式系统设计嵌入式系统设计嵌入式系统设计嵌入式系统设计优先级继承协议优先级继承协议的基本思想是：当一个任务阻塞了一个或多个高

48、优先级任务时，该任务将不使用其原来的优先级，而使用被该任务所阻塞的所有任务的最高优先级作为其执行临界区的优先级。当该任务退出临界区时，又恢复到其最初的优先级。2023/1/嵌入式系统设计嵌入式系统设计嵌入式系统设计嵌入式系统设计t0t0t1t2t3t4t5t6t7t8Critical section guarded by Stime123t9t0t10t11t12t13t14t15t16t18t17如果任务如果任务T1T1被被T3T3阻塞，优先级继承协议要求任务阻塞，优先级继承协议要求任务T3T3以任务以任务T1T1的优先级执的优先级执行临界区。这样，任务行临界区。这样，任务T3T3在执行临界

49、区的时候，原来比在执行临界区的时候，原来比T3T3具有更高优先具有更高优先级的任务级的任务T2T2就不能抢占就不能抢占T3T3了。当了。当T3T3退出临界区时，退出临界区时，T3T3又恢复到其原来的又恢复到其原来的低优先级，使任务低优先级，使任务T1T1又成为最高优先级的任务。这样任务又成为最高优先级的任务。这样任务T1T1会抢占任务会抢占任务T3T3而继续获得而继续获得CPUCPU资源，而不会出现资源，而不会出现T1T1会无限期被任务会无限期被任务T2T2所阻塞。所阻塞。2023/1/嵌入式系统设计嵌入式系统设计嵌入式系统设计嵌入式系统设计优先级继承协议优先级继承协议的定义如果任务T为具有最

50、高优先级的就绪任务，任务T将获得CPU资源。在任务T进入临界区前，任务T需要首先请求获得该临界区的信号量S：w如果信号量S已经被加锁，则任务T的请求会被拒绝。n在这种情况下，任务T被称为是被拥有信号量S的任务所阻塞；w如果信号量S未被加锁，任务T将获得信号量S而进入临界区。n当任务T退出临界区时，使用临界区过程中所加锁的信号量将被解锁。n如果有其他任务因为请求信号量S而被阻塞，其中具有最高优先级的任务将被激活，处于就绪状态。2023/1/嵌入式系统设计嵌入式系统设计嵌入式系统设计嵌入式系统设计优先级继承协议任务T将保持其被分配的原有优先级不变，除非任务T进入了临界区并阻塞了更高优先级的任务。w