0%

Linux进程管理(四)多核调度

原图

概述

SMP(Symmetrical MultiProcessing)的全称是“对称多处理”技术,是指在一台计算机上汇集了一组处理器,这些处理器都是对等的,它们之间共享内存子系统和系统总线。

下图所示为4核的SMP处理器架构,在4核处理器中,每个物理CPU核心拥有独立的L1缓存且不支持超线程技术,分成两个簇(cluster)簇0和簇1,每个簇包含两个物理CPU核,簇中的CPU核共享L2缓存。

调度域和调度组

根据处理器的实际物理属性,CPU和Linux内核的分类如下所示。

  • SMT(超线程) Linux内核配置项CONFIG_SCHED_SMT 一个物理核心可以有两个或更多执行线程,被称为超线程技术。超线程使用相同的cpu资源且共享L1缓存,迁移进程不会影响高速缓存的利用率

  • MC(多核) Linux内核配置项CONFIG_SCHED_MC 每个物理核心独享L1高速缓存,多个物理核心可以组成族,族里的cpu共享L2高速缓存

  • SOC(处理器) 内核称为DIE SOC级别

Linux内核使用数据结构sched_domain_topology_level来描述CPU的层次关系,本节中简称为SDTL。

1
2
3
4
5
6
7
8
9
10
11
<include/linux/sched/topology.h>
struct sched_domain_topology_level {
sched_domain_mask_f mask; //函数指针,用于指定某个SDTL的cpumask位图
sched_domain_flags_f sd_flags;//函数指针,用于指定某个SDTL的标志位
int flags;
int numa_level;
struct sd_data data;
#ifdef CONFIG_SCHED_DEBUG
char *name;
#endif
};

另外,Linux内核默认定义了数组default_topology[]来概括CPU物理域的层次结构。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
<kernel/sched/topology.c>
/*
* Topology list, bottom-up.
*/
static struct sched_domain_topology_level default_topology[] = {
#ifdef CONFIG_SCHED_SMT
{ cpu_smt_mask, cpu_smt_flags, SD_INIT_NAME(SMT) },
#endif
#ifdef CONFIG_SCHED_MC
{ cpu_coregroup_mask, cpu_core_flags, SD_INIT_NAME(MC) },
#endif
{ cpu_cpu_mask, SD_INIT_NAME(DIE) },
{ NULL, },
};

Linux内核使用sched_domain数据结构来描述调度层级,从defaul_topology[]数组可知,系统默认支持DIE类型层级、SMT类型层级以及MC类型层级。另外,可在调度域里划分调度组,然后使用sched_group数据结构来描述调度组,调度组是负载均衡调度的最小单位。在最低层级的调度域中,通常用调度组描述CPU核心。 在支持NUMA架构的处理器中,假设支持SMT技术,那么整个系统的调度域和调度组的关系如图所示,可在默认的调度层级中新增NUMA层级的调度域。在超大系统中,系统会频繁访问调度域数据结构。为了提升系统的性能和可扩展性,调度域数据结构sched_domain采用Per-CPU变量来构建

负载的计算

例1

假设在如图所示的双核处理器里,CPU0的就绪队列里有4个进程,CPU1的就绪队列里有两个进程,那么究竟哪个CPU上的负载重呢?

假设上述6个进程的nice值是相同的,也就是优先级和权重都相同,那么明显可以看出 CPU0的就绪队列里有4个进程,相比CPU1的就绪队列里的进程数目要多,从而得出CPU0 上的负载相比CPU1更重的结论。

CPU上的负载=就绪队列的总权重

为了计算CPU上的负载,最简单的方法是计算CPU的就绪队列中所有进程的权重。

但是,仅考虑优先级和权重是有问题的,有的是CPU密集型的,也有的是I/O密集型的。如果延伸到多CPU之间的负载均衡,结果就显得不准确了。

例2

在如图所示的双核处理器里,CPU0和CPU1的就绪队列里都只有一个进程在运行,而且进程的优先级和权重相同。但是,CPUO上的进程一直在占用CPU,而CPU1上的进程走走停停,那么究竟CPU0和CPU1上的负载是不是相同呢?

从例1中的判断条件看,两个CPU上的负载是一样的。但是,从我们的直观感受看,CPU0上的进程一直占用CPU,CPU0是一直满负荷运行的,而CPU1上的进程走走停停,CPU使用率不高。为什么会得出不一样的结论呢? 这是因为例1使用的计算方法没有考虑进程在时间因素下的作用,也就是没有考虑历史负载对当前负载的影响。那么该如何计算历史负载对CPU上的负载的影响呢?

CPU上的负载的计算公式如下。 \[ CPU上的负载 = \frac{运行时间}{总时间} \times 就绪队列总权重 \tag{2} \] 其中,运行时间是指就绪队列占用CPU的总时间;总时间是指采样的总时间,包括CPU处于空闲的时间以及CPU正在运行的时间;就绪队列总权重是指就绪队列里所有进程的总权重。

式2把负载这个概念量化到了权重,这样不同运行行为的进程就有了量化的标准来衡量负载,本书把这种用运行时间与总时间的比值来计算的权重,称为量化负载。另外,我们把时间与权重的乘积称为工作负载。

式2并不完美,因为它把历史工作负载和当前工作负载平等对待了。

因此,自Linux3.8内核以后,进程的负载计算不仅要考虑权重,而且要跟踪每个调度实体的历史负载情况,因而称为PELT (Per-Entitv Load Tracking)。PELT算法引入了 "accumulation of an infinite geometric series”这个概念,英文字面意思是无穷几何级数的累加,本书把这个概念简单称为历史累计计算。

Linux内核使用量化负载这个概念来计算和比较进程以及就绪队列的负载。 根据量化负载的定义,量化负载的计算如式3所示。 \[ decay\_avg\_load = (\frac{decay\_sum\_runnable\_time}{decay\_sum\_runnable\_time}) \times weight \tag{3} \]

其中,decay_avg_load表示量化负载;decay_sum_runnable_time指的是就绪队列或调度实体在可运行状态下的所有历史累计衰减时间;decay_sum_period_time指的是就绪队列或调度实体在所有的采样周期里全部时间的累加衰减时间。通常从进程开始执行时就计算和累计这些值。weight表示调度实体或就绪队列的权重。 计算进程的量化负载的意义在于能够把负载量化到权重里。当一个进程的decay_sumrunnable_time 无限接近decay_sum_period_time时,它的量化负载就无限接近权重值,说明这个进程一直在占用CPU,满负荷工作,CPU占用率很高。一个进程的decay_sum_runnable_time越小,它的量化负载就越小,说明这个进程的工作负荷很小,占用的CPU资源很少,CPU占用率很低。这样,我们就对负载实现了统一和标准化的量化计算,不同行为的进程就可以进行标准化的负载计算和比较了。

负载均衡算法

SMP负载均衡机制从注册软中断开始,系统每次调度tick中断时,都会检查当前是否需要处理SMP负载均衡。rebalance_domains()函数是负载均衡的核心入口。load_balance()函数中的主要流程如下。

  • 负载均衡以当前CPU开始,由下至上地遍历调度域,从最底层的调度域开始做负载均衡
  • 允许做负载均衡的首要条件是当前CPU是调度域中的第一个CPU,或者当前CPU是空闲CPU。详见should_we_balance()函数
  • 在调度域中查找最繁忙的调度组,更新调度域和调度组的相关信息,最后计算出调度域的不均衡负载值
  • 最繁忙的调度组中找出最繁忙的CPU,然后把繁忙CPU中的进程迁移到当前CPU上,迁移的负载量为不均衡负载值

Per-CPU变量

Per-CPU变量是Linux内核中同步机制的一种。当系统中的所有CPU都访问共享的一个变量v时,如果CPU0修改了变量v的值,而CPU1也在同时修改变量v的值,就会导致变量v的值不正确。一种可行的办法就是在CPU0访问变量v时使用原子加锁指令,这样CPU1访问变量v时就只能等待了,但这样做有两个比较明显的缺点。

  • 原子操作是比较耗时的
  • 在现代处理器中,每个CPU都有L1缓存,因而多个CPU同时访问同一个变量就会导致缓存一致性问题。当某个CPU对共享的数据变量v进行修改后,其他CPU上对应的缓存行需要做无效操作,这对性能是有损耗的

Per-CPU变量是为了解决上述问题而出现的一种有趣的特性,它为系统中的每个处理器都分配自身的副本。这样在多处理器系统中,当处理器只能访问属于自己的那个变量副本时,不需要考虑与其他处理器的竞争问题,还能充分利用处理器本地的硬件缓存来提升性能。

Per-CPU变量的定义和声明

Per-CPU变量的定义和声明有两种方式。一种是静态声明,另一种是动态分配。静态的Per-CPU变量可通过DEFINE_PER_CPU和DECLARE_PER_CPU宏来定义和声明。这类变量与普通变量的主要区别在于它们存放在一个特殊的段中。

1
2
3
4
5
6
7
8
9
/*
* Variant on the per-CPU variable declaration/definition theme used for
* ordinary per-CPU variables.
*/
#define DECLARE_PER_CPU(type, name) \
DECLARE_PER_CPU_SECTION(type, name, "")

#define DEFINE_PER_CPU(type, name) \
DEFINE_PER_CPU_SECTION(type, name, "")

用于动态分配和释放per-cpu变量的API函数如下。

1
2
3
4
#define alloc_percpu(type)						\
(typeof(type) __percpu *)__alloc_percpu(sizeof(type), \
__alignof__(type))
extern void free_percpu(void __percpu *__pdata);

使用Per-CPU变量

对于静态定义的Per-CPU变量,可以通过get_cpu_var()和put_cpu_var()函数来访问和修改,这两个函数内置了关闭和打开内核抢占的功能。另外需要注意的是,这两个函数需要配对使用。

1
2
3
4
5
6
7
8
9
10
11
#define get_cpu_var(var)						\
(*({ \
preempt_disable(); \
this_cpu_ptr(&var); \
}))

#define put_cpu_var(var) \
do { \
(void)&(var); \
preempt_enable(); \
} while (0)

对于动态分配的Per-CPU变量,需要通过以下接口来访问:

1
2
3
4
5
6
7
8
9
10
11
#define get_cpu_ptr(var)						\
({ \
preempt_disable(); \
this_cpu_ptr(var); \
})

#define put_cpu_ptr(var) \
do { \
(void)(var); \
preempt_enable(); \
} while (0)

TLB处理

单核处理

在进程切换的时候,需要有tlb的操作,以便清除旧进程的影响,具体怎样做呢?我们下面一一讨论。

  • 绝对没有问题,但是性能不佳的方案 所有TLB和Cache的数据都全部flush掉。当然,稍微有一点遗憾的就是在B进程开始执行的时候,TLB和Cache都是冰冷的

  • 如何提高TLB的性能 对于所有的进程(包括内核线程),内核地址空间是一样的,因此对于这部分地址翻译,无论进程如何切换,内核地址空间转换到物理地址的关系是永远不变的,不需要flush TLB。对于用户地址空间,各个进程都有自己独立的地址空间,在进程A切换到B的时候,TLB中的和A进程相关的entry(上图中,青色的block)需要flush掉 我们其实需要区分global和local这两种类型的地址翻译,因此,在页表描述符中往往有一个bit来标识该地址翻译是global还是local的,同样的,在TLB中,这个标识global还是local的flag也会被缓存起来。有了这样的设计之后,我们可以根据不同的场景而flush all或者只是flush local tlb entry

  • 特殊情况的考量 对于多线程环境,切换可能发生在一个进程中的两个线程,这时候,线程在同样的地址空间,也根本不需要flush tlb

  • 进一步提升TLB的性能 这里有一个术语叫做ASID(address space ID)。原来TLB查找是通过虚拟地址VA来判断是否TLB hit。有了ASID的支持后,TLB hit的判断标准修改为(虚拟地址+ASID),ASID是每一个进程分配一个,标识自己的进程地址空间。TLB block如何知道一个tlb entry的ASID呢?一般会来自CPU的系统寄存器(对于ARM64平台,它来自TTBRx_EL1寄存器),这样在TLB block在缓存(VA-PA-Global flag)的同时,也就把当前的ASID缓存在了对应的TLB entry中,这样一个TLB entry中包括了(VA-PA-Global flag-ASID)

多核处理

在多核系统中,进程切换的时候,TLB的操作要复杂一些,原因是进程可以调度到任何一个cpu core上执行。

根据上一节的描述,我们了解到地址翻译有global(各个进程共享)和local(进程特定的)的概念,因而tlb entry也有global和local的区分。如果区分global 和local,那么tlb操作也基本类似,只不过进程切换的时候,不是flush该cpu上的所有tlb entry,而是flush所有的tlb local entry就OK了。

对local tlb entry还可以进一步细分,那就是ASID(address space ID)或者PCID(process context ID)的概念了(global tlb entry不区分ASID)。如果支持ASID(或者PCID)的话,tlb操作变得简单一些,或者说我们没有必要执行tlb操作了,因为在TLB搜索的时候已经可以区分各个task上下文了,这样,各个cpu中残留的tlb不会影响其他任务的执行。

不过,对于多核系统,这种情况有一点点的麻烦,其实也就是传说中的TLB shootdown带来的性能问题。在多核系统中,如果cpu支持PCID并且在进程切换的时候不flush tlb,那么系统中各个cpu中的tlb entry则保留各种task的tlb entry,当在某个cpu上,一个进程被销毁,或者修改了自己的页表(也就是修改了VA PA映射关系)的时候,我们必须将该task的相关tlb entry从系统中清除出去。这时候,你不仅仅需要flush本cpu上对应的TLB entry,还需要shootdown其他cpu上的和该task相关的tlb残余。而这个动作一般是通过IPI实现(例如X86),从而引入了开销。此外PCID的分配和管理也会带来额外的开销,因此,OS是否支持PCID(或者ASID)是由各个arch代码自己决定。

参考文献

《奔跑吧Linux内核》
《Linux内核设计与实现》
http://www.wowotech.net/process_management/context-switch-tlb.html