我想知道是否有最早截止时间优先（EDF）调度算法的替代方案可用。如果有，请提供参考链接。
谢谢。
谢谢。
EDF算法的替代方案
4
- Mudassir
4
除了你提到的页面链接 http://en.wikipedia.org/wiki/Scheduling_algorithm 上列出的所有算法之外，还有其他的算法吗？ - Ian Mercer
http://en.wikipedia.org/wiki/Category:Scheduling_algorithms 还有更多相关内容。 - Gareth Rees
你是在询问理论上的调度算法，还是在主流Linux内核中实现的调度算法？ - andersoj
@andersoj：如果我能得到一些例子会更好。 - Mudassir
2个回答
6
截止日期调度可分为两类：1）实时计算社区所考虑的；2）调度理论社区所考虑的。类别1是类别2的一个子集。大多数实时计算从业者不知道类别2。
主要区别在于，类别1假设截止日期要么达成要么未达成，未达成截止日期就是失败，因此调度最优性标准是满足所有截止日期（所谓的“硬”实时）。最早截止日期优先（EDF）是最常见的类别1截止日期调度算法。有大量关于类别1截止日期调度的文献资料，例如IEEE实时系统研讨会的会议记录。一本好书是Stankovic等人的《截止日期调度实时系统-EDF和相关算法》Deadline Scheduling for Real-Time Systems - EDF and Related Algorithms。
据我所知，目前没有现成的实时操作系统COTS产品实现了截止日期调度，特别是EDF。曾经有几个商业产品尝试过（例如DEC、IBM），但由于各种困难而被放弃，比如将EDF与其他资源管理（例如同步器、非调度活动）集成到操作系统中，并保持向后兼容性。解决方案是从头设计截止日期调度（包括EDF和其他算法）作为操作系统的一个组成部分。我知道有三个COTS实时操作系统产品做到了这一点，但由于与操作系统无关的组织原因，它们都没有进入市场：DEC的Libra、IBM的PowerPC上的OS/2（与DEC合作完成）、以及开放软件基金会的OSF-1 Mk7.3a（与DEC和IBM合作完成）。一些从裸机开始设计和实现的研究操作系统（例如CMU的Jensen's Alpha）已经成功地将截止日期调度纳入其中。Alpha利用了完全自由的优势，允许插入任意调度算法，包括EDF和Utility Acrual算法。其他研究操作系统试图增强Linux（例如Jonatan Anderson帖子引用的VA Tech的ChronOS项目）。ChronOS受到基于Linux的限制，但也支持Utility Accrual调度算法。
类别2涵盖了一般的截止日期调度主题，其中类别1是一个更容易的子集。特别地，类别2考虑了相对于截止日期的早期和迟到的概念。调度最优性标准包括最小化错过截止日期的数量，最小化平均迟到时间，最小化最大迟到时间以及许多其他标准。从技术上讲，类别2减去类别1子集是“软”实时，尽管实时从业者甚至研究人员使用许多不精确和不准确的术语描述“软”实时。类别2调度比类别1调度更困难。但是它更现实和更广泛适用于许多行业（例如运输、制造等）。比类别1还有更多的文献资料。一本好的教科书是Pindo的Scheduling: Theory, Algorithms, and Systems。
主要区别在于，类别1假设截止日期要么达成要么未达成，未达成截止日期就是失败，因此调度最优性标准是满足所有截止日期（所谓的“硬”实时）。最早截止日期优先（EDF）是最常见的类别1截止日期调度算法。有大量关于类别1截止日期调度的文献资料，例如IEEE实时系统研讨会的会议记录。一本好书是Stankovic等人的《截止日期调度实时系统-EDF和相关算法》Deadline Scheduling for Real-Time Systems - EDF and Related Algorithms。
据我所知，目前没有现成的实时操作系统COTS产品实现了截止日期调度，特别是EDF。曾经有几个商业产品尝试过（例如DEC、IBM），但由于各种困难而被放弃，比如将EDF与其他资源管理（例如同步器、非调度活动）集成到操作系统中，并保持向后兼容性。解决方案是从头设计截止日期调度（包括EDF和其他算法）作为操作系统的一个组成部分。我知道有三个COTS实时操作系统产品做到了这一点，但由于与操作系统无关的组织原因，它们都没有进入市场：DEC的Libra、IBM的PowerPC上的OS/2（与DEC合作完成）、以及开放软件基金会的OSF-1 Mk7.3a（与DEC和IBM合作完成）。一些从裸机开始设计和实现的研究操作系统（例如CMU的Jensen's Alpha）已经成功地将截止日期调度纳入其中。Alpha利用了完全自由的优势，允许插入任意调度算法，包括EDF和Utility Acrual算法。其他研究操作系统试图增强Linux（例如Jonatan Anderson帖子引用的VA Tech的ChronOS项目）。ChronOS受到基于Linux的限制，但也支持Utility Accrual调度算法。
类别2涵盖了一般的截止日期调度主题，其中类别1是一个更容易的子集。特别地，类别2考虑了相对于截止日期的早期和迟到的概念。调度最优性标准包括最小化错过截止日期的数量，最小化平均迟到时间，最小化最大迟到时间以及许多其他标准。从技术上讲，类别2减去类别1子集是“软”实时，尽管实时从业者甚至研究人员使用许多不精确和不准确的术语描述“软”实时。类别2调度比类别1调度更困难。但是它更现实和更广泛适用于许多行业（例如运输、制造等）。比类别1还有更多的文献资料。一本好的教科书是Pindo的Scheduling: Theory, Algorithms, and Systems。
- E. Douglas Jensen
3
股票的Linux内核仅支持以下调度策略（用于CPU）：
SCHED_FIFO-- 先进先出实时优先级调度SCHED_RR-- 轮询实时优先级调度SCHED_OTHER-- 非实时，尽力而为调度
值得注意的是，EDF或任何基于截止日期的调度器均未提供，为什么？因为愿意进行所需分析以利用截止日期调度程序的应用程序数量及将其与其他调度策略集成的复杂性可能是驱动因素。LWN文章在2009年讨论了Linux中的截止日期调度。
一些工作尝试为Linux提供额外的调度策略。其中几个好的例子是UNC的LitmusRT项目和Virginia Tech的ChronOS项目。 LitmusRT专注于一系列软实时调度程序和相应的同步原语。 ChronOS在同一领域，但主要关注实用累积（UA）驱动的调度（例如，请参见this thesis和Jensen页面上的time-utility functions）和同步策略。
还有最近出现了EDF调度程序的实现（我没有使用过，并且在回答这个问题之前也没有注意到）。"Evidence" EDF scheduler。
还有一些商业Linux供应商提供其他实时调度程序的实现，它们的可用性可能会有些混淆。例如Concurrent的RedHawk Linux，其中包括基于时间驱动的调度策略。操作系统的详细信息在数据表中介绍。RedHawk目前在许多实时和分布式美国国防部应用程序中使用。
- andersoj
1
Linux 也实现了 EDF (SCHED_DEADLINE)。请参阅 https://www.mjmwired.net/kernel/Documentation/scheduler/sched-deadline.txt。 - Bacon
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接