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