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

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