动态优先级调度算法的特点与实现.docVIP

......word...专业技术行业资料...... ......范文范例学习参考指导....... 动态优先级调度算法的特点和实现 摘要：本文从实时操作系统的调度功能入手，简单介绍了实时调度算法的分类和种类，并主要讨论动态优先级调度算法的特点和实现。接下来本文介绍了两类动态优先级调度算法：截止时间优先调度算法和最短空闲时间优先调度算法的定义及实现方式。然后将静态调度与动态调度进行比较，突出动态优先级调度的特点，同时指出其可能导致的优先级反转、死锁等不良后果。然后具体介绍了优先级反转的定义以及解决该问题的两种方案：采用优先级继承协议与采用优先级天花板协议。 关键词：嵌入式系统 动态优先级 调度算法 优先级反转 在嵌入式的实时操作系统中，调度是一个非常重要的功能，用来确定多任务环境下任务执行的顺序和在获得CPU资源后能够执行的时间长度。 操作系统通过一个调度程序（Scheduler）来实现调度功能。调度程序以函数的形式存在，用来实现操作系统的调度算法。调度程序本身并不是一个任务，而是一个函数调用，可在内核的各个部分进行调用。调度程序是影响系统性能（如吞吐率、延迟时间等）的重要部分。在设计调度程序是、时，通常要综合考虑如下因素： ●CPU的使用率（CUP utilization）； ●输入/输出设备的吞吐率； ●响应时间（responsive time）； ●公平性； ●截止时间。 这些因素之间具有一定的冲突性。比如可通过让更多的任务处于就绪状态来提高CPU的使用率，但这显然会降低系统的响应时间。因此，调度程序的设计需要优先考虑最重要的需求，然后在各种因素之间进行折中处理。 可以把一个调度算法（Scheduling Algorithms）描述为是在一个特定时刻用来确定将要运行的任务的一组规则。从1973年Liu和Layland开始关于实时调度算法的研究工作以来（1973年，Liu和Layland发表了 一篇名为“Scheduling Algorithms for Multiprogramming in a Hard Real-Time Environment”的论文），相继出现了许多调度算法和方法。 对于大量的实时调度方法而言，存在着以下几类主要的划分方法： ●离线（off-line）和在线（on-line）调度； ●抢占（preemptive）和非抢占（non-preemptive）调度； ●静态（static）和动态（dynamic）调度； ●最佳（optimal）和试探性（heuristic）调度。 以下主要讨论动态优先级调度算法的特点和实现。 一、动态优先级调度算法的定义 优先级驱动策略指按照任务的优先级的高低确定任务的执行顺序。根据任务优先级的确定时机，调度算法分为静态调度和动态调度两类。在静态调度算法中，所有任务的优先级在设计时就确定下来了，且在运行过程中不会发生变化（如RMS）。在动态调度算法中，任务的优先级则在运行过程中确定，并可能不断地发生变化（如EDF）。静态调度算法适用于能够完全把握系统中所有任务及其时间约束（如截止时间、运行时间、优先顺序和运行过程中的到达时间）特性的情况。静态调度比较简单，但是缺乏灵活性，不利于系统扩展；动态调度有足够的灵活性来处理变化的系统情况，但是需要消耗更多的系统资源。 在动态调度中，任务的优先级可根据需要进行改变，也可能随着时间按照一定的策略自动发生变化。 二、动态优先级调度算法的分类 1、截止时间优先调度算法 RMS调度算法（Rate-Monotonic Scheduling algorithm，比率单调调度算法）的CPU使用率比较低，在任务比较多的情况下，可调度上限为68%。Liu和Layland又提出了一种采用动态调度的、具有更高CPU使用率的调度算法——截止时间优先调度算法EDF（Earliest Deadline First）。在EDF中，任务的优先级根据任务的截止时间来确定。任务的绝对截止时间越近，任务的优先级越高；任务的绝对截止时间越远，任务的优先级越低。当有新的任务处于就绪状态时，任务的优先级就有可能需要进行调整。同RMS一样，Liu和Layland对EDF算法的分析也是在一系列假设的基础上进行的。在Liu和Layland的分析中，EDF不要求任务为周期任务，其他假设条件与RMS相同。 例如在系统中有3个进程需要执行，分别为P1、P2、P3，其执行需花费的时间各为1、2、1l，而执行周期为3、5、4，在时间单位4时，因为P1的执行时限为6，P2的执行时限为10，P3的执行时限为8，所以P1的优先级最高，进程切换到P1：在时间单位6时，因为P1的执行时限为9，P2的执行时限为10，P3的执行时限为12，所以P1的优先级最高，进程又再次切换到P1，而非P2：在时间