图解|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 调度器的运行队列中。
- 进行进程调度(在中断返回时)。
参考资料:
http://www.wowotech.net/process_management/deadline-scheduler-1.html