前言

本文梳理了Linux进程调度器的框架结构，旨在通过本文阐述Linux进程调度器的基本工作原理。用一句话概括调度：cpu按照特定的规则（调度器：CFS / RT / DL）在特定的时机（主调度+周期调度）通过特定的数据结构（priority queue / RB-tree）对数据对象（进程描述符task_struct->sched_*_entity）的增删改查，以实现对系统任务（task）的调度管理

内核版本：linux-4.9.140

什么是调度器

The scheduling activity is carried out by a process called scheduler. Schedulers are often designed so as to keep all computer resources busy (as in load balancing), allow multiple users to share system resources effectively, or to achieve a target quality-of-service.

如图1，调度器是按照特定的策略高效的利用有限的计算资源

图1 调度器

调度对象

从内核的角度，调度器管理的是使用task struct数据结构描述的调度对象调度对象均使用_do_fork()接口创建，代入不同flag的创建不同属性的调度对象，从应用层的角度表现出的就是线程和进程的区别

进程创建流程

fork creates a duplicate copy of the calling process as its child. The exec() family of functions replaces the current process image with a new process image wait and exit

图2 进程创建流程

线程创建流程
图3 线程创建流程
线程进程创建原理
图4 进程线程创建接口
User Space
- 创建进程（fork）
- 创建应用层线程（pthread_create）
Kernel Space
- 创建内核层线程（kernel_thread）
- 均调用_do_fork，只是flag不一样
进程是资源分配的最小单元
线程是CPU调度的最小单元（从内核角度，线程可以看作一种特殊的进程）
调度对象的本质：进程描述符struct task_struct数据结构中的struct sched_entity se
一共包括三类调度实体
- struct sched_entity se;
- struct sched_rt_entity rt;
- struct sched_dl_entity dl;

图5 进程线程创建原理

如何选择调度器

调度器框架

为了使代码可维护性高、解耦，内核代码中大量使用了面向对象的设计思想，在调度器的设计中也不例外。尽管C没有像C++拥有专有的面向对象的语言特性，但并不妨碍C使用面向对象的思想设计框架结构。

在调度器的框架结构设计中，使用struct中的函数指针（相当于C++中的虚函数表）实现"多态"概念，搭好框架后，只需要按照各自的调度功能需求实现函数指针的接口即可实现不同功能特性的调度器，这样的设计思想和技巧在内核中随处可见。

图6 调度器框架

内核中一共实现了五种调度器，按照调度器优先级依次是：stop_sched_class, dl_sched_class, rt_sched_class, fair_sched_class, idle_sched_class

stop_sched_class和idle_sched_class由内核使用，没有应用层vfs交互调整接口
stop_sched_class：在cpu hotplug时使用，用于停止当前cpu的处理任务
idle_sched_class：cpu空闲运行idle进程，arm64执汇编指令// WFI may enter a low-power mode

其中暴露给应用层的调度器分别是：DL, RT, CFS

	DL	RT	CFS
调度策略	SCHED_DEADLINE	SCHED_FIFO，SCHED_RR	SCHED_NORMAL，SCHED_BATCH，SCHED_IDLE
内核态优先级	-1（无优先级）	0 - 99	100 - 139 （120 + nice值(-20 ~ 19)）

SCHED_BATCH策略，用于非交互式任务的批处理，这些任务会在一段时间内不间断地运行
SCHED_NORMAL策略（在用户空间中称为SCHED_OTHER），适用于用于Linux环境中运行的大多数任务
SCHED_IDLE策略是为系统中优先级最低的任务设计的，只有在没有其他任务可运行时，这些任务才有机会运行。

核心数据结构

为了实现不同调度器的特点，内核采用了红黑树和优先级队列数据结构进行管理，如图7所示：

图7 核心数据结构

CFS调度器

CFS：Completely Fair Scheduler调度器有三要素：priority(nice) → weight → vruntime nice值（-20 ~ 19）为应用层进程属性，进程nice值越高，表示该进程越“友好”，进程优先级越低，反之则进程优先级越高

nice值到内核层进程权重的关系为： \[ weight = \frac{1024}{1.25^{nice}} \] 一般默认属性创建的进程nice = 0，对应的weight = NICE_0_LOAD(1024)

通过计算可以知道，这么设计的初衷，是为了保证每降低进程一个单位nice值，将使其多获得10% 的cpu占用时间

通过权重值就可以计算调度周期内需要分配给进程的运行时间片 \[ 分配给进程的时间 = \frac{进程的权重}{就绪队列（runqueue）所有进程权重之和} * 调度周期 \] 注意，CFS调度器下的调度周期并不是固定值，伪代码逻辑如下：

sched_nr_latency = (sysctl_sched_latency + sysctl_sched_min_granularity – 1) / sysctl_sched_min_granularity
if (nr_running > sched_nr_latency) {
    sched_period = nr_running  * sched_min_granularity_ns;
} else {
    sched_period = sysctl_sched_latency;
}

当进程数量nr_running超过sched_nr_latency时，为了保证进程的最小执行时间sysctl_sched_min_granularity（避免因为分配的时间片过小造成频繁的调度开销），会动态调整当前的调度周期sched_period = nr_running * sched_min_granularity_ns；否则，调度周期sched_period = sysctl_sched_latency

进程最小执行时间：/proc/sys/kernel/sched_min_granularity_ns
CFS调度延迟：/proc/sys/kernel/sched_latency_ns

在调度算法上，CFS调度器引入了虚拟运行时间vruntime的概念，将优先级nice和实时运行时间两个维度通过公式转换到了一个维度 \[ vruntime(虚拟运行时间) = wall\_time (实际运行时间) * \frac{NICE\_0\_LOAD}{weight} \] \[ vruntime(虚拟运行时间) = wall\_time (实际运行时间) * \frac{1024}{\frac{1024}{1.25^{nice}}} \] \[ vruntime(虚拟运行时间) = wall\_time (实际运行时间) * 1.25^{nice} \]

推出: 进程nice越大 → 优先级越低 → vruntime增长越快 → 在相同vruntime下实际占用cpu时间越短

nice = 0时， vruntime(虚拟运行时间) = wall_time (实际运行时间)

同时，根据上述转换公式，可以得到分配给进程的虚拟时间片计算公式 \[ 分配给进程的时间(virtual) = \frac{进程的权重 * 调度周期}{就绪队列（runqueue）所有进程权重之和} * \frac{NICE\_0\_LOAD}{weight} \] \[ 分配给进程的时间(virtual) = \frac{调度周期 * NICE\_0\_LOAD}{就绪队列（runqueue）所有进程权重之和} \] 通过上述公式，可以得到分配给进程的虚拟时间片是个与调度周期相关的固定值，即在一个调度周期内，该cpu调度队列中的进程任务分配到的虚拟时间片相同 结合上述理论，以单核CPU为例

	nice	权重weight	调度周期period	真实时间片ideal_runtime	虚拟时间片	进程执行1ms后vruntime值
进程A	0	1024	6ms	3.3ms	3.3ms	1ms
进程B	1	820	6ms	2.7ms	3.3ms	1.25ms

进程A：
- 权重weight = 1024 / 1.250 = 1024
- 调度周期period = sysctl_sched_latency * （1 + log1）= sysctl_sched_latency = 6ms
- 真实时间片ideal_runtime = 6ms * 1024 / (1024 + 820) = 3.3ms
- 虚拟时间片 = 3.3ms * 1.250 = 3.3ms
- 真实步进1ms = 虚拟步进1ms * 1.250 = 虚拟步进1ms
进程B：
- 权重weight = 1024 / 1.251 = 820
- 调度周期period = sysctl_sched_latency * （1 + log1）= sysctl_sched_latency = 6ms
- 真实时间片ideal_runtime = 6ms * 820 / (1024 + 820) = 2.7ms
- 虚拟时间片 = 2.7ms * 1.251 = 3.3ms
- 真实步进1ms = 虚拟步进1ms * 1.251 = 虚拟步进1.25ms

如上计算，进程A和B的真实时间片根据nice值（权重weight）分配调度周期，二者分配的虚拟时间片相同；

在1ms真实步进下，进程B的虚拟步进（1.25ms）大于进程A（1ms），更快的用完分配的虚拟时间片，执行时间更短、更快被换出，也即：nice值越高，占用CPU更短

RT调度器

RT：Real Time调度器要素：priority | timeslice（/proc/sys/kernel/sched_rr_timeslice_ms）

不相同优先级的实时调度线程
- 不论是SCHED_RR还是SCHED_FIFO，高优先级线程均能对低优先级线程实施抢占，且在主动放弃CPU之前不会释放占用
相同优先级的实时调度线程
- 如果同为SCHED_RR线程，线程之间分享时间片，轮转运行。
- 如果同为SCHED_FIFO线程，其中之一（谁先运行）会一直运行直到到其主动释放占用CPU，另一个才会执行。即同优先级不会分享时间片
两个分别为SCHED_RR，SCHED_FIFO线程
- SCHED_RR线程会分享时间片，即时间片用完后会放弃占用CPU，被SCHED_FIFO线程占用，SCHED_FIFO线程占用后不会和SCHED_RR线程分享时间片，会一直运行到其主动释放占用后，SCHED_RR线程才会再次执行
两个线程一个为实时调用线程，一个为非实时调用线程、
- 实时线程不论是何优先级（>0），何种调度方式，都能对非实时线程实施抢占，且不会对非实时线程共享时间片

另：

Round-Robin调度策略的时间片由/proc/sys/kernel/sched_rr_timeslice_ms决定（timeslice必须是tick倍数(1 / CONFIG_HZ_250 = 4ms)）
- 输入为ms，输出为滴答数，即写入的参数单位是ms，读出时的单位是当前系统的jiffies
RT进程和普通进程之间存在分配带宽的比例，默认情况是RT:CFS=95:5。
- 可通过/proc/sys/kernel/sched_rt_period_us和/proc/sys/kernel/sched_rt_runtime_us来设置
- 如果设置sched_rt_runtime_us为-1（慎用），则禁止对RT进程的带宽限制，即如果存在RT进程会占满整个CPU且该CPU不在会有调度CFS进程的机会

DL调度器

DL：Deadline调度器要素：runtime | deadline | period

在period周期内，抵达deadline前，执行runtime时间

带宽bw = runtime / period

要求1us < runtime <= deadline <= period (if period != 0)

图8 DL调度器要素

对比在CFS调度器，当任务总数增加时，单个任务其在一个调度周期内所能获得的时间片会相应减少直到最小执行时间sched_min_granularity_ns DL调度中的任务的需求就不会受到系统中其他任务的影响，这个特性是Deadline调度器策略最大的优势

测试：3个线程绑定到core 6，7，三要素属性分别为：[50, 100, 100]; [50, 100, 100]; [20, 100, 100]，cpu占用情况如图9所示：core6 50%；core7 50%；core6 20%

图9 DL调度器测试

什么时候发起调度

调度器并不是管家式的管理方式（由专门进程任务进行管理），而是将调度的判断、换出等操作嵌进了整个内核的运转中

这里以arm体系结构为例，介绍Arm体系结构相关，并引入介绍“主调度器”和“周期调度器”

Arm体系结构相关

图10 ARMv8异常级别

EL0：应用程序运行（用户空间）
EL1：操作系统内核和相关功能
EL2：Hypervisor（虚拟化相关）
EL3：Noraml world和Secure world的切换 (ARM Trusted Firmware)

图11 ARMv8异常处理流程

“主调度器”

系统调用返回到用户空间
中断返回到用户空间
中断返回到内核空间，需要内核支持内核抢占
重新使能内核抢占时

这些调度点都会检查调度标志位，根据标志位是否置位再决定是否执行调度

图12 主调度器流程

“周期调度器”

周期调度器在每一个系统tick中断，对当前CPU的执行任务进行检查是否需要调度，满足条件则将调度标志置位，在下个主动调度的时机触发调度换出

图13 周期度器流程

调度器如何调度

上下文切换

图14 上下文切换流程

Q & A

主调度器和周期调度器是否冲突？不冲突，只是调度时机不同，相辅相成，互为补充
内核任务（内核线程，内核系统调用）是否可以被抢占？在使能内核抢占开关CONFIG_PREEMPTION=y后，且满足抢占计数preempt_count == 0（防止抢占嵌套）时，可以被抢占
TIF_NEED_RESCHED的内涵？在调度器决策出当前进程需要被换出时设置进程描述符的对应flag，在下个调度时机到来时藉由该flag决定是否启动schedule流程，启动schedule后再由class->pick_next_task接口返回值决定该进程是否换出
何时会设置TIF_NEED_RESCHED标志？通用场景：有进程待唤醒时，当前进程满足被抢占条件；修改正在运行的进程优先级；进程主动放弃cpu（yield）；特殊情况下的强制cpu reschedule 针对不同调度器的具体场景： CFS：当前进程时间片耗尽；当前运行进程的调度策略转换成CFS时； DL：下个被pick的进程deadline更小且当前进程可以被迁移时；当前运行进程的调度策略转换成DL时；当前进程runtime耗尽等
当一个进程从休眠状态唤醒时，是否会立即被CPU执行？不会。新唤醒的进程会被入列到对应cpu runqueue，同时设置当前进程TIF_NEED_RESCHED，在下个调度时机到来时，启动schedule流程
调度器框架的函数指针，分别实现功能是？ *next：指向下一个调度器，用于遍历调度器接口时使用，应用场景举例：调度pick下一个任务时 *enqueue_task：将task加入对应的调度器数据结构，应用场景举例：创建进程、调整优先级等 *dequeue_task：将task从对应的调度器数据结构移除，应用场景举例：进程结束等 *pick_next_task：挑选下一个需要换入的task（具体换入策略由各自调度器实现），在触发schedule时执行 *put_prev_task：不同调度器有不同实现：cfs：将换出的task，归置到runqueue队尾；dl：则是将当前执行任务归置到可供迁移到其他cpu的红黑树节点上。应用场景举例：调整当前运行进程的优先级时 *task_tick：周期调度器中断handler的实现，更新当前进程的时间相关参数（cfs时间片，dl调度器runtime & deadline）并决定是否resched_curr …

工具介绍

trace-cmd & kernelshark

参考文献

Linux进程管理 (9)实时调度类分析，以及FIFO和RR对比实验

https://www.cnblogs.com/arnoldlu/p/9025981.html

Linux进程调度策略

https://www.cnblogs.com/jacklikedogs/p/4029825.html

试谈Linux下的线程调度-『Linux 源码解析（一）』

https://zhuanlan.zhihu.com/p/58868634

Using KernelShark to analyze the real-time scheduler

https://lwn.net/Articles/425583/

ftrace利器之trace-cmd和kernelshark

https://www.cnblogs.com/arnoldlu/p/9014365.html

kernelshark使用说明

https://kernelshark.org/Documentation.html

进程的创建

https://zhuanlan.zhihu.com/p/185751680

AArch64 Exception and Interrupt Handling

https://developer.arm.com/documentation/100933/0100/

linux内核同步机制-RCU（1）系列

https://zhuanlan.zhihu.com/p/347279156

linux程序是如何开始运行的

https://zhuanlan.zhihu.com/p/337477747

内存屏障（Memory Barrier）究竟是个什么鬼

https://zhuanlan.zhihu.com/p/125737864

linux调度子系统6 - 周期调度 timer setup

https://zhuanlan.zhihu.com/p/363787529

CFS调度器（1）-基本原理

http://www.wowotech.net/process_management/447.html