一种基于任务计算密度优先的改进EDF实时调度算法研究

李 赞，黄燕挺

（电子科技大学中山学院，中山 528400）

0 引言

实时系统是采用实时调度算法处理具有时效限制的多任务处理系统。每个任务必须在规定的时间内处理完。计算机的硬件资源有限，处理能力有限，如果多个实时任务的计算需求超出了处理器能力上限，则发生任务过载情况，造成无法预料的后果。

实时任务分为周期实时任务和非周期实时任务，调度算法又分为抢占式与非抢占式调度算法，经典的调度算法中，EDF（截止时间优先）常被应用于非周期实时任务，LLF（最低松驰度优先）算法应用于周期实时任务，实时调度算法多数以动态计算的优先级来切换任务。经典的的是EDF（最早截止时间优先）和LLF（最低松驰度优先）算法，但是EDF算法存在条件的不完备性，LLF算法存在逻辑设计缺陷，在不添加必要约束条件情况时算法是难以实现的。虽然也有一些算法通过添加某些约束条件来改进EDF和LLF算法，甚至有一些算法尝试综合两种算法来实现实时调度，但是这些实时调度算法并没有明确算法的一些基本要素，本文首先分析了两种算法的不足之处，并指出实时调度算法须具有的算法要素，并提出了一个改进的EDF算法用于周期性实时任务的调度。

1 经典EDF算法与LLF调度算法的问题

经典的EDF（截止时间优先）算法常被应用于非抢占式非周期实时任务和抢占式实时任务，LLF（最低松驰度优先）算法被应用于周期实时任务，但是参考文献对这两个算法的描述都存在不完备因素，缺少必要的约束条件，并且算法也没有明确调度算法执行的时机，因此很难转化为实际算法。

1.1 EDF算法条件的不完备性

EDF（Earliest Deadline First）根据任务的截止时间确定任务的优先级，任务的截止时间越早，其优先级越高。EDF（最早截止时间优先）算法即可用于非抢占式非周期实时任务，也可应用于周期实时任务，是一种抢点式的调度算法，该算法的思想是从就绪任务队列中选取截止时间早的任务执行。经典EDF算法有缺少两个条件：第一是调度算法的执行时机，调度程序无法实现每时每刻的运行，第二是如果存在多个截止时刻相同的任务又如何处理，但是这两个缺失的条件是容易解决的。

1.2 LLF算法存在的设计逻辑问题

最低松驰度优先算法LLF缺失两个条件：第一何时执行调度算法，第二松驰度相同时的任务如何处理，LLF算法缺乏调用的时机的条件，例如下面的调度由于时机选择的不同，造成任务的调度产生随意性。图1表示两种采用LLF算法由于调度时机选择不同造成不同的调度过程。

图1 实时任务调度选择时机造成调度差异

即使补全了缺失条件LLF算法也无法实施，这是因为LLF算法存在逻辑问题，接下来分析其算法逻辑的问题。松驰度计算方法为：任务松驰度=任务完成截止时刻点-当前时刻点-任务还剩余的时长。假设前时刻点为，一个实时任务设当任务还剩余执行的时长为，任务松驰度为τ，任务完成截止时刻点为。则：=--，当该任务被系统执行了一个较短的时长Δ，任务没有结束，则时刻点变为+Δ，而任务剩余的时长为-Δ，新时刻点任务松驰度：1=-（+Δ）-（-Δ），由此可得1=，任务在经过一个较短的执行时长Δ后的松驰度保持不变仍为。所以一个实时任务A执行过程中，松驰度的值保持不变，与执行的时长Δ无关，而等待的任务B的松驰度则减小，两个任务松驰度直线变化情况如图2所示。

图2 LLF算法中实时任务A和B的构驰度变化

图2中两个任务的松驰度直线有相交点，该相交点是LLF算法逻辑问题所在。任务A与任务B松驰度值相同时，如果A继续执行则松驰度值保持不变，B任务松驰度会减小，任务B因为松驰度小于A则算法会抢占正在执行的任务A，很快松驰度颠倒后A又要抢占B，这种任务的反复切换会发在极短的时间间隔，从而产生了选择抖动，其实是无法进行选择，这种选择抖动显然是逻辑错误的，这就是LLF算法思想的缺陷。一旦出现两个或多个任务松弛度相等的情况，将会出现这几个任务之间的频繁任务切换，这种现象又称为竞争抖动。

LLF算法目的是解决调度问题，如果切换时间片无穷小，则切换次数会变得无穷多，选择悖论会使得LLF算法无法实现。因此LLF算法必须要添加限制条件才可以实施，例如指定一个间隔时长，在每个间隔时长结束后再执行LLF算法来选取要执行的任务，这是多数改进LLF算法的实现方法。即使指定了LLF算法的间隔时长，还是会存在松驰度值相同的任务，仍然要进一步确定被选定的任务。

2 改进的EDF算法设计

2.1 实时调度算法要件

一个可实施的实时调度算法须解决的问题：①执行调度算法的时机。②实现就绪任务的排序。③判断系统硬件能力是否能够满足实时任务对截止时间的要求。参考文献［1］中LLF算法它选取的时间点依据不足。实时系统中每个任务具有两个固定的属性：①就绪时间点。②完成截止时间点。任务的这两个属性是固定的。在经典文献［1］中，单处理机情况下，假定系统中有个周性期的硬实时任务HRT，任务处理时长为C，周期时长表示为P，实时系统中处理能力必须满足下面的限制条件才是可调度的：

2.2 改进的EDF算法设计原理

非周期实时任务的截止时间无特定规则，例如一个实时任务相较其它任务有特别长的截止时间，则该任务在初始调度时是可以忽略的，因此很难进行量化讨论，而系统存在两个调度算法的执行时机，①新任务到达时刻。②当前任务执行结束，添加这两个调度时机的EDF算法可适用非周期实时任务调度。对于具有若干周期实时任务的系统，每个任务的需求计算密度T可由其需要的系统处理时长C除以任务允许的响应结束时长P，P=截止时刻-到达时刻，每个实时任务相对于系统的需求计算密度由下式得出：

为了使硬件条件满足实时任务的需求，所有任务的计算密度要满足公式（1），所有实时任务的需求计算密度之和须小于1。假设系统存在有个周期实时任务，其总的需求计算密度之和为＜1，只要选取特定长的时间段，将每个周期任务看成是均匀分布的计算需求，所有任务需要的计算总时长小于该时间段长度，如果系统还能满足每个实时进程的截止时间的条件，系统只要保持满负荷处理，假设调度粒度无限细小，则每个任务的执行将被无限细分，只要保持调度分配在任务间的比率与其计算密度相同则所有任务都可顺利执行，因为总需求计算密度小于1，即小于系统满负荷能力，因此调度方案必存在。假设有一个新的周期任务X其计算密度为欲加入系统中，如果+＞1，即总需求计算密度大于1，即表示系统的计算能力小于任务总的计算需求，则任务X加入到系统会使系统超载。

由上述讨论可知任务的需求计算密度Ti是任务的重要特征，体现任务在实时调度算法中的地位，经典的EDF算法满足实时任务截止时间的要求条件，本文提出将EDF算法结合计算密度参数，首先对任务的截止时间进行排序，然后求出每个任务的需求计算密度，再依据计算密度值继续排序，并选取队首的作业执行。实际的调度算法无法在执行粒度上无限细小，为了减少不必要的任务切换，调度算法执行的时机被明确为两个：第一是新任务到达时刻，第二是当前任务结束时刻。为方便说明算法的实现，设计下面的任务控制块：

2.3 改进的任务队列的构建与任务调度

改进的EDF算法支持周期实时任务的动态增加与删除，下面分析算法对周期实时任务队列的管理流程，在新任务到达和当前任务执行结束时运行调度算法，算法首先根据截止时间对任务队列进行排序，对相同截止时间的任务计算其计算密度并进行减序排列，具有相同的截止时间和相同计算密度的任务则按入队顺序排列，排序完成后取出队首任务执行。有新增周期任务时只需对任务队列进行计算密度累加，可判断系统处理能力是否满足任务队列需求，从而决定是否允许新任务的加入，系统处理流程如图3所示。

图3 基于计算密度的改进EDF周期实时调度算法流程

通过上图的调度流程，周期实时处理系统采用改进的EDF算法能够有效管理就绪任务队列，可以实现对周期实时任务的调度，运行条件完备，逻辑设计正确，避免了LLF算法产生的竞争抖动现象，具有较高的实施价值。

3 结语

本文分析了实时系统中经典EDF算法的不完备以及LLF算法的逻辑缺陷，明确指出实时任务系统算法的一些要素，并提出了一种改进的EDF实时调度算法，该算法消除了旧EDF算法中不完备的条件，通过引入需求计算密度讨论了实时任务调度的理论可行性。算法的创新点有三点：①明确了调度算法执行的时机。②用需求计算密度可动态判断系统条件是否满足实时任务需求。③实现了就绪任务队列的排序方法。最终给出了改进EDF调度算法流程，它能避免LLF算法产生的竞争抖动现象，能有效发挥硬件资源效率，可实施性好，能够很好地处理周期性实时任务，具有较高的价值。