Linux的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”。
这三个元素的关系可以见下图：
（图1）
从上图可以看出，三者之间的关系：runtime ≤ deadline ≤ period。
我们举一个实际的例子，假设系统中有三个周期性任务。为了简单起见，本例中的任务为之前面提到过的 “implicit deadline”，即 deadline 等于 period：
task runtime period
t1 1 4
t2 2 6
t3 3 8
如果三个任务都运行在同一个 cpu 上，那么 cpu 的利用率为（未达到100%）：
cpu利用率 = 1/4 + 2/6 + 3/8 = 23/24
那么这三个任务的工作状态可以如下图所示：
（图2）
通过上图可知，三个任务都在 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）。如下图所示：
（图3）
上图中的数字就是任务的 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 结构各个字段的作用：
rb_node：红黑树节点，用来将任务添加到 deadline 运行队列中。
dl_runtime：任务能够运行的时间。
dl_deadline：任务的相对限期。
dl_period：任务的调度周期。
runtime：任务的剩余运行时间。
deadline：任务的绝对限期（dl_deadline 字段加上当前时间）。
dl_timer：高精度定时器，用来实现任务的周期性调度。
2. 实现逻辑
deadline 调度器实现了两种调度算法：
edf，early deadline first。
cbs，constant bindwidth server。
下面我们来介绍一下 edf 算法的实现。
所谓edf，即 deadline 最早到期的任务优先得到调度。在 edf 算法实现中，调度器会通过红黑树来存储系统中的实时任务，而红黑树的键就是任务的 deadline，如图 3 所示。
deadline 调度器通过调用 enqueue_dl_entity() 函数来将一个实时任务添加到运行队列中，而 enqueue_dl_entity() 函数最终会调用 __enqueue_dl_entity() 函数来实现将任务添加到队列中。
我们来看看 __enqueue_dl_entity() 函数的实现：
static void __enqueue_dl_entity(struct sched_dl_entity *dl_se){ struct dl_rq *dl_rq = dl_rq_of_se(dl_se); struct rb_node **link = &dl_rq->rb_root.rb_node; struct rb_node *parent = null; struct sched_dl_entity *entry; int leftmost = 1; // 1. 通过任务的deadline，找到其在运行队列红黑树中的位置 while (*link) { parent = *link; entry = rb_entry(parent, struct sched_dl_entity, rb_node); if (dl_time_before(dl_se->deadline, entry->deadline)) link = &parent->rb_left; else { link = &parent->rb_right; leftmost = 0; } } // 2. 如果当前任务是队列中deadline最早到期的，那么缓存到运行队列的rb_leftmost字段中 if (leftmost) dl_rq->rb_leftmost = &dl_se->rb_node; // 3. 将任务添加到运行队列的红黑树中 rb_link_node(&dl_se->rb_node, parent, link); rb_insert_color(&dl_se->rb_node, &dl_rq->rb_root); // 4. 增加运行队列的任务数 inc_dl_tasks(dl_se, dl_rq);} 从上面代码可以看到，当把一个实时任务添加到运行队列的红黑树中时，是根据该任务的 deadline 来找到其在红黑树中的相应位置，然后添加到运行队列的红黑树中。任务添加成功后，会增加运行队列的任务计数器。
当进行任务切换时，deadline 调度器选择红黑树最左面的节点进行调度，其通过 pick_next_task_dl() 函数来实现，代码如下：
struct task_struct *pick_next_task_dl(struct rq *rq, struct task_struct *prev){ struct sched_dl_entity *dl_se; struct task_struct *p; struct dl_rq *dl_rq; dl_rq = &rq->dl; ... // 1. 找到 deadline 最早到期的调度实体 dl_se = pick_next_dl_entity(rq, dl_rq); // 2. 获取改调度实体对应的任务 p = dl_task_of(dl_se); ... // 3. 返回 deadline 最早到期的任务 return p;} pick_next_task_dl() 函数通过取得运行队列红黑树的最左边的节点，并返回该节点上对应的任务。
那么 deadline 调度器是怎么保证每个任务都能在其调度周期内执行呢？
每个任务都有一个高精度定时器（sched_dl_entity 结构的 dl_timer 字段），其超时时间为任务的调度周期。当定时器触发时，便会调用 dl_task_timer() 函数来处理定时器事件。我们来看看 dl_task_timer() 函数的实现：
static enum hrtimer_restart dl_task_timer(struct hrtimer *timer){ struct sched_dl_entity *dl_se = container_of(timer, struct sched_dl_entity, dl_timer); struct task_struct *p = dl_task_of(dl_se); ... // 1. 将任务添加到运行队列中 enqueue_task_dl(rq, p, enqueue_replenish); if (dl_task(rq->curr)) { check_preempt_curr_dl(rq, p, 0); } else { // 2. 进行进程调度 resched_curr(rq); } ...} dl_task_timer() 函数的主要完成以下两个步骤：
将任务重新添加到 deadline 调度器的运行队列中。
进行进程调度（在中断返回时）。
您可以使用Word查找和替换，多么酷啊？
如何用T3Ster测试IC的热特性
创新医疗保健 看人体传感器如何消除痛感
PE薄膜瑕疵在线检测仪的检测方法及特点
不锈钢管道腐蚀的常见类型及治理方法
Linux的Deadline实时调度算法
力科针对Inter-Chip和移动器件开发发布新的测试夹具
为什么电源上会有安规Y电容和X电容？
Google已在Play商店中引入了八个新类别
当今的汽车格局：复杂的标准和挑战生态系统
喷雾定量测试仪可用来测定织物的表面润湿性
宁德时代再投100亿开矿！
中天协创参加第二届安全生产领域科技成果展推介会荣获参展入场券
财付通扣钱客服电话是多少
基于机器视觉的检测案例的方法分析
瑞萨电子：以平台化创新解决方案应对物联网需求
第四季度光伏组件库存大幅下降
USB接口不够用怎么办，创基这款分线器来帮忙
电视行业价格战导致整体市场电视均价下跌，但难阻新玩家加入
主流服务器操作系统优劣完全点评
本文主要介绍 linux 的 deadline 实时调度算法。
什么是实时操作系统
实时操作系统能够保证在一定时间限制内完成特定功能的操作系统。实时操作系统有硬实时和软实时之分，硬实时要求在规定的时间内必须完成操作，这是在操作系统设计时保证的；软实时则只要按照任务的优先级，尽可能快地完成操作即可。属于硬实时操作系统的有 windriver 公司开发的 vxworks 和 blackberry 公司的 qnx 等，而 linux 则属于软实时操作系统。
deadline 调度算法原理
我们先来介绍一下 deadline 调度算法的原理。
实时系统除了要求在确定的时间期限内做出响应外，还要求在确定的时间期限内完成任务，这个确定的时间期限，我们称之为 deadline。如果系统未能在 deadline 内完成任务，那么该系统就会产生错误。
deadline 调度器定义了三个元素：
period：调度周期，即该任务需要被调度的周期时间。例如，地球围绕太阳旋转一周为一个周期，称之为一年。
runtime：每周期内的运行时间，即该任务在该调度周期内至少能够运行的时间。
deadline：每周期的截止时间，即该任务在一个调度周期内，必须在截止时间之前完成任务。在 deadline 调度器中，deadline 可以与 period 相同，称作 “implicit deadline”，deadline 也可以小于 period，称作 “constrained deadline”。
这三个元素的关系可以见下图：
（图1）
从上图可以看出，三者之间的关系：runtime ≤ deadline ≤ period。
我们举一个实际的例子，假设系统中有三个周期性任务。为了简单起见，本例中的任务为之前面提到过的 “implicit deadline”，即 deadline 等于 period：
task runtime period
t1 1 4
t2 2 6
t3 3 8
如果三个任务都运行在同一个 cpu 上，那么 cpu 的利用率为（未达到100%）：
cpu利用率 = 1/4 + 2/6 + 3/8 = 23/24
那么这三个任务的工作状态可以如下图所示：
（图2）
通过上图可知，三个任务都在 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）。如下图所示：
（图3）
上图中的数字就是任务的 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 结构各个字段的作用：
rb_node：红黑树节点，用来将任务添加到 deadline 运行队列中。
dl_runtime：任务能够运行的时间。
dl_deadline：任务的相对限期。
dl_period：任务的调度周期。
runtime：任务的剩余运行时间。
deadline：任务的绝对限期（dl_deadline 字段加上当前时间）。
dl_timer：高精度定时器，用来实现任务的周期性调度。
2. 实现逻辑
deadline 调度器实现了两种调度算法：
edf，early deadline first。
cbs，constant bindwidth server。
下面我们来介绍一下 edf 算法的实现。
所谓edf，即 deadline 最早到期的任务优先得到调度。在 edf 算法实现中，调度器会通过红黑树来存储系统中的实时任务，而红黑树的键就是任务的 deadline，如图 3 所示。
deadline 调度器通过调用 enqueue_dl_entity() 函数来将一个实时任务添加到运行队列中，而 enqueue_dl_entity() 函数最终会调用 __enqueue_dl_entity() 函数来实现将任务添加到队列中。
我们来看看 __enqueue_dl_entity() 函数的实现：
static void __enqueue_dl_entity(struct sched_dl_entity *dl_se){ struct dl_rq *dl_rq = dl_rq_of_se(dl_se); struct rb_node **link = &dl_rq->rb_root.rb_node; struct rb_node *parent = null; struct sched_dl_entity *entry; int leftmost = 1; // 1. 通过任务的deadline，找到其在运行队列红黑树中的位置 while (*link) { parent = *link; entry = rb_entry(parent, struct sched_dl_entity, rb_node); if (dl_time_before(dl_se->deadline, entry->deadline)) link = &parent->rb_left; else { link = &parent->rb_right; leftmost = 0; } } // 2. 如果当前任务是队列中deadline最早到期的，那么缓存到运行队列的rb_leftmost字段中 if (leftmost) dl_rq->rb_leftmost = &dl_se->rb_node; // 3. 将任务添加到运行队列的红黑树中 rb_link_node(&dl_se->rb_node, parent, link); rb_insert_color(&dl_se->rb_node, &dl_rq->rb_root); // 4. 增加运行队列的任务数 inc_dl_tasks(dl_se, dl_rq);} 从上面代码可以看到，当把一个实时任务添加到运行队列的红黑树中时，是根据该任务的 deadline 来找到其在红黑树中的相应位置，然后添加到运行队列的红黑树中。任务添加成功后，会增加运行队列的任务计数器。
当进行任务切换时，deadline 调度器选择红黑树最左面的节点进行调度，其通过 pick_next_task_dl() 函数来实现，代码如下：
struct task_struct *pick_next_task_dl(struct rq *rq, struct task_struct *prev){ struct sched_dl_entity *dl_se; struct task_struct *p; struct dl_rq *dl_rq; dl_rq = &rq->dl; ... // 1. 找到 deadline 最早到期的调度实体 dl_se = pick_next_dl_entity(rq, dl_rq); // 2. 获取改调度实体对应的任务 p = dl_task_of(dl_se); ... // 3. 返回 deadline 最早到期的任务 return p;} pick_next_task_dl() 函数通过取得运行队列红黑树的最左边的节点，并返回该节点上对应的任务。
那么 deadline 调度器是怎么保证每个任务都能在其调度周期内执行呢？
每个任务都有一个高精度定时器（sched_dl_entity 结构的 dl_timer 字段），其超时时间为任务的调度周期。当定时器触发时，便会调用 dl_task_timer() 函数来处理定时器事件。我们来看看 dl_task_timer() 函数的实现：
static enum hrtimer_restart dl_task_timer(struct hrtimer *timer){ struct sched_dl_entity *dl_se = container_of(timer, struct sched_dl_entity, dl_timer); struct task_struct *p = dl_task_of(dl_se); ... // 1. 将任务添加到运行队列中 enqueue_task_dl(rq, p, enqueue_replenish); if (dl_task(rq->curr)) { check_preempt_curr_dl(rq, p, 0); } else { // 2. 进行进程调度 resched_curr(rq); } ...} dl_task_timer() 函数的主要完成以下两个步骤：
将任务重新添加到 deadline 调度器的运行队列中。
进行进程调度（在中断返回时）。
您可以使用Word查找和替换，多么酷啊？
如何用T3Ster测试IC的热特性
创新医疗保健 看人体传感器如何消除痛感
PE薄膜瑕疵在线检测仪的检测方法及特点
不锈钢管道腐蚀的常见类型及治理方法
Linux的Deadline实时调度算法
力科针对Inter-Chip和移动器件开发发布新的测试夹具
为什么电源上会有安规Y电容和X电容？
Google已在Play商店中引入了八个新类别
当今的汽车格局：复杂的标准和挑战生态系统
喷雾定量测试仪可用来测定织物的表面润湿性
宁德时代再投100亿开矿！
中天协创参加第二届安全生产领域科技成果展推介会荣获参展入场券
财付通扣钱客服电话是多少
基于机器视觉的检测案例的方法分析
瑞萨电子：以平台化创新解决方案应对物联网需求
第四季度光伏组件库存大幅下降
USB接口不够用怎么办，创基这款分线器来帮忙
电视行业价格战导致整体市场电视均价下跌，但难阻新玩家加入
主流服务器操作系统优劣完全点评