Linux Scheduling Domains

Scheduling Domains 引入的背景

Scheduling Domains 是现代硬件技术尤其是多 CPU 多核技术发展的产物。现在,一个复杂的高端系统由上到下可以这样构成:

1.它是一个 NUMA 架构的系统,系统中的每个 Node 访问系统中不同区域的 内存有不同的速度。

2.同时它又是一个 SMP 系统。由多个物理 CPU(Physical Package) 构成。 这些物理 CPU 共享系统中所有的内存。但都有自己独立的 Cache 。

3.每个物理 CPU 又由多个核 (Core) 构成,即 Multi-core 技术或者叫 Chip- level Multi processor(CMP) 。这些核都被集成在一块 die 里面。一般 有自己独立的 L1 Cache,但可能共享 L2 Cache 。

4.每个核中又通过 SMT 之类的技术实现多个硬件线程,或者叫 Virtual CPU( 比如 Intel 的 Hyper-threading 技术 ) 。这些硬件线程,逻辑上看是就是一个 CPU 。它们之间几乎所有的东西都共享。包括 L1 Cache,甚至是逻辑运算 单元 (ALU) 以及 Power 。

在上述系统中,最小的执行单元是逻辑 CPU,进程的调度执行也是相对于逻辑 CPU 的。因此,后文皆简称逻辑 CPU 为 CPU,是物理 CPU 时会特别说明。

在这样复杂的系统,调度器要解决的一个首要问题就是如何发挥这么多 CPU 的性能,使得负载均衡。不存某些 CPU 一直很忙,进程在排队等待运行,而某些 CPU 却是处于空闲状态。

但是在这些 CPU 之间进行 Load Balance 是有代价的,比如对处于两个不同物理 CPU 的进程之间进行负载平衡的话,将会使得 Cache 失效。造成效率的下降。而且过多的 Load Balance 会大量占用 CPU 资源。

还有一个要考虑的就是功耗 (Power) 的问题。一个物理 CPU 中的两个 Virtual CPU 各执行一个进程,显然比两个物理 CPU 中的 Virtual CPU 各执行一个进程节省功耗。因为硬件上可以实现一个物理 CPU 不用时关掉它以节省功耗。

为了解决上述的这些问题,内核开发人员 Nick Piggin 等人在 Linux 2.6 中引入基于 Scheduling Domains 的解决方案。

Scheduling Domains 原理

每个 Scheduling Domain 其实就是具有相同属性的一组 cpu 的集合。并且跟据 Hyper-threading, Multi-core, SMP, NUMA architectures 这样的系统结构划分成不同的级别。不同级之间通过指针链接在一起,从而形成一种的树状的关系。如下图所示:

图 1. Scheduling Domains 原理

负载平衡就是针对 Scheduling domain 的。从叶节点往上遍历。直到所有的 domain 中的负载都是平衡的。当然对不同的 domain 会有不同的策略识别是否负载不平衡,以及不同的调度策略。通过这样的方式,从而很好的发挥众多 cpu 的效率。

Scheduling Domains 结构

基于 Scheduling Domains 的调度器引入了一组新的数据结构。下面先讲一下两个主要的数据结构:

struct sched_domain: 代表一个 Scheduling Domain,也就是一个 CPU 集合,这个集合里所有的 CPU 都具有相同的属性和调度策略。 Load Balance 是针对每个 domain 里的 CPU 进行的。这里要注意 Scheduling Domains 是分级的。像上节所讲的复杂系统就分为 Allnuma_domain,Numa_domain, Phy_domain, Core_domain, Smt_domain(Cpu_domain) 五个等级

表 1 列出了这个结构的主要字段。

  • struct sched_group: 每个 Scheduling domain 都有一个或多个 CPU group,每个 group 都被 domain 当做一个单独的单元来对待。 Load Balance 就是在这些 CPU group 之间的 CPU 进行的。表 2 列出了它的主要字段。
表 1. sched_domain 数据结构

下面以我们之前提到的 NUMA,SMP,Multcore,SMT 结合的复杂系统为例来具体解释一下 Scheduling domains 和 CPU groups 之间的关系。

这里为了简化讨论,假设每个物理 CPU 只有两个核,每个核只有两个逻辑 CPU 。

如下图所示:

图 2. 物理 CPU 示意图

当系统启动时,会分别把每个核的两个逻辑 CPU 放入一个 Scheduling Domain,

这个级别的 domain 叫做 cpu_domain 。其中每个 domain 包括两个 CPU groups,每个 CPU group 只有一个逻辑 CPU 。

如下图所示:

图 3. 逻辑 CPU

同时每个物理 CPU 的两个核被放入一个高一级的 Scheduling Domain 。这个 domain 命名为 core_domain 。其中每个 domain 包括两个 CPU groups,每个 CPU group 有两个逻辑 CPU 。

如下图所示:

图 4. CPU group

对于我们前述的复杂系统,再往上的话依次还有 phys_domain( 物理 CPU 放入的 domain) ;

numa_domain(NUMA 中的 16 个 nodes 放入的 domain) ; allnode_domain( 所有 NUMA 中的 node 放入的 domain) 。从而将所有 CPU 组织成一个基于 domain 的层次结构。

Scheduling Domains 实现

对每个 Scheduling Domain 中的 CPU groups 之间的 CPU 进行的。

每个 Scheduling Domain 都包含一些重要的信息用来决定在这级 domain 的 CPU groups 之间如何进行 Load Balance 。

典型的一些原则如下:

1.在 cpu_domain 级: 因为是共享 cache,cpu_power 也基本是共用的。 所以可以在这个 domain 级的 cpu groups 之间可以不受限制的进行 load balance 。

2.在 core_domain 级:可能会共享 L2 级 cache, 具体跟实现相关了。因此 这一级的 balance 相对没那么频繁。要 core 之间负载的不平衡达到一定 程度才进行 balance 。

3.在 phys_domain 级:在这一个 domain 级,如果进行 balance 。则每个 物理 CPU 上的 Cache 会失效一段时间,并且要考虑 cpu_power,因为 物理 CPU 级的 power 一般是被数关系。比如两个物理 CPU 是 power*2,而不像 core, 或逻辑 CPU,只是 power*1.1 这样的关系。

4.在 numa_domain 级:这一级的开销最大,一般很少进行 balance 。

基本实现

Linux 主要通过以下几个方面来实现基于 Scheduling domains 的 Load Balance 。

1. 周期性的 load balance

每次时钟中断到来,如果发现当前 cpu 的运行队列需要进行下一次的 balance 的时间已经到了,则触发 SCHED_SOFTIRQ 软中断。

触发软中断

if (time_after_eq(jiffies, rq->next_balance))

raise_softirq(SCHED_SOFTIRQ);

软中断的执行函数是 run_rebalance_domains(), 它主要是再调 rebalance_domains() 来实现。

2. 针对 CPU IDLE 的处理

如果一个逻辑 CPU 进入了 IDLE 状态,并且它所属的 domain 设置了 SD_BALANCE_NEWIDLE,则马上就会进行 balance,把忙的 CPU 上的进程 move 过来,从而最大的发挥多 CPU 的优势。

3.针对 fork(), exec() 的处理

当一个进行调用 exec() 执行时,本来就是要加载一个新进程,缓存 本来就会失效。所以,move 到哪里都可以。因此找设置了 SD_BALANCE_EXEC 标记的 domain 。然后把进程移动到那个 domain 中最闲的 CPU group 的 CPU 上。

fork() 时也进行类似的处理。

4.其它因素比如针对 cpu_power 的处理

本文分享自微信公众号 - 相遇Linux(LinuxJeff)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-08-10

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券