EDF

前言 在实时系统的世界里，调度算法是灵魂。一个优秀的调度算法可以在同样的硬件上，让更多任务按时完成；而一个糟糕的调度算法，即使是性能过剩的CPU，也可能出现任务超时。 我第一次深刻体会到调度的重要性是在 2019 年的一个工业控制项目。当时我们用的是某款主流 RTOS，系统中有 12 个周期性任务，利用率大约在 75%。按照传统的经验法则，这是一个相当安全的数值。然而，在一次现场测试中，当某个外部设备突然产生大量数据时，系统中优先级最低的那个数据记录任务竟然连续三次错过了截止期——每一次超时都意味着一条生产数据的丢失。 问题排查了整整三天，最后我们发现：系统中高优先级的任务虽然单个执行时间不长，但它们加起来的"时间碎片"效应，导致低优先级任务连续被抢占了 150 毫秒。而这个任务的截止期只有 100 毫秒。更讽刺的是，如果我们把所有任务的优先级都设成一样，采用时间片轮转，反而不会出现这个问题。 那一天我意识到：实时调度不是简单的"优先级高先执行"这么简单。 它是一门严谨的科学，有完善的理论基础和严格的可调度性证明。 这篇文章就是我对实时调度算法的系统性总结。从最经典的速率单调（RM）算法，到最优的最早截止期优先（EDF）算法，再到 Linux 内核中 SCHED_DEADLINE 的实际实现，我会带你一步步理解实时调度的核心原理，并提供可运行的代码示例。 一、实时调度的基本概念 在深入具体算法之前，我们需要先建立一些基本概念。这些概念是理解所有实时调度算法的基础。 1.1 什么是实时系统？ 实时系统的定义很简单： 实时系统是指系统的正确性不仅取决于计算的逻辑结果，还取决于结果产生的时间。 换句话说，在实时系统中，“晚到的正确答案就是错误答案”。 实时系统通常分为两类： 硬实时系统（Hard Real-Time）：绝对不允许任何任务错过截止期，一次错过就是系统失败。例如汽车的安全气囊控制系统、飞机的飞行控制系统。 软实时系统（Soft Real-Time）：允许偶尔错过截止期，错过的后果是性能下降而非系统失败。例如视频播放器、音频处理系统。 本文讨论的调度算法主要针对硬实时系统，但其中的原理同样适用于软实时系统。 1.2 实时任务模型 在调度理论中，我们通常用一个简化的模型来描述实时任务。对于周期性任务，最经典的模型包含三个参数： τi = (Ci, Ti, Di) 其中： Ci（Computation Time）：任务最坏情况下的执行时间 Ti（Period）：任务的周期，即两次释放之间的时间间隔 Di（Relative Deadline）：任务的相对截止期，即从任务释放到必须完成的时间 在很多情况下，我们假设 Di = Ti，也就是截止期等于周期。这是一个常见但非必须的假设。 举个具体的例子： τ1 = (1, 3, 3) # 每3毫秒执行一次，需要1毫秒，3毫秒内必须完成 τ2 = (2, 5, 5) # 每5毫秒执行一次，需要2毫秒，5毫秒内必须完成 τ3 = (3, 8, 8) # 每8毫秒执行一次，需要3毫秒，8毫秒内必须完成 1....