Deadline实时调度算法详解 深入解析Deadline实时调度算法

Deadline实时调度算法详解

如果想知道Deadline实时调度算法详解方面的知识，很不错的方法小知识，建议收藏哦！

严格来说，Linux 不是实时操作系统，但 Linux 却支持实时调度算法。

与通用调度算法（如完全公平调度算法）相比，实时调度算法更注重任务（进程）的实时性。

为什么 Linux 支持实时调度算法，却不是实时操作系统呢？

有兴趣的同学可以去网上查阅相关的文献或者资料。

本文主要介绍 Linux 的 Deadline 实时调度算法。

什么是实时操作系统

实时操作系统能够保证在一定时间限制内完成特定功能的操作系统。

实时操作系统有硬实时和软实时之分，硬实时要求在规定的时间内必须完成操作，这是在操作系统设计时保证的；软实时则只要按照任务的优先级，尽可能快地完成操作即可。

属于硬实时操作系统的有 WinDriver 公司开发的 VxWorks 和 BlackBerry 公司的 QNX 等，而 Linux 则属于软实时操作系统。

Deadline 调度算法原理

我们先来介绍一下 Deadline 调度算法的原理。

实时系统除了要求在确定的时间期限内做出响应外，还要求在确定的时间期限内完成任务，这个确定的时间期限，我们称之为 Deadline。如果系统未能在 Deadline 内完成任务，那么该系统就会产生错误。

Deadline 调度器定义了三个元素：

• period：调度周期，即该任务需要被调度的周期时间。例如，地球围绕太阳旋转一周为一个周期，称之为一年。

• runtime：每周期内的运行时间，即该任务在该调度周期内至少能够运行的时间。
• deadline：每周期的截止时间，即该任务在一个调度周期内，必须在截止时间之前完成任务。在 Deadline 调度器中，deadline 可以与 period 相同，称作 “implicit deadline”，deadline 也可以小于 period，称作 “constrained deadline”。

这三个元素的关系可以见下图：

从上图可以看出，三者之间的关系：runtime ≤ deadline ≤ period。

我们举一个实际的例子，假设系统中有三个周期性任务。为了简单起见，本例中的任务为之前面提到过的 “implicit deadline”，即 deadline 等于 period：

如果三个任务都运行在同一个 CPU 上，那么 CPU 的利用率为（未达到100%）：

CPU利用率 = 1/4 + 2/6 + 3/8 = 23/24

那么这三个任务的工作状态可以如下图所示：