我想知道 是否可以使用 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 .