在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的影响。）
推行到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值。这个函数值得罗列一下：
/* this_load便是run_queue实时的load值 */
unsigned long this_load = this_rq->load.weight;
for (i = 0, scale = 1; i < CPU_LOAD_IDX_MAX; i++, scale += scale) {
unsigned long old_load = this_rq->cpu_load[i];
unsigned long new_load = this_load;
/* 由于终究成果是要除以scale的，这儿相当于上取整 */
if (new_load > old_load)
new_load += scale-1;
/* cpu_load[i] = old_load + (new_load – old_load) / 2^i */
this_rq->cpu_load[i] = (old_load*(scale-1) + new_load) >> i;
}
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而未能被搬迁的那一个，或许更多，也或许一个没有。
