技术交流

好好学习,天天向上。

0%

调度器基础

[toc]

调度器基础

概念

调度就是解决CPU使用的分配问题的,内核支持非实时调度,也支持软实时调度。

数据结构

通用调度和调度类的关系

  • 调度功能的实现分通用调度部分,和调度类部分。通用调度部分可以被各种调度点触发,也可以是时钟周期性触发。通用调度部分不直接管理进程,所有具体的进程管理交个各个调度类负责

  • 调度类负责挑选出下一个可以被调度运行的进程,内核采用调度类的形式实现不同的调度策略,这使得调度策略的实现方式模块化

    image-20211211172743387

task_struct

task_struct中,有以下和进程调度有关的变量

1
2
3
4
5
6
7
8
9
10
11
12
13
<sched.h>
struct task_struct {
...
int prio, static_prio, normal_prio;
unsigned int rt_priority;
struct list_head run_list;
const struct sched_class *sched_class;
struct sched_entity se;
unsigned int policy;
cpumask_t cpus_allowed;
unsigned int time_slice;
...
}

字段含义

变量名称 来源
prio 调度器做进程调度时综合考量得出的优先级
nomal_prio 基于进程静态优先级和调度策略计算出的优先级,可以被子进程继承
static_prio 进程启动时分配,一般作为参数用于计算其他几个优先级变量的值
rt_priority 仅用于表示实时进程的优先级,值越大优先级越高。
sched_class 指向进程所属的调度器类,一个进程只能属于一个调度器类
sched_entity 调度器实际的调度对象为调度实体,该结构体可以嵌入到task_struct中表明进程是可调度的实体
policy 保存了进程的调度策略,见下表描述
cpus_allowed 保存进程的亲核性
run_list 仅用于实时调度器,保存一个运行表
time_slice 仅用于实时调度器,指定进程剩余可用的CPU时间片

调度策略宏

策略宏 描述
SCHED_NORMAL 用于普通进程的调度策略,采用完全公平调度器实现调度
SCHED_BATCH 用于CPU密集型、非交互类进程的调度策略,采用完全公平调度器实现调度
SCHED_IDLE 用于优先级很低的进程的调度,采用完全公平调度器实现调度
SCHED_RR 用于软实时进程的调度,采用RR实时调度器的实现调度
SCHED_FIFO 用于软实时进程的调度,采用FIFO实时调度器实现调度

调度类

对各个调度类,都必须提供struct sched_class的一个实例。不同的调度类之间的层次结构是平坦的,由链表管理。但不同的进行类型的处理顺序有先后之分。

1
2
3
4
5
6
7
8
9
10
11
12
struct sched_class {
const struct sched_class *next;
void (*enqueue_task) (struct rq *rq, struct task_struct *p, int wakeup);
void (*dequeue_task) (struct rq *rq, struct task_struct *p, int sleep);
void (*yield_task) (struct rq *rq);
void (*check_preempt_curr) (struct rq *rq, struct task_struct *p);
struct task_struct * (*pick_next_task) (struct rq *rq);
void (*put_prev_task) (struct rq *rq, struct task_struct *p);
void (*set_curr_task) (struct rq *rq);
void (*task_tick) (struct rq *rq, struct task_struct *p);
void (*task_new) (struct rq *rq, struct task_struct *p);
};

字段含义

变量名称 来源
enqueue_task 向就绪队列中添加一个新进程
dequeue_task 执行与enqueue_task相反操作,从就绪队列中移除一个进程
yield_task 进程自愿放弃CPU时,可以使用sched_yield系统调用,进而执行到yield_task
check_preempt_curr 必要情况下,该接口用于唤醒一个新的进程来抢占当前进程
put_prev_task 在调度下一个进程之前调用
pick_next_task 用于选择下一个将要运行的线程
set_curr_task 当进程的调度策略发生变化时需要调用
task_tick 每次周期性调度器激活时,周期性调度器会调用该接口
new_task 用于fork流程,每次新进程创建后,用该接口通知调度器

就绪队列

每个CPU核心都有自己的绪队列,所有的就绪队列保存在一个全局的数组中

1
2
kernel/sched.c
static DEFINE_PER_CPU_SHARED_ALIGNED(struct rq, runqueues);

就绪队列的详细结构定义如下

1
2
3
4
5
6
7
8
9
10
11
12
13
kernel/sched.c
struct rq {
unsigned long nr_running;
#define CPU_LOAD_IDX_MAX 5
unsigned long cpu_load[CPU_LOAD_IDX_MAX];
...
struct load_weight load;
struct cfs_rq cfs;
struct rt_rq rt;
struct task_struct *curr, *idle;
u64 clock;
...
};

字段含义

变量名称 来源
nr_running 指定了队列上可运行进程的数目,不考虑优先级或调度类
load 提供了就绪队列当前负荷的度量,队列的负荷本质上与队列上当前活动进程的数目成正比。该值是虚拟时钟速度计算的基础,可以影响调度算法。
cpu_load 用于跟踪此前的CPU状态
cfs 嵌入的子就绪队列,用于完全公平调度器
rt 嵌入的子就绪队列,用于实时调度器
curr 指向当前运行进程的task_struct
idle 指向idle进程的task_struct,当CPU没有可执行进程时会调度idle进程执行
clock/prev_raw_clock 用于实现就绪队列自身的时钟,周期调度器激活的时候会更新clock。prev_raw_clock保存上一次更新前的clock值

调度实体

调度实体是调度器实际的调度对象,其不一定是进程。struct sched_entity需要嵌入到调度实体中。

1
2
3
4
5
6
7
8
9
10
11
<sched.h>
struct sched_entity {
struct load_weight load; /* 用于负载均衡 */
struct rb_node run_node;
unsigned int on_rq;
u64 exec_start;
u64 sum_exec_runtime;
u64 vruntime;
u64 prev_sum_exec_runtime;
...
}

字段含义

变量名称 来源
load 决定了各个实体占就绪队列总负荷的比例
run_node 用于将调度实体挂到红黑树上
on_rq 表示该调度实体是否在就绪队列上接受调度
sum_exec_runtime/exec_start 在调度流程中,update_curr函数负责更新进程运行时间,其会将当前时间和exec_start的差值累加到sum_exec_runtime上,同时将当前时间写入exec_start。

优先级的处理

优先级的表示

在用户态,用户可以使用nice命令改变一个进程的优先级,nice命令会进一步调用nice系统调用。用户视角下,nice值在[-20,+19]区间;在内核内部,进程优先级用区间[0,139]中的值表示。不管是在内核内部还是在用户态,都是值越小,进程优先级越高。用户态nice值和内核态进程优先级的映射如下图所示

可以看到,内核内部将[0,99]区间的值分配给了实时进程。内核提供了一系列辅助宏来完成nice值到进程优先级的转换。

1
2
3
4
5
6
7
8
9
10
<sched.h>
#define MAX_USER_RT_PRIO 100
#define MAX_RT_PRIO MAX_USER_RT_PRIO
#define MAX_PRIO (MAX_RT_PRIO + 40)
#define DEFAULT_PRIO (MAX_RT_PRIO + 20)

kernel/sched.c
#define NICE_TO_PRIO(nice) (MAX_RT_PRIO + (nice) + 20)
#define PRIO_TO_NICE(prio) ((prio) -MAX_RT_PRIO -20)
#define TASK_NICE(p) PRIO_TO_NICE((p)->static_prio)

优先级计算

内核做进程调度的时候,调度过程需要考虑进程的优先级。由前面内容可以知道,进程的task_struct中有多个和进程优先级有关的变量。内核做进程调度,会执行以下调用p->prio = effective_prio(p)。和effective_prio相关的代码如下

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
static int effective_prio(struct task_struct *p)
{
p->normal_prio = normal_prio(p); // 计算普通优先级,详细内容见下方描述
if (!rt_prio(p->prio)) // 如果非实时进程,或者进程优先级没有提高到实时优先级范围,则直接返回normal_prio
return p->normal_prio;
return p->prio; // 如果是实时进程,或者进程优先级已经提高到实时优先级范围,则返回prio
}
static inline int normal_prio(struct task_struct *p)
{
int prio;
if (task_has_rt_policy(p)) // 对实时进程来说,其normal_prio的计算要考虑rt_priority,在内核中rt_priority值越高进程优先级越高
prio = MAX_RT_PRIO-1 - p->rt_priority;
else
prio = __normal_prio(p); // 非是实时进程的话,进程的normal_prio就是static_prio
return prio;
}
static inline int __normal_prio(struct task_struct *p) // 出于历史原因,将static_prio到normal_prio的计算被实现为一个函数
{
return p->static_prio;
}
static inline int rt_prio(int prio)
{
if (unlikely(prio < MAX_RT_PRIO))
return 1;
return 0;
}

在p->prio = effective_prio(p)语句执行过后,根据进程的静态优先级(static_prio)和进程的调度策略,各个变量的变化情况如下表所示

进程类型/优先级 static_prio normal_prio prio
非实时进程 保持不变 赋予static_prio 赋予static_prio
优先级提高的非实时进程 保持不变 赋予static_prio 保持不变
实时进程 保持不变 赋予MAX_RT_PRIO-1-rt_priority 保持不变

static_prio的值可以通过nice或者sched_setscheduler系统调用修改。

计算负荷权重

在内核中,进程的调度过程只考虑进程的优先级,则难以评估被调度进程的运行时间。所以又引入了进程的权重概念,用struct load_weight表示,其定义如下

1
2
3
struct load_weight {
unsigned long weight, inv_weight;
};

内核定义了一张从优先级到权重值的映射表,每个相邻的数组值之间,index较小值比上index较大值有1.25的比例因子。主要原因是内核期望进程的优先级每降低1,则CPU时间增加10%,经过数学演算就得出的下表

1
2
3
4
5
6
7
8
9
10
static const int prio_to_weight[40] = {
/* -20 */ 88761, 71755, 56483, 46273, 36291,
/* -15 */ 29154, 23254, 18705, 14949, 11916,
/* -10 */ 9548, 7620, 6100, 4904, 3906,
/* -5 */ 3121, 2501, 1991, 1586, 1277,
/* 0 */ 1024, 820, 655, 526, 423,
/* 5 */ 335, 272, 215, 172, 137,
/* 10 */ 110, 87, 70, 56, 45,
/* 15 */ 36, 29, 23, 18, 15,
};

普通进程、实时进程以及IDLE进程在计算权重的时候,有一些小差异,见下方代码

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
kernel/sched.c
#define WEIGHT_IDLEPRIO 2
#define WMULT_IDLEPRIO (1 << 31)
static void set_load_weight(struct task_struct *p)
{
/*
* 实时进程的权重要按照2倍放大
*/
if (task_has_rt_policy(p)) {
p->se.load.weight = prio_to_weight[0] * 2;
p->se.load.inv_weight = prio_to_wmult[0] >> 1;
return;
}
/*
* SCHED_IDLE进程得到的权重最小
*/
if (p->policy == SCHED_IDLE) {
p->se.load.weight = WEIGHT_IDLEPRIO;
p->se.load.inv_weight = WMULT_IDLEPRIO;
return;
}
/*
* 普通进程只做简单的映射
*/
p->se.load.weight = prio_to_weight[p->static_prio -MAX_RT_PRIO];
p->se.load.inv_weight = prio_to_wmult[p->static_prio -MAX_RT_PRIO];
}

进程自身的权重保存在task_struct.sched_entity.load中,就绪队列的总权重保存在rq.load中。当一个进程新加入一个就绪队列的时候,内核会将进程的load添加到就绪队列的load上。当进程从就绪队列中移除的时候,做相反操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
static inline void update_load_add(struct load_weight *lw, unsigned long inc)
{
lw->weight += inc;
}
static inline void inc_load(struct rq *rq, const struct task_struct *p)
{
update_load_add(&rq->load, p->se.load.weight);
}
static void inc_nr_running(struct task_struct *p, struct rq *rq)
{
rq->nr_running++;
inc_load(rq, p);
}

核心调度器

调度入口

调度器的入口有两个,一个是在各个调度点调用的schedule函数,另一个是时钟触发的scheduler_tick函数。

scheduler_tick(周期性调度器)

scheduler_tick是可以关闭的,可以实现省电目的。scheduler_tick的任务有以下几个个:

  • 更新当前CPU上的rq队列的时钟信息
  • 更新当前CPU上的rq队列的load信息,就是将历史load往后移动,然后追加当前load到队列头
  • 调用当前进程所属调度类的task_tick函数
  • 如果系统为SMP系统,则触发负载均衡
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
void scheduler_tick(void)
{
int cpu = smp_processor_id();
struct rq *rq = cpu_rq(cpu);
struct task_struct *curr = rq->curr;
u64 next_tick = rq->tick_timestamp + TICK_NSEC;

spin_lock(&rq->lock);
__update_rq_clock(rq);
/*
* Let rq->clock advance by at least TICK_NSEC:
*/
if (unlikely(rq->clock < next_tick))
rq->clock = next_tick;
rq->tick_timestamp = rq->clock;
update_cpu_load(rq);
if (curr != rq->idle) /* FIXME: needed? */
curr->sched_class->task_tick(rq, curr); // 特定于调度类的task_tick函数,如果进程需要被重新调度,会设置进程的TIF_NEED_RESCHED标志
spin_unlock(&rq->lock);

#ifdef CONFIG_SMP
rq->idle_at_tick = idle_cpu(cpu);
trigger_load_balance(rq, cpu);
#endif
}

schedule函数(主调度器)

各个调度点,例如系统调用的退出阶段,会检查进程的TIF_NEED_RESCHED标志。如果进程的标志置位,则会调用schedule函数,进一步执行进程切换。

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
61
62
63
64
65
66
67
68
69
/*
* schedule函数的函数声明中有__sched标志,意思是告知内核该函数用于进程调度。因为调度代码本身不是进程的一部分,所以当进程发生错误时,所生成的backtrace信息中不会包含调度代码的信息。这种机制是将带有__sched的代码放到单独的.sched.text段实现的。
*/
asmlinkage void __sched schedule(void)
{
struct task_struct *prev, *next;
long *switch_count;
struct rq *rq;
int cpu;

need_resched:
preempt_disable();
cpu = smp_processor_id();
rq = cpu_rq(cpu);
rcu_qsctr_inc(cpu);
prev = rq->curr; // prev指向调度前活动进程的task_struct
switch_count = &prev->nivcsw;

release_kernel_lock(prev);
need_resched_nonpreemptible:

schedule_debug(prev);

/*
* Do the rq-clock update outside the rq lock:
*/
local_irq_disable();
__update_rq_clock(rq); // 同样会处理调度队列的时钟信息
spin_lock(&rq->lock);
clear_tsk_need_resched(prev); // 这里清除了调度进程的TIF_NEED_RESCHED标志

if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) {
// 这里是检查进程在调度期间是否又再次收到了信号且本身也是处于中断可睡眠状态,这种情况进程必须提升为运行进程,继续处于就绪队列中
if (unlikely((prev->state & TASK_INTERRUPTIBLE) &&
unlikely(signal_pending(prev)))) {
prev->state = TASK_RUNNING;
} else {
deactivate_task(rq, prev, 1); // 否则,将进程从rq中移除。这里会调用调度类的dequeue_task
}
switch_count = &prev->nvcsw;
}

if (unlikely(!rq->nr_running))
idle_balance(cpu, rq);

prev->sched_class->put_prev_task(rq, prev); // 这里告知调度类,当前进程即将从CPU上被调度下来,调度类将做数据更新
next = pick_next_task(rq, prev); // 调度类将从rq中选出下一个可被调度到CPU上的进程

sched_info_switch(prev, next);

if (likely(prev != next)) {
rq->nr_switches++;
rq->curr = next;
++*switch_count;

context_switch(rq, prev, next); /* unlocks the rq */ // 在本句代码执行后,schedule就处于新的进程上下文了,栈内容已经变化
} else
spin_unlock_irq(&rq->lock);

if (unlikely(reacquire_kernel_lock(current) < 0)) {
cpu = smp_processor_id();
rq = cpu_rq(cpu);
goto need_resched_nonpreemptible;
}
preempt_enable_no_resched();
// 此处检查新调度上CPU的进程是否同样有设置TIF_NEED_RESCHED标志。若是,则需要重新执行调度流程,选取下一个进程运行
if (unlikely(test_thread_flag(TIF_NEED_RESCHED)))
goto need_resched;
}

fork相关

当内核执行fork函数或者相关变体的时候,会调用sched_fork函数。在sched_fork函数中,会为新创进程设定优先级,指定调度类。新创进程的prio被赋予父进程的normal_prio,非实时进程的调度类会被设为完全公平调度类。

当使用wake_up_new_task的时候,调度器会调用进程调度类的task_new接口,此时会将进程添加到就绪队列中。

switch_to

// TODO