Linux任务调度(5)

分享:  

演进过程

首先，再次回顾下下Linux进程调度器的一个发展历史：

  • v0.01~v2.4.x: the very first scheduler，复杂度O(n)
  • v2.6.0~v2.6.22: O(1) scheduler，复杂度O(1)
  • v2.6.23~: Completely Fair Scheduler (CFS)，复杂度O(log(n))

前一篇文章中我们介绍了v0.01版本中的调度器实现，复杂度为O(n)，在v0.01内核实现中写死了最多可调度的任务数量，只能算作是一个toy！随着从v0.01~v2.4.x版本中的优化，能调度的任务数量也上来了，但是复杂度还是O(n)。O(1)调度器对其进行了优化，但是其启发式算法来识别、奖惩交互性的逻辑难以建模、理解、维护、优化。RSDL调度器相比O(1)调度器有了很大的改进，但是Con Kolivas和Torvalds、Ingo等人有不同看法，最终迟迟未能合入内核主线。

问题背景

对Linux调度器做过点了解的话，应该都听说过“完全公平调度器”这个术语吧。完全公平调度器(Complete Fair Scheduler, 简称CFS)。CFS从v2.6.23到现在v6.0.0+久经沙场考验，它一定是有些过人之处，才能在多用户多任务、服务器、桌面、虚拟机、容器化乃至云原生领域都表现还不错。

业务在项目部署上的实践，让我产生了对Linux scheduler设计实现的一些思考。事情是这样的，项目虽然也是微服务架构但是在部署上，目前测试期为了节约成本是采用的混部的方式，每个微服务都是通过统一的框架进行开发的，有完善的日志、监控、告警支持。但是有这么例外服务，是采用标准库http实现的工具服务，没有上述可观测性相关的支持，如果这个服务实现不健壮，很可能会影响到混部的其他服务。

服务混部

一点挑战

对于采用了k8s容器化部署的项目而言，一般就不会遇到这样的困扰，因为容器运行时已经做了比较好的资源隔离，包括CPU、内存等等，混部的话就有一定的挑战，尤其是像go这种支持协程、本身也是多线程而且支持GC的程序。

  • go本身就是多线程程序，用来支持多处理器多核上的goroutine调度执行，支持GC，轮询网络IO事件、轮询定时器事件等；
  • go本身支持协程，协程的调度、最终执行依赖于多线程，尽管可以限制GOMAXPROCS，但本质上还是多线程程序；
  • go支持GC，但是对于程序上限没有硬限制（有别于Java等），只有软限制；
  • 其他；

内存分配

对于go程序混部，有一定的挑战，综合投入产出比，可以考虑根据服务的重要程度、吞吐量、响应时间等要求给与不同的设置。以内存为例，混部服务GOMEMLIMIT上限尽量不要高于总可用内存的70%，留一点buffer给系统服务、超额分配的情况（实际上go1.19之后内存占用逼近软限制后会导致申请内存的goroutine做一定量的标记清理动作延迟内存分配），这是对内存，那么对CPU呢？

cpu分配

对于计算密集型任务，如果涉及到混部，为了分配CPU资源可能回考虑通过taskset进行绑核，实际上对于IO密集型任务也未尝不可，但是收益有多少呢？作者此前曾经在压测中做过这方面的一点尝试，将不同服务绑定在不同核上，这是我的一个单机用于压测的探索，实际真正线上服务，这种方案不一定真的可取。资源分配要取决于真实的负载情况才合理，不能简单的cpu 1,2,3,4给服务1，cpu 5,6给服务2，cpu 7给3，cpu 8给4这样。这样的粒度太糙了，而且预期的资源配给可能跟真实的负载相差很多。

与其瞎琢磨，瞎测试，不如多了解下CFS调度器让内核自己来解决。CFS调度器其实可以比较好地解决这个问题，不同服务可能创建了不同数量的线程、协程来支持对一个的请求量级，CFS调度器尽可能保证每个线程调度的公平（CFS调度的目标实际上是更抽象的sched_entity，这里用“线程”先简化问题范畴），从而让服务获得应该和负载匹配的cpu执行时间。

仍有顾虑

看似通过上述设置，即使是混部，也可以工作的很好，嗯，但是我还是有一点其他的顾虑。俗话说“无规矩不成方圆”，如果大家都守规矩、不犯错，可能也没写这篇文章的必要了。或者说，写这篇文章主要是想探讨下，研发规范、平台能力如何避免让这些不守规矩、爱犯错的人犯错。《波斯王子》里老国王对儿子说，“一个伟大的人，不仅自己要尽量不犯错，也要阻止他人犯错”。

我有这些顾虑，重点考虑cpu资源：

1、如果机器混部有不同用户1、用户2的服务，用户1的进程数（线程数）特别多，如果不加控制手段，用户1会挤占用户2的资源；

2、如果用户1混部了多个服务1、2、3，如果服务3实现有问题，创建了大量线程，服务3会挤占服务1、2的资源；

3、还有种情况，每个服务可能对应着一个进程组，如果某个服务创建大量进程、线程，从而挤占了其他服务的资源怎么办；

其实这些问题，都属于调度器层面对于“公平性”的考虑范畴，只是它们有不同的层次：线程级别，用户级别，组级别。

CFS调度器随着第一个patch以及后续的很多次优化，可以解决上述不同层级的“公平性”问题，这就是“组调度(CFS group scheduling)”，我们在后面介绍。

CFS调度器

在学习RSDL调度器中我们也了解了它是如何保证和体现调度的公平性的，那么CFS调度器又是如何做的呢？一起来看下。

公平性建模

抽象vruntime

在我看来，抛开道德、协作争议等问题不谈，我认为CFS调度器比Con Kolivas提出的RSDL调度器对公平性的建模上更胜一筹，因为它非常容易理解、容易实现，能够比较简单地论证这个算法能否比较好的工作。

CFS调度器，提出了vruntime（虚拟运行时间）的概念，CFS调度器的宗旨就是力图维持所有进程的vruntime都尽可能相同，通过这种方式来尽可能保证每个被调度实体都执行了相同的虚拟运行时间。

之所以强调是虚拟运行时间，而非是实际执行时间，是因为“公平性”还必须体现出优先级的概念，即简单说：

虚拟运行时间 = 实际执行时间 / 优先级对应的权重

优先级高的权重也大，优先级低的权重小，实际执行时间相同的两个不同优先级进程p1、p2，其中优先级低的虚拟运行时间偏大，意味着高优先级的进程会获得更多调度机会。

vruntime的实际计算式为：

virtual runtime = (real runtime) * (NICE_0_LOAD) / (weight of the process)
  • 其中virtual runtime指的就是vruntime;
  • real runtime指的是cpu上的实际执行时间;
  • NICE_0_LOAD表示nice==0时的默认权重（1024）;
  • 而weight of the process指的是由进程的实际优先级从映射表映射而来的权重;

完整的映射表可以参考：

const int sched_prio_to_weight[40] = {
 /* -20 */     88761,     71755,     56483,     46273,     36291,
 /* -15 */     29154,     23254,     18705,     14949,     11916,
 /* -10 */      9548,      7620,      6100,      4904,      3906,
 /*  -5 */      3121,      2501,      1991,      1586,      1277,
 /*   0 */      1024,       820,       655,       526,       423,
 /*   5 */       335,       272,       215,       172,       137,
 /*  10 */       110,        87,        70,        56,        45,
 /*  15 */        36,        29,        23,        18,        15,
};

这样的话，可以直观感受到：

  • 如果一个进程优先级为默认值（nice==0），那么其权重为1024，那么其virtual runtime 完全等于其 real runtime；
  • 如果一个进程优先级越高，意味着其权重大，执行相同的real runtime，其对应的vruntime偏小，此后仍然更容易被调度；
  • 如果一个进程优先级越低，意味着权重越小，执行相同的real runtime，其对应的vruntime偏大，此后会被冷落优先调度其他vruntime更小的实体；

CFS对公平性的建模，是非常容易理解的，而且实现上也更简单、易论证检查器有效性。

抽象sched_entity

另外，如果要对不同用户先进行公平调度，然后再对用户下的任务进行公平调度；如果要对不同的任务组先进行公平调度，再对组内的任务进行公平调度；再或者说不同的会话先进行公平调度，再对会话内启动的进程进行公平调度呢……如何建模并解决这种场景。

CFS将以往调度的对象从具体的一个线程（thread或者lwp），抽象为了一个任务调度实体sched_entity，你可以用它来实现上述提出的几个刁钻的场景，在不同用户之间实现公平，在不同任务组之间实现公平，在不同会话之间实现公平。

而它也可以建模多层级结构下的调度的公平性，如不同用户->不同会话->不同任务组->不同线程的各级调度均保证公平。实际上在Linux 2.6.24还是Linux 2.6.30的CFS补丁中确实有一个选项，CONFIG_FAIR_USER_SCHED=y，编译构建时设置为打开，那么CFS调度器会自动对不同用户线进行公平调度。但是后续又移除了这个编译选项，感兴趣的可以继续看下这两篇内容：

实际上有了sched_entity这层抽象设计，赋予了CFS调度器组调度的能力，组调度也可以实现上述所有提及的场景，实现多层级的调度时的公平性。比如让系统管理员为不同用户设置不同的组调度，然后将用户创建的进程全部放到这个组中，多个用户对应的组各自的cpu.shares相同，这样就可以实现多用户之间调度的公平性，疯狂创建进程、线程的用户并不会获得更多的cpu执行时间。

ps：一个有趣的功能，Linux内核提供了autogroup的特征，新session创建时会自动创建一个task group并将session中创建的任务放到这个相同的task group用于cfs公平调度。

阻塞唤醒后抢占

阻塞后唤醒后，查看是否要调度另一个任务，此时会将当前进程的vruntime设置为：

vruntime = max(p.old_vruntime, global.min_vruntime-sched_latency)

如果阻塞比较久的话, global.min_vruntime表示当前正在被调度的进程的vruntime，sched_latency是个时间常量，这样的话min_vruntime-sched_latency至少比当前应该正在执行的那个进程的vruntime要小，就会导致那个进程被当前恢复的进程抢占（preempted），从IO中恢复的进程会被奖励，和MLFQ类似的思路，让阻塞的任务赶紧恢复执行。

被更高优进程抢占

cfs调度器中没有固定大小的timeslice时间片的概念了，一个任务执行到什么时候会发生切换，完全依赖于是否仍旧被判定为“最不公平”，只要不是了，scheduler工作的时候就会切换其他进程执行。

但是要注意控制vruntime变化的粒度，以避免频繁发生任务切换导致不必要的开销。

设计实现

这里有几篇文章介绍了CFS调度器的源码层面的分析，包括运行队列的核心数据结构、CFS相关的核心字段，以及vruntime的计算更新逻辑，以及新创建1个进程时或者调度其他进程时CFS是如何选择并更新vruntime的。

类似O(1)那样，每个cpu维护独立的数据结构（rbtree），避免锁竞争，也存在需要负载均衡的问题。

伴随着CFS的patch，也一并提交了一个可插拔的模块化调度器实现，可以插入自定义的调度器实现，这个之前是Con Kolivas一直给Torvalds和Ingo等人建议的，但是他俩更倾向于使用一个默认的支持通用场景的内核，但是实际情况是没有银弹，没有一个调度器能够胜任各种设备类型、应用场景。这也是为什么CFS看似稳定以后，仍然有些人在桌面环境下表达了对Linux调度交互性的不满，Con Kolivas更是在2009年左右又提出了新的调度器算法Brain Fucker Scheduler。

OK，我们不牵扯太多设计实现的细节了，上面两篇文章由浅入深，写的很好，我实在没必要再重新总结一遍，OK，我们来测试下如何使用CFS来做些控制。

在执行下面的测试之前，我们还需要了解下如何组调度扩展如何使用：

其实cgroups下面的一些配置项，恰恰是CFS调度器工作时可以读取的一些参数，比如bandwidth、latency、shares等。这里我们简单总结下吧，读者可以按需去加深了解下。

2.2.1 核心概念 - 调度实体

2.2.2 核心概念 - 调度类

看完这些后，会发现cpu.shares, cpu.fair_period_us, cpu.fair_quota_us都是cfs调度器的一些参数，用来控制：

  • cpu.fair_period_us，cfs不需要为进程指定时间片，完全依赖虚拟时间vruntime来保证公平性，除了公平调度，cfs还需要保证每隔一段时间至少执行任务一次，这就是调度周期。有个概念，调度延迟，指同一个schedentity前后两次调度的时间间隔。调度周期就是要保证这个schedentity的调度延迟小于调度周期，简言之就是调度周期内至少要执行一次。see: https://s3.shizhz.me/linux-sched/cfs-sched/logic-period

  • cpu.fair_quota_us，cfs调度器需要能限制任务在一个调度周期内的执行时间，这个值可以不限制，但是最大就是上面fair_period_us的值，这个很好理解。\

    see: https://s3.shizhz.me/linux-sched/cfs-sched/bandwidth,

    see: https://s3.shizhz.me/linux-sched/cfs-sched/bandwidth-time

  • cpu.shares，控制的是不同控制组的调度权重，如果cpu.shares=1024, 下面有10个进程，那么就是102410=10240,其他调度组也是这么计算，如果其他调度组也是1024，但是是5个进程，那么就是10245=10240/2，意味着前一个调度组将获得两倍于后者的执行时间。see: https://s3.shizhz.me/linux-sched/cfs-sched/group-weight

cfs组调度其实是控制组cgroups对cpu资源进行控制的基石，它们都依赖sched_entity，最开始调度器针对的对象是task_struct，后面为了更好的对公平性（多个用户之间，多个任务组之间）进行建模，就抽象出了sched_entity，它非常灵活了，cgroups /sys/fs/cgroup/cpu只不过是在这个的基础上构建来的更便利的一个可以提供给用户进行操作的接口。sched_entity代指的是用户（用户组其实任务组的一个特例），也可以是自定义的一组进程（比如我还把同一个进程的线程编为一组），也可以是单个进程。

CFS的测试

测试1：单线程程序，测试cgroups cpu.shares影响调度

首先要构造一个测试场景：有不少的的进程需要调度，调度器切换时会发现存在待调度的多个进程在竞争，所以调度器就要需要做选择来执行。

测试机是1 cpu 8 cores，测试过程如下：

  • 起1个是单线程的c程序，for循环打印

  • 起1个是多线程的go程序，for起多个goroutine，每个goroutine循环打印

  • nohup启动c程序2次、nohup启动go程序8次，

    这样，至少启动了2+8个线程，超过机器cpu cores，这样可以断定进程调度的时候有调度竞争，这样cpu.shares的作用才能体现出来嘛

  • 然后/sys/fs/cgroup/cpu下创建两个taskgroup

    • god1，god1/tasks中放入其中1个c程序的pid，然后cpu.shares中从默认值1024设为1
    • god2，god2/tasks中放入另一个c程序的pid，然后cpu.shares中从默认值1024设为10240
    • atop观察进程执行时间……虽然不满足1:10240的倍数关系，但是可以明显看到影响到了对这两个c程序的调度，cpu.shares=1的组的c程序，片上执行时间明显少很多（ps：至于为何不满足1:10240关系，这涉及到cpu.shares对cfs调度的影响了，先放放）。

image-20231119155148580

测试2：多线程程序，测试cgroups cpu.shares影响调度

对于go这个多线程程序而言呢，我只将进程pid加入到tasks里面可以吗？比如创建cgroup perf3，然后将下面的cpu.shares设为1，然后将父进程pid放进去，发现并不会影响整个进程的片上执行时间，或者说影响很小。

其实这里的tasks中的id都是进程id，而线程也是进程（lwp），你得把所有线程的id都加进去才可以。当全部加进去之后，效果就出来了。

image-20231119155113015

这里的测试只是将某个go进程下的线程的调度机会调低了，比如我可以这样调进程A的，然后也可以这样调进程B的，这样来实现A、B进程整体调度的相对公平。

ps：A创建1000个线程，B创建10个线程，要实现A、B的公平，可以这样做：A创建控制组gp-a, 然后将cpu.shares设置为1024/1000，B创建控制组gp-b，将cpu.shares设置为1024/10，这样可以实现A、B调度的整体公平……到这里还是猜测，可以继续测试下。

测试3：继续测试

写一个多线程c程序：

  • 起8个线程、加主线程9个，循环打印……控制组cpu.shares=50，线程全加入控制组

  • 起4个线程、加主线程5个，循环打印……控制组cpu.shares=500，线程全加入控制组

这样的情况下两个进程整体调度的片上时间能持平。

image-20231119155221438

但是测试下来发现，根据“cpu.shares=1024/线程数”，这种方式是不科学的，算出来的值不能让进程A、B实现片上时间持平……可能还没抓到问题的核心？

继续看下cpu.cfs_quota_us，至少效果上是我要找的东西，这个配额相当于一个上限，可以直接实现我们的目标。能够轻松实现A、B两个线程数不同的进程在整体调度上片上执行时间达到一个持平的状态，实现对进程调度公平性的探索。

image-20231119155235004

ps：但是我只是想让A、B进程持平，却不想给它们加什么配额上限，这样会让cpu无法跑满，有点浪费……似乎我需要的是一个类似控制组之间的权重的东西？

能相对公平，同时又能充分利用cpu空闲资源来调度，只是说要尽量公平调度A、B进程。

等等，是我忽略了配置项的实际意义：

  • cpu.cfs_period_us，单位微秒，表示多久为当前调度组更新可用执行时间
  • cpu.cfs_quota_us，单位微秒，表示一个period内该调度组下的任务最多执行多久
  • cpu.shares，表示当前调度组与其他调度组相比，他们之间调度的一个权重

那么我们可以直接不修改cpu.shares，A、B两个调度组cg-a cg-b的cpu.shares都是1024，意味着他们都有相同概率被调度到，但是它们下面的诸多线程，可以通过cpu.cfs_period_us、cpu.cfs_quota_us来控制，只要这3个值相同，表示他们被调度的概率相同、定期申请cpu资源的周期相同、周期内可以消耗的上限也相同，假设他们确实有干活的线程……那么A、B进程整体调度执行的时间就是持平的了！而且cpu资源也能得到充分利用，完美！

image-20231119155250555

通过调节这里的cpu.cfs_quota_us/cpu.cfs_period_us可以精确控制进程实际执行时间占比。

ps：现在设置了上面两个配置项后，cpu.shares就没啥效果了，调大调低都没作用。

image-20231119155310165

如果按上面提示，取消quota设置，只设置cpu.shares，如果启动mt_thread 2个实例，分别设置他们的shares，确实他们cpu执行片上时间的比例基本和cpu.shares的比例近似，只能说这个比例差不多，但不是相等，还是有点差值的。

ps: 使用cgroup v2的cpu.weight可以做到吗？

see：如何在wsl2中启用cgroup v2？How to enable cgroup v2 in WSL2?

cgroup v2中提供了权重，难道能帮助我更轻松的实现这个目标吗？

本文小结

本文首先介绍了作者在业务实践中遇到的一点问题，进而引出了对Linux调度机制公平性的思考，然后介绍了CFS调度器的对公平性的建模，我们介绍了vruntime（虚拟运行时间）的由来以及计算更新方式，也介绍了group scheduling（组调度）对于用户、任务组的公平性的支持。也介绍了cgroups如何提供了一个用户友好的接口来方便地发挥组调度的能力（而且支持多层级），意味着你可以轻松实现“用户->会话->任务组->任务”多层级的公平性调度支持。

最后回到作者最初心头萦绕的那些问题，我们写了一些测试程序、跑了一些测试来验证CFS调度器中cpu.shares、cpu.cfs_period_us、cpu.cfs_quota_us对调度的一些影响和作用，我们也测试并得出了一些有价值的结论，比如：

  • 多线程程序A、B，它们线程数不同，我们该如何保证A、B进程层面的调度公平性，而不是默认的线程层面的调度公平性。
  • 以及如何保证用户层面的调度公平。

其实这篇论文，也是想探讨我提出的这些问题， https://www.cs.mtsu.edu/~waderholdt/6450/papers/cfs.pdf，…. In the 17th revision of CFS, the scheduler includes scheduling entities (group, container, tasks, users, etc) patch [5], which are used to implement group-fair and user-fair scheduling……论文作者提出的是，process fair scheduler而非linux cfs默认的thread fair scheduler。

其实解决user fairness、group fairness的问题呢？都是通过这个sched_entity来实现的，cfs只提供基础能力不限制如何对任务进行分组，你要分组的话随便你自己怎么组织（CFS早期实现确实有支持user fairness的编译选项，但后面又移除了）。

写了这么多，读到这里的都是对细节很专注的人，也感谢大家的阅读分享。

参考文献

  1. cfs group scheduling
  2. linux核心概念"调度实体"
  3. linux核心概念"调度类"
  4. digging into linux scheduler
  5. brain fucker scheduler
  6. group scheduling extension
Edit this page on GitHub
← Linux任务调度(6)
Linux任务调度(3) →