> For the complete documentation index, see [llms.txt](https://s3.shizhz.me/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://s3.shizhz.me/linux-sched/dl-sched/logic.md).

# 2.4.2 DL调度器 -核心代码

Deadline 调度器的实现在文件 `kernel/sched/deadline.c` 中，任务的相关参数、CBS需要使用到的各种状态信息都封装在 `sched_dl_entity` 中：

```
/* file: include/linux/sched.h */
struct sched_dl_entity {
    /*
      任务的参数，即前文提到的 runtime, deadline 与 period. 这几个参数通过系统调用
      sched_setattr 进行修改，在运行过程中保持不变。
    */
    u64 dl_runtime;  /* Maximum runtime for each instance   */
    u64 dl_deadline; /* Relative deadline of each instance  */
    u64 dl_period;   /* Separation of two instances (period) */

    u64 dl_bw;      /* dl_runtime / dl_period       */
    u64 dl_density; /* dl_runtime / dl_deadline     */

    /*
      即前文提到的 scheduling deadline 与 remaining runtime, CBS
      用来控制CPU的带宽分配。
    */
    s64 runtime;  /* Remaining runtime for this instance    */
    u64 deadline; /* Absolute deadline for this instance    */

    /* 标识该任务是否是 throttled 状态，如果是的话调度器需要在下一个 replenishment
     * time 时调整 runtime 与 deadline 属性。replenishment 操作通过定时器 dl_timer
     * 完成 */
    unsigned int dl_throttled : 1;
    /* 标识该任务是否在消耗完自己的 runtime 之前主动让出 CPU */
    unsigned int dl_yielded : 1;

    /*
      高精度定时器，例如用来为throttled任务做replenishment操作。
    */
    struct hrtimer dl_timer;
};
```

此处仅仅保留了前文中讨论到的几个重要字段。EDF算法要求调度器每次找到deadline最近的任务，为了提升效率，dl调度器使用红黑树（Red-black Tree）来组织任务，以任务的deadline作为key值。相关字段定义在运行队列 `dl_rq` 中：

```
/* kernel/sched/sched.h */

struct dl_rq {
    /* runqueue is an rbtree, ordered by deadline */
    struct rb_root_cached root;

    /* 运行队列中的任务总数 */
    unsigned long dl_nr_running;

    /* 此处删除剩余的其他字段 */
}
```

因此 dl 调度类挑选下一个任务的逻辑是很直观的：

```
/* file: kernel/sched/deadline.c */

/* 从dl_rq中取出最左边的节点，该节点即为deadline最近的任务节点，并从该节点中抽取出对应的 sched_dl_entity */
static struct sched_dl_entity *pick_next_dl_entity(struct rq *rq,
                                                   struct dl_rq *dl_rq)
{
    struct rb_node *left = rb_first_cached(&dl_rq->root);

    if (!left)
        return NULL;

    return rb_entry(left, struct sched_dl_entity, rb_node);
}

/* 实现调度类中的 pick_next_task 方法 */
static struct task_struct *pick_next_task_dl(struct rq *rq)
{
    struct sched_dl_entity *dl_se;
    struct dl_rq *dl_rq = &rq->dl;
    struct task_struct *p;

    if (!sched_dl_runnable(rq))
        return NULL;

    dl_se = pick_next_dl_entity(rq, dl_rq);
    BUG_ON(!dl_se);
    p = dl_task_of(dl_se);
    set_next_task_dl(rq, p, true);
    return p;
}
```

CBS机制的所有逻辑也都在deadline.c中，例如函数 `update_dl_entity` 用来对唤醒的任务进行校验，即完成上一节CBS算法中的第二步，其主体逻辑如下：

```
/* file: kernel/sched/deadline.c */
static void update_dl_entity(struct sched_dl_entity *dl_se)
{
    struct dl_rq *dl_rq = dl_rq_of_se(dl_se);
    struct rq *rq = rq_of_dl_rq(dl_rq);

    if (dl_time_before(dl_se->deadline, rq_clock(rq)) || /* 校验是否已经错过 deadline */
        dl_entity_overflow(dl_se, rq_clock(rq))) { /* dl_entity_overflow 用来判断带宽是否会溢出 */

        /* 更新 scheduling deadline 与 remaining runtime */
        dl_se->deadline = rq_clock(rq) + pi_of(dl_se)->dl_deadline;
        dl_se->runtime = pi_of(dl_se)->dl_runtime;
    }
}
```

函数 `sched_dl_overflow` 对整个调度器的带宽是否溢出进行校验，例如创建Deadline任务或者修改其调度参数（runtime, deadline, period）时，系统的准入机制就需要调用该函数进行逻辑判断：

```
/* file: kernel/sched/core.c */

static int __sched_setscheduler(struct task_struct *p,
                                const struct sched_attr *attr, bool user,
                                bool pi)
{
    /* 省略前面部分代码 */

    /* 对于 dl 任务，如果此次修改会导致调度器的带宽溢出，则报错 */
    if ((dl_policy(policy) || dl_task(p)) &&
        sched_dl_overflow(p, policy, attr)) {
        retval = -EBUSY;
        goto unlock;
    }


    /* 省略后面部分代码 */
}
```

该文件中还包括很多其他逻辑，例如针对 SMP 架构的各种处理，此处不再一一讲解。