I want to know whether any alternatives to Earliest Deadline First (EDF) scheduling algorithm are available. If yes, please provide the reference links.
Deadline scheduling can be divided into two categories: 1) as thought of by the real-time computing community; and 2) as thought of by the scheduling theory community. Category 1 is a subset of category 2. Most practitioners of real-time computing are unaware of category 2.
The primary distinction is that category 1 assumes the relatively simple special case that deadlines are either met or missed, and that missing deadlines is a failure, so the scheduling optimality criterion is to meet all deadlines (so-called "hard" real-time). Earliest Deadline First (EDF) is the most common category 1 deadline scheduling algorithm. There is a vast body of literature on category 1 deadline scheduling -- e.g., in the proceedings of the IEEE Real-Time Systems Symposium. A good book is Stankovic et al.'s Deadline Scheduling for Real-Time Systems - EDF and Related Algorithms.
AFAIK, there are no extant real-time operating system COTS products that implement deadline scheduling, particularly EDF. Several commercial products have been attempted (e.g., DEC, IBM) but abandoned due to various difficulties, such as integrating EDF with other resource management (e.g., synchronizers, non-scheduled activities) in the OS while maintaining backwards compatibility. The solution is to design deadline scheduling (EDF and other algorithms) as an integral part of the OS from scratch. I am aware of three COTS real-time OS products that did that, none of which made it to the market for organizational reasons unrelated to the OS: DECs Libra, IBMs OS/2 for PowerPC (done in collaboration with DEC), and the Open Software Foundation's OSF-1 Mk7.3a (done in collaboration with DEC and IBM). Some research OSs designed and implemented from the bare hardware up (e.g., Jensen's Alpha at CMU) have succeeded at incorporating deadline scheduling. Alpha took advantage of having total freedom by allowing arbitrary scheduling algorithms to be plugged in, including EDF and Utility Acrual ones. Other research OSs have sought to augment Linux (cf. VA Tech's ChronOS project cited by Jonatan Anderson's post). ChronOS is constrained by being Linux-based but also supports Utility Accrual scheduling algorithms.
Category 2 encompasses the entire topic of deadline scheduling in general, of which category 1 is an easier subset. In particular, category 2 recognizes the concepts of earliness and tardiness with respect to a deadline. Scheduling optimality criteria include minimizing the number of missed deadlines, minimizing the mean tardiness, minimzing the maximum tardiness, and many (any) others. Technically, category 2 minus the category 1 subset is "soft" real-time," although real-time practitioners and even researchers use many different imprecise and inaccurate descriptions of the term "soft" real-time. Category 2 scheduling is more difficult than is category 1 scheduling. However, it is more realistic and more widely applicable, used in many industries (e.g., transportation, manufacturing, etc.). There is an even greater body of literature than for category 1. A good textbook is Pindo's Scheduling: Theory, Algorithms, and Systems.
SCHED_OTHER -- non real-time, best-effort scheduling
Notably absent given your question is EDF, or indeed any deadline-driven scheduler. Why not? Well, the number of applications willing to do the analysis required to make use of a deadline scheduler and the complications with integrating it with other scheduling policies may be the drivers. An LWN article does discuss deadline scheduling in Linux, circa 2009.
Some efforts have attempted to provide additional scheduling policies for Linux. A couple of good examples would be UNC's LitmusRT project and Virginia Tech's ChronOS project. LitmusRT focuses on a family of soft real-time schedulers and accompanying synchronization primitives. ChronOS is in the same domain, but is primarily focused on Utility-Accrual (UA) driven scheduling (see, e.g., this thesis and time-utility functions on Jensen's page) and synchronization policies.
There also appears to be a recent EDF scheduler implementation (which I haven't used, and hadn't noticed until answering this question.) "Evidence" EDF scheduler.
There are also commercial linux vendors which have other real-time scheduler implementations. Their availability can be a bit confusing. An example is Concurrent's RedHawk linux, which includes a time-driven scheduling policy. Details of the OS are covered in the datasheet. RedHawk is in use in a number of real-time and distributed US DoD applications.
发布评论
评论（2）
截止日期调度可以分为两类：1）实时计算界认为的； 2) 调度理论界的想法。第 1 类是第 2 类的子集。大多数实时计算从业者都不知道第 2 类。
主要区别在于，第 1 类假设相对简单的特殊情况，即满足或错过最后期限，错过最后期限就是失败，因此调度最优性标准是满足所有截止日期（所谓的“硬”实时）。最早截止时间优先 (EDF) 是最常见的 1 类截止时间调度算法。有大量关于 1 类截止时间调度的文献——例如，在 IEEE 实时系统研讨会的会议记录中。 Stankovic 等人的《实时系统的截止日期调度 - EDF 及相关》是一本好书。算法。
AFAIK，目前还没有实时操作系统 COTS 产品可以实现截止时间调度，特别是 EDF。已经尝试了几种商业产品（例如，DEC、IBM），但由于各种困难而放弃，例如将EDF与操作系统中的其他资源管理（例如，同步器、非调度活动）集成，同时保持向后兼容性。解决方案是从头开始将截止时间调度（EDF 和其他算法）设计为操作系统的组成部分。我知道三个 COTS 实时操作系统产品做到了这一点，但由于与操作系统无关的组织原因，它们都没有进入市场：DEC 的 Libra、IBM 的 OS/2 for PowerPC（与 DEC 合作完成）以及开放软件基金会的 OSF-1 Mk7.3a（与 DEC 和 IBM 合作完成）。一些从裸硬件开始设计和实现的研究操作系统（例如，CMU 的 Jensen's Alpha）已经成功地合并了截止日期调度。 Alpha 通过允许插入任意调度算法（包括 EDF 和 Utility Accrual 算法）来利用完全自由的优势。其他研究操作系统也试图增强 Linux（参见 Jonatan Anderson 的帖子中引用的 VA Tech 的 ChronOS 项目）。 ChronOS 受到基于 Linux 的限制，但也支持实用应计调度算法。
一般而言，类别 2 涵盖了截止日期调度的整个主题，其中类别 1 是一个更简单的子集。特别是，类别 2 承认截止日期方面的提前和迟到的概念。调度优化标准包括最小化错过最后期限的数量、最小化平均迟到、最小化最大迟到以及许多（任何）其他标准。从技术上讲，类别 2 减去类别 1 子集就是“软”实时”，尽管实时从业者甚至研究人员对“软”实时一词使用了许多不同的不精确和不准确的描述。类别 2 调度比类别 2 调度更困难是类别 1 调度。但是，它更现实，应用更广泛，在许多行业中都有使用（例如，运输、制造等）。文献比类别 1 还要多。一本很好的教科书是 Pindo 的 < a href="https://rads.stackoverflow.com/amzn/click/com/0387789340" rel="noreferrer">调度：理论、算法和系统。
Deadline scheduling can be divided into two categories: 1) as thought of by the real-time computing community; and 2) as thought of by the scheduling theory community. Category 1 is a subset of category 2. Most practitioners of real-time computing are unaware of category 2.
The primary distinction is that category 1 assumes the relatively simple special case that deadlines are either met or missed, and that missing deadlines is a failure, so the scheduling optimality criterion is to meet all deadlines (so-called "hard" real-time). Earliest Deadline First (EDF) is the most common category 1 deadline scheduling algorithm. There is a vast body of literature on category 1 deadline scheduling -- e.g., in the proceedings of the IEEE Real-Time Systems Symposium. A good book is Stankovic et al.'s Deadline Scheduling for Real-Time Systems - EDF and Related Algorithms.
AFAIK, there are no extant real-time operating system COTS products that implement deadline scheduling, particularly EDF. Several commercial products have been attempted (e.g., DEC, IBM) but abandoned due to various difficulties, such as integrating EDF with other resource management (e.g., synchronizers, non-scheduled activities) in the OS while maintaining backwards compatibility. The solution is to design deadline scheduling (EDF and other algorithms) as an integral part of the OS from scratch. I am aware of three COTS real-time OS products that did that, none of which made it to the market for organizational reasons unrelated to the OS: DECs Libra, IBMs OS/2 for PowerPC (done in collaboration with DEC), and the Open Software Foundation's OSF-1 Mk7.3a (done in collaboration with DEC and IBM). Some research OSs designed and implemented from the bare hardware up (e.g., Jensen's Alpha at CMU) have succeeded at incorporating deadline scheduling. Alpha took advantage of having total freedom by allowing arbitrary scheduling algorithms to be plugged in, including EDF and Utility Acrual ones. Other research OSs have sought to augment Linux (cf. VA Tech's ChronOS project cited by Jonatan Anderson's post). ChronOS is constrained by being Linux-based but also supports Utility Accrual scheduling algorithms.
Category 2 encompasses the entire topic of deadline scheduling in general, of which category 1 is an easier subset. In particular, category 2 recognizes the concepts of earliness and tardiness with respect to a deadline. Scheduling optimality criteria include minimizing the number of missed deadlines, minimizing the mean tardiness, minimzing the maximum tardiness, and many (any) others. Technically, category 2 minus the category 1 subset is "soft" real-time," although real-time practitioners and even researchers use many different imprecise and inaccurate descriptions of the term "soft" real-time. Category 2 scheduling is more difficult than is category 1 scheduling. However, it is more realistic and more widely applicable, used in many industries (e.g., transportation, manufacturing, etc.). There is an even greater body of literature than for category 1. A good textbook is Pindo's Scheduling: Theory, Algorithms, and Systems.
原生linux内核仅支持以下调度策略（针对CPU）：
SCHED_FIFO-- FIFO实时优先级调度SCHED_RR-- 循环实时优先级调度SCHED_OTHER-- 非实时、尽力而为的调度考虑到您的问题是 EDF，或者实际上是任何截止日期驱动的调度程序，显然没有。为什么不呢？愿意进行使用截止日期调度程序所需分析的应用程序数量以及将其与其他调度策略集成的复杂性可能是驱动因素。大约 2009 年，LWN 文章确实讨论了 Linux 中的截止时间调度。
一些努力尝试提供额外的调度策略对于Linux。 UNC 的 LitmusRT 项目 和 弗吉尼亚理工大学的 ChronOS 项目。 LitmusRT 专注于一系列软实时调度程序和随附的同步原语。 ChronOS 位于同一领域，但主要关注效用应计 (UA) 驱动的调度（例如，参见 本论文和时间实用函数）和同步策略。
最近似乎还有一个 EDF 调度程序实现（我没有使用过，并且在回答这个问题之前没有注意到。） "证据" EDF 调度程序。
还有一些商业 Linux 供应商拥有其他实时调度程序实现。它们的可用性可能有点令人困惑。一个示例是 Concurrent 的 RedHawk linux，其中包含时间驱动的调度策略。 数据表中介绍了操作系统的详细信息。 RedHawk 用于许多实时和分布式美国国防部应用程序。
The stock linux kernel only supports the following scheduling policies (for the CPU):
SCHED_FIFO-- FIFO real-time priority schedulingSCHED_RR-- Round-robin real-time priority schedulingSCHED_OTHER-- non real-time, best-effort schedulingNotably absent given your question is EDF, or indeed any deadline-driven scheduler. Why not? Well, the number of applications willing to do the analysis required to make use of a deadline scheduler and the complications with integrating it with other scheduling policies may be the drivers. An LWN article does discuss deadline scheduling in Linux, circa 2009.
Some efforts have attempted to provide additional scheduling policies for Linux. A couple of good examples would be UNC's LitmusRT project and Virginia Tech's ChronOS project. LitmusRT focuses on a family of soft real-time schedulers and accompanying synchronization primitives. ChronOS is in the same domain, but is primarily focused on Utility-Accrual (UA) driven scheduling (see, e.g., this thesis and time-utility functions on Jensen's page) and synchronization policies.
There also appears to be a recent EDF scheduler implementation (which I haven't used, and hadn't noticed until answering this question.) "Evidence" EDF scheduler.
There are also commercial linux vendors which have other real-time scheduler implementations. Their availability can be a bit confusing. An example is Concurrent's RedHawk linux, which includes a time-driven scheduling policy. Details of the OS are covered in the datasheet. RedHawk is in use in a number of real-time and distributed US DoD applications.