1.开场白
环境：
处理器架构：arm64
内核源码：linux-5.11
ubuntu版本：20.04.1
代码阅读工具：vim+ctags+cscope
我们或许经常听说过内核抢占，可是我们是否真正理解它呢?内核抢占和抢占式内核究竟有什么关系呢?抢占计数器究竟干什么用?... 本文我们就来好好讨论下，关于内核抢占的一些技术细节，力求让大家理解内核抢占。
注：本文主要关注CFS调度类。
2.内核抢占和抢占式内核
我们经常使用uname -a命令能看到“PREEMPT”的字样，没错，我们使用的是抢占式内核。
- # uname -a
- Linux (none) 5.11.0-g08a3831f3ae1 #1 SMP PREEMPT Fri Apr 30 17:41:53 CST 2021 aarch64 GNU/Linux
那什么是抢占式内核呢? 实际上，支持内核抢占的内核叫做抢占式内核，不支持内核抢占的内核叫做不可抢占式内核。那么问题又来了，什么是内核抢占呢?我们都知道，拿周期性的tick来说：对于用户任务，当每个时钟中断到来后都会检查它的实际运行时间是否超过理想运行时间，或者运行队列中有没有优先级更高的进程，一般如果满足其中一个条件就会设置重新调度标志，然后在中断返回用户态的前夕发生调度，这是所谓的用户任务抢占。
但是如果处于一个内核态的任务正在运行，这个时候发生中断唤醒了一个高优先级的任务，那么这个被唤醒的任务能否被调度执行呢?这个时候就会分两种情况分析，如果是抢占式内核那么高优先级任务就有可能抢占当前任务而调度执行(之所有是有可能是因为两者虚拟运行时间差值要大于抢占粒度才允许抢占)，如果是不可抢占式内核那么不允许抢占，除非当前进程执行完或者主动发生调度高优先级进程该有机会被调度。
也就是说，支持内核抢占的内核不仅允许在用户态的任务可以被抢占，处在内核态的任务也允许被抢占(请注意这里说的是内核态，因为用户空间任务可以通过系统调用等进入内核态)，这样对于交互性或者低延迟的应用场景很友好，如手持设备和桌面应用，响应会很快。而对于服务器来说，它就对吞吐量要求较高，希望获得更多的cpu时间，而交互性或者低延迟都是次要的，所以被设计成不可抢占式内核。
下图给出非抢占式内核调度情况：
下图给出抢占式内核调度情况：
对比两个图可以发现：采用抢占式内核调度的情况下，在中断中唤醒一个高优先级任务能够得到很好的响应。
关于抢占式内核还是不可抢占式内核的选择在源码的kernel/Kconfig.preempt有所描述：
- config PREEMPT_NONE
- bool "No Forced Preemption (Server)"
- help
- ¦ This is the traditional Linux preemption model, geared towards
- ¦ throughput. It will still provide good latencies most of the
- ¦ time, but there are no guarantees and occasional longer delays
- ¦ are possible.
-
- ¦ Select this option if you are building a kernel for a server or
- ¦ scientific/computation system, or if you want to maximize the
- ¦ raw processing power of the kernel, irrespective of scheduling
- ¦ latencies.
-
- config PREEMPT
- bool "Preemptible Kernel (Low-Latency Desktop)"
- depends on !ARCH_NO_PREEMPT
- select PREEMPTION
- select UNINLINE_SPIN_UNLOCK if !ARCH_INLINE_SPIN_UNLOCK
- select PREEMPT_DYNAMIC if HAVE_PREEMPT_DYNAMIC
- help
- ¦ This option reduces the latency of the kernel by making
- ¦ all kernel code (that is not executing in a critical section)
- ¦ preemptible. This allows reaction to interactive events by
- ¦ permitting a low priority process to be preempted involuntarily
- ¦ even if it is in kernel mode executing a system call and would
- ¦ otherwise not be about to reach a natural preemption point.
- ¦ This allows applications to run more 'smoothly' even when the
- ¦ system is under load, at the cost of slightly lower throughput
- ¦ and a slight runtime overhead to kernel code.
-
- ¦ Select this if you are building a kernel for a desktop or
- ¦ embedded system with latency requirements in the milliseconds
- ¦ range.
上面列举了两个编译选项一个是支持内核抢占一个是不支持内核抢占，其实还有PREEMPT_VOLUNTARY和PREEMPT_RT，前者会显式增加一些抢占点，后者用于支持实时性 。
3.重新调度标志和抢占计数器
内核有些路径是不允许调度的，如原子上下文，那么这个时候如果唤醒一个高优先级的任务或者tick的时候检查可重新调度条件满足，那么高优先级的任务将不能马上得到执行，但是我又要标识一下需要重新调度，那么就需要设置重新调度标志，当返回到可调度上下文的时候(如开抢占)，这个时候就会检查是否设置了这个标志来决定是否调用调度器来选择下一个任务来运行。
标识重新调度是设置：
- //当前任务的task_struct的thread_info的flag
- stsk->thread_info->flags设置TIF_NEED_RESCHED标志
- #define TIF_NEED_RESCHED 1
内核的某些路径上设置了这个标志之后，将在最近的调度点发生调度(可能是最近开启抢占的时候，也可能是最近中断异常返回的时候)。
当前任务被设置了重新调度标志，只是表明不久的将来会发生调度，并不是马上发生调度，对于用户任务来说就是中断异常返回用户态的前夕发生调度，而对于处于内核态的任务来说，想要在内核态抢占当前进程，仅仅置位重新调度标志还不行，还需要判断当前进程的抢占计数器是否为0。
所有对于处于内核态的任务来说，抢占计数器对于重新调度至关重要，只要抢占计数器不为0，无论被唤醒的任务在紧急都不能获得调度器，我们来看看这个抢占计数器：
- tsk->thread_info->preempt.count
我们来看下对于arm64架构，抢占计数器的定义：
- 24 struct thread_info {
- 25 unsigned long flags;
-
- 29 union {
- 30 u64 preempt_count;
- 31 struct {
- 32 #ifdef CONFIG_CPU_BIG_ENDIAN
- 33 u32 need_resched;
- 34 u32 count;
- 35 #else
- 36 u32 count;
- 37 u32 need_resched;
- 38 #endif
- 39 } preempt;
- 40 };
- 45 };
可以发现它是一个共用体，内核某些路径使用preempt_count，有的是preempt，为何会使用这么奇怪的定义呢?因为一个成员可以表示两种状态：重新调度标志和抢占计数器的数值
当需要重新调度的时候会置位flags的TIF_NEED_RESCHED标志，与此同时会将preempt.need_resched清零。当检查thread_info 的preempt_count==0成立时，说明抢占计数器的数值为0且flags的TIF_NEED_RESCHED标志被置位，这个时候可以进程重新调度(如中断返回内核态前夕的检查)。
下面看下如何设置重新调度标志：
- resched_curr //kernel/sched/core.c
- 613 if (cpu == smp_processor_id()) {
- 614 set_tsk_need_resched(curr);
- 615 set_preempt_need_resched();
- 616 return;
- 617 }
-
-
- 29 static inline void set_preempt_need_resched(void) //arch/arm64/include/asm/preempt.h
- 30 {
- 31 current_thread_info()->preempt.need_resched = 0;
- 32 }
-
当内核的某个路径设置重新调度标志(如时钟中断tick时)，会调用到resched_curr 来设置重新调度标志：可以看到除了设置任务的flags的TIF_NEED_RESCHED标志外，还设置了preempt.need_resched为0。
如何清除重新调度标志：
- kernel/sched/core.c
- __schedule //主动调度或抢占式调度 都会调用到这
- 5046 clear_tsk_need_resched(prev);
- 5047 clear_preempt_need_resched();
-
- //arch/arm64/include/asm/preempt.h
- 34 static inline void clear_preempt_need_resched(void)
- 35 {
- 36 current_thread_info()->preempt.need_resched = 1;
- 37 }
可以看到在主调度器中，除了调用clear_tsk_need_resched来清除任务的flags的TIF_NEED_RESCHED标志外，会调用clear_preempt_need_resched来设置preempt.need_resched为1, 来清除重新调度。
下面为抢占计数器的各个域的表示：
0-7 表示抢占计数 ，8-15表示软中断计数， 16-19表示硬中断计数，20-23表示不可屏蔽中断计数。当进入不同的上下文时会设置响应的位域，表示在某个上下文中，当某个位域被设置，抢占计数器不为0，任务在内核态就不容许被抢占。
所以，抢占计数器有两个作用：一个是标识内核路径在某个原子上下文，一个是用来判断是否允许任务在内核态被抢占。
- include/linux/preempt.h
-
- 85
- 93 #define in_nmi() (nmi_count()) //判断是否在 不可屏蔽中断上下文
- 94 #define in_hardirq() (hardirq_count()) //判断是否在硬中断上下文
- 95 #define in_serving_softirq() (softirq_count() & SOFTIRQ_OFFSET) //判断是否在软中断上下文
- 96 #define in_task() (!(in_nmi() | in_hardirq() | in_serving_softirq())) //判断是否在进程上下文
- 97
-
-
- 98
- 104 #define in_irq() (hardirq_count()) //判断是否在硬中断上下文
- 105 #define in_softirq() (softirq_count()) //判断是否在软中断上下文（关闭软中断或者在执行软中断）
- 106 #define in_interrupt() (irq_count()) //判断是否在中断上下文（包括硬中断 软中断和不可屏蔽中断）
-
-
- //判断是否在原子上下文（抢占计数器不为0）
- 144 #define in_atomic() (preempt_count() != 0)
4.内核抢占的调度时机
这里调度时机我将它细分为两种情况，一种是不进行调度的cheek点，一种是真正的抢占点(即是调用主调度器进行调度)：
cheek点->
tick的时候 : 满足条件(任务使用完理想运行时间，运行时间大于最小抢占粒度且运行队列有优先级更高的任务) 时，设置TIF_NEED_RESCHED标志,最近的抢占点发生调度 。
唤醒抢占 : 满足条件(唤醒的任务与当前任务的虚拟运行时间差值大于最小唤醒抢占粒度 ，唤醒的任务虚拟运行时间更小) 时， 设置TIF_NEED_RESCHED标志，最近的抢占点发生调度。
抢占点->
中断返回内核态 : 满足条件(重新调度标志置位且抢占计数器为0) 时， 抢占式调度 。
打开抢占的时候 : (如开抢占，开中断下半部，释放自旋锁) 满足条件(重新调度标志置位且抢占计数器为0)时， 抢占式调度。
开启软中断的时候 ： 满足条件(重新调度标志置位且抢占计数器为0)时， 抢占式调度。
中断返回内核态是常规的抢占点，一般情况下即使没有其他中断产生，周期性的tick中断也会发生， 满足条件(重新调度标志置位且抢占计数器为0)时，当前任务就会被抢占。而在一些会发生多任务竟态的临界区中，我们需要关闭内核抢占，有的直接调用preempt_disable, 有的是间接调用preempt_disable(如申请自旋锁的临界区), 有的则是关闭软中断等，这些都会导致抢占计数器不为0，但是在这些临界区中如果中断唤醒了高优先级的任务，中断返回内核态的前夕是不能进行调度的，所以在这些临界区结束的时候会检查调度条件是否满足，如果满足进行抢占式调度，从而使得被唤醒的任务被及时的响应。一般，一些cheek点设置了当前任务的重新调度标志之后，如果抢占计数器为0，会在最近的抢占点发生调度(就是上面所说的三种情况)。还有需要注意的是：关抢占的临界区中，只是禁止了当前任务所在cpu的内核抢占，其他cpu依然可以进行内核抢占，如果这段临界区有可能被其他cpu访问到，可以直接使用自旋锁来保护。
4.1 cheek点
1) 时钟中断tick时：
- kernel/sched/core.c
-
- scheduler_tick
- ->curr->sched_class->task_tick(rq, curr, 0)
- ->task_tick_fair
- ->entity_tick
- ->check_preempt_tick
- ->4374 if (delta_exec > ideal_runtime) { //1.当前任务的实际运行时间大于理想运行时间
- 4375 resched_curr(rq_of(cfs_rq)); //设置重新调度标志
- 4389 if (delta_exec < sysctl_sched_min_granularity) //当前任务的实际运行时间 小于 最小调度粒度吗？
- 4390 return;
-
- 4398 if (delta > ideal_runtime) //2.红黑树最左边的任务的虚拟运行时间和当前任务的虚拟运行时间的差值小于 理想运行时间
- 4399 resched_curr(rq_of(cfs_rq)); //设置重新调度标志
每个时钟tick到来时，会调用scheduler_tick来检查是否需要重新调度，以下两个条件有一个发生都会设置重新调度标志：
当前任务的实际运行时间大于理想运行时间(保证任务在一个调度周期内运行时间不会超过理想运行时间，防止“流氓”任务一直霸占cpu，通过周期性的时钟中断夺回处理器的使用权)。
当前任务的实际运行时间大于最小调度粒度，且红黑树最左边的任务的虚拟运行时间和当前任务的虚拟运行时间的差值小于理想运行时间(红黑树中的高优先级的任务可以抢占当前任务)。
2)唤醒抢占：
在fork和正常的唤醒路径上：
fork路径:
- kernel/fork.c
-
- kernel_clone
- ->wake_up_new_task(p)
- ->check_preempt_curr(rq, p, WF_FORK)
- ->rq->curr->sched_class->check_preempt_curr(rq, p, flags)
- ->check_preempt_wakeup //kernel/sched/fair.c
- -> 6994 if (wakeup_preempt_entity(se, pse) == 1) { //唤醒的任务的虚拟运行时间和当前任务的虚拟运行时间差值小于最新唤醒抢占粒度转换的虚拟运行时间
- 6995
- 6999 if (!next_buddy_marked)
- 7000 set_next_buddy(pse);
- 7001 goto preempt;
- 7002 }
- 7003
- 7004 return;
- 7005
- 7006 preempt:
- 7007 resched_curr(rq); //设置重新调度标志
正常唤醒路径：
- kernel/sched/core.c
- wake_up_process
- ->try_to_wake_up
- ->ttwu_queue
- ->ttwu_do_activate
- ->ttwu_do_wakeup
- ->check_preempt_curr(rq, p, wake_flags)
无论是创建新任务或者是唤醒任务的时候，都有可能新唤醒的任务抢占当前任务，判断条件如下：唤醒的任务的虚拟运行时间和当前任务的虚拟运行时间差值小于最小唤醒抢占粒度转换的虚拟运行时间(唤醒的任务的虚拟运行时间更小)。
4.2 抢占点
上面介绍的都是cheek点，只是设置重新调度标志，并没有让抢占的任务运行，真正的抢占点是调用主调度器的时候。
1)中断返回内核态
当开启内核抢占的时候，在中断返回内核态的前夕，会检查当前任务是否设置了重新调度标志且抢占计数器为0，如果都满足，进行抢占式调度。
- arch/arm64/kernel/entry.S
-
- el1_irq
- -> 671 #ifdef CONFIG_PREEMPTION
- 672 ldr x24, [tsk, #TSK_TI_PREEMPT] // get preempt count
- 673 alternative_if ARM64_HAS_IRQ_PRIO_MASKING
- 674
- 678 mrs x0, daif
- 679 orr x24, x24, x0
- 680 alternative_else_nop_endif
- 681 cbnz x24, 1f // preempt count != 0 || NMI return path
- 682 bl arm64_preempt_schedule_irq // irq en/disable is done inside
- 683 1:
- 684 #endif
当发生中断时，会执行el1_irq来处理中断，
672行 来读取当前任务的thread_info.preempt_count 681行 判断thread_info.preempt_count是否为0，如果为0 则调用682 行的arm64_preempt_schedule_irq 进行抢占式调度(上一节已经分析过)。
下面看下抢占式调度：
- arm64_preempt_schedule_irq
- ->preempt_schedule_irq
- ->__schedule(true) //调用主调度器进行抢占式调度
2)打开抢占的时候
开启抢占：
- preempt_enable
- ->if (unlikely(preempt_count_dec_and_test())) \ //抢占计数器减一 为0
- __preempt_schedule(); \
- ->preempt_schedule //kernel/sched/core.c
- -> __schedule(true) //调用主调度器进行抢占式调度
释放自旋锁：
- spin_unlock
- ->raw_spin_unlock
- ->__raw_spin_unlock
- ->preempt_enable //如上
3) 开启软中断
- local_bh_enable
- ->__local_bh_enable_ip
- ->preempt_check_resched
- ->if (should_resched(0)) \
- __preempt_schedule();
- ->preempt_schedule
- -> __schedule(true) //调用主调度器进行抢占式调度
其实，无论是主动进行调度还是抢占式调度都会调用__schedule，而__schedule是属于关抢占上下文，在调度期间不允许被抢占。
5.不可抢占内核的低延迟处理
下面我们来看下在没有开启内核抢占的内核中如何处理低延迟：
我们会看到在一些比较耗时的处理中如文件系统和内存回收的一些路径会调用cond_resched，它是干什么用呢：
下面是使用这个宏的例子：在内存回收路径中，会从不活跃的lru链表尾部取出一些页面回收隔离到page_list中，最终会调用到shrink_page_list：
- mm/vmscan.c
- shrink_page_list
- ->
- 1084 while (!list_empty(page_list)) {
-
- ...
-
- 1091 cond_resched();
-
- ... //回收处理
- }
可以看到对于page_list中的每一个被隔离的候选回收页，在处理之前都会调用到cond_resched来主动判断是否需要重新调度。
下面我们来看下cond_resched这个宏实现：
- include/linux/sched.h
-
- 1868
- 1874 #ifndef CONFIG_PREEMPTION
- 1875 extern int _cond_resched(void);
- 1876 #else
- 1877 static inline int _cond_resched(void) { return 0; }
- 1878 #endif
- 1879
- 1880 #define cond_resched() ({ \
- 1881 ___might_sleep(__FILE__, __LINE__, 0); \
- 1882 _cond_resched(); \
- 1883 })
我们可以很清楚的看到，抢占式内核中(CONFIG_PREEMPTION=y)cond_resched宏的_cond_resched为空，并没有主动判断重新调度的功能，只有非抢占式内核才会调用_cond_resched来执行主动检查可抢占性。
下面我们来看下_cond_resched：
- 6671 #ifndef CONFIG_PREEMPTION
- 6672 int __sched _cond_resched(void)
- 6673 {
- 6674 if (should_resched(0)) { //判断抢占计数器是否为0
- 6675 preempt_schedule_common(); //进行抢占式调度
- 6676 return 1;
- 6677 }
- 6678 rcu_all_qs();
- 6679 return 0;
- 6680 }
- 6681 EXPORT_SYMBOL(_cond_resched);
- 6682 #endif
会主动检查抢占计数器是否为0(实际上抢占计数器是否为0且当前任务被设置了重新调度标志)，则进行抢占式调度。
实际上，对于非抢占式内核来说，在内核的很多地方，特别是文件系统操作和内存管理相关的一些耗时路径中，都已经被内核开发者识别出来，并使用cond_resched来减小延迟(感兴趣的小伙伴可以通过grep和wc -l命令来查看一下)。
6.自愿内核抢占
内核抢占模型有一种叫做自愿内核抢占模型(CONFIG_PREEMPT_VOLUNTARY=y)，可以使得内核开发者在进行耗时操作的时候，主动检查是否需要发生抢占式调度，这个和上一节差不多。
- config PREEMPT_VOLUNTARY
- bool "Voluntary Kernel Preemption (Desktop)"
- depends on !ARCH_NO_PREEMPT
- help
- ¦ This option reduces the latency of the kernel by adding more
- ¦ "explicit preemption points" to the kernel code. These new
- ¦ preemption points have been selected to reduce the maximum
- ¦ latency of rescheduling, providing faster application reactions,
- ¦ at the cost of slightly lower throughput.
-
- ¦ This allows reaction to interactive events by allowing a
- ¦ low priority process to voluntarily preempt itself even if it
- ¦ is in kernel mode executing a system call. This allows
- ¦ applications to run more 'smoothly' even when the system is
- ¦ under load.
-
- ¦ Select this if you are building a kernel for a desktop system.
使用might_resched：
- 83 #ifdef CONFIG_PREEMPT_VOLUNTARY
- 84 extern int _cond_resched(void);
- 85 # define might_resched() _cond_resched()
- 86 #else
- 87 # define might_resched() do { } while (0)
- 88 #endif
发现只有CONFIG_PREEMPT_VOLUNTARY=y时，might_resched才有效，否则为空。
可以惊奇的发现，当搜索might_resched在内核中使用的使用的时候，并没有看见有任何地方在使用，猜想是因为大多数耗时的内核路径，都已经使用cond_resched来进行检查是否具备调度时机。
7.总结
本文讲解了内核抢占的方方面面，非抢占式内核主要用于服务器等对吞吐量要求较高的场景，而抢占式内核主要用于嵌入式设备和桌面等对响应要求较高的场景。内核抢占的调度时机主要从check点和抢占点两个角度去分析：check点是在合适的时机(如时钟中断tick时或者任务唤醒的时候)判断是否需要重新调度任务，如果需要设置重新调度标志(need_resched)，并没有马上进行调度，然后在最近的抢占点发生调度;而抢占点是真正调用主调度器发生调度的时机，一般会在中断返回内核态或者重新开启内核抢占等情况下发生。最后，我们又分析了非抢占式内核如何进行低延迟处理已经自愿抢占式内核如何实现自愿式抢占。
