explorer

万丈高楼平地起,勿在浮沙筑高台

0%

[What]Linux 调度的实现

参考:

  1. 《Linux 内核设计与实现》
kernel version arch
v5.4.x lts arm32

之前对 linux 调度有了粗略的认识,现在再来窥探一些细节。

调度器类(scheduler classes)

Linux 调度器以模块化的方式提供,这样允许任务可以有针对的选择调度算法。

Linux 会按照优先级顺序遍历调度器类,选择可执行任务的最高优先级调度器,然后去执行该调度器的任务。

完全公平调度(CFS)

基于时间片调度的缺陷

传统 UNIX 优先级以 nice 值形式输出到用户空间,nice 值越小,获得的时间片越多,这会有下面这些问题:

  • 低 nice 值也就是高优先级的任务获得的时间片很多,但一般情况下高优先级的线程实际上是 IO 密集型。而高 nice 值的低优先级任务往往是 CPU 密集型,获得的时间片反而更小。
    • 这显然与保证高响应度的同时保证高吞吐量的初衷背道而驰。
  • nice 值是 0 和 1 分配的时间片是 100/95,但 nice 值是 18 和 19 分配的时间片确实 10/5,同样的 nice 值只差 1,但分配比例却相差很大。
    • 这不能保证公平性,所以 nice 值的时间片应该以几何增加而非算数增加
  • 时间片是定时器节拍的整数倍,但如果一个 nice 值对应一个时间片,当定时器节拍被改变后,原先的时间片大小虽然没有变,但绝对时间就变了。
    • 所以需要将时间片与定时器节拍分离开来
  • 调度器将提升 IO 密集型任务优先级(占用时间片少),但如果其它任务通过主动睡眠来降低自己的时间片占用,那就会迷惑调度器。

公平调度

CFS 采用的方法是对时间片分配方式任务根本性的重新设计:通过时间分配处理器比例的方式摒弃时间片,从而保证公平性。

CFS 的出发点基于一个简单的理念:任务调度的效果应如同系统具备一个理想的完美的多任务处理器。 在这个系统中将能获得 1/n 的处理器时间(n 是指可运行任务的数量)。同时,我们可以调度给它们无限小的时间周期, 所以在任何可测量周期内,我们给予 n 个任务中每个任务同样多的运行时间。

CFS 的做法是允许每个任务运行一段时间、循环轮转、选择运行最少的任务作为下一个运行任务,而不是使用固定分配的时间片。

  • nice 值再 CFS 中被作为任务获得处理器运行的权重。

CFS 有一个“目标延迟”的概念,对所有任务的最小调度周期:

  • 假设目标延迟是 20ms,具有两个相同优先级的任务,不管它们优先级是多少,每个任务的运行时间都是 10ms
    • 如果具有 4 个相同优先级的任务,每个任务的运行时间就是 5ms。
    • 如果任务特别多,CFS 也规定了一个最小粒度以避免无限的切换消耗(通常是 1ms)
  • 假设目标延迟是 20ms,有 nice 值为 0 和 5 的任务,其运行时间分别是 15ms 和 5ms。
    • 如果 nice 值为 10 和 15,其运行时间依然为 15ms 和 5ms
    • 可以看到分配比例只与 nice 值的相对值有关

实现 CFS

CFS 实现的代码位于路径 kernel/sched/fair.c ,下面进行依次分析。

时间记账

传统的调度器对任务的时间片进行记录,以在任务的时间片耗尽时切换到其他任务,而 CFS 记录的是任务运行的虚拟时间

在 task_struct 结构体中有一个 struct sched_entity se 成员变量,该成员就是对该任务进行时间记账。

该结构体中具有成员 u64 vruntime 就是用于存放任务的虚拟运行时间,该虚拟运行时间的单位是 ns,它已经与定时器节拍不再关联。

而 vruntime 的计算则是在函数 update_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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
//此函数执行的公式便是 delta_vtime = delta_ptime * 1024 / weight
static inline u64 calc_delta_fair(u64 delta, struct sched_entity *se)
{
if (unlikely(se->load.weight != NICE_0_LOAD))
delta = __calc_delta(delta, NICE_0_LOAD, &se->load);

return delta;
}
static void update_curr(struct cfs_rq *cfs_rq)
{
//当前的任务记录器
struct sched_entity *curr = cfs_rq->curr;
//当前的运行时间
u64 now = rq_clock_task(rq_of(cfs_rq));
u64 delta_exec;

if (unlikely(!curr))
return;

//上一次进入该函数到目前所经过的时间
delta_exec = now - curr->exec_start;
if (unlikely((s64)delta_exec <= 0))
return;

curr->exec_start = now;

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

//该任务当前运行的总时间
curr->sum_exec_runtime += delta_exec;
schedstat_add(cfs_rq->exec_clock, delta_exec);

//得到虚拟运行时间
curr->vruntime += calc_delta_fair(delta_exec, curr);
update_min_vruntime(cfs_rq);

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

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

account_cfs_rq_runtime(cfs_rq, delta_exec);
}

任务选择

CFS 选择任务的核心就是:选择具有最小 vruntime 的任务来运行。

Linux 使用红黑树来将所有处于运行状态的任务挂接起来,那么最左侧的叶子节点便是 vruntime 最小的节点。

  • 选择下一个要运行的任务是通过函数 __pick_next_entity 来完成的:
1
2
3
4
5
6
7
8
9
static struct sched_entity *__pick_next_entity(struct sched_entity *se)
{
struct rb_node *next = rb_next(&se->run_node);

if (!next)
return NULL;

return rb_entry(next, struct sched_entity, run_node);
}
  • 而将一个任务加入红黑树是通过 enqueue_entity() 来完成,该函数调用 __enqueue_entity() 来完成插入。
  • 删除一个任务是通过 dequeue_entity() 来完成

调度器入口

调度器的入口函数是 schedule() 位于 kernel/sched/core.c

该函数会调用 __schedule() 函数,其执行逻辑为:

  • 选择优先级最高的调度策略
  • 从该调度策略中选择优先级最高的任务运行

以上两个重要的执行逻辑是通过函数 pick_next_task() 来完成的:

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/*
* Pick up the highest-prio task:
*/
static inline struct task_struct *
pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
{
const struct sched_class *class;
struct task_struct *p;

/*
* Optimization: we know that if all tasks are in the fair class we can
* call that function directly, but only if the @prev task wasn't of a
* higher scheduling class, because otherwise those loose the
* opportunity to pull in more work from other CPUs.
*/
//! 当所有可运行任务都是 CFS 任务(NICE 策略)时,可以使用快捷方式得到下一个将要运行的任务
if (likely((prev->sched_class == &idle_sched_class ||
prev->sched_class == &fair_sched_class) &&
rq->nr_running == rq->cfs.h_nr_running)) {

p = fair_sched_class.pick_next_task(rq, prev, rf);
if (unlikely(p == RETRY_TASK))
goto restart;

/* Assumes fair_sched_class->next == idle_sched_class */
if (unlikely(!p))
p = idle_sched_class.pick_next_task(rq, prev, rf);

return p;
}

restart:
#ifdef CONFIG_SMP
/*
* We must do the balancing pass before put_next_task(), such
* that when we release the rq->lock the task is in the same
* state as before we took rq->lock.
*
* We can terminate the balance pass as soon as we know there is
* a runnable task of @class priority or higher.
*/
for_class_range(class, prev->sched_class, &idle_sched_class) {
if (class->balance(rq, prev, rf))
break;
}
#endif

put_prev_task(rq, prev);

//! 从最高优先级策略开始遍历每个调度类,获取最高优先级可运行任务
for_each_class(class) {
p = class->pick_next_task(rq, NULL, NULL);
if (p)
return p;
}

/* The idle class should always have a runnable task: */
BUG();
}

睡眠和唤醒

  • 睡眠:任务从可执行红黑树中移出,被放入等待队列
  • 唤醒:任务被设置为可执行状态,然后从等待队列中移到可执行红黑树

上述过程在此处有完整的示例。

可以看到:调度器真正调度的是处于运行状态的任务!

为了避免任务的休眠和唤醒产生竞争条件,通常的处理代码如下:

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
//为当前任务创建一个节点,名叫 wait
DEFINE_WAIT(wait);

//将当前任务节点加入等待队列 q 中
add_wait_queue(q, &wait);

//当事件不满足时,进入睡眠
while(!condition)
{
//将当前任务设置为 TASK_INTERRUPTIBLE 状态
prepare_to_wait(&q, &wait, TASK_INTERRUPTIBLE);
//如果当前任务被信号唤醒,则处理信号
if(signal_pending(current))
{
//一般返回 restart 错误,然后退出循环
ret = -ERESTARTSYS;
break;
}
//在调用 schedule() 前需要释放必要的锁
//主动调度到其它任务运行
schedule();
//在返回 schedule() 后需要获取必要的锁
}
//将当前任务设置为运行态,并移出等待队列
finish_wait(&q, &wait);

inotify_read() 提供了标准使用方式:

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
static ssize_t inotify_read(struct file *file, char __user *buf,
size_t count, loff_t *pos)
{
struct fsnotify_group *group;
struct fsnotify_event *kevent;
char __user *start;
int ret;
//! 为当前任务创建等待节点
DEFINE_WAIT_FUNC(wait, woken_wake_function);

start = buf;
group = file->private_data;

//将当前任务加入等待队列
add_wait_queue(&group->notification_waitq, &wait);
while (1) {
//获取条件
spin_lock(&group->notification_lock);
kevent = get_one_event(group, count);
spin_unlock(&group->notification_lock);

pr_debug("%s: group=%p kevent=%p\n", __func__, group, kevent);

//条件为真则处理
if (kevent) {
ret = PTR_ERR(kevent);
if (IS_ERR(kevent))
break;
ret = copy_event_to_user(group, kevent, buf);
fsnotify_destroy_event(group, kevent);
if (ret < 0)
break;
buf += ret;
count -= ret;
continue;
}

ret = -EAGAIN;
//如果用户空间以非阻塞处理,则依然退出
if (file->f_flags & O_NONBLOCK)
break;
ret = -ERESTARTSYS;
//如果是信号唤醒则退出
if (signal_pending(current))
break;

if (start != buf)
break;

//将当前任务设置为 TASK_INTERRUPTIBLE 状态,并进行超时判断调度
//当任务被唤醒后,状态会被设置为 TASK_RUNNING
wait_woken(&wait, TASK_INTERRUPTIBLE, MAX_SCHEDULE_TIMEOUT);
}
//退出循环后将当前任务移出等待队列
remove_wait_queue(&group->notification_waitq, &wait);

if (start != buf && ret != -EFAULT)
ret = buf - start;
return ret;
}

唤醒则是通过 wake_up() 类宏来将 指定队列上所有任务唤醒

  • 将任务设置为 TASK_RUNNING 状态
  • 将任务放入调度用的红黑树中

抢占和上下文切换

抢占和上下文切换

上下文切换就是将一个任务切换到另一个任务运行,其实现是由 kernel/sched/core.c 中的 context_switch() 来实现的。

此函数会被 schedule() 调用,其执行步骤如下:

  • 将虚拟内存从上一个任务切换到新的任务
  • 将处理器状态从上一个任务切换到新的任务
    • 保存、恢复栈信息,寄存器信息等

内核会检测任务 need_resched 标记来确认是否调用 schedule() 来进行上下文切换,比如当有高优先级任务需要运行时,该标记就会被置位。

include/linux/sched.h 中提供一些对标记的操作函数:

名称 说明
need_resched() 获取该标记是否置位
set_tsk_need_resched(struct task_struct *tsk) 将该任务的标记置位
clear_tsk_need_resched(struct task_struct *tsk) 将该任务的标记清零

该标记被 thread_info 中的 flags 成员保存。

用户任务抢占会在以下情况时发生:

  • 用户进行系统调用时,内核会检查 need_resched 标记
  • 执行中断处理程序时,内核会检查 need_resched 标记

内核任务抢占:只要任务没有持有锁,内核就可以进行抢占。

thread_info 有个 preempt_count 计数器,每当获得一个锁时该计数值加 1,释放锁时该计数值减 1。 所以可以判断当 preempt_count 为 0 时,代表它没有获取到锁,是可以执行抢占的。

也就是说:当 need_resched 标记置位并且 preempt_count 值为 0 时,就可以执行内核抢占。

内核抢占会发生在:

  • 执行中断处理程序时
  • 内核代码再一次具有可抢占性时
  • 内核代码显式调用 schedule()
  • 内核中的任务阻塞时

实时调度策略

实时调度策略在内核中的定义是 SCHED_FIFO 和 SCHED_RR ,而 CFS 调度策略是 SCHED_NORMAL.

Linux 的实时调度算法提供了一种软实时工作方式:内核调度进程尽力使进程在它的限定时间到来前运行,但内核不保证一定能满足。

有关调度的系统调用如下:

与调度策略和优先级:

  • sched_setscheduler() / sched_getscheduler() : 设置和获取任务的调度策略
    • 对应读写内核 task_struct 的 policy 和 rt_priority 成员
  • sched_setparram() / sched_getparram() : 设置和获取 RT 任务的优先级
    • 对应读写内核 sched_param 的 rt_priority 成员
  • sched_get_priority_max() / sched_get_priority_min() : 获取 RT 优先级的最大和最小值
    • 内核最大优先级定义在 include/linux/sched/prio.h 中的 MAX_USER_RT_PRIO ,默认是 100,所以范围就是 0~99
  • nice() : 设置 CFS 任务的 nice 值
    • 对应内核 task_struct 的 static_prio 和 prio 成员

与处理器绑定有关的系统调用:

  • sched_setaffinity() / sched_getaffinity() : 设置和获取任务对 CPU 的亲和性
    • 对应内核 task_struct 的 nr_cpus_allowed 成员,默认掩码为全 1 ,代表任务可以在所有的 CPU 上运行

主动放弃处理器时间:

  • sched_yield()

对于 CFS 策略而言,任务会被放入优先级队列的末尾,并放入过期队列中。

但对于 RT 策略而言,由于任务没有时间的概念,它们只会被放入到优先级队列的末尾。

Last Updated 2020-10-19 一 22:29.
Render by hexo-renderer-org with Emacs 26.3 (Org mode 9.4)