# linux kernel documentation-CFS Scheduler
Date: 2019-08-29


这篇文章 [CFS Scheduler](https://www.kernel.org/doc/Documentation/scheduler/sched-design-CFS.txt)是Linux Kernel文档

### 1.概述

`CFS` - "Completely Fair Scheduler"，是新的交互式流程调度算法,由Ingo Molnar实现，并在Linux 2.6.23中合并。它是替换以前的Vanilla Kernel的SCHED\_OTHER调度策略对应的调度算法。

> _`SCHED_OTHER`是老版本中的调度策略后续成为`SCHED_NORMAL`_ _Vanilla Kernel是指http://www.kernel.org/的上Linux的发布版本_ _[What is Vanilla kernel](https://www.linuxquestions.org/questions/linux-general-1/what-is-vanilla-kernel-79388/)_ _[Debian wiki vanilla](https://wiki.debian.org/vanilla)_

CFS 80%的设计可以用一句话来概括：CFS基本上是模型真实硬件上的“理想，精确的多任务CPU”。

`理想的多任务CPU`是一种（不存在的 :-) ）具有100％物理性能的CPU 功率和每个任务可以以精确的相等速度并行运行每个任务 1 / nr\_running速度。例如：如果有2个任务在运行，那么它就会运行每个物理功率为50％, 即实际上并联。

在真正的硬件上，我们一次只能运行一个任务，所以我们必须这样做 介绍`虚拟运行时`(vruntime))的概念。任务的虚拟运行时 指定下一个时间片何时开始执行理想 上面描述的多任务CPU。在实践中，任务的虚拟运行时是它的实际运行时间标准化为正在运行的任务总数。

### 2.部分实现细节

在CFS中，通过每个任务task的虚拟运行时(vruntime)通过 p->se.vruntime（纳秒为单位）值体现。这样，就可以任务可以等到准确时间戳并测量应该得到的`预期CPU时间`。

\[小细节：在`理想`硬件上，任何时候所有任务都会相同 p-> se.vruntime --- 任务将同时执行, 没有任务将从CPU时间等到一样的份额。\]

CFS的任务选择逻辑基于此p->se.vruntime值，因此非常简单：它总是尝试以最小的p->se.vruntime运行任务值（即至少执行到目前为止的任务）。 CFS总是试图拆分 可运行任务之间的CPU时间接近`理想的多任务硬件` 可能。

CFS的其余大部分设计都脱离了这个非常简单的概念， 有一些附加的装饰，如nice值,多处理和各种算法变体去识别睡眠者。

### 3\. 红黑树

CFS的设计非常激进：它没有使用旧的数据结构 runqueues，但它使用按时间排序的rbtree来构建未来执行任务的`时间轴` ，因此不涉及`数组切换`（以前的Vanilla Kernel调度器O(1)和RSDL/SD涉及到）。

> _Linux 2.4调度使用时间片epoch,类似多路复用模式,使用runqueue调度方法与进程个数有关_ _array switch:O(1)为每个CPU维护了两个数组active与expire数组,随着时钟中断发生，1.调度器判断当前进程类型交互进程或者实时进程，重置其时间片重新插入active数组，不是交互实时进程、时间片使用完毕的放入expired数组, 当所有active为空,active与expired交换_ _RSDL/SD是对O(1)改进_ _[Linux 调度器发展简述](https://www.ibm.com/developerworks/cn/linux/l-cn-scheduler/index.html)_

CFS还维护rq->cfs.min\_vruntime值，这是一个单调递增值，用于跟踪runqueue中所有任务中的最小vruntime。使用min\_vruntime跟踪系统完成的工作总量; 该值用于尽可能多地将新激活的实体放置在树的左侧。

> _每一个cpu维护一个min\_vruntime,每一个子进程创建时被初始化为这个值，如果schedule\_feature 设置了SCHED\_DEBIT，vruntime还会再增大一些_ [从几个问题开始理解CFS调度器](http://linuxperf.com/?p=42)

runqueue中运行任务的总数通过rq->cfs.load值计算，该值是在runqueue上排队的任务的权重之和。

CFS维护一个按时间排序的红黑树，其中所有可运行的任务都按p->se.vruntime排序。CFS总是从这棵树中挑选出`最左边`的任务。随着系统向前推进，执行的任务越来越多地被放入树中 - 缓慢但肯定地为每个任务提供机会成为`最左边的任务`，从而在确定的数量范围内进入CPU时间。

> _如果发现当前进程不是最左边节点,设置`TIF_NEED_RESCHED`在下一次进程调度进程切换_

总而言之，CFS的工作方式如下：它运行一个任务，当任务计划（或发生时钟中断）时，任务的CPU使用率被`占用`：它使用物理CPU花费的（小）时间是添加到p->se.vruntime。一旦p-> se.vruntime变得足够高，以便另一个任务成为时间排序红黑树的`最左边的任务`（加上相对于最左边任务的少量`粒度`距离，这样我们就不会过度安排任务并删除缓存），然后选择新的最左边任务并抢占当前任务。

### 4\. CFS的一些特点

CFS使用纳秒粒度计算，不依赖于任何jiffies或其他HZ细节。因此，CFS调度程序没有先前调度程序具有的`timeslices`概念，并且没有任何启发式方法。只有一个中央可调参数（您必须打开CONFIG\_SCHED\_DEBUG）：

/proc/sys/kernel/sched\_min\_granularity\_ns

可用于将调度程序从`desktop`（交互式即低延迟）调整到“服务器”（即，良好的批处理）工作负载。它默认为适合桌面工作负载的设置。SCHED\_BATCH也由CFS调度程序模块处理。

由于它的设计，有些著名的程序：fiftyp.c，thud.c，chew.c，ring-test.c，massive\_intr.c总能让调度器的性能下降，CFS调度程序一切正常，不影响交互性，产生预期的行为。

与以前的Vanilla Kernel调度程序相比，CFS调度程序对nice的级别和SCHED\_BATCH的处理要强得多：两种类型的工作负载都被更加积极地隔离。

SMP负载平衡已经过重新设计/清理：现在从负载平衡代码中消除了runqueue-walking假设，并且使用了调度模块的迭代器。结果平衡代码变得更加简单。

### 5.调度策略

`CFS`实施三种调度策略：

- `SCHED_NORMAL`(传统上称为`SCHED_OTHER`）：用于常规任务的调度策略。
- `SCHED_BATCH`:不像常规任务那样经常抢占，因此允许任务运行更长时间并更好地利用缓存，但代价是交互性。这非常适合批量作业。
- `SCHED_IDLE`：这甚至比nice 19更弱，但它不是真正的空闲定时器调度程序，以避免进入导致机器死锁的优先级反转问题。

SCHED\_FIFO/SCHED\_RR 在 sched/rt.c 实现由POSIX指定。

来自util-linux-ng 2.13.1.1的命令chrt可以设置除SCHED\_IDLE之外的所有这些命令。

### 6.调度类

新的CFS调度程序的设计方式是引入`调度类`，这是一个可扩展的调度程序模块层次结构。这些模块封装了调度策略的详细信息，并由调度程序核心处理，而核心不需要关心他的实现细节。

sched/fair.c实现了上述CFS调度程序。

sched/rt.c以比以前的Vanilla Kernel调度程序更简单的方式实现SCHED\_FIFO和SCHED\_RR语义。它使用100个运行队列（对于所有100个RT优先级，而不是之前的调度程序中的140个）并且它不需要过期的数组。

调度类是通过sched\_class结构实现的，该结构包含必须在发生相关事件时调用的函数的钩子。

这是部分hooks(功能实现)的列表：

- enqueue\_task(...)
    
    在任务进入可运行状态时调用。它将调度实体（任务）放入红黑树中并递增nr\_running变量。
    
- dequeue\_task(...)
    
    当任务不再可运行时，将调用此函数以使相应的调度实体保持在红黑树之外。它递减nr\_running变量。
    
- yield\_task(...)
    
    除非打开compat\_yield，否则此函数基本上只是一个队列后出队列的队列; 在这种情况下，它将调度实体放在红黑树的最右端。
    
- check\_preempt\_curr(...)
    
    该函数将检查当前运行的任务是否被抢占。在实际抢占正在运行的任务之前，CFS 调度程序模块将执行公平性测试。这将驱动唤醒式（wakeup）抢占。
    
- pick\_next\_task(...)
    
    此功能选择最适合下次运行的任务。
    
- set\_curr\_task(...)
    
    当任务更改其调度类或更改其任务组时，将调用此函数。
    
- task\_tick（...）
    
    该函数通常调用自 time tick 函数；它可能引起进程切换。这将驱动运行时（running）抢占。
    

### 7.CFS扩展组调度

通常，调度程序根据各个任务进行操作，并努力为每个任务提供合理的CPU时间。有时，可能需要对任务进行分组并为每个此类任务组提供合理的CPU时间。例如，可能希望首先向系统上的每个用户提供公平的CPU时间，然后为属于用户的每个任务提供公平的CPU时间。

CONFIG\_CGROUP\_SCHED努力实现这一目标。它允许对任务进行分组，并在这些组之间公平地划分CPU时间。

CONFIG\_RT\_GROUP\_SCHED允许对实时（即SCHED\_FIFO和SCHED\_RR）任务进行分组。

CONFIG\_FAIR\_GROUP\_SCHED允许对CFS（即SCHED\_NORMAL和SCHED\_BATCH）任务进行分组。

> _这些选项需要定义CONFIG\_CGROUPS，并让管理员使用`cgroup`伪文件系统创建任意任务组。有关此文件系统的详细信息，请参阅[Documentation/admin-guide/cgroup-v1/cgroups.rst](https://www.kernel.org/doc/html/latest/admin-guide/cgroup-v1/cgroups.html)。_

定义CONFIG\_FAIR\_GROUP\_SCHED时，将为使用伪文件系统创建的每个组创建“cpu.shares”文件。请参阅下面的示例步骤以使用`cgroups`伪文件系统创建任务组并修改其CPU份额：

```C
# mount -t tmpfs cgroup_root /sys/fs/cgroup
# mkdir /sys/fs/cgroup/cpu
# mount -t cgroup -ocpu none /sys/fs/cgroup/cpu
# cd /sys/fs/cgroup/cpu

# mkdir multimedia  # create "multimedia" group of tasks
# mkdir browser     # create "browser" group of tasks

# #Configure the multimedia group to receive twice the CPU bandwidth
# #that of browser group

# echo 2048 > multimedia/cpu.shares
# echo 1024 > browser/cpu.shares

# firefox & # Launch firefox and move it to "browser" group
# echo <firefox_pid> > browser/tasks

# #Launch gmplayer (or your favourite movie player)
# echo <movie_player_pid> > multimedia/tasks
```