diff options
| author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-07 18:49:45 +0000 |
|---|---|---|
| committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-07 18:49:45 +0000 |
| commit | 2c3c1048746a4622d8c89a29670120dc8fab93c4 (patch) | |
| tree | 848558de17fb3008cdf4d861b01ac7781903ce39 /Documentation/translations/zh_CN/scheduler | |
| parent | Initial commit. (diff) | |
| download | linux-2c3c1048746a4622d8c89a29670120dc8fab93c4.tar.xz linux-2c3c1048746a4622d8c89a29670120dc8fab93c4.zip | |
Adding upstream version 6.1.76.upstream/6.1.76
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'Documentation/translations/zh_CN/scheduler')
12 files changed, 2070 insertions, 0 deletions
diff --git a/Documentation/translations/zh_CN/scheduler/completion.rst b/Documentation/translations/zh_CN/scheduler/completion.rst new file mode 100644 index 000000000..bc8218514 --- /dev/null +++ b/Documentation/translations/zh_CN/scheduler/completion.rst @@ -0,0 +1,256 @@ +.. include:: ../disclaimer-zh_CN.rst + +:Original: Documentation/scheduler/completion.rst + +:翻译: + + 司延腾 Yanteng Si <siyanteng@loongson.cn> + +:校译: + + 唐艺舟 Tang Yizhou <tangyeechou@gmail.com> + +======================================= +完成 - "等待完成" 屏障应用程序接口(API) +======================================= + +简介: +----- + +如果你有一个或多个线程必须等待某些内核活动达到某个点或某个特定的状态，完成可以为这 +个问题提供一个无竞争的解决方案。从语义上讲，它们有点像pthread_barrier()，并且使 +用的案例类似 + +完成是一种代码同步机制，它比任何滥用锁/信号量和忙等待循环的行为都要好。当你想用yield() +或一些古怪的msleep(1)循环来允许其它代码继续运行时，你可能想用wait_for_completion*() +调用和completion()来代替。 + +使用“完成”的好处是，它们有一个良好定义、聚焦的目标，这不仅使得我们很容易理解代码的意图， +而且它们也会生成更高效的代码，因为所有线程都可以继续执行，直到真正需要结果的时刻。而且等 +待和信号都高效的使用了低层调度器的睡眠/唤醒设施。 + +完成是建立在Linux调度器的等待队列和唤醒基础设施之上的。等待队列中的线程所等待的 +事件被简化为 ``struct completion`` 中的一个简单标志，被恰如其名地称为‘done’。 + +由于完成与调度有关，代码可以在kernel/sched/completion.c中找到。 + + +用法: +----- + +使用完成需要三个主要部分: + + - 'struct completion' 同步对象的初始化 + - 通过调用wait_for_completion()的一个变体来实现等待部分。 + - 通过调用complete()或complete_all()实现发信端。 + +也有一些辅助函数用于检查完成的状态。请注意，虽然必须先做初始化，但等待和信号部分可以 +按任何时间顺序出现。也就是说，一个线程在另一个线程检查是否需要等待它之前，已经将一个 +完成标记为 "done"，这是完全正常的。 + +要使用完成API，你需要#include <linux/completion.h>并创建一个静态或动态的 +``struct completion`` 类型的变量，它只有两个字段:: + + struct completion { + unsigned int done; + wait_queue_head_t wait; + }; + +结构体提供了->wait等待队列来放置任务进行等待（如果有的话），以及->done完成标志来表明它 +是否完成。 + +完成的命名应当与正在被同步的事件名一致。一个好的例子是:: + + wait_for_completion(&early_console_added); + + complete(&early_console_added); + +好的、直观的命名（一如既往地）有助于代码的可读性。将一个完成命名为 ``complete`` +是没有帮助的，除非其目的是超级明显的... + + +初始化完成: +----------- + +动态分配的完成对象最好被嵌入到数据结构中，以确保在函数/驱动的生命周期内存活，以防 +止与异步complete()调用发生竞争。 + +在使用wait_for_completion()的_timeout()或_killable()/_interruptible()变体 +时应特别小心，因为必须保证在所有相关活动（complete()或reinit_completion()）发生 +之前不会发生内存解除分配，即使这些等待函数由于超时或信号触发而过早返回。 + +动态分配的完成对象的初始化是通过调用init_completion()来完成的:: + + init_completion(&dynamic_object->done); + +在这个调用中，我们初始化 waitqueue 并将 ->done 设置为 0，即“not completed”或 +“not done”。 + +重新初始化函数reinit_completion()，只是将->done字段重置为0（“not done”），而 +不触及等待队列。这个函数的调用者必须确保没有任何令人讨厌的wait_for_completion() +调用在并行进行。 + +在同一个完成对象上调用init_completion()两次很可能是一个bug，因为它将队列重新初始 +化为一个空队列，已排队的任务可能会“丢失”--在这种情况下使用reinit_completion()，但 +要注意其他竞争。 + +对于静态声明和初始化，可以使用宏。 + +对于文件范围内的静态（或全局）声明，你可以使用 DECLARE_COMPLETION():: + + static DECLARE_COMPLETION(setup_done); + DECLARE_COMPLETION(setup_done); + +注意，在这种情况下，完成在启动时（或模块加载时）被初始化为“not done”，不需要调用 +init_completion()。 + +当完成被声明为一个函数中的局部变量时，那么应该总是明确地使用 +DECLARE_COMPLETION_ONSTACK()来初始化，这不仅仅是为了让lockdep正确运行，也是明确表 +名它有限的使用范围是有意为之并被仔细考虑的:: + + DECLARE_COMPLETION_ONSTACK(setup_done) + +请注意，当使用完成对象作为局部变量时，你必须敏锐地意识到函数堆栈的短暂生命期：在所有 +活动（如等待的线程）停止并且完成对象完全未被使用之前，函数不得返回到调用上下文。 + +再次强调这一点：特别是在使用一些具有更复杂结果的等待API变体时，比如超时或信号 +（_timeout(), _killable()和_interruptible()）变体，等待可能会提前完成，而对象可 +能仍在被其他线程使用 - 从wait_on_completion*()调用者函数的返回会取消分配函数栈，如 +果complete()在其它某线程中完成调用，会引起微小的数据损坏。简单的测试可能不会触发这 +些类型的竞争。 + +如果不确定的话，使用动态分配的完成对象， 最好是嵌入到其它一些生命周期长的对象中，长到 +超过使用完成对象的任何辅助线程的生命周期，或者有一个锁或其他同步机制来确保complete() +不会在一个被释放的对象中调用。 + +在堆栈上单纯地调用DECLARE_COMPLETION()会触发一个lockdep警告。 + +等待完成: +--------- + +对于一个线程来说，要等待一些并发活动的完成，它要在初始化的完成结构体上调用 +wait_for_completion():: + + void wait_for_completion(struct completion *done) + +一个典型的使用场景是:: + + CPU#1 CPU#2 + + struct completion setup_done; + + init_completion(&setup_done); + initialize_work(...,&setup_done,...); + + /* run non-dependent code */ /* do setup */ + + wait_for_completion(&setup_done); complete(setup_done); + +这并不意味着调用wait_for_completion()和complete()有任何特定的时间顺序--如果调 +用complete()发生在调用wait_for_completion()之前，那么等待方将立即继续执行，因为 +所有的依赖都得到了满足；如果没有，它将阻塞，直到complete()发出完成的信号。 + +注意，wait_for_completion()是在调用spin_lock_irq()/spin_unlock_irq()，所以 +只有当你知道中断被启用时才能安全地调用它。从IRQs-off的原子上下文中调用它将导致难以检 +测的错误的中断启用。 + +默认行为是不带超时的等待，并将任务标记为“UNINTERRUPTIBLE”状态。wait_for_completion() +及其变体只有在进程上下文中才是安全的（因为它们可以休眠），但在原子上下文、中断上下文、IRQ +被禁用或抢占被禁用的情况下是不安全的--关于在原子/中断上下文中处理完成的问题，还请看下面的 +try_wait_for_completion()。 + +由于wait_for_completion()的所有变体都可能（很明显）阻塞很长时间，这取决于它们所等 +待的活动的性质，所以在大多数情况下，你可能不想在持有mutex锁的情况下调用它。 + + +wait_for_completion*()可用的变体: +--------------------------------- + +下面的变体都会返回状态，在大多数(/所有)情况下都应该检查这个状态--在故意不检查状态的情 +况下，你可能要做一个说明(例如，见arch/arm/kernel/smp.c:__cpu_up())。 + +一个常见的问题是不准确的返回类型赋值，所以要注意将返回值赋值给适当类型的变量。 + +检查返回值的具体含义也可能被发现是相当不准确的，例如，像这样的构造:: + + if (!wait_for_completion_interruptible_timeout(...)) + +...会在成功完成和中断的情况下执行相同的代码路径--这可能不是你想要的结果:: + + int wait_for_completion_interruptible(struct completion *done) + +这个函数在任务等待时标记为TASK_INTERRUPTIBLE。如果在等待期间收到信号，它将返回 +-ERESTARTSYS；否则为0:: + + unsigned long wait_for_completion_timeout(struct completion *done, unsigned long timeout) + +该任务被标记为TASK_UNINTERRUPTIBLE，并将最多超时等待“timeout”个jiffies。如果超时发生，则 +返回0，否则返回剩余的时间（但至少是1）。 + +超时最好用msecs_to_jiffies()或usecs_to_jiffies()计算，以使代码在很大程度上不受 +HZ的影响。 + +如果返回的超时值被故意忽略，那么注释应该解释原因 +（例如，见drivers/mfd/wm8350-core.c wm8350_read_auxadc():: + + long wait_for_completion_interruptible_timeout(struct completion *done, unsigned long timeout) + +这个函数传递一个以jiffies为单位的超时，并将任务标记为TASK_INTERRUPTIBLE。如果收到 +信号，则返回-ERESTARTSYS；否则，如果完成超时，则返回0；如果完成了，则返回剩余的时间 +（jiffies）。 + +更多的变体包括_killable，它使用TASK_KILLABLE作为指定的任务状态，如果它被中断，将返 +回-ERESTARTSYS，如果完成了，则返回0。它也有一个_timeout变体:: + + long wait_for_completion_killable(struct completion *done) + long wait_for_completion_killable_timeout(struct completion *done, unsigned long timeout) + +wait_for_completion_io()的_io变体的行为与非_io变体相同，只是将等待时间计为“IO等待”， +这对任务在调度/IO统计中的计算方式有影响:: + + void wait_for_completion_io(struct completion *done) + unsigned long wait_for_completion_io_timeout(struct completion *done, unsigned long timeout) + + +对完成发信号: +------------- + +一个线程想要发出信号通知继续的条件已经达到，就会调用complete()，向其中一个等待者发出信 +号表明它可以继续:: + + void complete(struct completion *done) + +... or calls complete_all() to signal all current and future waiters:: + + void complete_all(struct completion *done) + +即使在线程开始等待之前就发出了完成的信号，信号传递也会继续进行。这是通过等待者 +“consuming”（递减）“struct completion” 的完成字段来实现的。等待的线程唤醒的顺序 +与它们被排队的顺序相同（FIFO顺序）。 + +如果多次调用complete()，那么这将允许该数量的等待者继续进行--每次调用complete()将 +简单地增加已完成的字段。但多次调用complete_all()是一个错误。complete()和 +complete_all()都可以在IRQ/atomic上下文中安全调用。 + +在任何时候，只能有一个线程在一个特定的 “struct completion”上调用 complete() 或 +complete_all() - 通过等待队列自旋锁进行序列化。任何对 complete() 或 +complete_all() 的并发调用都可能是一个设计错误。 + +从IRQ上下文中发出完成信号 是可行的，因为它将正确地用 +spin_lock_irqsave()/spin_unlock_irqrestore()执行锁操作 + + +try_wait_for_completion()/completion_done(): +-------------------------------------------- + +try_wait_for_completion()函数不会将线程放在等待队列中，而是在需要排队（阻塞）线 +程时返回false，否则会消耗一个已发布的完成并返回true:: + + bool try_wait_for_completion(struct completion *done) + +最后，为了在不以任何方式改变完成的情况下检查完成的状态，可以调用completion_done()， +如果没有发布的完成尚未被等待者消耗，则返回false（意味着存在等待者），否则返回true:: + + bool completion_done(struct completion *done) + +try_wait_for_completion()和completion_done()都可以在IRQ或原子上下文中安全调用。 diff --git a/Documentation/translations/zh_CN/scheduler/index.rst b/Documentation/translations/zh_CN/scheduler/index.rst new file mode 100644 index 000000000..a8eaa7325 --- /dev/null +++ b/Documentation/translations/zh_CN/scheduler/index.rst @@ -0,0 +1,45 @@ +.. include:: ../disclaimer-zh_CN.rst + +:Original: Documentation/scheduler/index.rst + +:翻译: + + 司延腾 Yanteng Si <siyanteng@loongson.cn> + 唐艺舟 Tang Yizhou <tangyeechou@gmail.com> + +:校译: + + + +=============== +Linux调度器 +=============== + +.. toctree:: + :maxdepth: 1 + + completion + sched-arch + sched-bwc + sched-design-CFS + sched-domains + sched-capacity + sched-energy + schedutil + sched-nice-design + sched-stats + sched-debug + +TODOList: + + sched-deadline + sched-rt-group + + text_files + +.. only:: subproject and html + + Indices + ======= + + * :ref:`genindex` diff --git a/Documentation/translations/zh_CN/scheduler/sched-arch.rst b/Documentation/translations/zh_CN/scheduler/sched-arch.rst new file mode 100644 index 000000000..754a15c6b --- /dev/null +++ b/Documentation/translations/zh_CN/scheduler/sched-arch.rst @@ -0,0 +1,76 @@ +.. include:: ../disclaimer-zh_CN.rst + +:Original: Documentation/scheduler/sched-arch.rst + +:翻译: + + 司延腾 Yanteng Si <siyanteng@loongson.cn> + +:校译: + + + +=============================== +架构特定代码的CPU调度器实现提示 +=============================== + + Nick Piggin, 2005 + +上下文切换 +========== +1. 运行队列锁 +默认情况下，switch_to arch函数在调用时锁定了运行队列。这通常不是一个问题，除非 +switch_to可能需要获取运行队列锁。这通常是由于上下文切换中的唤醒操作造成的。见 +arch/ia64/include/asm/switch_to.h的例子。 + +为了要求调度器在运行队列解锁的情况下调用switch_to，你必须在头文件 +中`#define __ARCH_WANT_UNLOCKED_CTXSW`(通常是定义switch_to的那个文件）。 + +在CONFIG_SMP的情况下，解锁的上下文切换对核心调度器的实现只带来了非常小的性能损 +失。 + +CPU空转 +======= +你的cpu_idle程序需要遵守以下规则： + +1. 现在抢占应该在空闲的例程上禁用。应该只在调用schedule()时启用，然后再禁用。 + +2. need_resched/TIF_NEED_RESCHED 只会被设置，并且在运行任务调用 schedule() + 之前永远不会被清除。空闲线程只需要查询need_resched，并且永远不会设置或清除它。 + +3. 当cpu_idle发现（need_resched() == 'true'），它应该调用schedule()。否则 + 它不应该调用schedule()。 + +4. 在检查need_resched时，唯一需要禁用中断的情况是，我们要让处理器休眠到下一个中 + 断（这并不对need_resched提供任何保护，它可以防止丢失一个中断）: + + 4a. 这种睡眠类型的常见问题似乎是:: + + local_irq_disable(); + if (!need_resched()) { + local_irq_enable(); + *** resched interrupt arrives here *** + __asm__("sleep until next interrupt"); + } + +5. 当need_resched变为高电平时，TIF_POLLING_NRFLAG可以由不需要中断来唤醒它们 + 的空闲程序设置。换句话说，它们必须定期轮询need_resched，尽管做一些后台工作或 + 进入低CPU优先级可能是合理的。 + + - 5a. 如果TIF_POLLING_NRFLAG被设置，而我们确实决定进入一个中断睡眠，那 + 么需要清除它，然后发出一个内存屏障（接着测试need_resched，禁用中断，如3中解释）。 + +arch/x86/kernel/process.c有轮询和睡眠空闲函数的例子。 + + +可能出现的arch/问题 +=================== + +我发现的可能的arch问题（并试图解决或没有解决）。: + +ia64 - safe_halt的调用与中断相比，是否很荒谬？ (它睡眠了吗) (参考 #4a) + +sh64 - 睡眠与中断相比，是否很荒谬？ (参考 #4a) + +sparc - 在这一点上，IRQ是开着的（？），把local_irq_save改为_disable。 + - 待办事项: 需要第二个CPU来禁用抢占 (参考 #1) diff --git a/Documentation/translations/zh_CN/scheduler/sched-bwc.rst b/Documentation/translations/zh_CN/scheduler/sched-bwc.rst new file mode 100644 index 000000000..90e931f4c --- /dev/null +++ b/Documentation/translations/zh_CN/scheduler/sched-bwc.rst @@ -0,0 +1,204 @@ +.. include:: ../disclaimer-zh_CN.rst + +:Original: Documentation/scheduler/sched-bwc.rst + +:翻译: + + 司延腾 Yanteng Si <siyanteng@loongson.cn> + +:校译: + + + +============ +CFS 带宽控制 +============ + +.. note:: + 本文只讨论了SCHED_NORMAL的CPU带宽控制。 + SCHED_RT的情况在Documentation/scheduler/sched-rt-group.rst中有涉及。 + +CFS带宽控制是一个CONFIG_FAIR_GROUP_SCHED扩展，它允许指定一个组或层次的最大CPU带宽。 + +一个组允许的带宽是用配额和周期指定的。在每个给定的”周期“（微秒）内，一个任务组被分配多 +达“配额”微秒的CPU时间。当cgroup中的线程可运行时，该配额以时间片段的方式被分配到每个cpu +运行队列中。一旦所有的配额被分配，任何额外的配额请求将导致这些线程被限流。被限流的线程将不 +能再次运行，直到下一个时期的配额得到补充。 + +一个组的未分配配额是全局跟踪的，在每个周期边界被刷新为cfs_quota单元。当线程消耗这个带宽时， +它以需求为基础被转移到cpu-local“筒仓”，在每次更新中转移的数量是可调整的，被描述为“片“（时 +间片）。 + +突发特性 +-------- +现在这个功能借来的时间是用于防范我们对未来的低估，代价是对其他系统用户的干扰增加。所有这些都 +有很好的限制。 + +传统的（UP-EDF）带宽控制是这样的: + + (U = \Sum u_i) <= 1 + +这既保证了每个最后期限的实现，也保证了系统的稳定。毕竟，如果U>1，那么每一秒钟的壁钟时间，我 +们就必须运行超过一秒钟的程序时间，显然会错过我们的最后期限，但下一个最后期限会更远，永远没有 +时间赶上，无边无界的失败。 + +突发特性观察到工作负载并不总是执行全部配额；这使得人们可以将u_i描述为一个统计分布。 + +例如，让u_i = {x,e}_i，其中x是p(95)和x+e p(100)（传统的WCET）。这实际上允许u更小，提 +高了效率（我们可以在系统中打包更多的任务），但代价是当所有的概率都一致时，会错过最后期限。然 +而，它确实保持了稳定性，因为只要我们的x高于平均水平，每一次超限都必须与低估相匹配。 + +也就是说，假设我们有两个任务，都指定了一个p(95)值，那么我们有一个p(95)*p(95)=90.25%的机 +会，两个任务都在他们的配额内，一切都很好。同时，我们有一个p(5)p(5)=0.25%的机会，两个任务同 +时超过他们的配额（保证最后期限失败）。在这两者之间有一个阈值，其中一个超过了，而另一个没有不足， +无法补偿；这取决于具体的CDFs。 + +同时，我们可以说，最坏的情况下的截止日期失败，将是Sum e_i；也就是说，有一个有界的迟延（在假 +设x+e确实是WCET的情况下）。 + +使用突发时的干扰是由错过最后期限的可能性和平均WCET来评价的。测试结果表明，当有许多cgroup或 +CPU未被充分利用时，干扰是有限的。更多的细节显示在： +https://lore.kernel.org/lkml/5371BD36-55AE-4F71-B9D7-B86DC32E3D2B@linux.alibaba.com/ + +管理 +---- +配额、周期和突发是在cpu子系统内通过cgroupfs管理的。 + +.. note:: + 本节描述的cgroupfs文件只适用于cgroup v1.对于cgroup v2，请参阅Control Group v2。 + :ref:`Documentation/admin-guide/cgroup-v2.rst <cgroup-v2-cpu>`. + +- cpu.cfs_quota_us：在一个时期内补充的运行时间（微秒）。 +- cpu.cfs_period_us：一个周期的长度（微秒）。 +- cpu.stat: 输出节流统计数据[下面进一步解释] +- cpu.cfs_burst_us：最大累积运行时间（微秒）。 + +默认值是:: + + cpu.cfs_period_us=100ms + cpu.cfs_quota_us=-1 + cpu.cfs_burst_us=0 + +cpu.cfs_quota_us的值为-1表示该组没有任何带宽限制，这样的组被描述为无限制的带宽组。这代表 +了CFS的传统工作保护行为。 + +写入不小于cpu.cfs_burst_us的任何（有效的）正值将配发指定的带宽限制。该配额或周期允许的最 +小配额是1ms。周期长度也有一个1s的上限。当带宽限制以分层方式使用时，存在额外的限制，这些在下 +面有更详细的解释。 + +向cpu.cfs_quota_us写入任何负值都会移除带宽限制，并使组再次回到无限制的状态。 + +cpu.cfs_burst_us的值为0表示该组不能积累任何未使用的带宽。它使得CFS的传统带宽控制行为没有 +改变。将不大于 cpu.cfs_quota_us 的任何(有效的)正值写入 cpu.cfs_burst_us 将配发未使用 +带宽累积的上限。 + +如果一个组处于受限状态，对该组带宽规格的任何更新都将导致其成为无限流状态。 + +系统范围设置 +------------ +为了提高效率，运行时间在全局池和CPU本地“筒仓”之间以批处理方式转移。这大大减少了大型系统的全 +局核算压力。每次需要进行这种更新时，传输的数量被描述为 "片"。 + +这是可以通过procfs调整的:: + + /proc/sys/kernel/sched_cfs_bandwidth_slice_us (default=5ms) + +较大的时间片段值将减少传输开销，而较小的值则允许更精细的消费。 + +统计 +---- +一个组的带宽统计数据通过cpu.stat的5个字段导出。 + +cpu.stat: + +- nr_periods：已经过去的执行间隔的数量。 +- nr_throttled: 该组已被节流/限制的次数。 +- throttled_time: 该组的实体被限流的总时间长度（纳秒）。 +- nr_bursts：突发发生的周期数。 +- burst_time: 任何CPU在各个时期使用超过配额的累计壁钟时间（纳秒）。 + +这个接口是只读的。 + +分层考虑 +-------- +该接口强制要求单个实体的带宽总是可以达到的，即：max(c_i) <= C。然而，在总体情况下，是明确 +允许过度订阅的，以便在一个层次结构中实现工作保护语义: + + 例如，Sum (c_i)可能超过C + +[ 其中C是父方的带宽，c_i是其子方的带宽。 ] + +.. note:: + 译文中的父亲/孩子指的是cgroup parent, cgroup children。 + +有两种方式可以使一个组变得限流: + + a. 它在一段时期内完全消耗自己的配额 + b. 父方的配额在其期间内全部用完 + +在上述b)情况下，即使孩子可能有剩余的运行时间，它也不会被允许，直到父亲的运行时间被刷新。 + +CFS带宽配额的注意事项 +--------------------- +一旦一个片断被分配给一个cpu，它就不会过期。然而，如果该cpu上的所有线程都无法运行，那么除了 +1ms以外的所有时间片都可以返回到全局池中。这是在编译时由min_cfs_rq_runtime变量配置的。这 +是一个性能调整，有助于防止对全局锁的额外争夺。 + +cpu-local分片不会过期的事实导致了一些有趣的罕见案例，应该被理解。 + +对于cgroup cpu限制的应用程序来说，这是一个相对有意义的问题，因为他们自然会消耗他们的全部配 +额，以及每个cpu-本地片在每个时期的全部。因此，预计nr_periods大致等于nr_throttled，并且 +cpuacct.用量的增加大致等于cfs_quota_us在每个周期的增加。 + +对于高线程、非cpu绑定的应用程序，这种非过期的细微差别允许应用程序短暂地突破他们的配额限制， +即任务组正在运行的每个cpu上未使用的片断量（通常每个cpu最多1ms或由min_cfs_rq_runtime定 +义）。这种轻微的突发只适用于配额已经分配给cpu，然后没有完全使用或在以前的时期返回。这个突发 +量不会在核心之间转移。因此，这种机制仍然严格限制任务组的配额平均使用量，尽管是在比单一时期更 +长的时间窗口。这也限制了突发能力，每个cpu不超过1ms。这为在高核数机器上有小配额限制的高线程 +应用提供了更好的更可预测的用户体验。它还消除了在使用低于配额的cpu时对这些应用进行节流的倾向。 +另一种说法是，通过允许一个片断的未使用部分在不同时期保持有效，我们减少了在不需要整个片断的cpu +时间的cpu-local 筒仓上浪费配额的可能性。 + +绑定cpu和非绑定cpu的交互式应用之间的互动也应该被考虑，特别是当单核使用率达到100%时。如果你 +给了这些应用程序一半的cpu-core，并且它们都被安排在同一个CPU上，理论上非cpu绑定的应用程序有 +可能在某些时期使用多达1ms的额外配额，从而阻止cpu绑定的应用程序完全使用其配额，这也是同样的数 +量。在这些情况下，将由CFS算法（见CFS调度器）来决定选择哪个应用程序来运行，因为它们都是可运行 +的，并且有剩余的配额。这个运行时间的差异将在接下来的交互式应用程序空闲期间得到弥补。 + +例子 +---- +1. 限制一个组的运行时间为1个CPU的价值:: + + 如果周期是250ms，配额也是250ms，那么该组将每250ms获得价值1个CPU的运行时间。 + + # echo 250000 > cpu.cfs_quota_us /* quota = 250ms */ + # echo 250000 > cpu.cfs_period_us /* period = 250ms */ + +2. 在多CPU机器上，将一个组的运行时间限制为2个CPU的价值 + + 在500ms周期和1000ms配额的情况下，该组每500ms可以获得2个CPU的运行时间:: + + # echo 1000000 > cpu.cfs_quota_us /* quota = 1000ms */ + # echo 500000 > cpu.cfs_period_us /* period = 500ms */ + + 这里较大的周期允许增加突发能力。 + +3. 将一个组限制在1个CPU的20%。 + + 在50ms周期内，10ms配额将相当于1个CPU的20%。:: + + # echo 10000 > cpu.cfs_quota_us /* quota = 10ms */ + # echo 50000 > cpu.cfs_period_us /* period = 50ms */ + + 通过在这里使用一个小的周期，我们以牺牲突发容量为代价来确保稳定的延迟响应。 + +4. 将一个组限制在1个CPU的40%，并允许累积到1个CPU的20%，如果已经累积了的话。 + + 在50ms周期内，20ms配额将相当于1个CPU的40%。而10毫秒的突发将相当于1个 + CPU的20%:: + + # echo 20000 > cpu.cfs_quota_us /* quota = 20ms */ + # echo 50000 > cpu.cfs_period_us /* period = 50ms */ + # echo 10000 > cpu.cfs_burst_us /* burst = 10ms */ + + 较大的缓冲区设置（不大于配额）允许更大的突发容量。 diff --git a/Documentation/translations/zh_CN/scheduler/sched-capacity.rst b/Documentation/translations/zh_CN/scheduler/sched-capacity.rst new file mode 100644 index 000000000..3a52053c2 --- /dev/null +++ b/Documentation/translations/zh_CN/scheduler/sched-capacity.rst @@ -0,0 +1,390 @@ +.. SPDX-License-Identifier: GPL-2.0 +.. include:: ../disclaimer-zh_CN.rst + +:Original: Documentation/scheduler/sched-capacity.rst + +:翻译: + + 唐艺舟 Tang Yizhou <tangyeechou@gmail.com> + +:校译: + + 时奎亮 Alex Shi <alexs@kernel.org> + +============= +算力感知调度 +============= + +1. CPU算力 +========== + +1.1 简介 +-------- + +一般来说，同构的SMP平台由完全相同的CPU构成。异构的平台则由性能特征不同的CPU构成，在这样的 +平台中，CPU不能被认为是相同的。 + +我们引入CPU算力（capacity）的概念来测量每个CPU能达到的性能，它的值相对系统中性能最强的CPU +做过归一化处理。异构系统也被称为非对称CPU算力系统，因为它们由不同算力的CPU组成。 + +最大可达性能（换言之，最大CPU算力）的差异有两个主要来源: + +- 不是所有CPU的微架构都相同。 +- 在动态电压频率升降（Dynamic Voltage and Frequency Scaling，DVFS）框架中，不是所有的CPU都 + 能达到一样高的操作性能值（Operating Performance Points，OPP。译注，也就是“频率-电压”对）。 + +Arm大小核（big.LITTLE）系统是同时具有两种差异的一个例子。相较小核，大核面向性能（拥有更多的 +流水线层级，更大的缓存，更智能的分支预测器等），通常可以达到更高的操作性能值。 + +CPU性能通常由每秒百万指令（Millions of Instructions Per Second，MIPS）表示，也可表示为 +per Hz能执行的指令数，故:: + + capacity(cpu) = work_per_hz(cpu) * max_freq(cpu) + +1.2 调度器术语 +-------------- + +调度器使用了两种不同的算力值。CPU的 ``capacity_orig`` 是它的最大可达算力，即最大可达性能等级。 +CPU的 ``capacity`` 是 ``capacity_orig`` 扣除了一些性能损失（比如处理中断的耗时）的值。 + +注意CPU的 ``capacity`` 仅仅被设计用于CFS调度类，而 ``capacity_orig`` 是不感知调度类的。为 +简洁起见，本文档的剩余部分将不加区分的使用术语 ``capacity`` 和 ``capacity_orig`` 。 + +1.3 平台示例 +------------ + +1.3.1 操作性能值相同 +~~~~~~~~~~~~~~~~~~~~ + +考虑一个假想的双核非对称CPU算力系统，其中 + +- work_per_hz(CPU0) = W +- work_per_hz(CPU1) = W/2 +- 所有CPU以相同的固定频率运行 + +根据上文对算力的定义: + +- capacity(CPU0) = C +- capacity(CPU1) = C/2 + +若这是Arm大小核系统，那么CPU0是大核，而CPU1是小核。 + +考虑一种周期性产生固定工作量的工作负载，你将会得到类似下图的执行轨迹:: + + CPU0 work ^ + | ____ ____ ____ + | | | | | | | + +----+----+----+----+----+----+----+----+----+----+-> time + + CPU1 work ^ + | _________ _________ ____ + | | | | | | + +----+----+----+----+----+----+----+----+----+----+-> time + +CPU0在系统中具有最高算力（C），它使用T个单位时间完成固定工作量W。另一方面，CPU1只有CPU0一半 +算力，因此在T个单位时间内仅完成工作量W/2。 + +1.3.2 最大操作性能值不同 +~~~~~~~~~~~~~~~~~~~~~~~~ + +具有不同算力值的CPU，通常来说最大操作性能值也不同。考虑上一小节提到的CPU（也就是说， +work_per_hz()相同）: + +- max_freq(CPU0) = F +- max_freq(CPU1) = 2/3 * F + +这将推出： + +- capacity(CPU0) = C +- capacity(CPU1) = C/3 + +执行1.3.1节描述的工作负载，每个CPU按最大频率运行，结果为:: + + CPU0 work ^ + | ____ ____ ____ + | | | | | | | + +----+----+----+----+----+----+----+----+----+----+-> time + + workload on CPU1 + CPU1 work ^ + | ______________ ______________ ____ + | | | | | | + +----+----+----+----+----+----+----+----+----+----+-> time + +1.4 关于计算方式的注意事项 +-------------------------- + +需要注意的是，使用单一值来表示CPU性能的差异是有些争议的。两个不同的微架构的相对性能差异应该 +描述为：X%整数运算差异，Y%浮点数运算差异，Z%分支跳转差异，等等。尽管如此，使用简单计算方式 +的结果目前还是令人满意的。 + +2. 任务使用率 +============= + +2.1 简介 +-------- + +算力感知调度要求描述任务需求，描述方式要和CPU算力相关。每个调度类可以用不同的方式描述它。 +任务使用率是CFS独有的描述方式，不过在这里介绍它有助于引入更多一般性的概念。 + +任务使用率是一种用百分比来描述任务吞吐率需求的方式。一个简单的近似是任务的占空比，也就是说:: + + task_util(p) = duty_cycle(p) + +在频率固定的SMP系统中，100%的利用率意味着任务是忙等待循环。反之，10%的利用率暗示这是一个 +小周期任务，它在睡眠上花费的时间比执行更多。 + +2.2 频率不变性 +-------------- + +一个需要考虑的议题是，工作负载的占空比受CPU正在运行的操作性能值直接影响。考虑以给定的频率F +执行周期性工作负载:: + + CPU work ^ + | ____ ____ ____ + | | | | | | | + +----+----+----+----+----+----+----+----+----+----+-> time + +可以算出 duty_cycle(p) == 25%。 + +现在，考虑以给定频率F/2执行 *同一个* 工作负载:: + + CPU work ^ + | _________ _________ ____ + | | | | | | + +----+----+----+----+----+----+----+----+----+----+-> time + +可以算出 duty_cycle(p) == 50%，尽管两次执行中，任务的行为完全一致（也就是说，执行的工作量 +相同）。 + +任务利用率信号可按下面公式处理成频率不变的（译注：这里的术语用到了信号与系统的概念）:: + + task_util_freq_inv(p) = duty_cycle(p) * (curr_frequency(cpu) / max_frequency(cpu)) + +对上面两个例子运用该公式，可以算出频率不变的任务利用率均为25%。 + +2.3 CPU不变性 +------------- + +CPU算力与任务利用率具有类型的效应，在算力不同的CPU上执行完全相同的工作负载，将算出不同的 +占空比。 + +考虑1.3.2节提到的系统，也就是说:: + +- capacity(CPU0) = C +- capacity(CPU1) = C/3 + +每个CPU按最大频率执行指定周期性工作负载，结果为:: + + CPU0 work ^ + | ____ ____ ____ + | | | | | | | + +----+----+----+----+----+----+----+----+----+----+-> time + + CPU1 work ^ + | ______________ ______________ ____ + | | | | | | + +----+----+----+----+----+----+----+----+----+----+-> time + +也就是说， + +- duty_cycle(p) == 25%，如果任务p在CPU0上按最大频率运行。 +- duty_cycle(p) == 75%，如果任务p在CPU1上按最大频率运行。 + +任务利用率信号可按下面公式处理成CPU算力不变的:: + + task_util_cpu_inv(p) = duty_cycle(p) * (capacity(cpu) / max_capacity) + +其中 ``max_capacity`` 是系统中最高的CPU算力。对上面的例子运用该公式，可以算出CPU算力不变 +的任务利用率均为25%。 + +2.4 任务利用率不变量 +-------------------- + +频率和CPU算力不变性都需要被应用到任务利用率的计算中，以便求出真正的不变信号。 +任务利用率的伪计算公式是同时具备CPU和频率不变性的，也就是说，对于指定任务p:: + + curr_frequency(cpu) capacity(cpu) + task_util_inv(p) = duty_cycle(p) * ------------------- * ------------- + max_frequency(cpu) max_capacity + +也就是说，任务利用率不变量假定任务在系统中最高算力CPU上以最高频率运行，以此描述任务的行为。 + +在接下来的章节中提到的任何任务利用率，均是不变量的形式。 + +2.5 利用率估算 +-------------- + +由于预测未来的水晶球不存在，当任务第一次变成可运行时，任务的行为和任务利用率均不能被准确预测。 +CFS调度类基于实体负载跟踪机制（Per-Entity Load Tracking, PELT）维护了少量CPU和任务信号， +其中之一可以算出平均利用率（与瞬时相反）。 + +这意味着，尽管运用“真实的”任务利用率（凭借水晶球）写出算力感知调度的准则，但是它的实现将只能 +用任务利用率的估算值。 + +3. 算力感知调度的需求 +===================== + +3.1 CPU算力 +----------- + +当前，Linux无法凭自身算出CPU算力，因此必须要有把这个信息传递给Linux的方式。每个架构必须为此 +定义arch_scale_cpu_capacity()函数。 + +arm和arm64架构直接把这个信息映射到arch_topology驱动的CPU scaling数据中（译注：参考 +arch_topology.h的percpu变量cpu_scale），它是从capacity-dmips-mhz CPU binding中衍生计算 +出来的。参见Documentation/devicetree/bindings/arm/cpu-capacity.txt。 + +3.2 频率不变性 +-------------- + +如2.2节所述，算力感知调度需要频率不变的任务利用率。每个架构必须为此定义 +arch_scale_freq_capacity(cpu)函数。 + +实现该函数要求计算出每个CPU当前以什么频率在运行。实现它的一种方式是利用硬件计数器（x86的 +APERF/MPERF，arm64的AMU），它能按CPU当前频率动态可扩展地升降递增计数器的速率。另一种方式是 +在cpufreq频率变化时直接使用钩子函数，内核此时感知到将要被切换的频率（也被arm/arm64实现了）。 + +4. 调度器拓扑结构 +================= + +在构建调度域时，调度器将会发现系统是否表现为非对称CPU算力。如果是，那么： + +- sched_asym_cpucapacity静态键（static key）将使能。 +- SD_ASYM_CPUCAPACITY_FULL标志位将在尽量最低调度域层级中被设置，同时要满足条件：调度域恰好 + 完整包含某个CPU算力值的全部CPU。 +- SD_ASYM_CPUCAPACITY标志将在所有包含非对称CPU的调度域中被设置。 + +sched_asym_cpucapacity静态键的设计意图是，保护为非对称CPU算力系统所准备的代码。不过要注意的 +是，这个键是系统范围可见的。想象下面使用了cpuset的步骤:: + + capacity C/2 C + ________ ________ + / \ / \ + CPUs 0 1 2 3 4 5 6 7 + \__/ \______________/ + cpusets cs0 cs1 + +可以通过下面的方式创建： + +.. code-block:: sh + + mkdir /sys/fs/cgroup/cpuset/cs0 + echo 0-1 > /sys/fs/cgroup/cpuset/cs0/cpuset.cpus + echo 0 > /sys/fs/cgroup/cpuset/cs0/cpuset.mems + + mkdir /sys/fs/cgroup/cpuset/cs1 + echo 2-7 > /sys/fs/cgroup/cpuset/cs1/cpuset.cpus + echo 0 > /sys/fs/cgroup/cpuset/cs1/cpuset.mems + + echo 0 > /sys/fs/cgroup/cpuset/cpuset.sched_load_balance + +由于“这是”非对称CPU算力系统，sched_asym_cpucapacity静态键将使能。然而，CPU 0--1对应的 +调度域层级，算力值仅有一个，该层级中SD_ASYM_CPUCAPACITY未被设置，它描述的是一个SMP区域，也 +应该被以此处理。 + +因此，“典型的”保护非对称CPU算力代码路径的代码模式是： + +- 检查sched_asym_cpucapacity静态键 +- 如果它被使能，接着检查调度域层级中SD_ASYM_CPUCAPACITY标志位是否出现 + +5. 算力感知调度的实现 +===================== + +5.1 CFS +------- + +5.1.1 算力适应性（fitness） +~~~~~~~~~~~~~~~~~~~~~~~~~~~ + +CFS最主要的算力调度准则是:: + + task_util(p) < capacity(task_cpu(p)) + +它通常被称为算力适应性准则。也就是说，CFS必须保证任务“适合”在某个CPU上运行。如果准则被违反， +任务将要更长地消耗该CPU，任务是CPU受限的（CPU-bound）。 + +此外，uclamp允许用户空间指定任务的最小和最大利用率，要么以sched_setattr()的方式，要么以 +cgroup接口的方式（参阅Documentation/admin-guide/cgroup-v2.rst）。如其名字所暗示，uclamp +可以被用在前一条准则中限制task_util()。 + +5.1.2 被唤醒任务的CPU选择 +~~~~~~~~~~~~~~~~~~~~~~~~~ + +CFS任务唤醒的CPU选择，遵循上面描述的算力适应性准则。在此之上，uclamp被用来限制任务利用率， +这令用户空间对CFS任务的CPU选择有更多的控制。也就是说，CFS被唤醒任务的CPU选择，搜索满足以下 +条件的CPU:: + + clamp(task_util(p), task_uclamp_min(p), task_uclamp_max(p)) < capacity(cpu) + +通过使用uclamp，举例来说，用户空间可以允许忙等待循环（100%使用率）在任意CPU上运行，只要给 +它设置低的uclamp.max值。相反，uclamp能强制一个小的周期性任务（比如，10%利用率）在最高性能 +的CPU上运行，只要给它设置高的uclamp.min值。 + +.. note:: + + CFS的被唤醒的任务的CPU选择，可被能耗感知调度（Energy Aware Scheduling，EAS）覆盖，在 + Documentation/scheduler/sched-energy.rst中描述。 + +5.1.3 负载均衡 +~~~~~~~~~~~~~~ + +被唤醒任务的CPU选择的一个病理性的例子是，任务几乎不睡眠，那么也几乎不发生唤醒。考虑:: + + w == wakeup event + + capacity(CPU0) = C + capacity(CPU1) = C / 3 + + workload on CPU0 + CPU work ^ + | _________ _________ ____ + | | | | | | + +----+----+----+----+----+----+----+----+----+----+-> time + w w w + + workload on CPU1 + CPU work ^ + | ____________________________________________ + | | + +----+----+----+----+----+----+----+----+----+----+-> + w + +该工作负载应该在CPU0上运行，不过如果任务满足以下条件之一： + +- 一开始发生不合适的调度（不准确的初始利用率估计） +- 一开始调度正确，但突然需要更多的处理器功率 + +则任务可能变为CPU受限的，也就是说 ``task_util(p) > capacity(task_cpu(p))`` ；CPU算力 +调度准则被违反，将不会有任何唤醒事件来修复这个错误的CPU选择。 + +这种场景下的任务被称为“不合适的”（misfit）任务，处理这个场景的机制同样也以此命名。Misfit +任务迁移借助CFS负载均衡器，更明确的说，是主动负载均衡的部分（用来迁移正在运行的任务）。 +当发生负载均衡时，如果一个misfit任务可以被迁移到一个相较当前运行的CPU具有更高算力的CPU上， +那么misfit任务的主动负载均衡将被触发。 + +5.2 实时调度 +------------ + +5.2.1 被唤醒任务的CPU选择 +~~~~~~~~~~~~~~~~~~~~~~~~~ + +实时任务唤醒时的CPU选择，搜索满足以下条件的CPU:: + + task_uclamp_min(p) <= capacity(task_cpu(cpu)) + +同时仍然允许接着使用常规的优先级限制。如果没有CPU能满足这个算力准则，那么将使用基于严格 +优先级的调度，CPU算力将被忽略。 + +5.3 最后期限调度 +---------------- + +5.3.1 被唤醒任务的CPU选择 +~~~~~~~~~~~~~~~~~~~~~~~~~ + +最后期限任务唤醒时的CPU选择，搜索满足以下条件的CPU:: + + task_bandwidth(p) < capacity(task_cpu(p)) + +同时仍然允许接着使用常规的带宽和截止期限限制。如果没有CPU能满足这个算力准则，那么任务依然 +在当前CPU队列中。 diff --git a/Documentation/translations/zh_CN/scheduler/sched-debug.rst b/Documentation/translations/zh_CN/scheduler/sched-debug.rst new file mode 100644 index 000000000..5e17740c2 --- /dev/null +++ b/Documentation/translations/zh_CN/scheduler/sched-debug.rst @@ -0,0 +1,51 @@ +.. SPDX-License-Identifier: GPL-2.0 +.. include:: ../disclaimer-zh_CN.rst + +:Original: Documentation/scheduler/sched-debug.rst + +:翻译: + + 唐艺舟 Tang Yizhou <tangyeechou@gmail.com> + +============= +调度器debugfs +============= + +用配置项CONFIG_SCHED_DEBUG=y启动内核后，将可以访问/sys/kernel/debug/sched +下的调度器专用调试文件。其中一些文件描述如下。 + +numa_balancing +============== + +`numa_balancing` 目录用来存放控制非统一内存访问（NUMA）平衡特性的相关文件。 +如果该特性导致系统负载太高，那么可以通过 `scan_period_min_ms, scan_delay_ms, +scan_period_max_ms, scan_size_mb` 文件控制NUMA缺页的内核采样速率。 + + +scan_period_min_ms, scan_delay_ms, scan_period_max_ms, scan_size_mb +------------------------------------------------------------------- + +自动NUMA平衡会扫描任务地址空间，检测页面是否被正确放置，或者数据是否应该被 +迁移到任务正在运行的本地内存结点，此时需解映射页面。每个“扫描延迟”（scan delay） +时间之后，任务扫描其地址空间中下一批“扫描大小”（scan size）个页面。若抵达 +内存地址空间末尾，扫描器将从头开始重新扫描。 + +结合来看，“扫描延迟”和“扫描大小”决定扫描速率。当“扫描延迟”减小时，扫描速率 +增加。“扫描延迟”和每个任务的扫描速率都是自适应的，且依赖历史行为。如果页面被 +正确放置，那么扫描延迟就会增加；否则扫描延迟就会减少。“扫描大小”不是自适应的， +“扫描大小”越大，扫描速率越高。 + +更高的扫描速率会产生更高的系统开销，因为必须捕获缺页异常，并且潜在地必须迁移 +数据。然而，当扫描速率越高，若工作负载模式发生变化，任务的内存将越快地迁移到 +本地结点，由于远程内存访问而产生的性能影响将降到最低。下面这些文件控制扫描延迟 +的阈值和被扫描的页面数量。 + +``scan_period_min_ms`` 是扫描一个任务虚拟内存的最小时间，单位是毫秒。它有效地 +控制了每个任务的最大扫描速率。 + +``scan_delay_ms`` 是一个任务初始化创建（fork）时，第一次使用的“扫描延迟”。 + +``scan_period_max_ms`` 是扫描一个任务虚拟内存的最大时间，单位是毫秒。它有效地 +控制了每个任务的最小扫描速率。 + +``scan_size_mb`` 是一次特定的扫描中，要扫描多少兆字节（MB）对应的页面数。 diff --git a/Documentation/translations/zh_CN/scheduler/sched-design-CFS.rst b/Documentation/translations/zh_CN/scheduler/sched-design-CFS.rst new file mode 100644 index 000000000..307640240 --- /dev/null +++ b/Documentation/translations/zh_CN/scheduler/sched-design-CFS.rst @@ -0,0 +1,205 @@ +.. SPDX-License-Identifier: GPL-2.0 +.. include:: ../disclaimer-zh_CN.rst + +:Original: Documentation/scheduler/sched-design-CFS.rst + +:翻译: + + 唐艺舟 Tang Yizhou <tangyeechou@gmail.com> + +=============== +完全公平调度器 +=============== + + +1. 概述 +======= + +CFS表示“完全公平调度器”，它是为桌面新设计的进程调度器，由Ingo Molnar实现并合入Linux +2.6.23。它替代了之前原始调度器中SCHED_OTHER策略的交互式代码。 + +CFS 80%的设计可以总结为一句话：CFS在真实硬件上建模了一个“理想的，精确的多任务CPU”。 + +“理想的多任务CPU”是一种（不存在的 :-)）具有100%物理算力的CPU，它能让每个任务精确地以 +相同的速度并行运行，速度均为1/nr_running。举例来说，如果有两个任务正在运行，那么每个 +任务获得50%物理算力。 --- 也就是说，真正的并行。 + +在真实的硬件上，一次只能运行一个任务，所以我们需要介绍“虚拟运行时间”的概念。任务的虚拟 +运行时间表明，它的下一个时间片将在上文描述的理想多任务CPU上开始执行。在实践中，任务的 +虚拟运行时间由它的真实运行时间相较正在运行的任务总数归一化计算得到。 + + + +2. 一些实现细节 +=============== + +在CFS中，虚拟运行时间由每个任务的p->se.vruntime（单位为纳秒）的值表达和跟踪。因此， +精确地计时和测量一个任务应得的“预期的CPU时间”是可能的。 + + 一些细节：在“理想的”硬件上，所有的任务在任何时刻都应该具有一样的p->se.vruntime值， + --- 也就是说，任务应当同时执行，没有任务会在“理想的”CPU分时中变得“不平衡”。 + +CFS的任务选择逻辑基于p->se.vruntime的值，因此非常简单：总是试图选择p->se.vruntime值 +最小的任务运行（也就是说，至今执行时间最少的任务）。CFS总是尽可能尝试按“理想多任务硬件” +那样将CPU时间在可运行任务中均分。 + +CFS剩下的其它设计，一般脱离了这个简单的概念，附加的设计包括nice级别，多处理，以及各种 +用来识别已睡眠任务的算法变体。 + + + +3. 红黑树 +========= + +CFS的设计非常激进：它不使用运行队列的旧数据结构，而是使用按时间排序的红黑树，构建出 +任务未来执行的“时间线”。因此没有任何“数组切换”的旧包袱（之前的原始调度器和RSDL/SD都 +被它影响）。 + +CFS同样维护了rq->cfs.min_vruntime值，它是单调递增的，跟踪运行队列中的所有任务的最小 +虚拟运行时间值。系统做的全部工作是：使用min_vruntime跟踪，然后用它的值将新激活的调度 +实体尽可能地放在红黑树的左侧。 + +运行队列中正在运行的任务的总数由rq->cfs.load计数，它是运行队列中的任务的权值之和。 + +CFS维护了一个按时间排序的红黑树，所有可运行任务以p->se.vruntime为键值排序。CFS从这颗 +树上选择“最左侧”的任务并运行。系统继续运行，被执行过的任务越来越被放到树的右侧 --- 缓慢， +但很明确每个任务都有成为“最左侧任务”的机会，因此任务将确定性地获得一定量CPU时间。 + +总结一下，CFS工作方式像这样：它运行一个任务一会儿，当任务发生调度（或者调度器时钟滴答 +tick产生），就会考虑任务的CPU使用率：任务刚刚花在物理CPU上的（少量）时间被加到 +p->se.vruntime。一旦p->se.vruntime变得足够大，其它的任务将成为按时间排序的红黑树的 +“最左侧任务”（相较最左侧的任务，还要加上一个很小的“粒度”量，使得我们不会对任务过度调度， +导致缓存颠簸），然后新的最左侧任务将被选中，当前任务被抢占。 + + + + +4. CFS的一些特征 +================ + +CFS使用纳秒粒度的计时，不依赖于任何jiffies或HZ的细节。因此CFS并不像之前的调度器那样 +有“时间片”的概念，也没有任何启发式的设计。唯一可调的参数（你需要打开CONFIG_SCHED_DEBUG）是： + + /sys/kernel/debug/sched/min_granularity_ns + +它可以用来将调度器从“桌面”模式（也就是低时延）调节为“服务器”（也就是高批处理）模式。 +它的默认设置是适合桌面的工作负载。SCHED_BATCH也被CFS调度器模块处理。 + +CFS的设计不易受到当前存在的任何针对stock调度器的“攻击”的影响，包括fiftyp.c，thud.c， +chew.c，ring-test.c，massive_intr.c，它们都能很好地运行，不会影响交互性，将产生 +符合预期的行为。 + +CFS调度器处理nice级别和SCHED_BATCH的能力比之前的原始调度器更强：两种类型的工作负载 +都被更激进地隔离了。 + +SMP负载均衡被重做/清理过：遍历运行队列的假设已经从负载均衡的代码中移除，使用调度模块 +的迭代器。结果是，负载均衡代码变得简单不少。 + + + +5. 调度策略 +=========== + +CFS实现了三种调度策略： + + - SCHED_NORMAL：（传统被称为SCHED_OTHER）：该调度策略用于普通任务。 + + - SCHED_BATCH：抢占不像普通任务那样频繁，因此允许任务运行更长时间，更好地利用缓存， + 不过要以交互性为代价。它很适合批处理工作。 + + - SCHED_IDLE：它比nice 19更弱，不过它不是真正的idle定时器调度器，因为要避免给机器 + 带来死锁的优先级反转问题。 + +SCHED_FIFO/_RR被实现在sched/rt.c中，它们由POSIX具体说明。 + +util-linux-ng 2.13.1.1中的chrt命令可以设置以上所有策略，除了SCHED_IDLE。 + + + +6. 调度类 +========= + +新的CFS调度器被设计成支持“调度类”，一种调度模块的可扩展层次结构。这些模块封装了调度策略 +细节，由调度器核心代码处理，且无需对它们做太多假设。 + +sched/fair.c 实现了上文描述的CFS调度器。 + +sched/rt.c 实现了SCHED_FIFO和SCHED_RR语义，且比之前的原始调度器更简洁。它使用了100个 +运行队列（总共100个实时优先级，替代了之前调度器的140个），且不需要过期数组（expired +array）。 + +调度类由sched_class结构体实现，它包括一些函数钩子，当感兴趣的事件发生时，钩子被调用。 + +这是（部分）钩子的列表： + + - enqueue_task(...) + + 当任务进入可运行状态时，被调用。它将调度实体（任务）放到红黑树中，增加nr_running变量 + 的值。 + + - dequeue_task(...) + + 当任务不再可运行时，这个函数被调用，对应的调度实体被移出红黑树。它减少nr_running变量 + 的值。 + + - yield_task(...) + + 这个函数的行为基本上是出队，紧接着入队，除非compat_yield sysctl被开启。在那种情况下， + 它将调度实体放在红黑树的最右端。 + + - check_preempt_curr(...) + + 这个函数检查进入可运行状态的任务能否抢占当前正在运行的任务。 + + - pick_next_task(...) + + 这个函数选择接下来最适合运行的任务。 + + - set_curr_task(...) + + 这个函数在任务改变调度类或改变任务组时被调用。 + + - task_tick(...) + + 这个函数最常被时间滴答函数调用，它可能导致进程切换。这驱动了运行时抢占。 + + + + +7. CFS的组调度扩展 +================== + +通常，调度器操作粒度为任务，努力为每个任务提供公平的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 + +当CONFIG_FAIR_GROUP_SCHED被定义后，通过伪文件系统，每个组被创建一个“cpu.shares”文件。 +参见下面的例子来创建任务组，并通过“cgroup”伪文件系统修改它们的CPU份额:: + + # 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 # 创建 "multimedia" 任务组 + # mkdir browser # 创建 "browser" 任务组 + + # #配置multimedia组，令其获得browser组两倍CPU带宽 + + # echo 2048 > multimedia/cpu.shares + # echo 1024 > browser/cpu.shares + + # firefox & # 启动firefox并把它移到 "browser" 组 + # echo <firefox_pid> > browser/tasks + + # #启动gmplayer（或者你最喜欢的电影播放器） + # echo <movie_player_pid> > multimedia/tasks diff --git a/Documentation/translations/zh_CN/scheduler/sched-domains.rst b/Documentation/translations/zh_CN/scheduler/sched-domains.rst new file mode 100644 index 000000000..e814d4c01 --- /dev/null +++ b/Documentation/translations/zh_CN/scheduler/sched-domains.rst @@ -0,0 +1,72 @@ +.. SPDX-License-Identifier: GPL-2.0 +.. include:: ../disclaimer-zh_CN.rst + +:Original: Documentation/scheduler/sched-domains.rst + +:翻译: + + 唐艺舟 Tang Yizhou <tangyeechou@gmail.com> + +:校译: + + 司延腾 Yanteng Si <siyanteng@loongson.cn> + +====== +调度域 +====== + +每个CPU有一个“基”调度域（struct sched_domain）。调度域层次结构从基调度域构建而来，可 +通过->parent指针自下而上遍历。->parent必须以NULL结尾，调度域结构体必须是per-CPU的， +因为它们无锁更新。 + +每个调度域管辖数个CPU（存储在->span字段中）。一个调度域的span必须是它的子调度域span的 +超集（如有需求出现，这个限制可以放宽）。CPU i的基调度域必须至少管辖CPU i。每个CPU的 +顶层调度域通常将会管辖系统中的全部CPU，尽管严格来说这不是必须的，假如是这样，会导致某些 +CPU出现永远不会被指定任务运行的情况，直到允许的CPU掩码被显式设定。调度域的span字段意味 +着“在这些CPU中做进程负载均衡”。 + +每个调度域必须具有一个或多个CPU调度组（struct sched_group），它们以单向循环链表的形式 +组织，存储在->groups指针中。这些组的CPU掩码的并集必须和调度域span字段一致。->groups +指针指向的这些组包含的CPU，必须被调度域管辖。组包含的是只读数据，被创建之后，可能被多个 +CPU共享。任意两个组的CPU掩码的交集不一定为空，如果是这种情况，对应调度域的SD_OVERLAP +标志位被设置，它管辖的调度组可能不能在多个CPU中共享。 + +调度域中的负载均衡发生在调度组中。也就是说，每个组被视为一个实体。组的负载被定义为它 +管辖的每个CPU的负载之和。仅当组的负载不均衡后，任务才在组之间发生迁移。 + +在kernel/sched/core.c中，trigger_load_balance()在每个CPU上通过scheduler_tick() +周期执行。在当前运行队列下一个定期调度再平衡事件到达后，它引发一个软中断。负载均衡真正 +的工作由run_rebalance_domains()->rebalance_domains()完成，在软中断上下文中执行 +（SCHED_SOFTIRQ）。 + +后一个函数有两个入参：当前CPU的运行队列、它在scheduler_tick()调用时是否空闲。函数会从 +当前CPU所在的基调度域开始迭代执行，并沿着parent指针链向上进入更高层级的调度域。在迭代 +过程中，函数会检查当前调度域是否已经耗尽了再平衡的时间间隔，如果是，它在该调度域运行 +load_balance()。接下来它检查父调度域（如果存在），再后来父调度域的父调度域，以此类推。 + +起初，load_balance()查找当前调度域中最繁忙的调度组。如果成功，在该调度组管辖的全部CPU +的运行队列中找出最繁忙的运行队列。如能找到，对当前的CPU运行队列和新找到的最繁忙运行 +队列均加锁，并把任务从最繁忙队列中迁移到当前CPU上。被迁移的任务数量等于在先前迭代执行 +中计算出的该调度域的调度组的不均衡值。 + +实现调度域 +========== + +基调度域会管辖CPU层次结构中的第一层。对于超线程（SMT）而言，基调度域将会管辖同一个物理 +CPU的全部虚拟CPU，每个虚拟CPU对应一个调度组。 + +在SMP中，基调度域的父调度域将会管辖同一个结点中的全部物理CPU，每个调度组对应一个物理CPU。 +接下来，如果是非统一内存访问（NUMA）系统，SMP调度域的父调度域将管辖整个机器，一个结点的 +CPU掩码对应一个调度组。亦或，你可以使用多级NUMA；举例来说Opteron处理器，可能仅用一个 +调度域来覆盖它的一个NUMA层级。 + +实现者需要阅读include/linux/sched/sd_flags.h的注释：读SD_*来了解具体情况以及调度域的 +SD标志位调节了哪些东西。 + +体系结构可以把指定的拓扑层级的通用调度域构建器和默认的SD标志位覆盖掉，方法是创建一个 +sched_domain_topology_level数组，并以该数组作为入参调用set_sched_topology()。 + +调度域调试基础设施可以通过CONFIG_SCHED_DEBUG开启，并在开机启动命令行中增加 +“sched_verbose”。如果你忘记调整开机启动命令行了，也可以打开 +/sys/kernel/debug/sched/verbose开关。这将开启调度域错误检查的解析，它应该能捕获（上文 +描述过的）绝大多数错误，同时以可视化格式打印调度域的结构。 diff --git a/Documentation/translations/zh_CN/scheduler/sched-energy.rst b/Documentation/translations/zh_CN/scheduler/sched-energy.rst new file mode 100644 index 000000000..fdbf6cfee --- /dev/null +++ b/Documentation/translations/zh_CN/scheduler/sched-energy.rst @@ -0,0 +1,351 @@ +.. SPDX-License-Identifier: GPL-2.0 +.. include:: ../disclaimer-zh_CN.rst + +:Original: Documentation/scheduler/sched-energy.rst + +:翻译: + + 唐艺舟 Tang Yizhou <tangyeechou@gmail.com> + +============ +能量感知调度 +============ + +1. 简介 +------- + +能量感知调度（EAS）使调度器有能力预测其决策对CPU所消耗的能量的影响。EAS依靠 +一个能量模型（EM）来为每个任务选择一个节能的CPU，同时最小化对吞吐率的影响。 +本文档致力于介绍介绍EAS是如何工作的，它背后的主要设计决策是什么，以及使其运行 +所需的条件细节。 + +在进一步阅读之前，请注意，在撰写本文时:: + + /!\ EAS不支持对称CPU拓扑的平台 /!\ + +EAS只在异构CPU拓扑结构（如Arm大小核，big.LITTLE）上运行。因为在这种情况下， +通过调度来节约能量的潜力是最大的。 + +EAS实际使用的EM不是由调度器维护的，而是一个专门的框架。关于这个框架的细节和 +它提供的内容，请参考其文档（见Documentation/power/energy-model.rst）。 + + +2. 背景和术语 +------------- + +从一开始就说清楚定义: + - 能量 = [焦耳] （比如供电设备上的电池提供的资源） + - 功率 = 能量/时间 = [焦耳/秒] = [瓦特] + + EAS的目标是最小化能量消耗，同时仍能将工作完成。也就是说，我们要最大化:: + + 性能 [指令数/秒] + ---------------- + 功率 [瓦特] + +它等效于最小化:: + + 能量 [焦耳] + ----------- + 指令数 + +同时仍然获得“良好”的性能。当前调度器只考虑性能目标，因此该式子本质上是一个 +可选的优化目标，它同时考虑了两个目标：能量效率和性能。 + +引入EM的想法是为了让调度器评估其决策的影响，而不是盲目地应用可能仅在部分 +平台有正面效果的节能技术。同时，EM必须尽可能的简单，以最小化调度器的时延 +影响。 + +简而言之，EAS改变了CFS任务分配给CPU的方式。当调度器决定一个任务应该在哪里 +运行时（在唤醒期间），EM被用来在不损害系统吞吐率的情况下，从几个较好的候选 +CPU中挑选一个经预测能量消耗最优的CPU。EAS的预测依赖于对平台拓扑结构特定元素 +的了解，包括CPU的“算力”，以及它们各自的能量成本。 + + +3. 拓扑信息 +----------- + +EAS（以及调度器的剩余部分）使用“算力”的概念来区分不同计算吞吐率的CPU。一个 +CPU的“算力”代表了它在最高频率下运行时能完成的工作量，且这个值是相对系统中 +算力最大的CPU而言的。算力值被归一化为1024以内，并且可与由实体负载跟踪 +（PELT）机制算出的利用率信号做对比。由于有算力值和利用率值，EAS能够估计一个 +任务/CPU有多大/有多忙，并在评估性能与能量时将其考虑在内。CPU算力由特定体系 +结构实现的arch_scale_cpu_capacity()回调函数提供。 + +EAS使用的其余平台信息是直接从能量模型（EM）框架中读取的。一个平台的EM是一张 +表，表中每项代表系统中一个“性能域”的功率成本。（若要了解更多关于性能域的细节， +见Documentation/power/energy-model.rst） + +当调度域被建立或重新建立时，调度器管理对拓扑代码中EM对象的引用。对于每个根域 +（rd），调度器维护一个与当前rd->span相交的所有性能域的单向链表。链表中的每个 +节点都包含一个指向EM框架所提供的结构体em_perf_domain的指针。 + +链表被附加在根域上，以应对独占的cpuset的配置。由于独占的cpuset的边界不一定与 +性能域的边界一致，不同根域的链表可能包含重复的元素。 + +示例1 + 让我们考虑一个有12个CPU的平台，分成3个性能域，（pd0，pd4和pd8），按以下 + 方式组织:: + + CPUs: 0 1 2 3 4 5 6 7 8 9 10 11 + PDs: |--pd0--|--pd4--|---pd8---| + RDs: |----rd1----|-----rd2-----| + + 现在，考虑用户空间决定将系统分成两个独占的cpusets，因此创建了两个独立的根域， + 每个根域包含6个CPU。这两个根域在上图中被表示为rd1和rd2。由于pd4与rd1和rd2 + 都有交集，它将同时出现于附加在这两个根域的“->pd”链表中: + + * rd1->pd: pd0 -> pd4 + * rd2->pd: pd4 -> pd8 + + 请注意，调度器将为pd4创建两个重复的链表节点（每个链表中各一个）。然而这 + 两个节点持有指向同一个EM框架的共享数据结构的指针。 + +由于对这些链表的访问可能与热插拔及其它事件并发发生，因此它们受RCU锁保护，就像 +被调度器操控的拓扑结构体中剩下字段一样。 + +EAS同样维护了一个静态键（sched_energy_present），当至少有一个根域满足EAS +启动的所有条件时，这个键就会被启动。在第6节中总结了这些条件。 + + +4. 能量感知任务放置 +------------------- + +EAS覆盖了CFS的任务唤醒平衡代码。在唤醒平衡时，它使用平台的EM和PELT信号来选择节能 +的目标CPU。当EAS被启用时，select_task_rq_fair()调用find_energy_efficient_cpu() +来做任务放置决定。这个函数寻找在每个性能域中寻找具有最高剩余算力（CPU算力 - CPU +利用率）的CPU，因为它能让我们保持最低的频率。然后，该函数检查将任务放在新CPU相较 +依然放在之前活动的prev_cpu是否可以节省能量。 + +如果唤醒的任务被迁移，find_energy_efficient_cpu()使用compute_energy()来估算 +系统将消耗多少能量。compute_energy()检查各CPU当前的利用率情况，并尝试调整来 +“模拟”任务迁移。EM框架提供了API em_pd_energy()计算每个性能域在给定的利用率条件 +下的预期能量消耗。 + +下面详细介绍一个优化能量消耗的任务放置决策的例子。 + +示例2 + 让我们考虑一个有两个独立性能域的（伪）平台，每个性能域含有2个CPU。CPU0和CPU1 + 是小核，CPU2和CPU3是大核。 + + 调度器必须决定将任务P放在哪个CPU上，这个任务的util_avg = 200（平均利用率）， + prev_cpu = 0（上一次运行在CPU0）。 + + 目前CPU的利用率情况如下图所示。CPU 0-3的util_avg分别为400、100、600和500。 + 每个性能域有三个操作性能值（OPP）。与每个OPP相关的CPU算力和功率成本列在能量 + 模型表中。P的util_avg在图中显示为"PP":: + + CPU util. + 1024 - - - - - - - Energy Model + +-----------+-------------+ + | Little | Big | + 768 ============= +-----+-----+------+------+ + | Cap | Pwr | Cap | Pwr | + +-----+-----+------+------+ + 512 =========== - ##- - - - - | 170 | 50 | 512 | 400 | + ## ## | 341 | 150 | 768 | 800 | + 341 -PP - - - - ## ## | 512 | 300 | 1024 | 1700 | + PP ## ## +-----+-----+------+------+ + 170 -## - - - - ## ## + ## ## ## ## + ------------ ------------- + CPU0 CPU1 CPU2 CPU3 + + Current OPP: ===== Other OPP: - - - util_avg (100 each): ## + + + find_energy_efficient_cpu()将首先在两个性能域中寻找具有最大剩余算力的CPU。 + 在这个例子中是CPU1和CPU3。然后，它将估算，当P被放在它们中的任意一个时，系统的 + 能耗，并检查这样做是否会比把P放在CPU0上节省一些能量。EAS假定OPPs遵循利用率 + （这与CPUFreq监管器schedutil的行为一致。关于这个问题的更多细节，见第6节）。 + + **情况1. P被迁移到CPU1**:: + + 1024 - - - - - - - + + Energy calculation: + 768 ============= * CPU0: 200 / 341 * 150 = 88 + * CPU1: 300 / 341 * 150 = 131 + * CPU2: 600 / 768 * 800 = 625 + 512 - - - - - - - ##- - - - - * CPU3: 500 / 768 * 800 = 520 + ## ## => total_energy = 1364 + 341 =========== ## ## + PP ## ## + 170 -## - - PP- ## ## + ## ## ## ## + ------------ ------------- + CPU0 CPU1 CPU2 CPU3 + + + **情况2. P被迁移到CPU3**:: + + 1024 - - - - - - - + + Energy calculation: + 768 ============= * CPU0: 200 / 341 * 150 = 88 + * CPU1: 100 / 341 * 150 = 43 + PP * CPU2: 600 / 768 * 800 = 625 + 512 - - - - - - - ##- - -PP - * CPU3: 700 / 768 * 800 = 729 + ## ## => total_energy = 1485 + 341 =========== ## ## + ## ## + 170 -## - - - - ## ## + ## ## ## ## + ------------ ------------- + CPU0 CPU1 CPU2 CPU3 + + **情况3. P依旧留在prev_cpu/CPU0**:: + + 1024 - - - - - - - + + Energy calculation: + 768 ============= * CPU0: 400 / 512 * 300 = 234 + * CPU1: 100 / 512 * 300 = 58 + * CPU2: 600 / 768 * 800 = 625 + 512 =========== - ##- - - - - * CPU3: 500 / 768 * 800 = 520 + ## ## => total_energy = 1437 + 341 -PP - - - - ## ## + PP ## ## + 170 -## - - - - ## ## + ## ## ## ## + ------------ ------------- + CPU0 CPU1 CPU2 CPU3 + + 从这些计算结果来看，情况1的总能量最低。所以从节约能量的角度看，CPU1是最佳候选 + 者。 + +大核通常比小核更耗电，因此主要在任务不适合在小核运行时使用。然而，小核并不总是比 +大核节能。举例来说，对于某些系统，小核的高OPP可能比大核的低OPP能量消耗更高。因此， +如果小核在某一特定时间点刚好有足够的利用率，在此刻被唤醒的小任务放在大核执行可能 +会更节能，尽管它在小核上运行也是合适的。 + +即使在大核所有OPP都不如小核OPP节能的情况下，在某些特定条件下，令小任务运行在大核 +上依然可能节能。事实上，将一个任务放在一个小核上可能导致整个性能域的OPP提高，这将 +增加已经在该性能域运行的任务的能量成本。如果唤醒的任务被放在一个大核上，它的执行 +成本可能比放在小核上更高，但这不会影响小核上的其它任务，这些任务将继续以较低的OPP +运行。因此，当考虑CPU消耗的总能量时，在大核上运行一个任务的额外成本可能小于为所有 +其它运行在小核的任务提高OPP的成本。 + +上面的例子几乎不可能以一种通用的方式得到正确的结果；同时，对于所有平台，在不知道 +系统所有CPU每个不同OPP的运行成本时，也无法得到正确的结果。得益于基于EM的设计， +EAS应该能够正确处理这些问题而不会引发太多麻烦。然而，为了确保对高利用率场景的 +吞吐率造成的影响最小化，EAS同样实现了另外一种叫“过度利用率”的机制。 + + +5. 过度利用率 +------------- + +从一般的角度来看，EAS能提供最大帮助的是那些涉及低、中CPU利用率的使用场景。每当CPU +密集型的长任务运行，它们将需要所有的可用CPU算力，调度器将没有什么办法来节省能量同时 +又不损害吞吐率。为了避免EAS损害性能，一旦CPU被使用的算力超过80%，它将被标记为“过度 +利用”。只要根域中没有CPU是过度利用状态，负载均衡被禁用，而EAS将覆盖唤醒平衡代码。 +EAS很可能将负载放置在系统中能量效率最高的CPU而不是其它CPU上，只要不损害吞吐率。 +因此，负载均衡器被禁用以防止它打破EAS发现的节能任务放置。当系统未处于过度利用状态时， +这样做是安全的，因为低于80%的临界点意味着： + + a. 所有的CPU都有一些空闲时间，所以EAS使用的利用率信号很可能准确地代表各种任务 + 的“大小”。 + b. 所有任务，不管它们的nice值是多大，都应该被提供了足够多的CPU算力。 + c. 既然有多余的算力，那么所有的任务都必须定期阻塞/休眠，在唤醒时进行平衡就足够 + 了。 + +只要一个CPU利用率超过80%的临界点，上述三个假设中至少有一个是不正确的。在这种情况下， +整个根域的“过度利用”标志被设置，EAS被禁用，负载均衡器被重新启用。通过这样做，调度器 +又回到了在CPU密集的条件下基于负载的算法做负载均衡。这更好地尊重了任务的nice值。 + +由于过度利用率的概念在很大程度上依赖于检测系统中是否有一些空闲时间，所以必须考虑 +（比CFS）更高优先级的调度类（以及中断）“窃取”的CPU算力。像这样，对过度使用率的检测 +不仅要考虑CFS任务使用的算力，还需要考虑其它调度类和中断。 + + +6. EAS的依赖和要求 +------------------ + +能量感知调度依赖系统的CPU具有特定的硬件属性，以及内核中的其它特性被启用。本节列出 +了这些依赖，并对如何满足这些依赖提供了提示。 + + +6.1 - 非对称CPU拓扑 +^^^^^^^^^^^^^^^^^^^ + + +如简介所提，目前只有非对称CPU拓扑结构的平台支持EAS。通过在运行时查询 +SD_ASYM_CPUCAPACITY_FULL标志位是否在创建调度域时已设置来检查这一要求是否满足。 + +参阅Documentation/scheduler/sched-capacity.rst以了解在sched_domain层次结构 +中设置此标志位所需满足的要求。 + +请注意，EAS并非从根本上与SMP不兼容，但在SMP平台上还没有观察到明显的节能。这一 +限制可以在将来进行修改，如果被证明不是这样的话。 + + +6.2 - 当前的能量模型 +^^^^^^^^^^^^^^^^^^^^ + +EAS使用一个平台的EM来估算调度决策对能量的影响。因此，你的平台必须向EM框架提供 +能量成本表，以启动EAS。要做到这一点，请参阅文档 +Documentation/power/energy-model.rst中的独立EM框架部分。 + +另请注意，调度域需要在EM注册后重建，以便启动EAS。 + +EAS使用EM对能量使用率进行预测决策，因此它在检查任务放置的可能选项时更加注重 +差异。对于EAS来说，EM的功率值是以毫瓦还是以“抽象刻度”为单位表示并不重要。 + + + +6.3 - 能量模型复杂度 +^^^^^^^^^^^^^^^^^^^^ + +任务唤醒路径是时延敏感的。当一个平台的EM太复杂（太多CPU，太多性能域，太多状态 +等），在唤醒路径中使用它的成本就会升高到不可接受。能量感知唤醒算法的复杂度为： + + C = Nd * (Nc + Ns) + +其中：Nd是性能域的数量；Nc是CPU的数量；Ns是OPP的总数（例如：对于两个性能域， +每个域有4个OPP，则Ns = 8）。 + +当调度域建立时，复杂性检查是在根域上进行的。如果一个根域的复杂度C恰好高于完全 +主观设定的EM_MAX_COMPLEXITY阈值（在本文写作时，是2048），则EAS不会在此根域 +启动。 + +如果你的平台的能量模型的复杂度太高，EAS无法在这个根域上使用，但你真的想用， +那么你就只剩下两个可能的选择： + + 1. 将你的系统拆分成分离的、较小的、使用独占cpuset的根域，并在每个根域局部 + 启用EAS。这个方案的好处是开箱即用，但缺点是无法在根域之间实现负载均衡， + 这可能会导致总体系统负载不均衡。 + 2. 提交补丁以降低EAS唤醒算法的复杂度，从而使其能够在合理的时间内处理更大 + 的EM。 + + +6.4 - Schedutil监管器 +^^^^^^^^^^^^^^^^^^^^^ + +EAS试图预测CPU在不久的将来会在哪个OPP下运行，以估算它们的能量消耗。为了做到 +这一点，它假定CPU的OPP跟随CPU利用率变化而变化。 + +尽管在实践中很难对这一假设的准确性提供硬性保证（因为，举例来说硬件可能不会做 +它被要求做的事情），相对于其他CPUFreq监管器，schedutil至少_请求_使用利用率 +信号计算的频率。因此，与EAS一起使用的唯一合理的监管器是schedutil，因为它是 +唯一一个在频率请求和能量预测之间提供某种程度的一致性的监管器。 + +不支持将EAS与schedutil之外的任何其它监管器一起使用。 + + +6.5 刻度不变性使用率信号 +^^^^^^^^^^^^^^^^^^^^^^^^ + +为了对不同的CPU和所有的性能状态做出准确的预测，EAS需要频率不变的和CPU不变的 +PELT信号。这些信号可以通过每个体系结构定义的arch_scale{cpu,freq}_capacity() +回调函数获取。 + +不支持在没有实现这两个回调函数的平台上使用EAS。 + + +6.6 多线程（SMT） +^^^^^^^^^^^^^^^^^ + +当前实现的EAS是不感知SMT的，因此无法利用多线程硬件节约能量。EAS认为线程是独立的 +CPU，这实际上对性能和能量消耗都是不利的。 + +不支持在SMT上使用EAS。 diff --git a/Documentation/translations/zh_CN/scheduler/sched-nice-design.rst b/Documentation/translations/zh_CN/scheduler/sched-nice-design.rst new file mode 100644 index 000000000..9107f0c0b --- /dev/null +++ b/Documentation/translations/zh_CN/scheduler/sched-nice-design.rst @@ -0,0 +1,99 @@ +.. SPDX-License-Identifier: GPL-2.0 +.. include:: ../disclaimer-zh_CN.rst + +:Original: Documentation/scheduler/sched-nice-design.rst + +:翻译: + + 唐艺舟 Tang Yizhou <tangyeechou@gmail.com> + +===================== +调度器nice值设计 +===================== + +本文档解释了新的Linux调度器中修改和精简后的nice级别的实现思路。 + +Linux的nice级别总是非常脆弱，人们持续不断地缠着我们，让nice +19的任务占用 +更少的CPU时间。 + +不幸的是，在旧的调度器中，这不是那么容易实现的（否则我们早就做到了），因为对 +nice级别的支持在历史上是与时间片长度耦合的，而时间片单位是由HZ滴答驱动的， +所以最小的时间片是1/HZ。 + +在O(1)调度器中（2003年），我们改变了负的nice级别，使它们比2.4内核更强 +（人们对这一变化很满意），而且我们还故意校正了线性时间片准则，使得nice +19 +的级别 _正好_ 是1 jiffy。为了让大家更好地理解它，时间片的图会是这样的（质量 +不佳的ASCII艺术提醒！）:: + + + A + \ | [timeslice length] + \ | + \ | + \ | + \ | + \|___100msecs + |^ . _ + | ^ . _ + | ^ . _ + -*----------------------------------*-----> [nice level] + -20 | +19 + | + | + +因此，如果有人真的想renice任务，相较线性规则，+19会给出更大的效果（改变 +ABI来扩展优先级的解决方案在早期就被放弃了）。 + +这种方法在一定程度上奏效了一段时间，但后来HZ=1000时，它导致1 jiffy为 +1ms，这意味着0.1%的CPU使用率，我们认为这有点过度。过度 _不是_ 因为它表示 +的CPU使用率过小，而是因为它引发了过于频繁（每毫秒1次）的重新调度（因此会 +破坏缓存，等等。请记住，硬件更弱、cache更小是很久以前的事了，当时人们在 +nice +19级别运行数量颇多的应用程序）。 + +因此，对于HZ=1000，我们将nice +19改为5毫秒，因为这感觉像是正确的最小 +粒度——这相当于5%的CPU利用率。但nice +19的根本的HZ敏感属性依然保持不变， +我们没有收到过关于nice +19在CPU利用率方面太 _弱_ 的任何抱怨，我们只收到 +过它（依然）太 _强_ 的抱怨 :-)。 + +总结一下：我们一直想让nice各级别一致性更强，但在HZ和jiffies的限制下，以及 +nice级别与时间片、调度粒度耦合是令人讨厌的设计，这一目标并不真正可行。 + +第二个关于Linux nice级别支持的抱怨是（不那么频繁，但仍然定期发生），它 +在原点周围的不对称性（你可以在上面的图片中看到），或者更准确地说：事实上 +nice级别的行为取决于 _绝对的_ nice级别，而nice应用程序接口本身从根本上 +说是“相对”的： + + int nice(int inc); + + asmlinkage long sys_nice(int increment) + +（第一个是glibc的应用程序接口，第二个是syscall的应用程序接口） +注意，“inc”是相对当前nice级别而言的，类似bash的“nice”命令等工具是这个 +相对性应用程序接口的镜像。 + +在旧的调度器中，举例来说，如果你以nice +1启动一个任务，并以nice +2启动 +另一个任务，这两个任务的CPU分配将取决于父外壳程序的nice级别——如果它是 +nice -10，那么CPU的分配不同于+5或+10。 + +第三个关于Linux nice级别支持的抱怨是，负数nice级别“不够有力”，以很多人 +不得不诉诸于实时调度优先级来运行音频（和其它多媒体）应用程序，比如 +SCHED_FIFO。但这也造成了其它问题：SCHED_FIFO未被证明是免于饥饿的，一个 +有问题的SCHED_FIFO应用程序也会锁住运行良好的系统。 + +v2.6.23版内核的新调度器解决了这三种类型的抱怨： + +为了解决第一个抱怨（nice级别不够“有力”），调度器与“时间片”、HZ的概念 +解耦（调度粒度被处理成一个和nice级别独立的概念），因此有可能实现更好、 +更一致的nice +19支持：在新的调度器中，nice +19的任务得到一个HZ无关的 +1.5%CPU使用率，而不是旧版调度器中3%-5%-9%的可变范围。 + +为了解决第二个抱怨（nice各级别不一致），新调度器令调用nice(1)对各任务的 +CPU利用率有相同的影响，无论其绝对nice级别如何。所以在新调度器上，运行一个 +nice +10和一个nice +11的任务会与运行一个nice -5和一个nice -4的任务的 +CPU利用率分割是相同的（一个会得到55%的CPU，另一个会得到45%）。这是为什么 +nice级别被改为“乘法”（或指数）——这样的话，不管你从哪个级别开始，“相对” +结果将总是一样的。 + +第三个抱怨（负数nice级别不够“有力”，并迫使音频应用程序在更危险的 +SCHED_FIFO调度策略下运行）几乎被新的调度器自动解决了：更强的负数级别 +具有重新校正nice级别动态范围的自动化副作用。 diff --git a/Documentation/translations/zh_CN/scheduler/sched-stats.rst b/Documentation/translations/zh_CN/scheduler/sched-stats.rst new file mode 100644 index 000000000..c5e0be663 --- /dev/null +++ b/Documentation/translations/zh_CN/scheduler/sched-stats.rst @@ -0,0 +1,156 @@ +.. SPDX-License-Identifier: GPL-2.0 +.. include:: ../disclaimer-zh_CN.rst + +:Original: Documentation/scheduler/sched-stats.rst + +:翻译: + + 唐艺舟 Tang Yizhou <tangyeechou@gmail.com> + +============== +调度器统计数据 +============== + +第15版schedstats去掉了sched_yield的一些计数器：yld_exp_empty，yld_act_empty +和yld_both_empty。在其它方面和第14版完全相同。 + +第14版schedstats包括对sched_domains（译注：调度域）的支持，该特性进入内核 +主线2.6.20，不过这一版schedstats与2.6.13-2.6.19内核的版本12的统计数据是完全 +相同的（内核未发布第13版）。有些计数器按每个运行队列统计是更有意义的，其它则 +按每个调度域统计是更有意义的。注意，调度域（以及它们的附属信息）仅在开启 +CONFIG_SMP的机器上是相关的和可用的。 + +在第14版schedstat中，每个被列出的CPU至少会有一级域统计数据，且很可能有一个 +以上的域。在这个实现中，域没有特别的名字，但是编号最高的域通常在机器上所有的 +CPU上仲裁平衡，而domain0是最紧密聚焦的域，有时仅在一对CPU之间进行平衡。此时， +没有任何体系结构需要3层以上的域。域统计数据中的第一个字段是一个位图，表明哪些 +CPU受该域的影响。 + +这些字段是计数器，而且只能递增。使用这些字段的程序将需要从基线观测开始，然后在 +后续每一个观测中计算出计数器的变化。一个能以这种方式处理其中很多字段的perl脚本 +可见 + + http://eaglet.pdxhosts.com/rick/linux/schedstat/ + +请注意，任何这样的脚本都必须是特定于版本的，改变版本的主要原因是输出格式的变化。 +对于那些希望编写自己的脚本的人，可以参考这里描述的各个字段。 + +CPU统计数据 +----------- +cpu<N> 1 2 3 4 5 6 7 8 9 + +第一个字段是sched_yield()的统计数据： + + 1) sched_yield()被调用了#次 + +接下来的三个是schedule()的统计数据： + + 2) 这个字段是一个过时的数组过期计数，在O(1)调度器中使用。为了ABI兼容性， + 我们保留了它，但它总是被设置为0。 + 3) schedule()被调用了#次 + 4) 调用schedule()导致处理器变为空闲了#次 + +接下来的两个是try_to_wake_up()的统计数据： + + 5) try_to_wake_up()被调用了#次 + 6) 调用try_to_wake_up()导致本地CPU被唤醒了#次 + +接下来的三个统计数据描述了调度延迟： + + 7) 本处理器运行任务的总时间，单位是纳秒 + 8) 本处理器任务等待运行的时间，单位是纳秒 + 9) 本CPU运行了#个时间片 + +域统计数据 +---------- + +对于每个被描述的CPU，和它相关的每一个调度域均会产生下面一行数据（注意，如果 +CONFIG_SMP没有被定义，那么*没有*调度域被使用，这些行不会出现在输出中）。 + +domain<N> <cpumask> 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 + +第一个字段是一个位掩码，表明该域在操作哪些CPU。 + +接下来的24个字段是load_balance()函数的各个统计数据，按空闲类型分组（空闲， +繁忙，新空闲）： + + + 1) 当CPU空闲时，load_balance()在这个调度域中被调用了#次 + 2) 当CPU空闲时，load_balance()在这个调度域中被调用，但是发现负载无需 + 均衡#次 + 3) 当CPU空闲时，load_balance()在这个调度域中被调用，试图迁移1个或更多 + 任务且失败了#次 + 4) 当CPU空闲时，load_balance()在这个调度域中被调用，发现不均衡（如果有） + #次 + 5) 当CPU空闲时，pull_task()在这个调度域中被调用#次 + 6) 当CPU空闲时，尽管目标任务是热缓存状态，pull_task()依然被调用#次 + 7) 当CPU空闲时，load_balance()在这个调度域中被调用，未能找到更繁忙的 + 队列#次 + 8) 当CPU空闲时，在调度域中找到了更繁忙的队列，但未找到更繁忙的调度组 + #次 + 9) 当CPU繁忙时，load_balance()在这个调度域中被调用了#次 + 10) 当CPU繁忙时，load_balance()在这个调度域中被调用，但是发现负载无需 + 均衡#次 + 11) 当CPU繁忙时，load_balance()在这个调度域中被调用，试图迁移1个或更多 + 任务且失败了#次 + 12) 当CPU繁忙时，load_balance()在这个调度域中被调用，发现不均衡（如果有） + #次 + 13) 当CPU繁忙时，pull_task()在这个调度域中被调用#次 + 14) 当CPU繁忙时，尽管目标任务是热缓存状态，pull_task()依然被调用#次 + 15) 当CPU繁忙时，load_balance()在这个调度域中被调用，未能找到更繁忙的 + 队列#次 + 16) 当CPU繁忙时，在调度域中找到了更繁忙的队列，但未找到更繁忙的调度组 + #次 + 17) 当CPU新空闲时，load_balance()在这个调度域中被调用了#次 + 18) 当CPU新空闲时，load_balance()在这个调度域中被调用，但是发现负载无需 + 均衡#次 + 19) 当CPU新空闲时，load_balance()在这个调度域中被调用，试图迁移1个或更多 + 任务且失败了#次 + 20) 当CPU新空闲时，load_balance()在这个调度域中被调用，发现不均衡（如果有） + #次 + 21) 当CPU新空闲时，pull_task()在这个调度域中被调用#次 + 22) 当CPU新空闲时，尽管目标任务是热缓存状态，pull_task()依然被调用#次 + 23) 当CPU新空闲时，load_balance()在这个调度域中被调用，未能找到更繁忙的 + 队列#次 + 24) 当CPU新空闲时，在调度域中找到了更繁忙的队列，但未找到更繁忙的调度组 + #次 + +接下来的3个字段是active_load_balance()函数的各个统计数据： + + 25) active_load_balance()被调用了#次 + 26) active_load_balance()被调用，试图迁移1个或更多任务且失败了#次 + 27) active_load_balance()被调用，成功迁移了#次任务 + +接下来的3个字段是sched_balance_exec()函数的各个统计数据： + + 28) sbe_cnt不再被使用 + 29) sbe_balanced不再被使用 + 30) sbe_pushed不再被使用 + +接下来的3个字段是sched_balance_fork()函数的各个统计数据： + + 31) sbf_cnt不再被使用 + 32) sbf_balanced不再被使用 + 33) sbf_pushed不再被使用 + +接下来的3个字段是try_to_wake_up()函数的各个统计数据： + + 34) 在这个调度域中调用try_to_wake_up()唤醒任务时，任务在调度域中一个 + 和上次运行不同的新CPU上运行了#次 + 35) 在这个调度域中调用try_to_wake_up()唤醒任务时，任务被迁移到发生唤醒 + 的CPU次数为#，因为该任务在原CPU是冷缓存状态 + 36) 在这个调度域中调用try_to_wake_up()唤醒任务时，引发被动负载均衡#次 + +/proc/<pid>/schedstat +--------------------- +schedstats还添加了一个新的/proc/<pid>/schedstat文件，来提供一些进程级的 +相同信息。这个文件中，有三个字段与该进程相关： + + 1) 在CPU上运行花费的时间(单位是纳秒) + 2) 在运行队列上等待的时间(单位是纳秒) + 3) 在CPU上运行了#个时间片 + +可以很容易地编写一个程序，利用这些额外的字段来报告一个特定的进程或一组进程在 +调度器策略下的表现如何。这样的程序的一个简单版本可在下面的链接找到 + + http://eaglet.pdxhosts.com/rick/linux/schedstat/v12/latency.c diff --git a/Documentation/translations/zh_CN/scheduler/schedutil.rst b/Documentation/translations/zh_CN/scheduler/schedutil.rst new file mode 100644 index 000000000..d1ea68007 --- /dev/null +++ b/Documentation/translations/zh_CN/scheduler/schedutil.rst @@ -0,0 +1,165 @@ +.. SPDX-License-Identifier: GPL-2.0 +.. include:: ../disclaimer-zh_CN.rst + +:Original: Documentation/scheduler/schedutil.rst + +:翻译: + + 唐艺舟 Tang Yizhou <tangyeechou@gmail.com> + +========= +Schedutil +========= + +.. note:: + + 本文所有内容都假设频率和工作算力之间存在线性关系。我们知道这是有瑕疵的， + 但这是最可行的近似处理。 + +PELT（实体负载跟踪，Per Entity Load Tracking） +============================================== + +通过PELT，我们跟踪了各种调度器实体的一些指标，从单个任务到任务组分片到CPU +运行队列。我们使用指数加权移动平均数（Exponentially Weighted Moving Average， +EWMA）作为其基础，每个周期（1024us）都会衰减，衰减速率满足y^32 = 0.5。 +也就是说，最近的32ms贡献负载的一半，而历史上的其它时间则贡献另一半。 + +具体而言： + + ewma_sum(u) := u_0 + u_1*y + u_2*y^2 + ... + + ewma(u) = ewma_sum(u) / ewma_sum(1) + +由于这本质上是一个无限几何级数的累加，结果是可组合的，即ewma(A) + ewma(B) = ewma(A+B)。 +这个属性是关键，因为它提供了在任务迁移时重新组合平均数的能力。 + +请注意，阻塞态的任务仍然对累加值（任务组分片和CPU运行队列）有贡献，这反映了 +它们在恢复运行后的预期贡献。 + +利用这一点，我们跟踪2个关键指标：“运行”和“可运行”。“运行”反映了一个调度实体 +在CPU上花费的时间，而“可运行”反映了一个调度实体在运行队列中花费的时间。当只有 +一个任务时，这两个指标是相同的，但一旦出现对CPU的争用，“运行”将减少以反映每个 +任务在CPU上花费的时间，而“可运行”将增加以反映争用的激烈程度。 + +更多细节见：kernel/sched/pelt.c + + +频率 / CPU不变性 +================ + +因为CPU频率在1GHz时利用率为50%和CPU频率在2GHz时利用率为50%是不一样的，同样 +在小核上运行时利用率为50%和在大核上运行时利用率为50%是不一样的，我们允许架构 +以两个比率来伸缩时间差，其中一个是动态电压频率升降（Dynamic Voltage and +Frequency Scaling，DVFS）比率，另一个是微架构比率。 + +对于简单的DVFS架构（软件有完全控制能力），我们可以很容易地计算该比率为:: + + f_cur + r_dvfs := ----- + f_max + +对于由硬件控制DVFS的更多动态系统，我们使用硬件计数器（Intel APERF/MPERF， +ARMv8.4-AMU）来计算这一比率。具体到Intel，我们使用:: + + APERF + f_cur := ----- * P0 + MPERF + + 4C-turbo; 如果可用并且使能了turbo + f_max := { 1C-turbo; 如果使能了turbo + P0; 其它情况 + + f_cur + r_dvfs := min( 1, ----- ) + f_max + +我们选择4C turbo而不是1C turbo，以使其更持久性略微更强。 + +r_cpu被定义为当前CPU的最高性能水平与系统中任何其它CPU的最高性能水平的比率。 + + r_tot = r_dvfs * r_cpu + +其结果是，上述“运行”和“可运行”的指标变成DVFS无关和CPU型号无关了。也就是说， +我们可以在CPU之间转移和比较它们。 + +更多细节见: + + - kernel/sched/pelt.h:update_rq_clock_pelt() + - arch/x86/kernel/smpboot.c:"APERF/MPERF frequency ratio computation." + - Documentation/translations/zh_CN/scheduler/sched-capacity.rst:"1. CPU Capacity + 2. Task utilization" + + +UTIL_EST / UTIL_EST_FASTUP +========================== + +由于周期性任务的平均数在睡眠时会衰减，而在运行时其预期利用率会和睡眠前相同， +因此它们在再次运行后会面临（DVFS）的上涨。 + +为了缓解这个问题，（一个默认使能的编译选项）UTIL_EST驱动一个无限脉冲响应 +（Infinite Impulse Response，IIR）的EWMA，“运行”值在出队时是最高的。 +另一个默认使能的编译选项UTIL_EST_FASTUP修改了IIR滤波器，使其允许立即增加， +仅在利用率下降时衰减。 + +进一步，运行队列的（可运行任务的）利用率之和由下式计算： + + util_est := \Sum_t max( t_running, t_util_est_ewma ) + +更多细节见: kernel/sched/fair.c:util_est_dequeue() + + +UCLAMP +====== + +可以在每个CFS或RT任务上设置有效的u_min和u_max clamp值（译注：clamp可以理解 +为类似滤波器的能力，它定义了有效取值范围的最大值和最小值）；运行队列为所有正在 +运行的任务保持这些clamp的最大聚合值。 + +更多细节见: include/uapi/linux/sched/types.h + + +Schedutil / DVFS +================ + +每当调度器的负载跟踪被更新时（任务唤醒、任务迁移、时间流逝），我们都会调用 +schedutil来更新硬件DVFS状态。 + +其基础是CPU运行队列的“运行”指标，根据上面的内容，它是CPU的频率不变的利用率 +估计值。由此我们计算出一个期望的频率，如下:: + + max( running, util_est ); 如果使能UTIL_EST + u_cfs := { running; 其它情况 + + clamp( u_cfs + u_rt, u_min, u_max ); 如果使能UCLAMP_TASK + u_clamp := { u_cfs + u_rt; 其它情况 + + u := u_clamp + u_irq + u_dl; [估计值。更多细节见源代码] + + f_des := min( f_max, 1.25 u * f_max ) + +关于IO-wait的说明：当发生更新是因为任务从IO完成中唤醒时，我们提升上面的“u”。 + +然后，这个频率被用来选择一个P-state或OPP，或者直接混入一个发给硬件的CPPC式 +请求。 + +关于截止期限调度器的说明: 截止期限任务（偶发任务模型）使我们能够计算出满足 +工作负荷所需的硬f_min值。 + +因为这些回调函数是直接来自调度器的，所以DVFS的硬件交互应该是“快速”和非阻塞的。 +在硬件交互缓慢和昂贵的时候，schedutil支持DVFS请求限速，不过会降低效率。 + +更多信息见: kernel/sched/cpufreq_schedutil.c + + +注意 +==== + + - 在低负载场景下，DVFS是最相关的，“运行”的值将密切反映利用率。 + + - 在负载饱和的场景下，任务迁移会导致一些瞬时性的使用率下降。假设我们有一个 + CPU，有4个任务占用导致其饱和，接下来我们将一个任务迁移到另一个空闲CPU上， + 旧的CPU的“运行”值将为0.75，而新的CPU将获得0.25。这是不可避免的，而且随着 + 时间流逝将自动修正。另注，由于没有空闲时间，我们还能保证f_max值吗？ + + - 上述大部分内容是关于避免DVFS下滑，以及独立的DVFS域发生负载迁移时不得不 + 重新学习/提升频率。 + |