# 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 架构的各种处理，此处不再一一讲解。


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://s3.shizhz.me/linux-sched/dl-sched/logic.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.