基于累计价值的最小松弛度优先算法

范凯胤，王学奇，谭小虎，胡阳光，石伟文

（空军工程大学航空航天工程学院，西安 710038）

0 引言

现如今所有的网络都满足实时性，这就决定了实时调度被广泛应用在众多的领域中，这些调度策略中常采用各种基于任务某个参数或特征的方法来群定任务的优先级［1-3］。而在设计和实现实时软件的过程中，抢占多任务是一个普遍使用的结构，在满足任务实时调度的同时，抢占多任务也带来了CPU资源的浪费和增加内存的总开销［4］。因此，在保证调度质量的条件下，减少任务频繁切换是选择调度算法要考虑的。

最低松弛度优先（Least Laxity First，LLF）［5］调度算法属于动态优先级调度算法，也是一种截止时间驱动的调度算法。根据任务松弛度的大小分配优先级［6］，松弛度越小，优先级越高，每次调度时都选取松弛度最小的任务来执行。但是LLF在调度时会引起大量的任务切换，并且在有两个任务的松弛度一样的情况下会产生松弛环，造成系统死锁。系统将在这两个任务之间不停地切换直到松弛环解除。这些原因使得LLF算法并不实用，应用较少。为此，文献［7］针对LLF算法和HVDF（价值密度最大优先）算法的缺陷，综合了松弛度和价值密度这两种调度考量指标来设计优先级分配策略，提出了LVDF算法；文献［8］基于抢占阈值的思想，提出基于奖赏因子的改进最小松弛度算法，动态地给每个任务配置抢占阈值。它们都在一定程度上改善了LLF算法的性能。

基于以上分析，本文通过将HVF（最大完成价值优先）算法和LLF算法相结合的方式，提出基于累计价值的LLF算法，有效地减少LLF中不必要的切换，降低颠簸现象的发生。

1 基于累计价值的LLF算法

1.1 系统的可调度性

在一个实时系统中，需要调度的任务很多，如果处理器的处理能力不够，就会导致很多实时任务不被处理或者延迟处理，从而给系统造成难以预料的后果。

在一个单处理器的系统中，如果系统包含m个周期性的硬实时任务，每个任务的执行时间为Ci，周期时间为Ti，1≤i≤m，为保证所有的周期任务都可以得到实时调度，必须满足下面的限制条件［9］。

在多处理器调度系统中，则要满足下面的条件，该系统才可认为是可调度的。

1.2 HVF算法

该算法是从为每个任务定义价值函数的角度出发，然后根据函数值确定任务的优先等级并进行排序，相应价值函数大任务的优先级就越高。和EDF算法一样，HVF算法［10-11］在处理器资源有限的系统中的表现也是不如人意，同时在过载情况下，性能下降更加明显。

在以价值函数的累计值来判定系统任务的优先级，这就决定了价值函数的选取对算法性能的影响有着决定作用，这是该算法要解决的主要问题。

1.3 LLF算法松弛度的计算

LLF算法是根据任务的关键程度来赋予相应的优先级。其中用来衡量任务关键程度的一个重要指标就是松弛度，记任务的松弛度为Li，当前到达时间为Ri，任务的剩余执行时间为Bi，则对于周期性任务i，假设在其到达之前或者介于第j个周期执行完毕等待第j+1个周期到来的这段时间其松弛度为无穷大。而在j个周期的执行过程中，任意时刻任务的松弛度为：

式中，Li（t）不能小于0，否则任务在截止期内将无法完成调度，在每个周期的初始时刻任务的松弛度为：

在任务的调度过程中，每次都选择松弛度最小的任务执行。但是任务的松弛度会随着执行时间的增加而减小，当某个任务的松弛度减小到比当前处理器正在执行任务的松弛度小时，任务必须进行切换，转而执行该任务。

1.4 LLF算法的颠簸现象

为方便分析，定义任务的优先级为p，任务的绝对截止期限为Di，任务的价值为v。假设任务的优先级由松弛度单一决定，当Li≥0时，任务才能被调度。当系统中有3个空闲时间相近的任务、、，其初始状态为：；；。由于任务的裕度最小，所以其得到最先执行，同时在执行过程中其裕度保持不变，这时任务处于等待状态，伴随的执行，任务、的裕度不断减少，也就是优先级在增加。所以当任务、的裕度小于任务时将发生一次抢占，由3个任务的初始状态可得，任务被抢占，然后被抢占，这样不断循环，频繁发生任务的切换，在3个任务都执行完毕后，切换才会停止。图1表示了3个任务由于裕度相近，在调度过程中产生了严重的颠簸现象。

图1 LLF算法中的颠簸现象

2 LLF算法改进

由以上的分析可以知道，对LLF算法的改进是为了减少不必要的资源浪费，但这样也不能简单地采用不可抢占的方式来实现，这是因为任务的松弛度会随着时间的进行而减少，非抢占的方式容易使任务错过截至期。所以针对LLF算法的缺点以及非抢占模型的不足，为每个任务按松弛度大小分配一个优先级的同时，还赋予一个动态的累计价值，在松弛度相同的情况下，将任务的累计价值作为优先级的比较对象。这样就成为一个具有双优先级的评判方式。在任务按价值调整优先级执行完毕后，恢复原有的优先级。假设一个实时任务i的优先级是Pi，累计价值为 Vi，另一个任务j的优先级为 Pj，累计价值为Vj，在以松弛度作为优先级评定标准时，值越小相应优先级越高。任务刚进入系统时，价值Vi=0，伴随着任务的运行，Vi的值都会有不同程度的增加，随着任务越接近截止期，它所增加的价值也就越大，这样被其他任务抢占的可能性就越小。继续利用上面的例子进行分析，任务最先得到执行，伴随着该任务的执行，任务和的松弛度逐渐减小，那么相应的优先级P1和P2逐渐增大，当P1＞P0或者 P2＞P0时，按照 LLF 算法，任务将发生切换，任务或者抢占执行，经过采用累计价值策略后，任务的优先级已经提升到V0的水平，这样只有 V1＞V0或者 V2＞V0时，才可以抢占。但是随着时间的运行，任务的累计价值最大，这就导致任务和无法发生抢占，这样3个任务就相继执行了，有效地减少了颠簸现象。具体的过程如图2所示。

图2 基于累计价值的LLF算法

相应算法执行流程如图3所示。

2.1 算法可行性分析

图3 算法执行流程图

那么就有

由以上分析可得任务Ai的最差相应时间Ri为：

以上分析可知，改进的LLF算法满足调度所要求的调度准则。最小松弛度算法是基于抢占阈值的抢占和非抢占模型的演化，但是可调度性较两者好。在现实中要准确判定任务的可调度性，还必须要考虑算法动态特性和算法所带来的颠簸问题以及一些不确定的内在因素。

3 实验结果分析

采用传统LLF算法和基于累计时间价值的LLF算法来测试下页表1中任务的前后切换次数。对于价值函数，在任务首次进入系统时，Vi=0，它的值随着任务的每次执行而有着不同程度的增加，越接近截至期任务的累计价值也就越大，这样就可以防止任务被打断，在实验中选择价值函数为：

表1 受测任务集合

仿真结果如图4所示，通过改进LLF算法，可以相对减少任务间的抢占次数。很好地降低了处理器的开销，节约CPU资源。从结果可以看出，对于周期较长的任务4和任务5在执行过程中受到的抢占次数较多，所以随着测试时间的增加，周期较长的任务执行的次数就越多，被抢占的减少比率越接近25%。

图4 原LLF算法和改进的LLF算法抢占次数的比较

4 结论

本文通过对LLF算法的深入研究，针对其在实时任务裕度相近或相同情况下，存在任务间的频繁抢占，一方面浪费了处理器资源，一方面加大了开销的问题，通过引入一个累计价值函数，构成双评价系统，在裕度相同情况下，采用价值来重新评定优先级，判定是否抢占当前执行的任务，同时在执行完成后又恢复原来优先级的解决策略，来达到减少任务间频繁的上下文切换，有效避免颠簸现象。仿真结果表明，这种方法有效减少了任务间不必要的切换，节约了CPU资源。

［1］张海涛，艾云峰.基于Petri网的分布式实时嵌入式系统的调度分析［J］.吉林大学学报，2007，37（3）：616-620.

［2］万加富，李迪，叶峰，等.提高混合实时任务确定性的两级调度算法［J］.吉林大学学报，2009，39（3）：753-758.

［3］张国斌，潘金贵.基于优先级的抢占式并行调度算法设计与分析［J］.计算机科学，2007，34（7）：279-281.

［4］SAKSENA M，WANG Y.Scalable real-time system design using preemption thresholds［C］//Proceeding of the Twelfth IEEE Real-Time System Symposium.Orlando，NY：IEEE，2000：25-34.

［5］汤小丹，梁红兵，哲凤屏，等.计算机操作系统［M］.西安：西安电子科技大学出版社，2007.

［6］DERTOUZOS M L.Control Robotics：the procedural control of physical processes ［C］//IFIP Congress，Chicago，1974：807-813.

［7］高峰，吕广申.CAN总线调度算法的改进［J］.佳木斯大学学报，2011，29（2）：213-214.

［8］王斌，王遵彤.基于奖赏因子的改进最小松弛度算法［J］.电子测量技术，2011，34（10）：27-29.

［9］KRILHI R，JOHN A.Scheduling algorithms and operating systems support for real-timesystem ［J］.Proceeding of the IEEE，1994，83（1）：55-67.

［10］翟鸿鸣.单处理器系统的实时调度算法研究［J］.微机发展，2003，13（10）：99-101.

［11］李琦，巴巍.两种改进的EDF软实时动态调度算法［J］.计算机学报，2011，34（5）：943-950.