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

PAGE\*MERGEFORMAT5

最早截止期优先调度算法（EDF）的特点及实现

1引言
随着计算机的发展，多道程序处理的出现需要强大的调度算法来对多任务进行调度，以确定多任务环境下任务的执行顺序以及占有CPU时间。相对于静态、不可抢占的调度方法，EDF的出现使之凭借灵活性高、CPU占有率高很快成为最优的单处理器调度算法。

2任务调度的基本概念
在计算机发展的初期，需要使用计算机时，通常要集中在计算机所在的地方，人为的以作业的方式把工作内容一件一件的交给计算机处理，也就不存在调度的概念。随后，出现了计算机的批处理方式，计算机把作业按照先来先服务的方式进行处理，体现了一种非常简单的调度概念。随着多道程序处理方式的出现，调度逐渐变得重要和复杂起来。
在多任务的实时操作系统中，调度是一个非常重要的功能，用来确定多任务环境下任务执行的顺序和获得CPU资源后能够执行的时间长度。操作系统通过一个调度程序看来实现调度功能，调度程序以函数的形式存在，用来实现操作系统的调度算法。
调度程序是影响系统性能（如吞吐率、延迟时间等）的重要部分。在设计调度程序时，通常要综合考虑如下因素：CPU的使用率、输入、输出设备的吞吐率、响应时间、公平性和截止时间。这些因素之间有一定的冲突性，在设计调度程序时需要优先考虑最重要的需求，然后再各种因素之间进行折中处理。

3调度方法的分类
对于大量的实时调度方法来说，主要存在以下几种划分方法：
1、离线（off-line）和在线（on-line）调度
根据获得调度信息的时机，调度算法可以分为离线调度和在线调度两类。对于离线调度算法，运行过程中使用的调度信息在系统运行之前就确定了，如时间驱动的调度。离线调度算法具有确定性，但缺乏灵活性，适用于特征能够预先确定，且不容易发生变化的应用。在线调度算法的调度信息则在系统运行过程中动态获得，如优先级驱动的调度（如EDF,RMS等）。在线调度算法在形成最佳调度决策上具有较大的灵活性。
2、抢占（preemptive）和非抢占（non-preemptive）调度
根据任务在运行过程中能否被打断的处理情况。调度算法分为抢占式调度和非抢占式调度两类。在抢占式调度方法中，正在运行的任务可能被其他任务打断。在非抢占式调度算法中，一旦任务开始运行，该任务只有在运行完成而主动放弃CPU资源，或是因为等待其他资源被阻塞的情况下才会停止运行。实时内核大都采用了抢占式调度算法，使关键任务能够打断非关键任务执行，确保关键任务的截止时间能够得到满足。相对来说，抢占式调度算法要更复杂些，且需要更多的资源，并可能在使用不当的情况下造成低优先级任务出现长时间得不到执行的情况。非抢占式调度算法常用于那些任务需要按照预先确定的顺序执行，且只有当任务主动放弃CPU资源后，其他任务才能得到执行的情况。
3、静态（static）和动态（dynamic）调度
根据任务优先级的确定时机，调度算法分为静态调度和动态调度两类。在静态调度算法中，所有任务的优先级在设计时已经确定下来，且在运行过程中不会发生变化（如RMS）。在动态调度算法中，任务的优先级则在运行过程中确定，并可能不断发生变化（如EDF）。静态调度算法适用于能够完全把握系统中所有任务及其时间约束（如截至时间、运行时间、优先顺序和运行过程中的到达时间）特性的情况。静态调度比较简单，但缺乏灵活性，不利于系统扩展；动态调度有足够的灵活性来处理变化的系统情况，但需要消耗更多的系统资源。

4最早截止期优先调度算法（EDF）理论分析
1、EDF算法的基本理解
最早截止期优先调度算法（EDF）是一种采用动态调度的优先级调度算法，任务的优先级根据任务的截止时间来确定。任务的截止时间越近，任务的优先级越高；任务的截止时间越远，任务额优先级越低。当有新的任务处于就绪状态时，任务的优先级就有可能需要进行调整。
现通过分析如下一系列任务来理解EDF算法：
任务名称到达时刻执行时间绝对时间限
T101030
T24310
T351025

当T1到达时，它是唯一等待运行的任务，因此立即开始执行。T2在时刻4到达，因为d2<d1，它的优先级高于T1因而打断T1抢先开始运行。T3在时刻5达到，由于d3>d2，因此T3的优先级低于T2，必须等待T2执行完毕。当T2执行完（在时刻7）以后，T3开始执行（由于它的优先级高于T1）。T3一直运行到时刻17，此时T1继续执行直到完成。
2、EDF算法的基本假设
EDF算法的分析是基于一系列假设的基础上的：
(1)没有任务非抢先的区域，并且抢先的成本是极小的；
(2)只有处理要求是显著的，内存、I/O和别的资源要求都可以忽略；
(3)所有的任务都是独立的，没有优先约束。
这些假设都极大地简化了EDF的分析。假设1表明，我们可以在任何时间抢占任