“在这套运行资格之上，偶发任务与作业截止期进一步规定每次释放的服务上界、截止窗口与最小到达间隔。最早截止期优先比较每份作业的绝对截止点，并用区间需求判断所有允许到达是否来得及；这比只观察一次派…”
形式陈述
选择绝对截止点最早的就绪作业
在单核可抢占偶发任务模型理路偶发任务与作业截止期Sporadic task model · Constrained deadline task · 实时作业模型用最坏执行需求、相对截止期和最小释放间隔描述一族允许的作业流，区分单次轨迹、全到达保证与过期处理。中，EDF在每个选择时刻运行绝对截止点d最小的未完成就绪作业。这里比较r+D，不是相对期限D，也不是剩余执行量。新作业到达时，若它的d更早，就抢占当前作业；截止点相同按固定任务名、作业序破同值，本页采用A、B、C顺序。
没有就绪作业才空闲。调度器无需预知未来释放，也无需根据真实剩余服务猜测谁更短；实际完成事件会通知它何时移除作业。核验器为了推进事件，知道输入的服务量，但选择函数不读取该量。
什么长度的窗口装不下
对任务τᵢ，长度t的任意窗口内，既在窗口开始之后释放、又必须在窗口结束前完成的作业最多有
于是定义处理器需求界
本页的无锁、无开销、独立可抢占模型中，任务集可行，当且仅当对所有t≥0有dbf(t)≤t；条件成立时EDF能让每条允许作业流都按时。[1, §2，Theorem 1]
“窗口内的需求”只计释放和截止同时落入窗口的作业。一个早已释放、截止还很远的作业，可以借用窗口之外的时间，不能把它的全部C机械加到任意短窗口。
直觉
数作业时，最后一个释放必须来得及等D
若t<Dᵢ，连一份完整作业窗都放不下，需求为0。否则最早可在窗口起点释放第一份，以后每隔Tᵢ释放；最后一次必须不晚于t−Dᵢ，所以份数为1+⌊(t−Dᵢ)/Tᵢ⌋。各任务可独立选择这样的同步最密释放，因此相加是能达到的需求界，不只是松估计。
若某t满足dbf(t)>t，让所有任务在0首次释放、随后按各T最密释放，取deadline≤t的作业。它们的服务都必须装进[0,t]，总量却大于t；这直接给出任何政策都无法满足的证书。
EDF第一次失败，必能找到超载窗口
反过来，假设EDF第一次在d错过某个截止点。只看deadline≤d的作业，从d向前找这一组作业持续未清空的最后一段忙区间[s,d]：起点之前它们没有待处理工作，或s就是系统开始0。
这段里EDF不会运行deadline>d的作业，也不会空闲；否则当时deadline≤d的就绪工作必为空，s还可以向后移。区间里需要服务的相关作业都在s及之后释放，不存在从s以前带来的未完成相关作业，否则s就不是这段的起点。
到d仍有相关作业没做完，说明它们总需求严格大于d−s；它们又都在[s,d]释放且截止于d前，所以总需求不超过dbf(d−s)。因此dbf(d−s)>d−s，与假设矛盾。这个忙区间论证同时解释了EDF为什么在本模型中具有可行性最优性，而不只是一条好用的启发式。
例子与边界
H=20的完整需求表
沿用A=(1,3,4)、B=(2,5,5)、C=(2,7,10)。这里每行列出t之前必须完成的最密作业份数。
| t | n_A | n_B | n_C | dbf(t) | 容量t |
|---|---|---|---|---|---|
| 3 | 1 | 0 | 0 | 1 | 3 |
| 5 | 1 | 1 | 0 | 3 | 5 |
| 7 | 2 | 1 | 1 | 6 | 7 |
| 10 | 2 | 2 | 1 | 8 | 10 |
| 11 | 3 | 2 | 1 | 9 | 11 |
| 15 | 4 | 3 | 1 | 12 | 15 |
| 17 | 4 | 3 | 2 | 14 | 17 |
| 19 | 5 | 3 | 2 | 15 | 19 |
| 20 | 5 | 4 | 2 | 17 | 20 |
全部不超过容量。同步轨迹开始为A₀[0,1)、B₀[1,3)、C₀[3,4)、A₁[4,5)、C₀[5,6)。在5，B₁到达且d=10，C₀仍有更早的d=7，所以先完成C₀。固定任务优先级则会在5换去B，正是两者出现差异的地方。
为什么只检查有限个点就够
整数T使H=lcm(T₁,…,Tₙ)有限。由于0<Dᵢ≤Tᵢ，t≥0时有⌊(t−Dᵢ)/Tᵢ⌋+1≥0，故
特别地dbf(H)=HU。若U>1，H本身就是不可行窗口；若U≤1，把任意t写成qH+r（0≤r<H），便有
因此只需检查[0,H]。该区间内dbf只在Dᵢ+kTᵢ处向上跳；两跳之间dbf不变而t增长，最危险的是跳点本身。检查所有这些点并加入H即可覆盖全部实数长度。这个证明依赖约束截止期；不能直接给D>T也套同一周期差分起点。
利用率判据的正确范围
若所有Dᵢ=Tᵢ，dbf(t)=Σ⌊t/Tᵢ⌋Cᵢ≤tU，所以U≤1已经充分；必要性仍由长期服务容量得到。这是经典隐含截止期EDF结论。[2, §7，Theorem 7]
若改成两任务(2,2,10)，U虽为2/5，dbf(2)=4却超过2。增加重试或换一个破同值顺序都没有用：这是输入需求不可行，不是实现的排序失误。
抢占条件也不可省。单次作业X在0释放，c=4、d=10；Y在1释放，c=1、d=2。可抢占EDF让X运行[0,1)、Y运行[1,2)，随后继续X；若X一旦开始必须完整运行，Y就错过2。多核、锁依赖、非抢占段和缓存开销也不自动继承本页定理。
推论与应用
调度、判定与证书是三个成本
实际选择可用优先队列理路优先队列Priority queue · Priority queue ADT按键的优先次序反复访问并移除当前最小元素的抽象数据类型。保存键(d,任务名,作业序)。每次释放入队、完成出队或抢占后的重入队为O(log(1+J))，处理J个已给定作业可用O(1+J log(1+J))事件开销；这里无自挂起，每次新释放至多触发一次抢占。输出K段轨迹另外占O(1+K)空间。
下载器的无锁执行核心使用这个堆。它还保存截止事件，按同刻完成优先的规则检查迟到；作业输入排序与证书记录也计入上述量级。若输入还列出n个任务，其中一些没有作业，校验任务表另需O(n)时间和空间，合计O(1+n+J log(1+J))时间。独立的证书验证会扫描所有段和作业，不能把穷举oracle的指数工作混入调度器成本。
有限需求检查不一定便宜。令Q=ΣᵢH/Tᵢ，先生成并排序至多Q+1个候选点，再每点求n项需求，简单实现需O(n+Q log(1+Q)+nQ)整数操作、O(n+Q)工作空间。H可能随输入位长指数增长；保存全部表行还要O(1+nQ)个整数的输出空间，因为每行附n个任务份数；实际大整数乘除、最小公倍数计算和这些整数的位成本另计。有限判据不等于位模型多项式算法。
审核失败时，保留容量差
返回失败点t时，同时输出每任务份数、总需求与容量；这些份数连同C/D/T可以重建从0开始的同步作业清单，无需为巨大的H把每份作业都存进报告。别人不用相信调度器，就能检验dbf(t)>t。返回成功时，保存C/D/T、H、U及全部检查点，有限检查的覆盖性由上面的证明承担。
若分析预算不足以枚举巨大的H，应返回“尚未完成判定”，不能把当前已检查前缀当作全部可调度。截止期证书终点分别保留数学成功、数学失败和计算预算不足这三种出口。
参考资料
- Lipari、George、Bini、Bertogna，On the Average Complexity of the Processor Demand Analysis for Earliest Deadline Scheduling，2013，§2，印刷pp.76–77（PDF第80–81页），式(1)–(3)及Theorem 1；§5说明超周期检查点数量。本文展开计数、忙区间及超周期覆盖证明，不实现文中的约束消除优化。
- Liu、Layland，Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment，1973，§7，pp.55–58：按当前deadline动态赋优先级及隐含截止期利用率结论。本页显式区分相对与绝对期限。