2.8.7 调度时机
调度进程的时机如下。
（1）进程主动调用schedule()函数。
（2）周期性地调度，抢占当前进程，强迫当前进程让出处理器。
（3）唤醒进程的时候，被唤醒的进程可能抢占当前进程。
（4）创建新进程的时候，新进程可能抢占当前进程。
如果编译内核时开启对内核抢占的支持，那么内核会增加一些抢占点。
1．主动调度
进程在用户模式下运行的时候，无法直接调用schedule()函数，只能通过系统调用进入内核模式，如果系统调用需要等待某个资源，例如互斥锁或信号量，就会把进程的状态设置为睡眠状态，然后调用schedule()函数来调度进程。
进程也可以通过系统调用sched_yield()让出处理器，这种情况下进程不会睡眠。
在内核中，有以下3种主动调度方式。
（1）直接调用schedule()函数来调度进程。
（2）调用有条件重调度函数cond_resched()。在非抢占式内核中，函数cond_resched()判断当前进程是否设置了需要重新调度的标志，如果设置了，就调度进程；在抢占式内核中，函数cond_resched()是空函数，没有作用。
（3）如果需要等待某个资源，例如互斥锁或信号量，那么把进程的状态设置为睡眠状态，然后调用schedule()函数以调度进程。
2．周期调度
有些“流氓”进程不主动让出处理器，内核只能依靠周期性的时钟中断夺回处理器的控制权，时钟中断是调度器的脉搏。时钟中断处理程序检查当前进程的执行时间有没有超过限额，如果超过限额，设置需要重新调度的标志。当时钟中断处理程序准备把处理器还给被打断的进程时，如果被打断的进程在用户模式下运行，就检查有没有设置需要重新调度的标志，如果设置了，调用schedule()函数以调度进程。
周期调度的函数是scheduler_tick()，它调用当前进程所属调度类的task_tick方法。如果需要重新调度，就为当前进程的thread_info结构体的成员flags设置需要重新调度的标志位（_TIF_NEED_RESCHED），中断处理程序在返回的时候会检查这个标志位。
（1）限期调度类的周期调度。限期调度类的task_tick方法是函数task_tick_dl，函数task_tick_dl把主要工作委托给update_curr_dl函数，函数update_curr_dl的主要代码如下：
kernel/sched/deadline.c
1 static void update_curr_dl(struct rq *rq)
2 {
3 struct task_struct *curr = rq->curr;
4 struct sched_dl_entity *dl_se = &curr->dl;
5 u64 delta_exec;
6
7 …
8 delta_exec = rq_clock_task(rq) - curr->se.exec_start;
9 if (unlikely((s64)delta_exec <= 0)) {
10 if (unlikely(dl_se->dl_yielded))
11 goto throttle;
12 return;
13 }
14
15 …
16 dl_se->runtime -= delta_exec;
17
18 throttle:
19 if (dl_runtime_exceeded(dl_se) || dl_se->dl_yielded) {
20 dl_se->dl_throttled = 1;
21 __dequeue_task_dl(rq, curr, 0);
22 if (unlikely(dl_se->dl_boosted || ! start_dl_timer(curr)))
23 enqueue_task_dl(rq, curr, ENQUEUE_REPLENISH);
24
25 if (! is_leftmost(curr, &rq->dl))
26 resched_curr(rq);
27 }
28
29 …
30 }
第16行代码，计算限期进程的剩余运行时间。
第19行代码，如果限期进程用完了运行时间或者主动让出处理器，处理如下。
❑ 第20行代码，设置节流标志。
❑ 第21行代码，把当前进程从限期运行队列中删除。
❑ 第22行和第23行代码，如果当前进程被临时提升为限期进程（因为占用某个限期进程等待的实时互斥锁），或者绝对截止期限已经过期，那么把当前进程重新加入限期运行队列，补充运行时间（如果绝对截止期限没有到期，函数start_dl_timer启动高精度定时器，到期时间是当前进程的绝对截止期限，到期的时候把进程重新加入限期运行队列，补充运行时间）。
❑ 第25行和第26行代码，如果当前进程不在限期运行队列中，或者虽然在限期运行队列中但是绝对截止期限不是最小的，那么给当前进程设置需要重新调度的标志位。
（2）实时调度类的周期调度。实时调度类的task_tick方法是函数task_tick_rt，其主要代码如下：
kernel/sched/rt.c
1 static void task_tick_rt(struct rq *rq, struct task_struct *p, int queued)
2 {
3 struct sched_rt_entity *rt_se = &p->rt;
4
5 …
6 if (p->policy ! = SCHED_RR)
7 return;
8
9 if (--p->rt.time_slice)
10 return;
11
12 p->rt.time_slice = sched_rr_timeslice;
13
14 for_each_sched_rt_entity(rt_se) {
15 if (rt_se->run_list.prev ! = rt_se->run_list.next) {
16 requeue_task_rt(rq, p, 0);
17 resched_curr(rq);
18 return;
19 }
20 }
21 }
第6行和第7行代码，如果调度策略不是轮流调度，那么直接返回。
第9行和第10行代码，把时间片减一，如果没用完时间片，那么返回。
第12行代码，如果用完了时间片，那么重新分配时间片。
第14～20行代码，从当前进程到根任务组的任何一个层次，如果实时调度实体不是实时运行队列的唯一调度实体，那么把当前进程重新添加到实时运行队列的尾部，并且设置需要重新调度的标志位。
（3）公平调度类的周期调度。公平调度类的task_tick方法是函数task_tick_fair，其主要代码如下：
kernel/sched/fair.c
static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued)
{
struct cfs_rq *cfs_rq;
struct sched_entity *se = &curr->se;
for_each_sched_entity(se) {
cfs_rq = cfs_rq_of(se);
entity_tick(cfs_rq, se, queued);
}
}
从当前进程到根任务组的每级公平调度实体，调用函数entity_tick。函数entity_tick的主要代码如下：
kernel/sched/fair.c
static void
entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, int queued)
{
…
if (cfs_rq->nr_running > 1)
check_preempt_tick(cfs_rq, curr);
}
如果公平运行队列的进程数量超过1，那么调用函数check_preempt_tick。函数check_preempt_tick的代码如下：
kernel/sched/fair.c
1 static void
2 check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr)
3 {
4 unsigned long ideal_runtime, delta_exec;
5 struct sched_entity *se;
6 s64 delta;
7
8 ideal_runtime = sched_slice(cfs_rq, curr);
9 delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;
10 if (delta_exec > ideal_runtime) {
11 resched_curr(rq_of(cfs_rq));
12 clear_buddies(cfs_rq, curr);
13 return;
14 }
15
16 if (delta_exec < sysctl_sched_min_granularity)
17 return;
18
19 se = __pick_first_entity(cfs_rq);
20 delta = curr->vruntime - se->vruntime;
21
22 if (delta < 0)
23 return;
24
25 if (delta > ideal_runtime)
26 resched_curr(rq_of(cfs_rq));
27 }
第8～14行代码，如果当前调度实体的运行时间超过了理想的运行时间，那么设置需要重新调度的标志位。理想的运行时间=（调度周期×当前公平调度实体的权重/公平运行队列中所有调度实体的权重总和）。
第16～26行代码，如果当前调度实体的运行时间大于或等于调度最小粒度，并且当前调度实体的虚拟运行时间和公平运行队列中第一个调度实体的虚拟运行时间的差值大于理想的运行时间，那么设置需要重新调度的标志位。
（4）中断返回时调度。如果进程正在用户模式下运行，那么中断抢占时，ARM64架构的中断处理程序的入口是e10_irq。中断处理程序执行完以后，跳转到标号ret_to_user以返回用户模式。标号ret_to_user判断当前进程的进程描述符的成员thread_info.flags有没有设置标志位集合_TIF_WORK_MASK中的任何一个标志位，如果设置了其中一个标志位，那么跳转到标号work_pending，标号work_pending调用函数do_notify_resume。
arch/arm64/kernel/entry.S
ret_to_user:
disable_irq // 禁止中断
ldr x1, [tsk, #TSK_TI_FLAGS]
and x2, x1, #_TIF_WORK_MASK
cbnz x2, work_pending
finish_ret_to_user:
enable_step_tsk x1, x2
kernel_exit 0
ENDPROC(ret_to_user)
work_pending:
mov x0, sp
/*
* 寄存器x0存放第一个参数regs
* 寄存器x1存放第二个参数task_struct.thread_info.flags
*/
bl do_notify_resume
#ifdef CONFIG_TRACE_IRQFLAGS
bl trace_hardirqs_on // 在用户空间执行时开启中断
#endif
ldr x1, [tsk, #TSK_TI_FLAGS] // 重新检查单步执行
b finish_ret_to_user
函数do_notify_resume判断当前进程的进程描述符的成员thread_info.flags有没有设置需要重新调度的标志位_TIF_NEED_RESCHED，如果设置了，那么调用函数schedule()以调度进程。
arch/arm64/kernel/signal.c
asmlinkage void do_notify_resume(struct pt_regs *regs,
unsigned int thread_flags)
{
...
do {
if (thread_flags & _TIF_NEED_RESCHED) {
schedule();
} else {
…
}
local_irq_disable();
thread_flags = READ_ONCE(current_thread_info()->flags);
} while (thread_flags & _TIF_WORK_MASK);
}
3．唤醒进程时抢占
如图2.30所示，唤醒进程的时候，被唤醒的进程可能抢占当前进程。
图2.30 唤醒进程时抢占
（1）如果被唤醒的进程和当前进程属于相同的调度类，那么调用调度类的check_preempt_curr方法以检查是否可以抢占当前进程。
（2）如果被唤醒的进程所属调度类的优先级高于当前进程所属调度类的优先级，那么给当前进程设置需要重新调度的标志。
停机调度类的check_preempt_curr方法是函数check_preempt_curr_stop，它是一个空函数。
限期调度类的check_preempt_curr方法是函数check_preempt_curr_dl，算法是：如果被唤醒的进程的绝对截止期限比当前进程的绝对截止期限小，那么给当前进程设置需要重新调度的标志。
实时调度类的check_preempt_curr方法是函数check_preempt_curr_rt，算法是：如果被唤醒的进程的优先级比当前进程的优先级高，那么给当前进程设置需要重新调度的标志。
公平调度类的check_preempt_curr方法是函数check_preempt_wakeup，其主要代码如下：
kernel/sched/fair.c
1 static void check_preempt_wakeup(struct rq *rq, struct task_struct *p, int wake_flags)
2 {
3 struct task_struct *curr = rq->curr;
4 struct sched_entity *se = &curr->se, *pse = &p->se;
5 …
6 if (unlikely(curr->policy == SCHED_IDLE) &&
7 likely(p->policy ! = SCHED_IDLE))
8 goto preempt;
9
10 if (unlikely(p->policy ! = SCHED_NORMAL) || ! sched_feat(WAKEUP_PREEMPTION))
11 return;
12
13 find_matching_se(&se, &pse);
14 update_curr(cfs_rq_of(se));
15 BUG_ON(! pse);
16 if (wakeup_preempt_entity(se, pse) == 1) {
17 …
18 goto preempt;
19 }
20
21 return;
22
23 preempt:
24 resched_curr(rq);
25 …
26 }
27
28 static int
29 wakeup_preempt_entity(struct sched_entity *curr, struct sched_entity *se)
30 {
31 s64 gran, vdiff = curr->vruntime - se->vruntime;
32
33 if (vdiff <= 0)
34 return -1;
35
36 gran = wakeup_gran(curr, se);
37 if (vdiff > gran)
38 return 1;
39
40 return 0;
41 }
第6～8行代码，如果当前进程的调度策略是SCHED_IDLE，被唤醒的进程的调度策略是SCHED_NORMAL或者SCHED_BATCH，那么允许抢占，给当前进程设置需要重新调度的标志。
第10行代码，如果被唤醒的进程的调度策略不是SCHED_NORMAL，那么不允许抢占当前进程。如果没有开启唤醒抢占的调度特性（默认开启唤醒抢占的调度特性），那么不允许抢占。
第13行代码，因为第16行代码调用函数wakeup_preempt_entity来判断是否可以抢占，只能在属于同一个任务组的两个兄弟调度实体之间判断，所以函数find_matching_se需要为当前进程和被唤醒的进程找到两个兄弟调度实体。
第16行代码，如果（当前进程的虚拟运行时间 − 被唤醒的进程的虚拟运行时间）大于虚拟唤醒粒度，那么允许抢占，给当前进程设置需要重新调度的标志。
虚拟唤醒粒度是唤醒粒度根据当前进程的权重转换成的虚拟时间，全局变量sysctl_sched_wakeup_granularity存放唤醒粒度，单位是纳秒，默认值是106，即默认的唤醒粒度是1毫秒。如果开启了配置宏CONFIG_SCHED_DEBUG，可以通过文件“/proc/sys/kernel/sched_wakeup_granularity_ns”设置唤醒粒度。
空闲调度类的check_preempt_curr方法是函数check_preempt_curr_idle，算法是：无条件抢占，给当前进程设置需要重新调度的标志。
4．创建新进程时抢占
如图2.31所示，使用系统调用fork、clone或vfork创建新进程的时候，新进程可能抢占当前进程；使用函数kernel_thread创建新的内核线程的时候，新的内核线程可能抢占当前进程。
图2.31 创建新进程时抢占
5．内核抢占
内核抢占是指当进程在内核模式下运行的时候可以被其他进程抢占，需要打开配置宏CONFIG_PREEMPT。如果不支持内核抢占，当进程在内核模式下运行的时候，不会被其他进程抢占，带来的问题是：如果一个进程在内核模式下运行的时间很长，将导致交互式进程等待的时间很长，响应很慢，用户体验差。内核抢占就是为了解决这个问题。
支持抢占的内核称为抢占式内核，不支持抢占的内核称为非抢占式内核。个人计算机的桌面操作系统要求响应速度快，适合使用抢占式内核；服务器要求业务的吞吐率高，适合使用非抢占式内核。
每个进程的thread_info结构体有一个类型为int的成员preempt_count，称为抢占计数器，如图2.32所示。
图2.32 进程的抢占计数器
其中第0～7位是抢占计数，第8～15位是软中断计数，第16～19位是硬中断计数，第20位是不可屏蔽中断计数。
进程在内核模式下运行时，可以调用preempt_disable()以禁止其他进程抢占，preempt_disable()把抢占计数器的抢占计数部分加1。
local_bh_disable()禁止软中断抢占，把抢占计数器的软中断计数部分加2；函数__do_softirq()在执行软中断之前把软中断计数部分加1。
中断处理程序会把抢占计数器的硬中断计数部分加1，表示在硬中断上下文里面。
不可屏蔽中断的处理程序会把抢占计数器的不可屏蔽中断计数部分和硬中断计数部分分别加1，表示在不可屏蔽中断上下文里面。
进程在内核模式下运行的时候，如果抢占计数器的值不是0，那么其他进程不能抢占。可以看出，如果禁止软中断抢占，那么同时也禁止了其他进程抢占。
内核抢占增加了一些抢占点。
❑ 在调用preempt_enable()开启抢占的时候。
❑ 在调用local_bh_enable()开启软中断的时候。
❑ 在调用spin_unlock()释放自旋锁的时候。
❑ 在中断处理程序返回内核模式的时候。
（1）开启内核抢占时抢占：在调用preempt_enable()开启抢占的时候，把抢占计数器的抢占计数部分减1，如果抢占计数器变成0，并且当前进程设置了重新调度标志位，那么执行抢占调度。
#include/linux/preempt.h
#ifdef CONFIG_PREEMPT
#define preempt_enable() \
do { \
barrier(); \
if (unlikely(preempt_count_dec_and_test())) \
__preempt_schedule(); \
} while (0)
#endif
#define preempt_count_dec_and_test() __preempt_count_dec_and_test()
include/asm-generic/preempt.h
static __always_inline bool __preempt_count_dec_and_test(void)
{
return ! --*preempt_count_ptr() && tif_need_resched();
}
（2）开启软中断时抢占：在调用local_bh_enable()开启软中断的时候，如果抢占计数器变成0，并且为当前进程设置了重新调度标志位，那么执行抢占调度。
kernel/softirq.c
local_bh_enable -> __local_bh_enable_ip
void __local_bh_enable_ip(unsigned long ip, unsigned int cnt)
{
…
preempt_check_resched();
}
include/asm-generic/preempt.h
#define preempt_check_resched() \
do { \
if (should_resched(0)) \
__preempt_schedule(); \
} while (0)
static __always_inline bool should_resched(int preempt_offset)
{
return unlikely(preempt_count() == preempt_offset &&
tif_need_resched());
}
（3）释放自旋锁时抢占：调用spin_unlock()释放自旋锁的时候，调用函数preempt_enable()开启抢占，如果抢占计数器变成0，并且当前进程设置了重新调度标志位，那么执行抢占调度。
include/linux/spinlock_api_smp.h
spin_unlock -> raw_spin_unlock -> _raw_spin_unlock -> _raw_spin_unlock -> __raw_spin_unlock
static inline void __raw_spin_unlock(raw_spinlock_t *lock)
{
spin_release(&lock->dep_map, 1, _RET_IP_);
do_raw_spin_unlock(lock);
preempt_enable();
}
（4）中断处理程序返回内核模式时抢占：如果进程正在内核模式下运行，那么中断抢占时，ARM64架构的中断处理程序的入口是el1_irq。中断处理程序执行完以后，如果进程的抢占计数器是0，并且设置了需要重新调度的标志位，那么调用函数el1_preempt，函数el1_preempt调用函数preempt_schedule_irq以执行抢占调度。如果被选中的进程也设置了需要重新调度的标志位，那么继续执行抢占调度。
arch/arm64/kernel/entry.S
el1_irq:
kernel_entry 1
enable_dbg
#ifdef CONFIG_TRACE_IRQFLAGS
bl trace_hardirqs_off
#endif
irq_handler
#ifdef CONFIG_PREEMPT
ldr w24, [tsk, #TSK_TI_PREEMPT] // 读取抢占计数
cbnz w24, 1f // 抢占计数不等于0
ldr x0, [tsk, #TSK_TI_FLAGS] // 读取标志
tbz x0, #TIF_NEED_RESCHED, 1f // 需要重新调度？
Bl el1_preempt
1:
#endif
#ifdef CONFIG_TRACE_IRQFLAGS
bl trace_hardirqs_on
#endif
kernel_exit 1
ENDPROC(el1_irq)
#ifdef CONFIG_PREEMPT
el1_preempt:
mov x24, lr
1: bl preempt_schedule_irq //在函数中开启和禁止中断
ldr x0, [tsk, #TSK_TI_FLAGS] // 读取新的进程标志
tbnz x0, #TIF_NEED_RESCHED, 1b // 需要重新调度？
ret x24
#endif
函数preempt_schedule_irq执行抢占调度，选择一个进程抢占正在内核模式下执行的当前进程。如果被选中的进程也设置了需要重新调度的标志位，那么继续执行抢占调度。
kernel/sched/core.c
asmlinkage __visible void __sched preempt_schedule_irq(void)
{
enum ctx_state prev_state;
/*捕获需要修正的调用者 */
BUG_ON(preempt_count() || ! irqs_disabled());
prev_state = exception_enter();
do {
preempt_disable();
local_irq_enable();
__schedule(true);
local_irq_disable();
sched_preempt_enable_no_resched();
} while (need_resched());
exception_exit(prev_state);
}
6．高精度调度时钟
调度器选择一个进程运行以后，周期调度函数检查进程的运行时间是否超过限额。如果时钟频率是100赫兹，时钟每隔10毫秒发送一次中断请求，那么对进程运行时间的控制精度只能达到10毫秒。
高精度时钟的精度是纳秒，如果硬件层面有一个高精度时钟，那么可以使用高精度调度时钟精确地控制进程的运行时间。启用高精度调度时钟的方法如下。
（1）打开高精度定时器的配置宏CONFIG_HIGH_RES_TIMERS，自动打开高精度调度时钟的配置宏CONFIG_SCHED_HRTICK。
（2）头文件“kernel/sched/features.h”默认禁止调度特性“高精度调度时钟”:SCHED_FEAT (HRTICK, false)，需要修改为默认开启。
在运行队列中添加一个高精度定时器，其代码如下：
kernel/sched/sched.h
struct rq {
…
#ifdef CONFIG_SCHED_HRTICK
…
struct hrtimer hrtick_timer;
#endif
…
};
高精度定时器的回调函数是hrtick，该函数调用当前进程所属调度类的task_tick方法。
kernel/sched/core.c
static enum hrtimer_restart hrtick(struct hrtimer *timer)
{
struct rq *rq = container_of(timer, struct rq, hrtick_timer);
struct rq_flags rf;
rq_lock(rq, &rf);
update_rq_clock(rq);
rq->curr->sched_class->task_tick(rq, rq->curr, 1);
rq_unlock(rq, &rf);
return HRTIMER_NORESTART;
}
当公平调度类调用函数pick_next_task_fair以选择一个普通进程时，启动高精度定时器，把相对超时设置为普通进程的理想运行时间。
当限期调度类调用函数pick_next_task_dl以选择一个限期进程时，启动高精度定时器，把相对超时设置为限期进程的运行时间。