极客时间已完结课程限时免费阅读

17 | 调度（下）：抢占式调度是如何发生的？

17 | 调度（下）：抢占式调度是如何发生的？-极客时间

17 | 调度（下）：抢占式调度是如何发生的？

2019-05-06 刘超 来自北京
《趣谈Linux操作系统》
课程介绍

讲述：刘超

时长08:52大小8.10M

上一节，我们讲了主动调度，就是进程运行到一半，因为等待 I/O 等操作而主动让出 CPU，然后就进入了我们的“进程调度第一定律”。所有进程的调用最终都会走 __schedule 函数。那这个定律在这一节还是要继续起作用。

抢占式调度

上一节我们讲的主动调度是第一种方式，第二种方式，就是抢占式调度。什么情况下会发生抢占呢？
最常见的现象就是一个进程执行时间太长了，是时候切换到另一个进程了。那怎么衡量一个进程的运行时间呢？在计算机里面有一个时钟，会过一段时间触发一次时钟中断，通知操作系统，时间又过去一个时钟周期，这是个很好的方式，可以查看是否是需要抢占的时间点。
时钟中断处理函数会调用 scheduler_tick()，它的代码如下：
void scheduler_tick(void)
{
int cpu = smp_processor_id();
struct rq *rq = cpu_rq(cpu);
struct task_struct *curr = rq->curr;
......
curr->sched_class->task_tick(rq, curr, 0);
cpu_load_update_active(rq);
calc_global_load_tick(rq);
......
}
这个函数先取出当前 CPU 的运行队列，然后得到这个队列上当前正在运行中的进程的 task_struct，然后调用这个 task_struct 的调度类的 task_tick 函数，顾名思义这个函数就是来处理时钟事件的。
如果当前运行的进程是普通进程，调度类为 fair_sched_class，调用的处理时钟的函数为 task_tick_fair。我们来看一下它的实现。
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);
}
......
}
根据当前进程的 task_struct，找到对应的调度实体 sched_entity 和 cfs_rq 队列，调用 entity_tick。
static void
entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, int queued)
{
update_curr(cfs_rq);
update_load_avg(curr, UPDATE_TG);
update_cfs_shares(curr);
.....
if (cfs_rq->nr_running > 1)
check_preempt_tick(cfs_rq, curr);
}
在 entity_tick 里面，我们又见到了熟悉的 update_curr。它会更新当前进程的 vruntime，然后调用 check_preempt_tick。顾名思义就是，检查是否是时候被抢占了。
static void
check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr)
{
unsigned long ideal_runtime, delta_exec;
struct sched_entity *se;
s64 delta;
ideal_runtime = sched_slice(cfs_rq, curr);
delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;
if (delta_exec > ideal_runtime) {
resched_curr(rq_of(cfs_rq));
return;
}
......
se = __pick_first_entity(cfs_rq);
delta = curr->vruntime - se->vruntime;
if (delta < 0)
return;
if (delta > ideal_runtime)
resched_curr(rq_of(cfs_rq));
}
check_preempt_tick 先是调用 sched_slice 函数计算出的 ideal_runtime。ideal_runtime 是一个调度周期中，该进程运行的实际时间。
sum_exec_runtime 指进程总共执行的实际时间，prev_sum_exec_runtime 指上次该进程被调度时已经占用的实际时间。每次在调度一个新的进程时都会把它的 se->prev_sum_exec_runtime = se->sum_exec_runtime，所以 sum_exec_runtime-prev_sum_exec_runtime 就是这次调度占用实际时间。如果这个时间大于 ideal_runtime，则应该被抢占了。
除了这个条件之外，还会通过 __pick_first_entity 取出红黑树中最小的进程。如果当前进程的 vruntime 大于红黑树中最小的进程的 vruntime，且差值大于 ideal_runtime，也应该被抢占了。
当发现当前进程应该被抢占，不能直接把它踢下来，而是把它标记为应该被抢占。为什么呢？因为进程调度第一定律呀，一定要等待正在运行的进程调用 __schedule 才行啊，所以这里只能先标记一下。
标记一个进程应该被抢占，都是调用 resched_curr，它会调用 set_tsk_need_resched，标记进程应该被抢占，但是此时此刻，并不真的抢占，而是打上一个标签 TIF_NEED_RESCHED。
static inline void set_tsk_need_resched(struct task_struct *tsk)
{
set_tsk_thread_flag(tsk,TIF_NEED_RESCHED);
}
另外一个可能抢占的场景是当一个进程被唤醒的时候。
我们前面说过，当一个进程在等待一个 I/O 的时候，会主动放弃 CPU。但是当 I/O 到来的时候，进程往往会被唤醒。这个时候是一个时机。当被唤醒的进程优先级高于 CPU 上的当前进程，就会触发抢占。try_to_wake_up() 调用 ttwu_queue 将这个唤醒的任务添加到队列当中。ttwu_queue 再调用 ttwu_do_activate 激活这个任务。ttwu_do_activate 调用 ttwu_do_wakeup。这里面调用了 check_preempt_curr 检查是否应该发生抢占。如果应该发生抢占，也不是直接踢走当前进程，而是将当前进程标记为应该被抢占。
static void ttwu_do_wakeup(struct rq *rq, struct task_struct *p, int wake_flags,
struct rq_flags *rf)
{
check_preempt_curr(rq, p, wake_flags);
p->state = TASK_RUNNING;
trace_sched_wakeup(p);
到这里，你会发现，抢占问题只做完了一半。就是标识当前运行中的进程应该被抢占了，但是真正的抢占动作并没有发生。

抢占的时机

真正的抢占还需要时机，也就是需要那么一个时刻，让正在运行中的进程有机会调用一下 __schedule。
你可以想象，不可能某个进程代码运行着，突然要去调用 __schedule，代码里面不可能这么写，所以一定要规划几个时机，这个时机分为用户态和内核态。

用户态的抢占时机

对于用户态的进程来讲，从系统调用中返回的那个时刻，是一个被抢占的时机。
前面讲系统调用的时候，64 位的系统调用的链路位 do_syscall_64->syscall_return_slowpath->prepare_exit_to_usermode->exit_to_usermode_loop，当时我们还没关注 exit_to_usermode_loop 这个函数，现在我们来看一下。
static void exit_to_usermode_loop(struct pt_regs *regs, u32 cached_flags)
{
while (true) {
/* We have work to do. */
local_irq_enable();
if (cached_flags & _TIF_NEED_RESCHED)
schedule();
......
}
}
现在我们看到在 exit_to_usermode_loop 函数中，上面打的标记起了作用，如果被打了 _TIF_NEED_RESCHED，调用 schedule 进行调度，调用的过程和上一节解析的一样，会选择一个进程让出 CPU，做上下文切换。
对于用户态的进程来讲，从中断中返回的那个时刻，也是一个被抢占的时机。
在 arch/x86/entry/entry_64.S 中有中断的处理过程。又是一段汇编语言代码，你重点领会它的意思就行，不要纠结每一行都看懂。
common_interrupt:
ASM_CLAC
addq $-0x80, (%rsp)
interrupt do_IRQ
ret_from_intr:
popq %rsp
testb $3, CS(%rsp)
jz retint_kernel
/* Interrupt came from user space */
GLOBAL(retint_user)
mov %rsp,%rdi
call prepare_exit_to_usermode
TRACE_IRQS_IRETQ
SWAPGS
jmp restore_regs_and_iret
/* Returning to kernel space */
retint_kernel:
#ifdef CONFIG_PREEMPT
bt $9, EFLAGS(%rsp)
jnc 1f
0: cmpl $0, PER_CPU_VAR(__preempt_count)
jnz 1f
call preempt_schedule_irq
jmp 0b
中断处理调用的是 do_IRQ 函数，中断完毕后分为两种情况，一个是返回用户态，一个是返回内核态。这个通过注释也能看出来。
咱们先来看返回用户态这一部分，先不管返回内核态的那部分代码，retint_user 会调用 prepare_exit_to_usermode，最终调用 exit_to_usermode_loop，和上面的逻辑一样，发现有标记则调用 schedule()。

内核态的抢占时机

用户态的抢占时机讲完了，接下来我们看内核态的抢占时机。
对内核态的执行中，被抢占的时机一般发生在 preempt_enable() 中。
在内核态的执行中，有的操作是不能被中断的，所以在进行这些操作之前，总是先调用 preempt_disable() 关闭抢占，当再次打开的时候，就是一次内核态代码被抢占的机会。
就像下面代码中展示的一样，preempt_enable() 会调用 preempt_count_dec_and_test()，判断 preempt_count 和 TIF_NEED_RESCHED 是否可以被抢占。如果可以，就调用 preempt_schedule->preempt_schedule_common->__schedule 进行调度。还是满足进程调度第一定律的。
#define preempt_enable() \
do { \
if (unlikely(preempt_count_dec_and_test())) \
__preempt_schedule(); \
} while (0)
#define preempt_count_dec_and_test() \
({ preempt_count_sub(1); should_resched(0); })
static __always_inline bool should_resched(int preempt_offset)
{
return unlikely(preempt_count() == preempt_offset &&
tif_need_resched());
}
#define tif_need_resched() test_thread_flag(TIF_NEED_RESCHED)
static void __sched notrace preempt_schedule_common(void)
{
do {
......
__schedule(true);
......
} while (need_resched())
在内核态也会遇到中断的情况，当中断返回的时候，返回的仍然是内核态。这个时候也是一个执行抢占的时机，现在我们再来上面中断返回的代码中返回内核的那部分代码，调用的是 preempt_schedule_irq。
asmlinkage __visible void __sched preempt_schedule_irq(void)
{
......
do {
preempt_disable();
local_irq_enable();
__schedule(true);
local_irq_disable();
sched_preempt_enable_no_resched();
} while (need_resched());
......
}
preempt_schedule_irq 调用 __schedule 进行调度。还是满足进程调度第一定律的。

总结时刻

好了，抢占式调度就讲到这里了。我这里画了一张脑图，将整个进程的调度体系都放在里面。
这个脑图里面第一条就是总结了进程调度第一定律的核心函数 __schedule 的执行过程，这是上一节讲的，因为要切换的东西比较多，需要你详细了解每一部分是如何切换的。
第二条总结了标记为可抢占的场景，第三条是所有的抢占发生的时机，这里是真正验证了进程调度第一定律的。

课堂练习

通过对于内核中进程调度的分析，我们知道，时间对于调度是很重要的，你知道 Linux 内核是如何管理和度量时间的吗？
欢迎留言和我分享你的疑惑和见解，也欢迎你收藏本节内容，反复研读。你也可以把今天的内容分享给你的朋友，和他一起学习、进步。
分享给需要的人，Ta购买本课程，你将得20元
生成海报并分享

赞 18

提建议

© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
上一篇
16 | 调度（中）：主动调度是如何发生的？
下一篇
18 | 进程的创建：如何发起一个新项目？
 写留言

精选留言(45)

  • why
    2019-05-10
    - 抢占式调度 - 两种情况: 执行太久, 需切换到另一进程; 另一个高优先级进程被唤醒 - 执行太久: 由时钟中断触发检测, 中断处理调用 scheduler_tick - 取当前进程 task_struct->task_tick_fair()->取 sched_entity cfs_rq 调用 entity_tick() - entity_tick() 调用 update_curr 更新当前进程 vruntime, 调用 check_preempt_tick 检测是否需要被抢占 - check_preempt_tick 中计算 ideal_runtime(一个调度周期中应该运行的实际时间), 若进程本次调度运行时间 > ideal_runtime, 则应该被抢占 - 要被抢占, 则调用 resched_curr, 设置 TIF_NEED_RESCHED, 将其标记为应被抢占进程(因为要等待当前进程运行 `__schedule`) - 另一个高优先级进程被唤醒: 当 I/O 完成, 进程被唤醒, 若优先级高于当前进程则触发抢占 - try_to_wake_up()->ttwu_queue() 将唤醒任务加入队列 调用 ttwu_do_activate 激活任务 - 调用 tt_do_wakeup()->check_preempt_curr() 检查是否应该抢占, 若需抢占则标记 - 抢占时机: 让进程调用 `__schedule`, 分为用户态和内核态 - 用户态进程 - 时机-1: 从系统调用中返回, 返回过程中会调用 exit_to_usermode_loop, 检查 `_TIF_NEED_RESCHED`, 若打了标记, 则调用 schedule() - 时机-2: 从中断中返回, 中断返回分为返回用户态和内核态(汇编代码: arch/x86/entry/entry_64.S), 返回用户态过程中会调用 exit_to_usermode_loop()->shcedule() - 内核态进程 - 时机-1: 发生在 preempt_enable() 中, 内核态进程有的操作不能被中断, 会调用 preempt_disable(), 在开启时(调用 preempt_enable) 时是一个抢占时机, 会调用 preempt_count_dec_and_test(), 检测 preempt_count 和标记, 若可抢占则最终调用 `__schedule` - 时机-2: 发生在中断返回, 也会调用 `__schedule`
    展开
    47
  • garlic
    2019-08-05
    linux内核依靠硬件定时电路特定时钟频率，tick rate，触发时钟中断，通过中断处理，实现系统时间更新， 定时器设置，延时处理， 学习笔记 https://garlicspace.com/2019/08/04/linux如何管理和度量时间/

    作者回复: 赞，很牛

    28
  • 兴文
    2019-05-30
    如果用户进程一直在用户态执行，没有发生系统调用和中断，就不会触发scheduler操作，那这个进程是不是一直占有CPU啊？

    作者回复: tick会中断他的

    共 3 条评论
    23
  • 多选参数
    2020-05-25
    针对大部分留言说假如没有系统调用等，那岂不是会死循环这类问题。简单来说就是如果发生了中断，那么当前进程肯定会陷入内核态。所以可能会有标记步骤和真正的抢占步骤。详细点来说，当一个进程正在 CPU 上运行，如果发生时钟中断，那么需要去处理这个时钟中断，也就是会调用相应的中断处理函数，而相应的中断处理函数需要在内核态下执行，所以当前进程会陷入内核态，然后保存用户态的情况，然后判断是否需要进行标记。然后中断函数处理完之后，会返回用户态，这个时候又会发生抢占。
    展开

    作者回复: 对的

    共 7 条评论
    19
  • 卫江
    2019-07-01
    老师，想问一下，中断处理程序到底是由谁调用的，而且一切函数调用肯定需要栈，那中断在哪个栈上面执行，如果在一个单核的计算机上面，有一个进程处于用户态死循环，没有调用系统调用，如果这个时候发生了时间中断，内核是怎么处理的，怎么打断当前的进程，从而可能影响调度？

    作者回复: 后面有专门的节讲中断，到时候回来看，就对上了。中断的处理是在内核里面的，用不到进程的用户栈。当cpu收到中断的时候，就会停止当然指令的运行，去调用内核中的中断处理函数。应用再怎么死循环，内核里面说把他拿下来，不就拿下来了吗。

    共 3 条评论
    18
  • zhouzg
    2019-06-20
    看《计算器是怎样跑起来的》书中有Z80的电路图，里面有介绍时钟发生器，它会把电流信号切割成单位，这样就可以度量和管理时钟了吧？

    作者回复: 牛

    12
  • 焰火
    2019-05-07
    进程调度第一定律总结的太棒了。 另外有个问题想问下老师：我把整个调度系统想成一个进程，这个调度进程来实现task调度？ 如果是这样的，Linux如果跑在单CPU上，多进程是怎么调度的呢？

    作者回复: 不能把调度系统想象成一个进程，他是管家，不是干活的。不存在他和别人一起竞争的事情，他想把谁从cpu上拿下来，就能拿下来，他只要一改指令指针寄存器，就能拿下来

    共 3 条评论
    9
  • zhengfan
    2020-04-16
    刘老师： 您在文中提到： 检查是否是时候被抢占的函数调用：check_preempt_tick，其中说到： “ideal_runtime 是一个调度周期中，该进程运行的实际时间。“ 从字面意思看似乎名实不符。我查到的一些资料多解释为“typical time slice"或者“target effort”。 我也粗略浏览了一下sched_slice方法的实现，似乎是通过rq.load,entity.load等参数计算出来一个预期的工作时长。 您看是不是应该改成：“ideal_runtime 是一个调度周期中，该进程预期的运行分配时间”为宜？
    展开
    6
  • JT
    2019-09-29
    老师你讲得太好了，清楚易懂，我自己看了《Linux内核设计与实现》，然后接着看《深入Linux内核》，前前后后尝试看了几遍，但发现怎么也啃不下。看你的课，然后总结，有了总体思路后，再自己阅读内核代码，收获真的是太大了
    共 3 条评论
    4
  • 二星球
    2019-05-06
    老师您好，我喜欢边调试边阅读代码，代码是死的但是跑起来是活的变的，linux内核代码有没有好的调试方式，或者添加打印日志的方式；另外时钟中断是怎么触发的呢，我记得cpu里面没有时钟这个物理设备的，应该有类似单片机晶振这个东西去无限循环执行指令的，这个也不会有时钟中断呀

    作者回复: 有的，看后面实践环节

    5
  • 蹦哒
    2020-06-14
    “进程调度第一定律”，以及在内核中进程和线程统一用task_struct表示，让我想起了一个设计模式：组合模式（Composite Design Pattern）

    作者回复: 融会贯通

    4
  • liu-dan
    2020-06-07
    看了好几遍，感觉慢慢能串联起来，虽然不如经典的kernel书籍严谨和全面，但是更容易理解，讲的确实很不错，很受用，感谢老师！

    作者回复: 一句更容易理解胜过千言万语，谢谢

    2
  • MARK
    2019-05-06
    Linux内核通过时钟中断管理和度量时间. Linux在初始化时会使用一个init_IRQ()函数设定定时周期(IRQ:Interrupt Request)，time_init()中调用setup_irq()设置时间中断向量irq 0；中断服务程序是timer_interrupt()，会调用另一个函数do_timer_interrupt(),do_timer_interrupt还会调用do_timer更新系统时间。do_timer中的工作包括，让全局变量jiffies增加1，并且调用update_process_times来更新进程的时间片以及修改进程的动态优先级... 搜索的一点信息，期待老师的详细讲解^_^
    展开
    2
  • 相逢是缘
    2020-08-15
    抢占式调度 在计算机里面有一个时钟，会过一段时间触发一次时钟中断，通知操作系统，时间又过去一个时钟周期，这是个很好的方式，可以查看是否是需要抢占的时间点 一、时钟中断处理函数会调用 scheduler_tick() ---这个函数取出当前 CPU 的运行队列，然后得到这个队列上当前正在运行中的进程的 task_struct，然后调用这个 task_struct 的调度类的 task_tick 函数； ---如果为普通进程，调度类为 fair_sched_class，调用的处理时钟的函数为 task_tick_fair ---根据他当前task_struct，找到对应的调度实体 sched_entity 和 cfs_rq 队列，调用 entity_tick ---entity_tick 里面，更新当前进程的 vruntime，然后调用 check_preempt_tick，检查是否是时候被抢占了 ---抢占的两个条件： 1、所以 sum_exec_runtime-prev_sum_exec_runtime 就是这次调度占用实际时间。如果这个时间大于 ideal_runtime，则应该被抢占了； 2、还会通过 __pick_first_entity 取出红黑树中最小的进程。如果当前进程的 vruntime 大于红黑树中最小的进程的 vruntime，且差值大于 ideal_runtime，也应该被抢占了； ---现当前进程应该被抢占，不能直接把它踢下来，而是把它标记为应该被抢占，而是打上一个标签 TIF_NEED_RESCHED 二、一个可能抢占的场景是当一个进程被唤醒的时候 ---但是当 I/O 到来的时候，进程往往会被唤醒。这个时候是一个时机。当被唤醒的进程优先级高于 CPU 上的当前进程，就会触发抢占 ---try_to_wake_up() 调用 ttwu_queue 将这个唤醒的任务添加到队列当中。ttwu_queue 再调用 ttwu_do_activate 激活这个任务。ttwu_do_activate 调用 ttwu_do_wakeup。这里面调用了 check_preempt_curr 检查是否应该发生抢占。如果应该发生抢占，也不是直接踢走当前进程，而是将当前进程标记为应该被抢占 抢占的时机： 用户态的抢占时机： ---从系统调用中返回的那个时刻，是一个被抢占的时机； do_syscall_64->syscall_return_slowpath->prepare_exit_to_usermode->exit_to_usermode_loop if (cached_flags & _TIF_NEED_RESCHED) schedule(); ---从中断中返回的那个时刻，也是一个被抢占的时机 中断处理调用的是 do_IRQ 函数，中断完毕后分为两种情况，一个是返回用户态，一个是返回内核态,retint_user 会调用 prepare_exit_to_usermode，最终调用 exit_to_usermode_loop,之后就和系统调用一样 内核态的抢占时机： ---在内核态的执行中，有的操作是不能被中断的，所以在进行这些操作之前，总是先调用 preempt_disable() 关闭抢占，当再次打开的时候，就是一次内核态代码被抢占的机会； eempt_enable() 会调用 preempt_count_dec_and_test()，判断 preempt_count 和 TIF_NEED_RESCHED 是否可以被抢占。如果可以，就调用 preempt_schedule->preempt_schedule_common->__schedule 进行调度 ---在内核态也会遇到中断的情况，当中断返回的时候，返回的仍然是内核态。
    展开
    1
  • 有米
    2020-03-21
    标记-清理。jvm回收内存的方法之一。看来都是相通的
    1
  • neohope
    2019-12-09
    操作系统内核，最简化之后，其实就是一个大循环，通过各种中断，尤其是时钟的中断来推动内核的运行，直到收到退出信号为止。 今天对于“抢占式调度”，有了进一步的理解：“抢占”仍然是内核帮各个进程抢，而不是想获取CPU时间的进程自己抢的，想获取CPU时间的进程，只能采取把自己的进程优先级调高的方式，让自己排队靠前而已。说白了，内核只是用了一种更合理的方式，来更好的安排CPU运行时间，防止饥饿和霸占CPU资源。而这一切都是在内核里完成的，用户进程想获取CPU和让渡CPU都是要靠内核态。
    展开
    2
  • wwj
    2019-05-15
    物理内存统一管理 本身也是程序 他的内存如何管理

    作者回复: 物理内存的管理程序也是程序，也分代码部分和数据部分，代码部分当然在内核代码段里面了，系统启动的时候就加载了。数据部分大部分分配在直接映射区，也会分配页表，页表在哪里呢？页表的根在代码段的那个区域里面。

    1
  • 白雲城主
    2022-03-03
    老师，咨询一个问题，比如我的TICK 配置的250，也就是每 4ms 调用一次 task_tick_fair，双核CPU 创建了4个用户进程一直在跑，此时应该无论 min_granularity_ns 是多少 ，每个进程至少running 4ms以上，但是用trace-cmd抓的有低于4ms 的情况，这是如何发生的 ？
  • 白雲城主
    2022-03-02
    双核CPU ，最小时间片为1.5ms，调度周期为12ms，起了6个进程，照理说应该每个进程至少运行1.5ms 才被抢占，还不考虑tick time 的情况，但是抓的 schedule trace event 看到的每个进程大概只运行了1.5us就被抢占了，这个是啥问题额 ？ sysctl_sched .sysctl_sched_latency : 12.000000 .sysctl_sched_min_granularity : 1.500000
    展开
  • 凉凉
    2022-02-05
    老师 我想问一下 在有多个cpu 的情况下或者是多核的情况，进程运行过程中cpu被抢占了 这时候能不能把这个进程调度到其他 cpu 或者 cpu 其他核运行