最早期限优先调度算法(EDF)的特点和实现

最早期限优先调度算法（EDF）的特点和实现摘要：最早期限优先调度算法是基于优先级的动态调度方法，是最优的单处理器调度算法，具有灵活性高、能充分利用CPU计算能力的特点。但是同时也具有调度开销增大、不能确定优先级低的任务截止之间能否得到满足的缺点，从而产生了EDF算法的优化算法NEDF和DPDS，较好的解决了上述问题，平衡了CPU使用率、响应时间、公平性和截止时间的问题。关键词：任务调度；动态调度；优先级；EDF引言：随着计算机的发展，多道程序处理的出现需要强大的调度算法来对多任务进行调度，以确定多任务环境下任务的执行顺序以及占有CPU时间。相对于静态、不可抢占的调度方法，EDF的出现使之凭借灵活性高、CPU占有率高很快成为最优的单处理器调度算法。一、任务调度的基本概念在计算机发展的初期，需要使用计算机时，通常要集中在计算机所在的地方，人为的以作业的方式把工作内容一件一件的交给计算机处理，也就不存在调度的概念。随后，出现了计算机的批处理方式，计算机把作业按照先来先服务的方式进行处理，体现了一种非常简单的调度概念。随着多道程序处理方式的出现，调度逐渐变得重要和复杂起来。在多任务的实时操作系统中，调度是一个非常重要的功能，用来确定多任务环境下任务执行的顺序和获得CPU资源后能够执行的时间长度。操作系统通过一个调度程序看来实现调度功能，调度程序以函数的形式存在，用来实现操作系统的调度算法。调度程序是影响系统性能（如吞吐率、延迟时间等）的重要部分。在设计调度程序时，通常要综合考虑如下因素：CPU的使用率、输入、输出设备的吞吐率、响应时间、公平性和截止时间。这些因素之间有一定的冲突性，在设计调度程序时需要优先考虑最重要的需求，然后再各种因素之间进行折中处理。二、调度方法的分类对于大量的实时调度方法来说，主要存在以下几种划分方法：1、离线（off-line）和在线（on-line）调度根据获得调度信息的时机，调度算法可以分为离线调度和在线调度两类。对于离线调度算法，运行过程中使用的调度信息在系统运行之前就确定了，如时间驱动的调度。离线调度算法具有确定性，但缺乏灵活性，适用于特征能够预先确定，且不容易发生变化的应用。在线调度算法的调度信息则在系统运行过程中动态获得，如优先级驱动的调度（如EDF,RMS等）。在线调度算法在形成最佳调度决策上具有较大的灵活性。2、抢占（preemptive）和非抢占（non-preemptive）调度根据任务在运行过程中能否被打断的处理情况。调度算法分为抢占式调度和非抢占式调度两类。在抢占式调度方法中，正在运行的任务可能被其他任务打断。在非抢占式调度算法中，一旦任务开始运行，该任务只有在运行完成而主动放弃CPU资源，或是因为等待其他资源被阻塞的情况下才会停止运行。实时内核大都采用了抢占式调度算法，使关键任务能够打断非关键任务执行，确保关键任务的截止时间能够得到满足。相对来说，抢占式调度算法要更复杂些，且需要更多的资源，并可能在使用不当的情况下造成低优先级任务出现长时间得不到执行的情况。非抢占式调度算法常用于那些任务需要按照预先确定的顺序执行，且只有当任务主动放弃CPU资源后，其他任务才能得到执行的情况。3、静态（static）和动态（dynamic）调度根据任务优先级的确定时机，调度算法分为静态调度和动态调度两类。在静态调度算法中，所有任务的优先级在设计时已经确定下来，且在运行过程中不会发生变化（如RMS）。在动态调度算法中，任务的优先级则在运行过程中确定，并可能不断发生变化（如EDF）。静态调度算法适用于能够完全把握系统中所有任务及其时间约束（如截至时间、运行时间、优先顺序和运行过程中的到达时间）特性的情况。静态调度比较简单，但缺乏灵活性，不利于系统扩展；动态调度有足够的灵活性来处理变化的系统情况，但需要消耗更多的系统资源。三、最早期限优先调度算法（EDF）1、EDF算法的基本理解最早期限优先调度算法（EDF）是一种采用动态调度的优先级调度算法，任务的优先级根据任务的截止时间来确定。任务的截止时间越近，任务的优先级越高；任务的截止时间越远，任务额优先级越低。当有新的任务处于就绪状态时，任务的优先级就有可能需要进行调整。现通过分析如下一系列任务来理解EDF算法：任务名称到达时刻执行时间绝对时间限𝑇101030𝑇24310𝑇351025当𝑇1到达时，它是唯一等待运行的任务，因此立即开始执行。𝑇2在时刻4到达，因为𝑑2𝑑1，它的优先级高于𝑇1因而打断𝑇1抢先开始运行。𝑇3在时刻5达到，由于𝑑3𝑑2，因此𝑇3的优先级低于𝑇2，必须等待𝑇2执行完毕。当𝑇2执行完（在时刻7）以后，𝑇3开始执行（由于它的优先级高于𝑇1）。𝑇3一直运行到时刻17，此时𝑇1继续执行直到完成。2、EDF算法的基本假设EDF算法的分析是基于一系列假设的基础上的：a)没有任务非抢先的区域，并且抢先的成本是极小的；b)只有处理要求是显著的，内存、I/O和别的资源要求都可以忽略；c)所有的任务都是独立的，没有优先约束。这些假设都极大地简化了EDF的分析。假设a表明，我们可以在任何时间抢占任何任务，此后还可以还原它，这个过程没有损失，一个任务被抢占的次数不改变处理器的总工作负荷。从b可以得出，为了检查可行性，我们只需要保证足够的处理容量，以在时间期限的要求下执行任务，没有内存或者其他的约束条件而导致问题变得复杂。c则表明不存在优先约束，意味着任务的释放时间不依赖于其他任务的结束时间。但是对于部分系统不满足上述三条假设，则需要采用优先的和排斥的约束来解决相应问题。EDF算法是最优的单处理器动态调度算法，其可调度上限为100%。也就是说，如果EDF算法不能够在一个处理器上合理的调度一个任务集，那么其他所有的调度算法也不能做到。3、EDF算法的测试如果所有的任务都是周期性的，并且对应的时间限等于它们的周期，对任务集的调度性的测试是非常简单的：如果任务集的总利用率不大于1，那么任务集就可以由EDF算法在一个单处理器上进行合理的调度。对于那些任务的时间限并不全等于其周期的情况，没有简答的调度性测试。在这样的情况下，需要使用EDF算法生成一个时间表，来判断是不是在一个给定的时间区间内所有的时间限都被满足。在这种情况下EDF的一个可调度性测试如下：定义u=∑(𝑒𝑖/𝑃𝑖)𝑛𝑖=1，𝑑𝑚𝑎𝑥=max1≤𝑖≤𝑛{𝑑𝑖}以及P=lcm(𝑃1,…𝑃𝑛)（这里的“lcm”表示最小公倍数）。定义ℎ𝑇(𝑡)是任务集T中所有满足其时间限的绝对值小鱼t的任务执行时间之和。一个由n个任务构成的集合不是可行的EDF的充分必要条件是：u1或存在某个tmin{𝑃+𝑑𝑚𝑎𝑥,𝑢1−𝑢max1≤𝑖≤𝑛{𝑃𝑖−𝑑𝑖}}使得ℎ𝑇(𝑡)𝑡（其中n为任务集中任务的数量；𝑒𝑖为任务𝑇𝑖的执行时间；𝑃𝑖为周期任务的周期；𝑑𝑖为任务𝑇𝑖的相对时间限；ℎ𝑇(𝑡)为在绝对时间不迟于t的任务集合T中，所有重复的任务执行时间和。）四、EDF算法的改进（1）：NEDF算法基于优先级的调度算法在实时进程调度中使用很广泛，静态优先级调度算法根据应用的属性来分配优先级,其可控性较强,而动态优先级调度算法在资源分配和调度时具有更大的灵活性。如果结合这两种算法的优点,扬长避短,就能够对实时任务进行更合理、更高效的任务调度。利用最著名的动态优先级调度算法EDF算法的高CPU利用率、可调度较大的任务集的特点,结合静态优先级调度算法的可控性就形成了一种新的调度算法—NEDF调度算法(NewEarliestDeadlineFirst)1、NEDF算法概述NEDF算法以任务的截止期限作为任务调度的首要指标,但不是唯一的指标。当两任务的截止期限在一定的范围内时,根据任务的优先级来决定要运行的任务,这时以任务的静态优先级来选择任务,一定程度上增强了算法的可控性。确定任务的静态优先级,主要依据有以下几个。1）执行时间：以执行时间为依据,执行时间越短,静态优先级越高。2）任务周期：以任务周期为依据,任务周期越短,静态优先级越高。3）任务的CPU利用率：任务的CPU利用率为任务执行时间与任务周期的比值越高,静态优先级越高。4）任务紧急程度：根据任务的紧急程度,人为安排任务的优先级。任务越紧急,静态优先级越高。2、NEDF算法说明先假定任务的优先级均不相同，则在某个调度时刻t，NEDF算法先查找距截止期限最近的任务。这时，可能有多个任务的截止期限相等或较为接近。如果截止期限相等，则选择高优先级的任务运行。如果截止期限均不相等，且最小截止期限比次小截止期限小许多，则选择最小截止期限的任务运行。若最小截止期限与次小截止期限的差值在一定的IM值范围内，则选择高优先级的任务运行。截止期限IM值的设定应保证最高优先级任务能够如期完成，一般可取最小相对截止期限的值，以确保在最小相对截止期限的周期范围内，最高优先级任务能够优先运行。五、EDF算法的改进（2）：DPDS算法1、DPDS算法概述DPDS是在EDF算法基础上进行改进而来的，DPDS基于截止时间和优先级两个特征参数。这里的优先级指的是综合考虑任务的运行时间和迫切度而得到的一个全局优先级。这样,每个任务拥有截止时间等级和全局优先级两个参数。在系统正常工作的情况下按照最早期限优先调度算法（即EDF算法）的调度方式运行；当系统过载情况下，先对所有任务按照全局优先级分成2个组，全局优先级较高的分为一个组，全局优先级相对较低的分为另一组；优先对全局优先级高的任务进行调度，对于优先级低的任务采用后台处理算法，即在处理器空闲时调度非关键任务集中的任务。考虑到嵌入式系统资源的有限性，DPDS尽量采用比较简单的算法，防止调度算法占用过多的计算时间,影响系统整体性能。2、算法的实现DPDS任务算法主要分为3步实现：第1步：判断当前系统任务是否超负荷，如果没有超负荷，就调用EDF算法调度；否则，调用DPDS算法；第2步：对任务进行分类，将任务按照优先级进行分类，优先级高的为一个集合，称之为关键任务集；优先级相对较低的为一个集合，称为非关键任务集；每当任务中有优先级发生变化时，都要对现有的全部任务进行划分。第3步：任务调度。当前任务完成之后,必须刷新当前任务的截止时间，然后判断任务的全局优先级是否有变化，如果优先级有变化，就对所有任务按优先级重新划分集合。划分好任务优先级后优先对周期任务集中的任务实例采用EDF调度算法进行调度。只有当周期任务集没有可运行的实例时才对队列中的任务实例同样采用EDF算法进行调度运行。由此保证优先调度关键任务集中的任务。六、总结最早期限优先调度算法（EDF）作为最佳的单处理器调度算法，具有灵活性高、CPU利用率高的特点，但是同时也存在开销大、在临时过载情况下不能确定哪个任务的截止时间不能得到满足的缺点。在此基础上，提出了改进后的EDF算法：NEDF算法以及DPDS算法，具有了更好的调度性能。任务调度是实时内核的关键，是整个嵌入式系统的心脏，为了满足具体应用需求，需要我们更进一步的探索和研究。参考文献：[1]C.M.KrishnaKangG.Shin著.戴琼海译.实时系统[M].北京：清华大学出版社，2004.37-73[2]罗蕾.嵌入式实时操作系统及应用开发[M].北京：北京航空航天大学出版社，2007.184-194[3]淮晓勇，邹勇，李开树.一种开放混合实时系统的开放自适应调度算法[J].软件学报,2004.488[4]翟鸿鸣.单处理器系统的实时调度算法研究[J].微机发展,2003.99-101