我想知道 是否可以使用 Earliest Deadline First (EDF) 调度算法 的任何替代方案。如果是，请提供引用链接。
谢谢。
最佳答案
Deadline 调度可以分为两类:1) 实时计算社区认为的；和 2)正如调度理论界所认为的那样。类别 1 是类别 2 的子集。 大多数实时计算从业者不知道类别 2。
主要区别在于，类别 1 假设了相对简单的特殊情况，即满足或错过期限，而错过期限是失败，因此调度最优性标准是满足所有期限(所谓的“硬”实时) .最早截止日期优先 (EDF) 是最常见的第 1 类截止日期调度算法。有大量关于第 1 类截止日期安排的文献——例如，在 IEEE 实时系统研讨会的 session 记录中。一本好书是 Stankovic 等人的 Deadline Scheduling for Real-Time Systems - EDF and Related Algorithms 。
AFAIK，没有现存的实时操作系统 COTS 产品可以实现截止日期调度，尤其是 EDF。已经尝试了几种商业产品(例如，DEC、IBM)但由于各种困难而被放弃，例如将 EDF 与操作系统中的其他资源管理(例如，同步器、非调度事件)集成，同时保持向后兼容性。解决方案是从头开始设计截止日期调度(EDF 和其他算法)作为操作系统的一个组成部分。我知道有三种 COTS 实时操作系统产品可以做到这一点，但没有一个是因为与操作系统无关的组织原因进入市场的:DEC 的 Libra、IBM 的用于 PowerPC 的 OS/2(与 DEC 合作完成)，以及开放软件基金会的 OSF-1 Mk7.3a(与 DEC 和 IBM 合作完成)。一些从裸硬件向上设计和实现的研究操作系统(例如，CMU 的 Jensen 的 Alpha)已经成功地结合了截止日期调度。 Alpha 通过允许插入任意调度算法(包括 EDF 和 Utility Acrual 算法)来利用完全自由的优势。其他研究操作系统试图增强 Linux(参见乔纳坦安德森的帖子引用的 VA Tech 的 ChronOS 项目)。 ChronOS 受到基于 Linux 的限制，但也支持 Utility Accrual 调度算法。
类别 2 涵盖了截止日期调度的整个主题，其中类别 1 是更简单的子集。特别是，第 2 类承认关于截止日期的提前和迟到的概念。调度最优性标准包括最小化错过最后期限的数量、最小化平均延迟、最小化最大延迟以及许多(任何)其他标准。从技术上讲，第 2 类减去第 1 类子集是“软”实时的，尽管实时从业者甚至研究人员对术语“软”实时使用了许多不同的不精确和不准确的描述。第 2 类调度比是第 1 类调度。但是，它更现实且适用范围更广，用于许多行业(例如，运输、制造等)。比第 1 类有更多的文献。一本好的教科书是 Pindo 的 Scheduling: Theory, Algorithms, and Systems .