CFS线程调度机制分析
一、前言
操作系统上运作着各种应用、服务来满足用户需求，这些应用、服务实现的功能，通常都会依托一个个具体的线程来完成。在2022年的今天，无论是手机用户还是平台厂商，都不会容忍一台手机的功能仅限于单一的通信功能。手机设备不比服务器，其多核架构体系上只存在8个cpu core，而执行线程的数量却轻而易举超过8个。
每个cpu上该执行什么线程，是由linux线程调度器来进行决策的，关于这一部分，网上已经有相当多的文章进行描述，因此本文在讲解一些概念的基础上，会分析为何当前的调度器仍满足不了android系统的业务需求，我们为何还需要做调度优化。先抛出一张图（图1），大家感受下高负载下的cpu，是不是像极了正在工作的你，忙的不可开交！
拥有android开发经验的伙伴，都清楚上面是通过google perfetto工具抓取的系统运行状态图示，8个核心全部跑满，要达到这样的现象并不困难，多启动几个应用，抓取下启动时的状态即可。那么问题来了，高负载的系统中，每个核心都不止运行一个线程，这必然导致线程执行存在先后顺序，每次执行的时间也存在差异，那么，影响用户体验的线程能否及时执行起来，能否得到足够长的执行时间，就显得尤为重要，这也是调度团队需要解决的问题。
二、线程调度器如何运作
实际的开发过程中，我们发现CFS调度类线程更容易出现调度问题，因此目前调度的优化围绕该调度类展开。下文的主要分析对象为CFS调度类，我们先从几个基础概念入手。
2.1 基础调度概念
- 调度类（sched class）：linux内核支持的调度类如图2所示，每个线程归属于其中一种调度类，并遵循一种调度策略。android系统中，覆盖面最广的是CFS调度类fair_sched_class，其次是实时调度类中的rt_sched_class，我们喜欢将它们的线程分别成为cfs线程和rt线程。调度类存在优先级，图2从上到下罗列的调度类，优先级从高至底。调度器总是从最高优先级的调度类中开始检索需要执行的线程，同个调度类存在多个线程，则按具体的调度策略进行检索。
调度类提供的实现接口用于定制具体的调度策略，开发人员也可按照相应的规则实现自己的调度类和调度策略。
- 运行队列（runqueue）：线程需要执行时，会选取某个核，并放置到该核对应的运行队列上，这个过程我们称为入队；当线程由于某种原因不再需要执行时，将从运行队列上摘除，对应的过程即出队。不同调度策略，运行队列的维护方式不同，如cfs线程的队列维护是通过红黑树完成，而rt线程的队列维护则是通过优先级链表完成。
注：图3为CFS调度类的实现，对应的接口作用如表1所示。
- 调度延迟（sched latency）：线程在运行队列中的等待时间，这主要来自三个方面：从idle cpu唤醒需要等待器件做好准备；等待更高优先级调度类线程执行完成；等待同调度类的线程时间片耗尽。
- 时间片（sched slice）：线程单次执行的时长。CFS调度策略存在调度周期，理想情况下，调度周期内运行队列的每个线程都将执行一次，当运行队列中只有一个线程时，将总是由该线程分得全部时间片。
2.2 权重的作用
CFS调度策略就是青天大老爷，它来到linux内核，只做三件事：公平！公平！还是公平！其公平规则紧紧围绕权重展开，理解了权重的作用，也就掌握了该调度策略的核心。
我们知道，每个线程都存在优先级priority，记录在其抽象结构体struct task_struct中，并提供相应的系统调用供用户修改。实际上，android通过这些系统调用指定的是nice值，如表2所示。
文件路径：system/core/libsystem/include/system/thread_defs.h
nice值与priority之间存在一个转换关系，如下：
（1）低优先级的调度延迟无法得到有效控制。由于总是让高优先级先执行，那么调度延迟很大程度上取决于高优先级线程的数量。
（2）固定时间片会导致低优先级线程的执行变得异常艰难。低优先级线程本身时间片是非常小的，如果长时间的等待换来的是几个ms的执行，那它的任务将很难执行完。
因此，内核引入CFS调度策略，保证公平调度。为此，调度器特地给nice值建立一一对应的权重值，如图5所示，注意到，一共有40个权重等级，代表CFS调度类线程的nice范围[-20, 19]：
权重与nice值的计算关系如下：
weight = 1024 / (1.25 ^ nice)
权重的作用主要体现在两个方面：
（1）时间片分配大小
时间片是按线程权重占比进行分配。如果两个权重为1024（nice值为0）的线程放在同个核上，在没有其它线程干扰的情况下，这两个线程将平分整个调度周期。我们将挂在运行队列的线程看做一个调度实体se（sched entity），则该se的时间片为：
slice = se->load.weight / cfs_rq->load
其中，se->load.weight代表该se的权重值，即图5中nice值对应的数值（如果该se代表一个具体线程）。cfs_rq->load则代表当前运行队列上所有调度实体的权重总和。注意，以上描述仅适用于未开启组调度的情况，当开启组调度后，情况会有些微不同，另有章节涉及。
（2）虚拟时间增长
调度实体的执行时间，将按照权重反馈到虚拟时间的增长上。我们之前说过，CFS调度策略是通过一棵红黑树来进行维护的，虚拟时间越小的线程，将挂在红黑树的越左端，而最左端是普遍情况下调度器选取的下一个执行对象。
对于一个权重为1024的线程，执行2ms时，会原封不动地将这2个ms累加到虚拟时间上，但是，当它的权重增加到9548时（对应nice值为-10），虚拟时间只增加0.2ms。它们之间存在以下关系：
vruntime = exectime * (1024 / se->load.weight)
虚拟时间除了会影响调度实体在红黑树中的位置外，还影响唤醒抢占能否成功。如下：
调度周期是10ms，任务A和B由于权重相同各分5ms，图中第二个tick到来后， A时间片耗尽切换到B。1ms后，任务C唤醒。如果发生抢占，那么在唤醒之前的调度周期中，任务B就太可怜了，没有跟A一样耗尽时间片。如果不发生抢占，那么唤醒的C需要等待下一次tick到来，基于新的系统状况来核算任务B的时间片（由于新增高优先级任务，大概率会耗尽其时间片），对于C这个高优先级任务而言，调度延迟又长了点。
总之，交给虚拟时间吧！值得注意的是，gran值依然是受权重值影响，*se的权重越大，gran值越小，其潜在含义是，如果唤醒线程优先级高，那么gran值就小，从而更容易发生唤醒抢占）。如下：
gran = sysctl_sched_wakeup_granularity * (1024 / se->load.weight)
其中，sysctl_sched_wakeup_granularity是内核提供给用户空间的一个可设置的数值。
三、如何进行优化
3.1 存在的问题
在了解调度的基础概念以及权重的作用后，我们应该明白调度器是如何运作的。CFS调度策略最让人惊叹的就是其基于虚拟时间的公平调度。假定调度周期为10ms，并且只有两个线程位于同个运行队列上，则：
这样的“公平”设计很巧妙，但是依然不满足手机这种强交互设备对及时性的需求。首先，执行时间会不断累积到虚拟时间上，这意味着，一个长时间执行的线程，即便权重很高，它依然逃脱不了虚拟时间的不停增加，也就存在被其它长时间睡眠的唤醒线程抢占的可能性。其次，实际运行情况下，即便一个线程的权重很高，它始终不能分到一个周期内全部的时间片，并且分到的时间片也是有限的，当时钟周期tick命中后，cpu使用权交给另一个线程，往往需要到下一个周期tick的调度点才能交换回来。
3.2 调度优化点
从2.2节表2可以发现，原生android对系统中一些关键线程会进行优化，比如将负责图形显示合成的surfaceflinger线程、hw-composer线程更改为实时调度类，能有效降低调度延迟，确保任务执行完再调度出去。但系统中如果存在较多的实时线程是不合适的，实时线程并不讲究“公平”，很可能会导致关键线程执行互相受到影响，或者影响其它普通线程。因此，android主要还是通过提高CFS调度类线程的优先级来进行改善，如音频普通线程使用的nice值为-16，前台交互应用的UI、Render线程使用的nice值为-10，system_server下一些关键持锁线程nice值为-2或者-4。
从3.1节我们也可以知道，这样的优化在高负载下仍然会存在问题，现在系统中CFS调度类的线程对时延要求越来越高，比如120刷新率的界面，一帧合成时间就要求在8ms以内，也就两个周期tick的时间长度（250HZ）。因此，我们可以从更底层的角度去对这些关键的CFS调度类线程做改善，比如做以下尝试：
（1）唤醒抢占维度：关键线程唤醒时，我们是不是可以不考虑虚拟时间的评估，直接对当前非关键线程发起抢占呢；反之，非关键线程在唤醒时，则不允许对关键线程进行抢占。
（2）避开高优先级调度类：关键线程在选核时，如果能避开更高优先级调度类所在的核心，那么这一部分的调度延迟就可以避免。
（3）虚拟时间补偿：原生内核其实已经存在此类做法，当线程长时间休眠时，并不会累加运行时间到其虚拟时间，线程唤醒后，将远小于当前运行队列的虚拟时间最小值。试想一下，如果我们不做任何改动，那该线程将长期霸占红黑树最左端的位置，这显然是不合理的。因此在唤醒时，内核对其进行修正，使虚拟时间对齐到最小虚拟时间的基础上，仅减少半个或1个调度周期时长作为补偿。对于短时间休眠呢？短休眠的线程有可能其虚拟时间大于补偿后的时间，那就仍维持现状挂入。
对于关键线程，我们依然可以采用这个思路，唤醒时削减一定的虚拟时间作为补偿，使其在接下来的几次调度中占据优势。
四、组调度的引入
4.1 认识调度组
谷歌这两年在推行通用内核镜像（GKI），使用android系统的手机厂商，都必须确保设备能直接使用GKI镜像，因此，厂商在内核修改这一块存在许多限制。在kernel-5.4内核引入GKI1.0之后，我们发现谷歌使能组调度功能， CONFIG_FAIR_GROUP_SCHED配置为true，分组的情况如图8所示，关键组别如下：
dev/cpuctl/tasks ---- root组
dev/cpuctl/top-app/tasks ---- top-app组（用户交互组）
dev/cpuctl/foreground/tasks ---- 前台组
dev/cpuctl/background/tasks ---- 后台组
...
组调度对CFS调度策略的影响是显著的，原生内核提供这套机制，是为了将各类线程按group的形式进行资源分配，也就是将同一属性的线程归纳到同一个group下，而android系统也顺势将各类应用进程、服务进程放入相应的组中，内核线程则默认放在root组（这一点很重要）。
4.2 公平分配规则的变动
我们在2.2节提到过调度实体的概念，当时是将每个线程看做一个调度实体，而调度实体是挂在运行队列上的，引入调度组之后，调度实体就不一定是代表一个待执行线程了，组调度为其建立起层级结构，如图9所示。
在顶层的cfs_rq上，挂载两个调度实体，其中一个为task级别的se，属于root group，你可以把它当成某个内核线程，它的pid号记录在“dev/cpuctl/tasks”中，另一个为group级别的se，代表某个调度组在当前cpu上的调度实体，比如前台组“foreground”。聪明的你已经发现，group的se拥有自己的运行队列，属于第二层的cfs_rq，其上挂载该组在当前cpu上的线程，记录在“dev/cpuctl/foreground/tasks”中。
层级结构引入后，时间片的分配规则也随之产生变化。我们之前提到，一个调度周期会按当前运行队列各个调度实体的权重占比进行分配，但层级结构需要注意的分配规则变动有两个：
（1）调度周期的分配自上而下。假如我们给定调度周期为10ms，那么，这10个ms将从顶层的cfs_rq开始分配，分配依然是按se的权重占比划分。我们假定顶层cfs_rq底下的两个se（task级别和group级别）各自分得5ms，那么group se的5个ms，将继续往下一层分配给其维护的第二层cfs_rq的task se们。
（2）group级别se的权重不再与nice值挂钩。我们之前提到，task级别的se，即具体某一个线程，可以通过调节nice值更改其权重，进而影响时间片的分配、虚拟时间的累加。然而，group se下面维护的cfs_rq，可能存在多个task se，难道是将这些task se的权重累加吗？显然不是这样的，linux的设计总是统一而优雅，对于一个group se，也有其与权重挂钩的“nice”值。
我们注意到，图8中存在一个参数“cpu.shares”。share值即代表当前group级别se的权重，它并不受其子task se的影响，这个值在android平台默认是1024。你也可以在其他group目录如“dev/cpuctl/foreground/”中发现它的存在。
4.3 带来的问题
受到4.2节（1）的影响，我们对某个task se进行虚拟时间上的补偿优化，意义已经不大，因为如果你的task se是挂在某个group的cfs_rq下，那么这个做法只会让task在group所属的cfs_rq中存在优势，而要让它优先得到执行，调度器必须得先在顶层的cfs_rq中选中这个group se才行。那对group se做虚拟时间补偿如何？这样也不行，相当于group底下的所有子task se都会受益，并且你还不能确保目标task能优先得到执行。
受4.2节（2）的影响，nice值的作用在不同层级的cfs_rq中表现就不一样了。我们之前说到group se的权重即share值，这样的说法也不太准确，实际上，同个组的线程们极有可能运行在不同的cpu，所以内核同样采取占比的方式来计算对应cpu上的group se的权重，公式如下：
ge->load.weight = tg->weight * grq->load.weight / SUM(grq->load.weight)
其中，ge->load.weight是当前cpu挂载的group se的权重；tg->weight就是我们提到的share值；grq->load.weight就是当前cpu挂载的group se，其维护的cfs_rq的权重，这个值是其上挂载的所有task se的权重总和；SUM(grq->load.weight)自然是group se在所有cpu的cfs_rq的权重总和。
感兴趣的伙伴可以看下内核函数calc_group_shares(struct cfs_rq *cfs_rq)，上面拥有非常详细的注释，这个函数用来更新group se的权重，它在线程入队、出队、周期tick命中以及用户修改share值时，都会调用更新。
下面通过2个实验来看下组调度带来的影响。我们首先创建4个循环执行的线程，命名为“root_0”、“root_1”、“top_0”、“top_1”。其中，“root_0”、“root_1”维持默认分组，也就是在root group中，它们入队时，会直接挂在顶层的cfs_rq。“top_0”、“top_1”则放入新创建的tmp group中，避免收到其它线程的干扰，它们位于所在cpu的group se维护的cfs_rq。之后，我们将“root_0”、“top_0”绑定在cpu4，“root_1”、“top_1”绑定在cpu5。则调度实体的分布如图10所示。
实验一：4个线程nice值均为默认值0（对应权重为1024），root group和tmp group的share值均为默认值1024，调度周期target latency为10ms。“top_0”和“top_1”虽然处于不同的cpu，但它们都属于tmp group。cpu4上“top_0”的时间片分配规则为：
（1）计算其所在group即tmp_grp_se的权重
tmp_grp_se.weight = tmp_grp.share * top_0_se.weight / (top_0_se.weight + top_1_se.weight) = 512
（2）顶层cfs_rq目前挂载两个se，它们的时间片分别为：
root_0_se_slice = target_latency * root_0_se.weight / (root_0_se.weight + tmp_grp_se.weight) = 6.7 ms
tmp_grp_se_slice = target_latency * tmp_grp_se.weight / (root_0_se.weight + tmp_grp_se.weight) = 3.3 ms
（3）tmp_grp再将其配额分给其拥有的task se。由于其所属的cfs_rq上只挂着“top_0”，因此top_0_se_slice为3.3 ms。
可以看到，虽然所有线程的nice值都是0，但是处于root group下的“root_0”却拿到多出一倍的时间配额。
实验二：在实验一的基础上，我们将“top_0”的nice值调整为-10，让它成为高优先级线程，其余条件不变。按照之前的处理步骤，在cpu4上，“root_0”拿到的时间片为5.3 ms，“top_0”拿到的时间片为4.7 ms，一个高优先级的线程居然跟低优先级的线程旗鼓相当！
我们也可以通过调整share值来影响结果，在此不再演示。现在我们再回过来看下，CFS调度策略还公平吗？其实从调度组的维度来看，还是公平的。这里我们难受的一点在于，root group的线程各自独立，在计算权重时拥有很大优势，但实际上这些线程很少直接参与用户图形绘制、音频输入等业务。具体的业务线程又被android推入诸如top-app、foreground组，组内还包含其它不影响用户体验的线程，同个组的线程分散在不同的核上，引起组权重的重新分配，也就是说，一些关键业务线程的时间片分配会受到同组内其他不相关线程的影响；另一个点，android的业务设计上，不同组之间的线程可能会建立联系，如app层对框架层的依赖，内核层的公共资源争夺等，也就是说，一些关键业务线程也会在某些特定场景下依赖其他组的线程，这些线程理论上在这个时刻更应该看做是同个组。总之，目前调度组这样的使用方式会带来问题，仅从share值和nice值去调整，是很难达到目的。
五、结语
我们今天了解到权重在CFS调度策略中的重要地位，也了解到CFS调度策略存在的一些问题，包括引入组调度后产生的弊端。基于权重的“公平”，看起来并不能满足手机场景对于关键线程的调度需求。如何保证关键线程的及时调度，同时又不饿死其它线程，或许还需要一种新的机制引入，至少目前来看，权重对这一块的调节很有限。
参考文献：
1、https://github.com/oppo-source/android_kernel_5.10_oppo_mt6983/
2、http://www.wowotech.net/sort/process_management