Linux 内核SMP负载均衡浅析

需求在《linux进程调度浅析》一文中提到,在SMP(对称多处理器)环境下,每个CPU对应一个run_queue(可执行队列)。如果一个进程处于TASK_RUNNING状态(可执行状态),则它会被加入到其中一个run_queue(且同一时刻仅会被加入到一个run_queue),以便让调度程序安排它在这个run_queue对应的CPU上面运行。

一个CPU对应一个run_queue这样的设计,其好处是:

1、一个持续处于TASK_RUNNING状态的进程总是趋于在同一个CPU上面运行(其间,这个进程可能被抢占、然后又被调度),这有利于进程的数据被CPU所缓存,提高运行效率;
2、各个CPU上的调度程序只访问自己的run_queue,避免了竞争;

然而,这样的设计也可能使得各个run_queue里面的进程不均衡,造成“一些CPU闲着、一些CPU忙不过来”混乱局面。为了解决这个问题,load_balance(负载均衡)就登场了。

load_balance所需要做的事情就是,在一定的时机,通过将进程从一个run_queue迁移到另一个run_queue,来保持CPU之间的负载均衡。

这里的“均衡”二字如何定义?load_balance又具体要做哪些事情呢?对于不同调度策略(实时进程 OR 普通进程),有着不同的逻辑,需要分开来看。

实时进程的负载均衡

实时进程的调度是严格按照优先级来进行的。在单CPU环境下,CPU上运行着的总是优先级最高的进程,直到这个进程离开TASK_RUNNING状态,新任的“优先级最高的进程”才开始得到运行。直到所有实时进程都离开TASK_RUNNING状态,其他普通进程才有机会得到运行。(暂时忽略sched_rt_runtime_us和sched_rt_period_us的影响,见《linux组调度浅析》。)

推广到SMP环境,假设有N个CPU,N个CPU上分别运行着的也必须是优先级最高的top-N个进程。如果实时进程不足N个,那么剩下的CPU才分给普通进程去使用。对于实时进程来说,这就是所谓的“均衡”。

实时进程的优先级关系是很严格的,当优先级最高的top-N个进程发生变化时,内核必须马上响应:

1、如果这top-N个进程当中,有一个离开TASK_RUNNING状态、或因为优先级被调低而退出top-N集团,则原先处于(N+1)位的那个进程将进入top-N。内核需要遍历所有的run_queue,把这个新任的top-N进程找出来,然后立马让它开始运行;
2、反之,如果一个top-N之外的实时进程的优先级被调高,以至于挤占了原先处于第N位的进程,则内核需要遍历所有的run_queue,把这个被挤出top-N的进程找出来,将它正在占用的CPU让给新进top-N的那个进程去运行;

在这几种情况下,新进入top-N的进程和退出top-N的进程可能原本并不在同一个CPU上,那么在它得到运行之前,内核会先将其迁移到退出top-N的进程所在的CPU上。

具体来说,内核通过pull_rt_task和push_rt_task两个函数来完成实时进程的迁移:

pull_rt_task – 把其他CPU的run_queue中的实时进程pull过来,放到当前CPU的run_queue中。被pull过来的实时进程要满足以下条件:

1、进程是其所在的run_queue中优先级第二高的(优先级最高的进程必定正在运行,不需要移动);
2、进程的优先级比当前run_queue中最高优先级的进程还要高;
3、进程允许在当前CPU上运行(没有亲和性限制);

该函数会在以下时间点被调用:

1、发生调度之前,如果prev进程(将要被替换下去的进程)是实时进程,且优先级高于当前run_queue中优先级最高的实时进程(这说明prev进程已经离开TASK_RUNNING状态了,否则它不会让位于比它优先级低的进程);
2、正在运行的实时进程优先级被调低时(比如通过sched_setparam系统调用);
3、正在运行的实时进程变成普通进程时(比如通过sched_setscheduler系统调用);

push_rt_task – 把当前run_queue中多余的实时进程推给其他run_queue。需要满足以下条件:

1、每次push一个进程,这个进程的优先级在当前run_queue中是第二高的(优先级最高的进程必定正在运行,不需要移动);
2、目标run_queue上正在运行的不是实时进程(是普通进程),或者是top-N中优先级最低的实时进程,且优先级低于被push的进程;
3、被push的进程允许在目标CPU上运行(没有亲和性限制);
4、满足条件的目标run_queue可能存在多个(可能多个CPU上都没有实时进程在运行),应该选择与当前CPU最具亲缘性的一组CPU中的第一个CPU所对应的run_queue作为push的目标(顺着sched_domain–调度域–逐步往上,找到第一个包含目标CPU的sched_domain。见后面关于sched_domain的描述);

该函数会在以下时间点被调用:

1、非正在运行的普通进程变成实时进程时(比如通过sched_setscheduler系统调用);
2、发生调度之后(这时候可能有一个实时进程被更高优先级的实时进程抢占了);
3、实时进程被唤醒之后,如果不能马上在当前CPU上运行(它不是当前CPU上优先级最高的进程);

看起来,实时进程的负载均衡对于每个CPU一个run_queue这种模式似乎有些别扭,每次需要选择一个实时进程,总是需要遍历所有run_queue,在尚未能得到运行的实时进程之中找到优先级最高的那一个。其实,如果所有CPU共用同一个run_queue,就没有这么多的烦恼了。为什么不这样做呢?

1、在CPU对run_queue的竞争方面,“每个CPU去竞争每一个run_queue”比“每个CPU去竞争一个总的run_queue”略微好一些,因为竞争的粒度更小了;
2、在进程的移动方面,每个CPU一个run_queue这种模式其实也不能很好的把进程留在同一个CPU上,因为严格的优先级关系使得进程必须在出现不均衡时立刻被移动。不过,一些特殊情况下进程的迁移还是有一定选择面的。比如优先级相同的时候就可以尽量不做迁移、push_rt_task的时候可以选择跟当前CPU最为亲近的CPU去迁移。

普通进程的负载均衡

可以看出,实时进程的负载均衡性能是不会太好的。为了满足严格的优先级关系,丝毫的不均衡都是不能容忍的。所以一旦top-N的平衡关系发生变化,内核就必须即时完成负载均衡,形成新的top-N的平衡关系。这可能会使得每个CPU频繁去竞争run_queue、进程频繁被迁移。

而普通进程则并不要求严格的优先级关系,可以容忍一定程度的不均衡。所以普通进程的负载均衡可以不必在进程发生变化时即时完成,而采用一些异步调整的策略。

普通进程的负载均衡在以下情况下会被触发:

1、当前进程离开TASK_RUNNING状态(进入睡眠或退出),而对应的run_queue中已无进程可用时。这时触发负载均衡,试图从别的run_queue中pull一个进程过来运行;
2、每隔一定的时间,启动负载均衡过程,试图发现并解决系统中不均衡;
另外,对于调用exec的进程,它的地址空间已经完全重建了,当前CPU上已经不会再缓存对它有用的信息。这时内核也会考虑负载均衡,为它们找一个合适的CPU。

那么,对于普通进程来说,“均衡”到底意味着什么呢?

在单CPU环境下,处于TASK_RUNNING状态的进程会以其优先级为权重,瓜分CPU时间。优先级越高的进程,权重越高,分得的CPU时间也就越多。在CFS调度(完全公平调度,针对普通进程的调度程序)中,这里的权重被称作load。假设某个进程的load为m,所有处于TASK_RUNNING状态的进程的load之和为M,那么这个进程所能分到的CPU时间是m/M。比如系统中有两个TASK_RUNNING状态的进程,一个load为1、一个load为2,总的load是1+2=3。则它们分到的CPU时间分别是1/3和2/3。

推广到SMP环境,假设有N个CPU,那么一个load为m的进程所能分到的CPU时间应该是N*m/M(如果不是,则要么这个进程挤占了别的进程的CPU时间、要么是被别的进程挤占)。对于普通进程来说,这就是所谓的“均衡”。

那么,如何让进程能够分到N*m/M的CPU时间呢?其实,只需要把所有进程的load平分到每一个run_queue上,使得每个run_queue的load(它上面的进程的load之和)都等于M/N,这样就好了。于是,每个run_queue的load就成了是否“均衡”的判断依据。

下面看看load_balance里面做些什么。注意,不管load_balance是怎样被触发的,它总是在某个CPU上被执行。而load_balance过程被实现得非常简单,只需要从最繁忙(load最高)的run_queue中pull几个进程到当前run_queue中(只pull,不push),使得当前run_queue与最繁忙的run_queue得到均衡(使它们的load接近于所有run_queue的平均load),仅此而已。load_balance并不需要考虑所有run_queue全局的均衡,但是当load_balance在各个CPU上分别得到运行之后,全局的均衡也就实现了。这样的实现极大程度减小了负载均衡的开销。

load_balance的过程大致如下:

1、找出最繁忙的一个run_queue;
2、如果找到的run_queue比本地run_queue繁忙,且本地run_queue的繁忙程度低于平均水平,那么迁移几个进程过来,使两个run_queue的load接近平均水平。反之则什么都不做;

在比较两个run_queue繁忙程度的问题上,其实是很有讲究的。这个地方很容易想当然地理解为:把run_queue中所有进程的load加起来,比较一下就OK了。而实际上,需要比较的往往并不是实时的load。

这就好比我们用top命令查看CPU占用率一样,top命令默认1秒刷新一次,每次刷新你将看到这1秒内所有进程各自对CPU的占用情况。这里的占用率是个统计值,假设有一个进程在这1秒内持续运行了100毫秒,那么我们认为它占用了10%的CPU。如果把1秒刷新一次改成1毫秒刷新一次呢?那么我们将有90%的机率看到这个进程占用0%的CPU、10%的机率占用100%的CPU。而无论是0%、还是100%,都不是这个进程真实的CPU占用率的体现。必须把一段时间以内的CPU占用率综合起来看,才能得到我们需要的那个值。

run_queue的load值也是这样。有些进程可能频繁地在TASK_RUNNING和非TASK_RUNNING状态之间变换,导致run_queue的load值不断抖动。光看某一时刻的load值,我们是体会不到run_queue的负载情况的,必须将一段时间内的load值综合起来看才行。于是,run_queue结构中维护了一个保存load值的数组:

unsigned long cpu_load[CPU_LOAD_IDX_MAX] (目前CPU_LOAD_IDX_MAX值为5)
每个CPU上,每个tick的时钟中断会调用到update_cpu_load函数,来更新该CPU所对应的run_queue的cpu_load值。这个函数值得罗列一下:

cpu_load[i] = old_load + (new_load – old_load) / 2^i。i值越大,cpu_load[i]受load的实时值的影响越小,代表着越长时间内的平均负载情况。而cpu_load[0]就是实时的load。

尽管我们需要的是一段时间内的综合的负载情况,但是,为什么不是保存一个最合适的统计值,而要保存这么多的值呢?这是为了便于在不同场景下选择不同的load。如果希望进行进程迁移,那么应该选择较小的i值,因为此时的cpu_load[i]抖动比较大,容易发现不均衡;反之,如果希望保持稳定,那么应该选择较大的i值。

那么,什么时候倾向于进行迁移、什么时候又倾向于保持稳定呢?这要从两个维度来看:

第一个维度,是当前CPU的状态。这里会考虑三种CPU状态:

1、CPU刚进入IDLE(比如说CPU上唯一的TASK_RUNNING状态的进程睡眠去了),这时候是很渴望马上弄一个进程过来运行的,应该选择较小的i值;
2、CPU处于IDLE,这时候还是很渴望弄一个进程过来运行的,但是可能已经尝试过几次都无果了,故选择略大一点的i值;
3、CPU非IDLE,有进程正在运行,这时候就不太希望进程迁移了,会选择较大的i值;

第二个维度,是CPU的亲缘性。离得越近的CPU,进程迁移所造成的缓存失效的影响越小,应该选择较小的i值。比如两个CPU是同一物理CPU的同一核心通过SMT(超线程技术)虚拟出来的,那么它们的缓存大部分是共享的。进程在它们之间迁移代价较小。反之则应该选择较大的i值。(后面将会看到linux通过调度域来管理CPU的亲缘性。)

至于具体的i的取值,就是具体策略的问题了,应该是根据经验或实验结果得出来的,这里就不赘述了。

调度域

前面已经多次提到了调度域(sched_domain)。在复杂的SMP系统中,为了描述CPU与CPU之间的亲缘关系,引入了调度域。

两个CPU之间的亲缘关系主要有以下几种:

1、超线程。超线程CPU是一个可以“同时”执行几个线程的CPU。就像操作系统通过进程调度能够让多个进程“同时”在一个CPU上运行一样,超线程CPU也是通过这样的分时复用技术来实现几个线程的“同时”执行的。这样做之所以能够提高执行效率,是因为CPU的速度比内存速度快很多(一个数量级以上)。如果cache不能命中,CPU在等待内存的时间内将无事可做,可以切换到其他线程去执行。这样的多个线程对于操作系统来说就相当于多个CPU,它们共享着大部分的cache,非常之亲近;
2、同一物理CPU上的不同核心。现在的多核CPU大多属于这种情况,每个CPU核心都有独立执行程序的能力,而它们之间也会共享着一些cache;
3、同一NUMA结点上的CPU;
4、不同NUMA结点上的CPU;

在NUMA(非一致性内存体系)中,CPU和RAM以“结点”为单位分组。当CPU访问与它同在一个结点的“本地”RAM芯片时,几乎不会有竞争,访问速度通常很快。相反的,CPU访问它所属结点之外的“远程”RAM芯片就会非常慢。

(调度域可以支持非常复杂的硬件系统,但是我们通常遇到的SMP一般是:一个物理CPU包含N个核心。这种情况下,所有CPU之间的亲缘性都是相同的,引入调度域的意义其实并不大。)

进程在两个很亲近的CPU之间迁移,代价较小,因为还有一部分cache可以继续使用;在属于同一NUMA结点上的两个CPU之间迁移,虽然cache会全部丢失,但是好歹内存访问的速度是相同的;如果进程在属于不同NUMA结点的两个CPU之间迁移,那么这个进程将在新NUMA结点的CPU上被执行,却还是要访问旧NUMA结点的内存(进程可以迁移,内存却没法迁移),速度就要慢很多了。

通过调度域的描述,内核就可以知道CPU与CPU的亲缘关系。对于关系远的CPU,尽量少在它们之间迁移进程;而对于关系近的CPU,则可以容忍较多一些的进程迁移。

对于实时进程的负载均衡,调度域的作用比较小,主要是在push_rt_task将当前run_queue中的实时进程推到其他run_queue时,如果有多个run_queue可以接收实时进程,则按照调度域的描述,选择亲缘性最高的那个CPU对应的run_queue(如果这样的CPU有多个,那么约定选择编号最小那一个)。所以,下面着重讨论普通进程的负载均衡。

首先,调度域具体是如何描述CPU之间的亲缘关系的呢?假设系统中有两个物理CPU、每个物理CPU有两个核心、每个核心又通过超线程技术虚拟出两个CPU,则调度域的结构如下:


1、一个调度域是若干CPU的集合,这些CPU都是满足一定的亲缘关系的(比如至少是属于同一NUMA结点的);
2、调度域之间存在层次关系,一个调度域可能包括多个子调度域,每个子调度域包含了父调度域的一个CPU子集,并且子调度域中的CPU满足比父调度域更严格的亲缘关系(比如父调度域中的CPU至少是属于同一NUMA结点的,子调度域中的CPU至少是属于同一物理CPU的);
3、每个CPU分别具有其对应的一组sched_domain结构,这些调度域处于不同层次,但是都包含了这个CPU;
4、每个调度域被依次划分成多个组,每个组代表调度域的一个CPU子集;
5、最低层次的调度域包含了亲缘性最近的几个CPU、而最低层次的调度组则只包含一个CPU;

对于普通进程的负载均衡来说,在一个CPU上,每次触发load_balance总是在某个sched_domain上进行的。低层次的sched_domain包含的CPU有着较高的亲缘性,将以较高的频率被触发load_balance;而高层次的sched_domain包含的CPU有着较低的亲缘性,将以较低的频率被触发load_balance。为了实现这个,sched_domain里面记录着每次load_balance的时间间隔,以及下次触发load_balance的时间。

前面讨论过,普通进程的load_balance第一步是需要找出一个最繁忙的CPU,实际上这是通过两个步骤来实现的:

1、找出sched_domain下最繁忙的一个sched_group(组内的CPU对应的run_queue的load之和最高);
2、从该sched_group下找出最繁忙的CPU;

可见,load_balance实际上是实现了对应sched_domain下的sched_group之间的平衡。较高层次的sched_domain包含了很多CPU,但是在这个sched_domain上的load_balance并不直接解决这些CPU之间的负载均衡,而只是解决sched_group之间的平衡(这又是load_balance的一大简化)。而最底层的sched_group是跟CPU一一对应的,所以最终还是实现了CPU之间的平衡。

其他问题

CPU亲和力

linux下的进程可以通过sched_setaffinity系统调用设置进程亲和力,限定进程只能在某些特定的CPU上运行。负载均衡必须考虑遵守这个限制(前面也多次提到)。

迁移线程

前面说到,在普通进程的load_balance过程中,如果负载不均衡,当前CPU会试图从最繁忙的run_queue中pull几个进程到自己的run_queue来。

但是如果进程迁移失败呢?当失败达到一定次数的时候,内核会试图让目标CPU主动push几个进程过来,这个过程叫做active_load_balance。这里的“一定次数”也是跟调度域的层次有关的,越低层次,则“一定次数”的值越小,越容易触发active_load_balance。

这里需要先解释一下,为什么load_balance的过程中迁移进程会失败呢?最繁忙run_queue中的进程,如果符合以下限制,则不能迁移:

1、进程的CPU亲和力限制了它不能在当前CPU上运行;
2、进程正在目标CPU上运行(正在运行的进程显然是不能直接迁移的);

(此外,如果进程在目标CPU上前一次运行的时间距离当前时间很小,那么该进程被cache的数据可能还有很多未被淘汰,则称该进程的cache还是热的。对于cache热的进程,也尽量不要迁移它们。但是在满足触发active_load_balance的条件之前,还是会先试图迁移它们。)

对于CPU亲和力有限制的进程(限制1),即使active_load_balance被触发,目标CPU也不能把它push过来。所以,实际上,触发active_load_balance的目的是要尝试把当时正在目标CPU上运行的那个进程弄过来(针对限制2)。

在每个CPU上都会运行一个迁移线程,active_load_balance要做的事情就是唤醒目标CPU上的迁移线程,让它执行active_load_balance的回调函数。在这个回调函数中尝试把原先因为正在运行而未能迁移的那个进程push过来。为什么load_balance的时候不能迁移,active_load_balance的回调函数中就可以了呢?因为这个回调函数是运行在目标CPU的迁移线程上的。一个CPU在同一时刻只能运行一个进程,既然这个迁移线程正在运行,那么期望被迁移的那个进程肯定不是正在被执行的,限制2被打破。

当然,在active_load_balance被触发,到回调函数在目标CPU上被执行之间,目标CPU上的TASK_RUNNING状态的进程可能发生一些变化,所以回调函数发起迁移的进程未必就只有之前因为限制2而未能被迁移的那一个,可能更多,也可能一个没有。

1 3 收藏 1 评论

相关文章

可能感兴趣的话题



直接登录
最新评论
跳到底部
返回顶部