0001 .. SPDX-License-Identifier: GPL-2.0
0002 .. include:: ../disclaimer-zh_CN.rst
0003
0004 :Original: Documentation/scheduler/sched-design-CFS.rst
0005
0006 :翻译:
0007
0008 唐艺舟 Tang Yizhou <tangyeechou@gmail.com>
0009
0010 ===============
0011 完全公平调度器
0012 ===============
0013
0014
0015 1. 概述
0016 =======
0017
0018 CFS表示“完全公平调度器”，它是为桌面新设计的进程调度器，由Ingo Molnar实现并合入Linux
0019 2.6.23。它替代了之前原始调度器中SCHED_OTHER策略的交互式代码。
0020
0021 CFS 80%的设计可以总结为一句话：CFS在真实硬件上建模了一个“理想的，精确的多任务CPU”。
0022
0023 “理想的多任务CPU”是一种（不存在的 :-)）具有100%物理算力的CPU，它能让每个任务精确地以
0024 相同的速度并行运行，速度均为1/nr_running。举例来说，如果有两个任务正在运行，那么每个
0025 任务获得50%物理算力。 --- 也就是说，真正的并行。
0026
0027 在真实的硬件上，一次只能运行一个任务，所以我们需要介绍“虚拟运行时间”的概念。任务的虚拟
0028 运行时间表明，它的下一个时间片将在上文描述的理想多任务CPU上开始执行。在实践中，任务的
0029 虚拟运行时间由它的真实运行时间相较正在运行的任务总数归一化计算得到。
0030
0031
0032
0033 2. 一些实现细节
0034 ===============
0035
0036 在CFS中，虚拟运行时间由每个任务的p->se.vruntime（单位为纳秒）的值表达和跟踪。因此，
0037 精确地计时和测量一个任务应得的“预期的CPU时间”是可能的。
0038
0039 一些细节：在“理想的”硬件上，所有的任务在任何时刻都应该具有一样的p->se.vruntime值，
0040 --- 也就是说，任务应当同时执行，没有任务会在“理想的”CPU分时中变得“不平衡”。
0041
0042 CFS的任务选择逻辑基于p->se.vruntime的值，因此非常简单：总是试图选择p->se.vruntime值
0043 最小的任务运行（也就是说，至今执行时间最少的任务）。CFS总是尽可能尝试按“理想多任务硬件”
0044 那样将CPU时间在可运行任务中均分。
0045
0046 CFS剩下的其它设计，一般脱离了这个简单的概念，附加的设计包括nice级别，多处理，以及各种
0047 用来识别已睡眠任务的算法变体。
0048
0049
0050
0051 3. 红黑树
0052 =========
0053
0054 CFS的设计非常激进：它不使用运行队列的旧数据结构，而是使用按时间排序的红黑树，构建出
0055 任务未来执行的“时间线”。因此没有任何“数组切换”的旧包袱（之前的原始调度器和RSDL/SD都
0056 被它影响）。
0057
0058 CFS同样维护了rq->cfs.min_vruntime值，它是单调递增的，跟踪运行队列中的所有任务的最小
0059 虚拟运行时间值。系统做的全部工作是：使用min_vruntime跟踪，然后用它的值将新激活的调度
0060 实体尽可能地放在红黑树的左侧。
0061
0062 运行队列中正在运行的任务的总数由rq->cfs.load计数，它是运行队列中的任务的权值之和。
0063
0064 CFS维护了一个按时间排序的红黑树，所有可运行任务以p->se.vruntime为键值排序。CFS从这颗
0065 树上选择“最左侧”的任务并运行。系统继续运行，被执行过的任务越来越被放到树的右侧 --- 缓慢，
0066 但很明确每个任务都有成为“最左侧任务”的机会，因此任务将确定性地获得一定量CPU时间。
0067
0068 总结一下，CFS工作方式像这样：它运行一个任务一会儿，当任务发生调度（或者调度器时钟滴答
0069 tick产生），就会考虑任务的CPU使用率：任务刚刚花在物理CPU上的（少量）时间被加到
0070 p->se.vruntime。一旦p->se.vruntime变得足够大，其它的任务将成为按时间排序的红黑树的
0071 “最左侧任务”（相较最左侧的任务，还要加上一个很小的“粒度”量，使得我们不会对任务过度调度，
0072 导致缓存颠簸），然后新的最左侧任务将被选中，当前任务被抢占。
0073
0074
0075
0076
0077 4. CFS的一些特征
0078 ================
0079
0080 CFS使用纳秒粒度的计时，不依赖于任何jiffies或HZ的细节。因此CFS并不像之前的调度器那样
0081 有“时间片”的概念，也没有任何启发式的设计。唯一可调的参数（你需要打开CONFIG_SCHED_DEBUG）是：
0082
0083 /proc/sys/kernel/sched_min_granularity_ns
0084
0085 它可以用来将调度器从“桌面”模式（也就是低时延）调节为“服务器”（也就是高批处理）模式。
0086 它的默认设置是适合桌面的工作负载。SCHED_BATCH也被CFS调度器模块处理。
0087
0088 CFS的设计不易受到当前存在的任何针对stock调度器的“攻击”的影响，包括fiftyp.c，thud.c，
0089 chew.c，ring-test.c，massive_intr.c，它们都能很好地运行，不会影响交互性，将产生
0090 符合预期的行为。
0091
0092 CFS调度器处理nice级别和SCHED_BATCH的能力比之前的原始调度器更强：两种类型的工作负载
0093 都被更激进地隔离了。
0094
0095 SMP负载均衡被重做/清理过：遍历运行队列的假设已经从负载均衡的代码中移除，使用调度模块
0096 的迭代器。结果是，负载均衡代码变得简单不少。
0097
0098
0099
0100 5. 调度策略
0101 ===========
0102
0103 CFS实现了三种调度策略：
0104
0105 - SCHED_NORMAL：（传统被称为SCHED_OTHER）：该调度策略用于普通任务。
0106
0107 - SCHED_BATCH：抢占不像普通任务那样频繁，因此允许任务运行更长时间，更好地利用缓存，
0108 不过要以交互性为代价。它很适合批处理工作。
0109
0110 - SCHED_IDLE：它比nice 19更弱，不过它不是真正的idle定时器调度器，因为要避免给机器
0111 带来死锁的优先级反转问题。
0112
0113 SCHED_FIFO/_RR被实现在sched/rt.c中，它们由POSIX具体说明。
0114
0115 util-linux-ng 2.13.1.1中的chrt命令可以设置以上所有策略，除了SCHED_IDLE。
0116
0117
0118
0119 6. 调度类
0120 =========
0121
0122 新的CFS调度器被设计成支持“调度类”，一种调度模块的可扩展层次结构。这些模块封装了调度策略
0123 细节，由调度器核心代码处理，且无需对它们做太多假设。
0124
0125 sched/fair.c 实现了上文描述的CFS调度器。
0126
0127 sched/rt.c 实现了SCHED_FIFO和SCHED_RR语义，且比之前的原始调度器更简洁。它使用了100个
0128 运行队列（总共100个实时优先级，替代了之前调度器的140个），且不需要过期数组（expired
0129 array）。
0130
0131 调度类由sched_class结构体实现，它包括一些函数钩子，当感兴趣的事件发生时，钩子被调用。
0132
0133 这是（部分）钩子的列表：
0134
0135 - enqueue_task(...)
0136
0137 当任务进入可运行状态时，被调用。它将调度实体（任务）放到红黑树中，增加nr_running变量
0138 的值。
0139
0140 - dequeue_task(...)
0141
0142 当任务不再可运行时，这个函数被调用，对应的调度实体被移出红黑树。它减少nr_running变量
0143 的值。
0144
0145 - yield_task(...)
0146
0147 这个函数的行为基本上是出队，紧接着入队，除非compat_yield sysctl被开启。在那种情况下，
0148 它将调度实体放在红黑树的最右端。
0149
0150 - check_preempt_curr(...)
0151
0152 这个函数检查进入可运行状态的任务能否抢占当前正在运行的任务。
0153
0154 - pick_next_task(...)
0155
0156 这个函数选择接下来最适合运行的任务。
0157
0158 - set_curr_task(...)
0159
0160 这个函数在任务改变调度类或改变任务组时被调用。
0161
0162 - task_tick(...)
0163
0164 这个函数最常被时间滴答函数调用，它可能导致进程切换。这驱动了运行时抢占。
0165
0166
0167
0168
0169 7. CFS的组调度扩展
0170 ==================
0171
0172 通常，调度器操作粒度为任务，努力为每个任务提供公平的CPU时间。有时可能希望将任务编组，
0173 并为每个组提供公平的CPU时间。举例来说，可能首先希望为系统中的每个用户提供公平的CPU
0174 时间，接下来才是某个用户的每个任务。
0175
0176 CONFIG_CGROUP_SCHED 力求实现它。它将任务编组，并为这些组公平地分配CPU时间。
0177
0178 CONFIG_RT_GROUP_SCHED 允许将实时（也就是说，SCHED_FIFO和SCHED_RR）任务编组。
0179
0180 CONFIG_FAIR_GROUP_SCHED 允许将CFS（也就是说，SCHED_NORMAL和SCHED_BATCH）任务编组。
0181
0182 这些编译选项要求CONFIG_CGROUPS被定义，然后管理员能使用cgroup伪文件系统任意创建任务组。
0183 关于该文件系统的更多信息，参见Documentation/admin-guide/cgroup-v1/cgroups.rst
0184
0185 当CONFIG_FAIR_GROUP_SCHED被定义后，通过伪文件系统，每个组被创建一个“cpu.shares”文件。
0186 参见下面的例子来创建任务组，并通过“cgroup”伪文件系统修改它们的CPU份额::
0187
0188 # mount -t tmpfs cgroup_root /sys/fs/cgroup
0189 # mkdir /sys/fs/cgroup/cpu
0190 # mount -t cgroup -ocpu none /sys/fs/cgroup/cpu
0191 # cd /sys/fs/cgroup/cpu
0192
0193 # mkdir multimedia # 创建 "multimedia" 任务组
0194 # mkdir browser # 创建 "browser" 任务组
0195
0196 # #配置multimedia组，令其获得browser组两倍CPU带宽
0197
0198 # echo 2048 > multimedia/cpu.shares
0199 # echo 1024 > browser/cpu.shares
0200
0201 # firefox & # 启动firefox并把它移到 "browser" 组
0202 # echo <firefox_pid> > browser/tasks
0203
0204 # #启动gmplayer（或者你最喜欢的电影播放器）
0205 # echo <movie_player_pid> > multimedia/tasks
