前言

由于 CFS 的实现原理比较重要这里单独拎出来。
Linux 调度器的实现主要由下面四个核心功能:

  • 时间记账
  • 进程选择
  • 调度器入口
  • 睡眠和唤醒

这一篇文章主要讲时间记账进程选择。下一篇文章Linux 调度器的实现(二)——调度器入口和睡眠和唤醒将主要讲解调度器入口睡眠和唤醒.

4、Linux 调度的实现

4.1 时间记账

4.1.1 调度器实体结构(struct sched_entity)

  1. CFS 不再有时间片的概念,但也必须维护每个进程的时间记账
  2. CFS 通过调度器实体结构 struct_sched_entity (linux/sched.h)来追踪进程运行进行记账
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 struct sched_entity {
struct load_weight load;
struct rb_node run_node;
struct list_head groupnode;
unsigned int on_rq;
u64 exec_start;
u64 sum_exec_runtime;
u64 vruntime;
u64 prev_sum_exec_runtime;
u64 last_wakeup;
u64 avg_overlap;
u64 nr_migrations;
u64 start_runtime;
u64 avg_wakeup;
/ * 这里省略了很多统计变量,只有在设置了CONFIG_SCHEDSTATS时才启用这些变量 */
};
  1. 调度器实体结构作为一个名为 se 的成员变量,嵌入在进程描述符 struct task_struct内。关于进程描述符struct task_struct 可以查看前面一篇文章的介绍

关于 struct_sched_entitystruct task_struct 以及 rbtree 的关系如下图:
进程和红黑树的结构关系

4.1.2 虚拟实时(vruntime)
  1. 我们可以看到该结构体中有一个 vruntime 变量,vruntime 变量存放进程虚拟运行时间,该运行时间(花在运行上的时间和)的计算是经过了所有可运行进程总数的标准化(或者说是被加权的)
  2. 虚拟时间是以 ns 为单位的,所以 vruntime 不再和定时器节拍不再相关
  3. 虚拟运行时间可以帮我们逼近 CFS 模型追求的“理想多任务处理器”。 如果我们真有这样一个处理器,我们就不再需要 vruntime 了。因为优先级相同的所有进程的虚拟运行时间都是相同的——所有处理器都将接收到相等的处理器份额。但是因为处理器无法实现完美的多任务,它必须依次运行每个任务。因此使用 vruntime 变量来记录一个进程到底运行了多长时间以及它还应该再运行多久。
  4. 记账功能在 linux/sched_fair.cupdate_curr()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
static void update_curr(struct cfs_rq *cfs_rq)
{
struct sched_entity *curr = cfs_rq->curr;
u64 now = rq_of(cfs_rq)->clock_task;
unsigned long delta_exec;

if (unlikely(!curr))
return;

/*
* Get the amount of time the current task was running
* since the last time we changed load (this cannot
* overflow on 32 bits):
*/
/*获得从最后一次修改负载后当前任务所占用的运行总时间(在32位系统上这不会溢出)*/
delta_exec = (unsigned long)(now - curr->exec_start);
if (!delta_exec)
return;

__update_curr(cfs_rq, curr, delta_exec);
/*更新exec_start*/
curr->exec_start = now;

if (entity_is_task(curr)) {
struct task_struct *curtask = task_of(curr);

trace_sched_stat_runtime(curtask, delta_exec, curr->vruntime);
cpuacct_charge(curtask, delta_exec);
account_group_exec_runtime(curtask, delta_exec);
}

account_cfs_rq_runtime(cfs_rq, delta_exec);
}
  1. update_curr() 计算当前进程的执行时间,并且将其存放在变量 delta_exec 中。然后它又将运行时间传给了 __update_curr() 函数,由后者再根据当前进程可运行总数对运行时间进行加权计算。最终将上述的权重值与当前运行进程的 vruntime 相加。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*
更新当前任务的运行时统计数据。跳过不再调度类中的当前任务
*/
static inline void
__update_curr(struct cfs_rq *cfs_rq, struct sched_entity *curr,
unsigned long delta_exec)
{
unsigned long delta_exec_weighted;

schedstat_set(curr->statistics.exec_max,
max((u64)delta_exec, curr->statistics.exec_max));

/*增加进程的总的运行时间*/
curr->sum_exec_runtime += delta_exec;
schedstat_add(cfs_rq, exec_clock, delta_exec);
delta_exec_weighted = calc_delta_fair(delta_exec, curr);

/*随着进程的运行,vruntime会增加,在红黑树中的位置越靠右*/
curr->vruntime += delta_exec_weighted;
update_min_vruntime(cfs_rq);
}
  1. update_cur() 是由系统定时器周期性调用的,无论是在进程处于可运行状态,还是被堵塞处于不可运行状态。根据这种方式 vruntime 可以准确地测量给定进程地运行时间,而且可以知道谁应该是下一个被运行地进程。

4.2 进程选择

  1. 前面我们说到若存在一个完美地多任务处理器,所有可运行进程地 vruntime 值将一致。但是事实上我们没有找到一个完美地多任务处理器,因此CFS 试图利用一个简单地规则去均衡进程的虚拟运行时间当 CFS 选择 下一个运行进程时,它会挑选一个 vruntime 最小的进程。这就是 CFS 的核心算法选择一个具有最小 vruntime 值的进程。
  2. CFS 使用红黑树来组织可运行进程队列,并利用其找到最小 vruntime 值的进程。在 Linux 中红黑树称为 rbtree,它是一个自平横二叉搜索树【将在后面展开讨论】
4.2.1 挑选下一个任务
  1. 我们先假设,系统中有那么一个红黑树存储了系统中所有可运行的进程,其中节点的键值是可运行进程的虚拟时间。
  2. CFS 调度器选取待运行的下一个进程,是所有进程 vruntime 最小的那个,它对应的便是在树中最左侧的叶子节点.也就是我们从树根节点沿着左子节点向下找,一直找到叶子节点,这样我们便找到了 vruntiem 最小的进程。
  3. CFS 的进程选择算法可以总结为:运行 rbtree 中最左叶节点存储的那个进程。实现算法函数是 __pick_next_entity() (linux/sched_fair.c):
1
2
3
4
5
6
7
8
9
static struct schedentity *__pick_next_entity(struct cfs_rq *cfs_rq)
{
struct rb_node *left = cfs_rq->rb_leftmost;

if (!left)
return NULL;

return rb_entry(left, struct sched_entity, run_node) ;
}

注意:
__pick_next_entity() 函数本身并不会遍历找到最左叶子节点,因为该值已缓存在 rb_leftmost 字段中,虽然红黑树我们可以在O(nlogn)O(nlog_n)时间复杂度内找到最左叶子节点,但是更加方便的做法是把它存储起来。
如果这个函数返回为 NULL ,就说明没有叶子节点也就是没有任何可运行进程,这个时候 CFS 调度器会选择 idle 任务运行。

4.2.2 向树中加入进程

  1. CFS 将进程加入 rbtree 中,以及缓存最左叶子节点。这一切发生在进程变为可运行状态(被唤醒)或是调用 fork() 创建进程后。
  2. enqueue_entity() 函数实现了这一目的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
static void enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
{
/**
* 通过调用 update_cur(),在更新 min_vruntime 之前更新规范化的 `vruntime`
**/
if (!(flags & ENQUEUE_WAKEUP) || (flags & ENQUEUE_WAKING))
se->vruntime += cfs_rq->min_vruntime;
/**
* 更新当前任务的运行时统计数据
**/
update_curr(cfs_rq);
enqueue_entity_load_avg(cfs_rq, se, flags & ENQUEUE_WAKEUP);
account_entity_enqueue(cfs_rq, se);

if (flags & ENQUEUE_WAKEUP) {
place_entity(cfs_rq, se, 0);
}

if (se != cfs_rq->curr)
__enqueue_entity(cfs_rq, se);
se->on_rq = 1;
}
  1. 该函数更新完运行时统计数据后,调用 __enqueue_entity() 进行繁重的插入操作,把数据项真正的插入到红黑树中。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
struct rb_node **link = &cfs_rq->tasks_timeline.rb_node;
struct rb_node *parent = NULL;
struct sched_entity *entry;
int leftmost = 1;
//在红黑树中查找合适的位置
while (*link) {
parent = *link;
entry = rb_entry(parent, struct sched_entity, run_node);
//并不关心冲突,具有相同节点的键值呆在一起
if (entity_before(se, entry)) {
link = &parent->rb_left;//向左走
} else {
link = &parent->rb_right;//向右走
leftmost = 0;
}
}
//维护一个缓存存放最左叶子节点
if (leftmost)
cfs_rq->rb_leftmost = &se->run_node;

rb_link_node(&se->run_node, parent, link);//插入
rb_insert_color(&se->run_node, &cfs_rq->tasks_timeline);//更新树的平衡
}
  1. 我们看看它的插入函数
  • while() 循环中遍历树以及寻找合适的匹配键值,该值就是被插入进程的 vruntime.
  • 平衡二叉树的基本规则是,如果键值小于当前节点的键值,则需转向树的左分支;相反如果大于当前节点的键值,则转向右分支。如果一旦走过右边分支,哪怕一次,也说明插入的进程不会是新的最左节点,因此可以设置 leftmost 为0。如果一直都是向左移动,那么 leftmost 维持1,这说明我们有一个新的最左节点,并且可以更新缓存——设置 rb_lestmost 指向被插入的进程.
  • 当我们沿着一个方向和一个没有子节点的节点(叶子节点)比较后:如果 link 是 NULL,则循环随之终止。
  • 当循环退出后,接着在父节点上调用 rb_link_node(),以使得新插入的节点成为其子节点
  • 最后函数 rb_insert_color() 更新树的自平衡相关属性

4.2.3 从树中删除进程

  1. 删除动作发生在进程堵塞(变为不可运行状态)或终止时(运行结束)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
static void
dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
{
/*
* 更新当前任务的运行时统计数据.
*/
update_curr(cfs_rq);
dequeue_entity_load_avg(cfs_rq, se);

if (schedstat_enabled())
update_stats_dequeue(cfs_rq, se, flags);

clear_buddies(cfs_rq, se);

if (se != cfs_rq->curr)
__dequeue_entity(cfs_rq, se);
se->on_rq = 0;
account_entity_dequeue(cfs_rq, se);

/*
* 在更新 min_vruntime 之后,对调度实体进行规范化,因为更新可以指向 ->curr 项,
* 我们需要在规范化的位置反应这一变化
*/
if (!(flags & DEQUEUE_SLEEP))
se->vruntime -= cfs_rq->min_vruntime;

/* return excess runtime on last dequeue */
return_cfs_rq_runtime(cfs_rq);

update_min_vruntime(cfs_rq);
update_cfs_shares(cfs_rq);
}

和向红黑树中添加进程一样,实际操作都是由辅助函数 __dequeue_entity() 完成的,

1
2
3
4
5
6
7
8
9
10
11
static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
if (cfs_rq->rb_leftmost == &se->run_node) {
struct rb_node *next_node;

next_node = rb_next(&se->run_node);
cfs_rq->rb_leftmost = next_node;
}

rb_erase(&se->run_node, &cfs_rq->tasks_timeline);
}

从红黑树中删除进程要容易很多,因为 rbtree 实现了 rb_erae() 函数,它能完成所有的工作。该函数剩下的工作是更新 rb_leftmost 缓存。
如果要删除的是最左叶节点,该函数会调用 rb_next() 按顺序遍历找到下一个最左节点。

参考文档