简介

CFS 是当前 linux 发行版中默认的 CPU 调度算法，在内核 2.6.23 版本中被第一次引入，用来决定在某一时刻哪个进程可以运行在物理CPU上。

先介绍一下 CPU 调度的基本概念

Linux调度类

调度类（scheduling class），目的是将调度器抽象化，使得更容易添加和切换具体的调度类的实现。

在Linux中，使用 struct sched_class 结构体描述一个具体的调度类。简单的介绍下 struct sched_class 部分成员作用。

  1. struct sched_class {
  2.     // 向该调度器管理的 runqueue 中添加一个进程。
  3.     void (*enqueue_task) (struct rq *rq, struct task_struct *p, int flags);
  4.     // 向该调度器管理的 runqueue 中删除一个进程。
  5.     void (*dequeue_task) (struct rq *rq, struct task_struct *p, int flags);
  6.     // 从 runqueue 中选择一个最适合运行的进程。
  7.     struct task_struct *(*pick_next_task)(struct rq *rq);
  8.     // 更新 rq 的状态-包括 vruntime
  9.     void (*update_curr)(struct rq *rq);
  10. }

CFS

CFS 每次从运行队列中获取 vruntime 值最小的 task，作为下一次在 CPU 上执行的进程。

运行队列-runqueue

等待被调度到CPU上进行运行的任务；

  • 每个 CPU 处理器上都有一个对应的 runqueue，同一个任务不可能同时出现在多个 runqueue 中；
  • 每一个 runqueue 都是一棵红黑树，树的节点按照 vruntime 进行排序，每个节点都代表一个任务。

虚拟运行时-vruntime

假设 runqueue 中有两个进程 A,B，如果 A运行 10ms，然后 B运行 10ms，然后在运行到 A，也就是 A 每隔 20ms 才会被再次调度到 CPU 上。这个延迟在 runqueue 中进程较多了，可能会变得非常的长。

CFS 为了解决这个问题，就提出了 vruntime 这个东西。它假设在一段时间把 runqueue 中每一个任务都运行一遍。比如 10ms 内，A 运行 5ms，接着 B 运行 5ms，然后就又轮到了 A。
**

即如果有 N 个task，则每个task 运行 1/N 的时间。

**

当然，为了防止调度过于频繁，内核还有一些其他机制保证调度间隔不能太小。

权重和优先级-nice

假设现在系统有A，B，C三个进程，A.weight=1,B.weight=2,C.weight=3.那么我们可以计算出整个公平调度队列的总权重是cfs_rq.weight = 6，公平就是你在重量中占的比重的多少来拍你的重要性，那么，A的重要性就是1/6,同理，B和C的重要性分别是2/6,3/6。很显然C最重要就应改被先调度，而且占用的资源也应该最多，即假设A，B,C运行一遍的总时间假设是6个时间单位的话，A占1个单位，B占2个单位，C占三个单位。

在CFS调度器中，将进程优先级这个概念弱化，而是强调进程的权重。一个进程的权重越大，则说明这个进程更需要运行，因此它的虚拟运行时间就越小，这样被调度的机会就越大。

CFS调度器中的权重在内核是对用户态进程的优先级 **nice** 值, 通过 **prio_to_weight** 数组进行 **nice** 值和权重的转换而计算出来的。
**

虚拟运行时间就是通过进程的实际运行时间和进程的权重(weight)计算出来的。

共享虚拟运行时-cpu.shares

主要用在 cgroup 中，可以在 CFS 中定义一个 group。该 group 作为独立的 task 计算 vruntime，在 group 的内部，通过 /sys/fs/cgroup/cpu/cpu.shares 中定义的比例去再次分配。

如下图所示，如果 group3 和 group4 按照 1:3 的比例进行配置 cpu.shares 则在运行时，分配给 group2 的cpu 时间中将会按照 1:3 的比例分配给 group3 和 group4
image.png

Linux cgroup 中 cfs 关键配置

  1. $ ls /sys/fs/cgroup/cpu/cpu.cfs_*
  2. /sys/fs/cgroup/cpu/cpu.cfs_period_us  /sys/fs/cgroup/cpu/cpu.cfs_quota_us