查看“︁最早截止时间优先调度”︁的源代码


'''最早截止时间''' ('''EDF''') 是一个[[实时操作系统]]中使用的，动态优先级的将进程放入优先队列的算法。每当一个引起调度的事件发生(任务完成等) ，将搜索出队列中最后期限最接近的进程，接下来要被执行的就是这个进程。

EDF在抢占式、单CPU的场景下是一个最优的调度算法：如果有一组互相无关的任务，每个任务都有一个到达时间、一个执行需求和一个截止时间，如果存在一个调度算法能够确保在截止时间前完成这些任务，使用EDF算法来调度这些任务将会达到这个效果。

对于调度最后期限等于其周期的周期性进程， '''EDF''' 的利用率为100％。'''EDF''' 的[http://portal.acm.org/citation.cfm?id=78285 可调度性检验]是：

: <math>U = \sum_{i=1}^{n} \frac{C_i}{T_i} \leq 1,</math>



然而，当该系统超载、会错过最后期限的进程集合很大程度上是不可预知的。在实时操作系统上，这是一个相当大的缺点。 算法也难以使用[[硬件]]实现，表达不同范围内的截止时间也是一个棘手的问题(截止时间不能比用于调度的时间粒度更为精确)。 因此， '''EDF''' 并不常用于工业实时计算机系统中。

相反，大多数实时计算机系统使用 固定优先级调度 (通常使用 [[速率单调|速率的单调调度]])。由于优先级是固定的，显然，超载时会造成的低优先级的任务会错过最后期限，而最高的优先级进程将仍然满足其最后期限。

<br />

== 例 ==
考虑在一个单处理器抢占式调度系统上的3个定期到来的进程。执行时间和到来周期如下表所示:
{| class="wikitable" cellpadding="20"
|+'''进程实现数据'''
!进程
!执行时间
!到来周期
|- align="center"
|P1
|1
|8
|- align="center"
|P2
|2
|5
|- align="center"
|P3
|4
|10
|}
在这个例子中，该单元的时间可以被认为是可调度 [[抢占式多任务处理|的时间片]]。截止时间是每个周期的进程必须在这一个周期内完成。

=== 时序图 ===
[[File:EDF Example Timing Diagram.png|缩略图|'''时序图''' 表示一个可能的时间安排的一部分。]]
在时序图中，列代表的时间片随时间增加，所有进程都在时间片0开始运行。 计时图的蓝色和白色阴影表示的每个进程的周期，颜色的变化表示最后期限到来。

由EDF调度的第一个进程是P2，因为它的周期短，因此具有最早的截止时间。 同样地，当P2完成，P1被调度，随后是P3。

在时间片5，P2和P3具有相同的截止时间：需要在时间片10前完成，所以EDF可能调度其中任何一个。

=== 利用率 ===
利用率为：

<math> \left ( \frac{1}{8} + \frac{2}{5} + \frac{4}{10} \right ) = \left ( \frac{37}{40} \right ) = 0.925 = {\mathbf{92.5\%}} </math>

由于周期的 [[最小公倍數|最小公倍数]] 是40、调度模式可在每40时间片后重复。 但是，只有这40个时间片中的37个用于P1、P2或P3的执行。 由于利用率，92.5%，是不大于100%，该系统可以用EDF调度。

== 截止时间交换 ==
EDF调度中可能出现截止时间交换问题。 一个进程可能在一个[[臨界區段|临界区]]内使用了一个共用内部资源，防止其被有一个较早的最后期限的进程抢占。 如果是这样，调度程序应该为正在运行过程中的进程分配比等待该资源的其他进程更早的截止时间。 否则有更早的最后期限的进程与可能会错过其期限。

== 与固定优先级的调度器相比较 ==
公认一个[[定优先权先发制人的调度|固定优先级的抢占式调度器]]比一个动态优先级调度器，如EDF，要容易实现。 但是，当比较固定优先级（每个线程的优先级由Rate-monotonic调度算法给出）下最佳调度的最大使用率时，EDF可以达到100％，而Rate-monotonic调度的理论最大值约为69％ 。

请注意，EDF没有对任务的周期性做出任何具体假设；因此，它可用于安排周期性和非周期性任务<ref>{{Citation|last=Buttazzo|first=Giorgio|title=Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications|publisher=Springer|place=New York, NY|year=2011|edition=Third|page=100|url=https://books.google.com/books?id=h6q-e4Q_rzgC&printsec=frontcover#v=snippet&q=%22earliest%20deadline%20first%22&f=false|accessdate=2019-10-29|archive-date=2020-08-19|archive-url=https://web.archive.org/web/20200819113656/https://books.google.com/books?id=h6q-e4Q_rzgC&printsec=frontcover#v=snippet&q=%22earliest%20deadline%20first%22&f=false|dead-url=no}}</ref> 。 

== 参见 ==

* 动态优先级调度

== 参考文献 ==
{{Reflist}}
[[Category:实时计算]]