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

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

本文从实时操作系统的调度功能入手，简单介绍了实时调度算法的分类和种类，并主要讨论动态优先级调度算法的特点和实现。接下来本文介绍了两类动态优先级调度算法：截止时间优先调度算法和最短空闲时间优先调度算法的定义及实现方式。然后将静态调度与动态调度进行比较，突出动态优先级调度的特点，同时指出其可能导致的优先级反转、死锁等不良后果。然后具体介绍了优先级反转的定义以及解决该问题的两种方案：采用优先级继承协议与采用优先级天花板协议。

在嵌入式的实时操作系统中，调度是一个非常重要的功能，用来确定多任务环境下任务执行的顺序和在获得CPU资源后能够执行的时间长度。

操作系统通过一个调度程序（Scheduler）来实现调度功能。调度程序以函数的形式存在，用来实现操作系统的调度算法。调度程序本身并不是一个任务，而是一个函数调用，可在内核的各个部分进行调用。调度程序是影响系统性能（如吞吐率、延迟时间等）的重要部分。在设计调度程序是、时，通常要综合考虑如下因素：

●CPU的使用率（CUP utilization）； ●输入/输出设备的吞吐率； ●响应时间（responsive time）； ●公平性； ●截止时间。

这些因素之间具有一定的冲突性。比如可通过让更多的任务处于就绪状态来提高CPU的使用率，但这显然会降低系统的响应时间。因此，调度程序的设计需要优先考虑最重要的需求，然后在各种因素之间进行折中处理。

可以把一个调度算法（Scheduling Algorithms）描述为是在一个特定时刻用来确定将要运行的任务的一组规则。从1973年Liu和Layland开始关于实时调度算法的研究工作以来

......范文范例学习参考指导.......

......word...专业技术行业资料......

（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的优先级最高，

......范文范例学习参考指导.......

......word...专业技术行业资料......

进程又再次切换到P1，而非P2：在时间单位7时，因为P1的执行时限为12，P2的执行时限为10，P3的执行时限为12，所以P2的优先级最高，进程切换到P2。后续流程以此类推。

EDF算法是最优的单处理器动态调度算法，其可调度上限为100%。在EDF调度算法下，对于给定的一组任务，任务可调度的充分必要条件为

C i

≤1 － T ∑ i

n i=1

对于给定的一组任务，如果EDF不能满足其调度性要求，则没有其他调度算法能够满

足这组任务的调度性要求。

同基于固定优先级的静态调度性比，采用基于动态优先级调度的EDF算法的显著优点在于EDF的可调度上限为100%，使CPU的计算能力能够被充分利用起来。EDF也存在不足之处，在实时系统中不容易实现，并且，同RMS相比，EDF具有更大的调度开销，需要在系统运行的过程中动态地计算确定任务的优先级。另外，在系统出现临时过载的情况下，EDF算法不能确定哪个任务的截止时间会得不到满足。为此，Liu和Layland提出了一种混合的调度算法，即大多数任务都采用RMS进行调度，只有少量任务采用EDF调度算法。尽管混合的调度算法不能达到100%的CUP使用率，大确实综合了EDF和RMS调度算法的优点，使这个调度比较容易实现。

2、最短空闲时间优先调度算法

在最短空闲时间优先调度算法（least-laxity-first scheduling）中，任务的优先级根据任务的空闲时间进行动态分配。任务的空闲时间越短，任务的优先级越高；任务的空闲时间越长，任务的优先级越低。任务的空闲时间可通过下式来表示，即

任务的空闲时间=任务的绝对截止时间－当前时间－任务的剩余时间 四、静态调度与动态调度之间的比较

动态调度的出现时为了确保低优先级任务也能被调度。这种公平性对于所有任务都同等重要的系统比较合适，对于需要绝对可预测性的系统一般不使用动态调度。这些系统中，在出现临时过载的情况下，要求调度算法能够选择最紧急的任务执行，而放弃那些不太紧急的

......范文范例学习参考指导.......

......word...专业技术行业资料......

任务。而动态调度的优先级只反映了任务的时间特性，没有把任务的紧急程度体现到优先级中去。

动态调度的调度代价通常都比静态调度高，这主要是由于在每一个调度点都需要对任务的优先级进行重新计算，而静态调度中任务的优先级则始终保持不变，不需要进行计算。

然而，要注意，动态优先级调度算法的滥用会导致优先级反转、死锁，甚至系统崩溃。 五、优先级反转

优先级反转是指由于资源竞争，低优先级的任务在执行，而高优先级的任务在等待的现象。当具有不同优先级的任务中存在相互依赖关系时，就可能发生优先级反转。

例如当系统内低优先级的任务C占用着高优先级任务A要使用的资源时，任务A只好等待任务C执行完毕，并释放该资源后才能被调度执行。这时，如果有中优先级任务B进入就绪，剥夺了任务C的CPU使用权，使得系统只有先让B运行完毕，且任务C重新运行结束并释放资源后，任务A才能运行。这样，任务A和B的优先级发生了颠倒。在这种情况下，高优先级的任务的优先级实际上已经降到了低优先级的水平，从而发生优先级反转现象，中优先级的任务抢占低优先级的任务，时间可能不确定，因此称为无界优先级反转。 类似地，当一个较高优先级的任务请求一个较低优先级任务占有的资源时，较低优先级的任务却锁住了该资源，即使较高优先级的任务就绪，它也必须等待低优先级的任务释放资源后才能继续运行。在这种情况下，低优先级的任务占用资源的时间是已知的，因此称为有界优先级反转。有界优先级反转实例当优先级发生反转时，某些任务的执行时间减少，同时其他任务的执行时间延长，导致任务错失时限，进而引起时序反常。

优先级反转是由不同优先级任务间的资源同步引起的，在实际应用中是不可避免的，但可以使用资源控制协议将其降到最低限度。解决优先级反转问题的常用方法主要有两种：采用优先级继承协议与采用优先级天花板协议。

1．优先级继承协议

为防止发生优先级的反转，多任务内核应允许动态地改变任务的优先级。如果一个任务占有被高优先级任务所请求的资源，那么，该任务的优先级会暂时提升到与被该任务阻塞的所有任务中优先级最高的任务同样的优先级水平，当该任务退出临界区时，再恢复到最初的优先级，这种方法称为优先级继承。目前，很多商业内核都具有优先级继承的功能。优先级继承协议规则如下表所示。

优先级继承协议规则

协议规则号

1

2

描述

如果资源R在使用，则任务T被阻塞；如果资源R是空闲的，则资源R被分配给任务T

当较高优先级的任务T，请求资源R时，任务T的优先级被提升到T’的优先级等级

......范文范例学习参考指导.......

......word...专业技术行业资料......

3 当任务T释放资源R后，返回到先前的优先级

优先级继承的例子如下：任务A是高优先级的，任务C是低优先级的。任务C首先获得共享资源S，而任务A也请求该资源，优先级继承协议要求任务C以任务A的优先级执行临界区，这样，任务C在执行临界区时，其优先级比它本身的优先级高，这时，中优先级的任务B不能抢占任务C了，当任务C退出临界区时，又恢复到原来的优先级，使任务A仍为最高优先级的任务，这样，任务A便不会被中优先级的任务无限期阻塞了。

在优先级继承协议中，任务T进入临界区而阻塞了更高优先级的任务，则任务T将继承被阻塞任务的优先级，直到任务T退出临界区。优先级继承协议是动态的，一个不相关的较高优先级任务仍可进行任务抢占，这是基于优先级可抢占调度模式的本性，并且任务优先级在反转期间，被提升优先级的任务的优先级可以继续被提升，即优先级继承具有传递性。虽然在优先级继承协议中，任务的阻塞时问是有界的，但可能出现阻塞链，从而会加长阻塞时间，甚至造成死锁。

2．天花板优先级协议

优先级继承协议具有死锁和阻塞链问题，而天花板优先级(CeilingPriority)协议可以解决这些问题。如果每个任务的优先级是已知的，对于给定资源(或控制该资源访问的信号量)，其优先级天花板是所有可能需要该资源的任务中最高的优先级。例如，资源R被三个任务A，B和C所需要，任务A具有优先级5，任务B具有优先级7，任务C具有优先级10，那么资源R的优先级天花板为10。

当一个任务T请求资源R时，其遵循的天花板优先级协议如下表所示。

天花板优先级协议规则

协议规则号

1 2

描述

如果资源R在使用，则任务T被阻塞

如果资源R是空闲的，则资源R被分配给任务T。如果资源R的优先级天花板比任务T的优先级高，则任务T的优先级被提升到资源R的优先级天花板等级。在任意给定时间，任务T的执行优先级等于所有它占有的资源中最高优先级天花板

当具有最高优先级天花板的资源被释放时，将任务T所占有资源的最高优先级天花板分配给它

当具有最高优先级天花板的资源被释放时，将任务T所占有资源的最高优先级天花板分配给它

3 4

使用天花板优先级协议时，一旦某任务获得该资源或暂无其他较高优先级的任务竞争同样资源时，则此任务便继承该资源的优先级天花板，即使没有其他较高优先级的任务竞争同样的资源，也要继承该资源的优先级天花板。这意味着访问某临界资源的所有任务的临界区具有同样的天花板等级。

......范文范例学习参考指导.......

......word...专业技术行业资料......

3．优先级天花板协议

优先级天花板是指控制访问临界资源的信号量的优先级天花板(简单的说，就是某个临界资源的优先级天花板)，信号量的优先级天花板是所有使用该信号量的任务中具有最高优先级的任务的优先级。在任意时刻，一个运行系统的当前优先级天花板(priority ceiling)是此时所有正在使用的资源中具有最高优先级的优先级天花板。例如，系统中有3个资源正在使用，资源R1的优先级天花板为4，资源R2的优先级天花板为6，资源R3的优先级天花板为9，则系统当前的优先级天花板为9。

在优先级天花板协议下，一个请求任务只可以被一个任务阻塞，不会发生传递阻塞(即产生阻塞链)，也不会发生死锁。当一个任务T请求资源R时，其访问控制协议规则如下表所示。

优先级天花板协议规则

协议规则号

1 2

描述

如果资源R在使用，任务T不能获得所申请的资源R，则任务T被阻塞 如果资源R空闲且任务T的优先级比当前优先级天花板的高，即任务T的优先级高于所有当前被其他任务所获取的资源的优先级天花板，则资源R分配给任务T；当任务T的优先级低于当前优先级天花板时，即使请求的资源R空闲时，任务T仍会被阻塞，即优先级天花板阻塞

如果当前天花板属于任务T当前保持的资源之一，则空闲资源R分配给任务T；反之，任务T被阻塞

任务T将按被分配的优先级执行，除非该任务在临界区执行过程中阻塞了其他高优先级的任务。如果任务T阻塞了高优先级的任务，则任务T将继承被它阻塞的具有最高优先级任务的优先级，并且按此优先级继续执行，直到它释放每个优先级天花板高于或等于任务T的优先级的资源，然后，恢复到原来的优先级

3 4

结论：在动态优先级调度算法中，会根据任务的资源需求来动态的分配任务的优先级，虽然在任务创立是赋予了优先级，但是任务的优先级可以用内核提供的调用进行改动。动态改变任务的优先级使得嵌入式应用更加适应于外部事件的灵活性，建立真正的实时响应系统。然而，在使用这种功能时，要注意不要滥用，以免导致优先级反转、死锁，甚至系统崩溃。

......范文范例学习参考指导.......