[toc]
调度器基础
概念
调度就是解决CPU使用的分配问题的,内核支持非实时调度,也支持软实时调度。
数据结构
通用调度和调度类的关系
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)) return p->normal_prio; return p->prio; } static inline int normal_prio(struct task_struct *p) { int prio; if (task_has_rt_policy(p)) prio = MAX_RT_PRIO-1 - p->rt_priority; else prio = __normal_prio(p); return prio; } static inline int __normal_prio(struct task_struct *p) { 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] = { 88761, 71755, 56483, 46273, 36291, 29154, 23254, 18705, 14949, 11916, 9548, 7620, 6100, 4904, 3906, 3121, 2501, 1991, 1586, 1277, 1024, 820, 655, 526, 423, 335, 272, 215, 172, 137, 110, 87, 70, 56, 45, 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) {
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; }
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);
if (unlikely(rq->clock < next_tick)) rq->clock = next_tick; rq->tick_timestamp = rq->clock; update_cpu_load(rq); if (curr != rq->idle) curr->sched_class->task_tick(rq, curr); 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
|
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; switch_count = &prev->nivcsw;
release_kernel_lock(prev); need_resched_nonpreemptible:
schedule_debug(prev);
local_irq_disable(); __update_rq_clock(rq); spin_lock(&rq->lock); clear_tsk_need_resched(prev);
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); } switch_count = &prev->nvcsw; }
if (unlikely(!rq->nr_running)) idle_balance(cpu, rq);
prev->sched_class->put_prev_task(rq, prev); next = pick_next_task(rq, prev);
sched_info_switch(prev, next);
if (likely(prev != next)) { rq->nr_switches++; rq->curr = next; ++*switch_count;
context_switch(rq, prev, next); } 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(); 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