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

Deadline实时调度算法详解

通过上图可知，三个任务都在 deadline 之前完成了各自的任务，周而复始。也就是说，当系统中所有任务的 CPU 利用率不超过 100% 时，Deadline 调度器能够很好的满足每个任务的需求。

Deadline 调度算法实现

1. 关键数据结构

在 Linux 内核中，每种调度器都会定义一个运行队列来存储系统中的任务（进程）。Deadline 调度器则通过dl_rq结构来描述这个运行队列，其定义如下：

struct dl_rq {
    struct rb_root rb_root;      // 红黑树根节点
    struct rb_node *rb_leftmost; // 保存deadline最早到期的任务
    unsigned long dl_nr_running; // 队列中有多少个实时任务
    ...
};

从dl_rq结构的定义可以看出，Deadline 调度器使用红黑树（红黑树是一种平衡二叉树）来存储系统中的实时任务，而红黑树的键则是任务的限期（deadline）。如下图所示：

上图中的数字就是任务的 deadline。

Linux 内核通过sched_dl_entity结构体来描述一个实时任务，其中的deadline字段则表示任务的 deadline。

我们来看看sched_dl_entity结构的定义：

struct sched_dl_entity {
    struct rb_node rb_node;  // 红黑树节点
    u64 dl_runtime;          // 任务能够运行的时间
    u64 dl_deadline;         // 任务的相对限期
    u64 dl_period;           // 任务的调度周期
    u64 dl_bw;               // dl_runtime / dl_deadline
    s64 runtime;             // 任务的剩余运行时间
    u64 deadline;            // 任务的绝对限期（dl_deadline加上当前时间）
    ...
    struct hrtimer dl_timer; // 高精度定时器，用来实现任务的周期调度
};

下面介绍一下sched_dl_entity结构各个字段的作用：

1. rb_node：红黑树节点，用来将任务添加到 Deadline 运行队列中。
2. dl_runtime：任务能够运行的时间。
3. dl_deadline：任务的相对限期。
4. dl_period：任务的调度周期。
5. runtime：任务的剩余运行时间。
6. deadline：任务的绝对限期（dl_deadline 字段加上当前时间）。
7. dl_timer：高精度定时器，用来实现任务的周期性调度。

2. 实现逻辑

Deadline 调度器实现了两种调度算法：

• EDF，Early deadline first。
• CBS，Constant bindwidth server。

下面我们来介绍一下 EDF 算法的实现。

所谓EDF，即 deadline 最早到期的任务优先得到调度。在 EDF 算法实现中，调度器会通过红黑树来存储系统中的实时任务，而红黑树的键就是任务的 deadline，如图 3 所示。