Linux CFS调度_nr_running

本文代码均基于主线4.19 LTS ，欢迎指正，持续更新。

目录

1. 度量

1.1 优先级

1.2 Weight

1.3 virtual runtime

1.4 physical runtime

1.5 nr_running

1.6 load三件套

1.6.1 衰减算法

1.6.2 load

1.6.3 blocked load

1.6.4 runnable load

 1.6.5 util

1.6.6 层级

1.7 capacity

1.8 task_h_load

2. 调度

2.1 红黑树

2.2 Timeline

2.3 Period

2.4 层级

 2.5 Quota

2.5.1 cfs_period_us和cfs_quota_us

2.5.2 CPU时间的统计

2.5.2 如何节流

2.5.2 如何恢复

3 负载均衡

3.1 调度域

3.2 load imbalance

3.2.1 busiest group

3.2.2 imbalance

3.2.3 busiest rq

3.3 Wakeup

3.3.1 Cache Hot

3.3.2 IDLE CPU

4 问题讨论

4.1 cfs_quota和cpuset

---

1. 度量

1.1 优先级

ps ax -o pid,ni,pri,cmd
  pid ni  pri cmd
  255 -20  39 [kworker/40:0H]
  256   0  19 [cpuhp/41]
  257   - 139 [watchdog/41]
  258   - 139 [migration/41]
  259   0  19 [ksoftirqd/41]

对于使用cfs的进程，我们会看到有两个优先级 

• Nice，范围是19 ~ -20，值越小优先级越高；nice是一个POSIX系统调用，UNIX和类UNIX系统上(比如Linux)的通用接口，用来设置用户态进程的优先级；
• Prio，这是Linux原生的，范围是0 ~ 149；

在内核中，nice值会被转换成prio，具体可以参考宏NICE_TO_PRIO()。

1.2 Weight

每个调度实体都拥有一个权重，即sched_entity.load.weight。

对于一个普通进程，task_struct.se.load.weight来自其优先级，具体可以参考，

const int sched_prio_to_weight[40] = {
 /* -20 */     88761,     71755,     56483,     46273,     36291,
 /* -15 */     29154,     23254,     18705,     14949,     11916,
 /* -10 */      9548,      7620,      6100,      4904,      3906,
 /*  -5 */      3121,      2501,      1991,      1586,      1277,
 /*   0 */      1024,       820,       655,       526,       423,
 /*   5 */       335,       272,       215,       172,       137,
 /*  10 */       110,        87,        70,        56,        45,
 /*  15 */        36,        29,        23,        18,        15,
};
 
当nice值增长1，weight增大25%，这是为了保证，
“ cfs scheduling algorithm guarantee, if you go up 1 level, it's -10% CPU usage,
if you go down 1 level it's +10% CPU usage.”
 
比如，我们有nice 0和nice 1两个任务跑在一个cpu上，
 
task with nice 0 get 1.25/2.25 = 0.55 cpu time
task with nice 1 get 1/2.25 = 0.44 cpu time
 
it is about 0.11 gap here

对于一个任务组，其包含了两组per-cpu的结构，

• sched_entity，用于参与上层cfs_rq的调度，
• cfs_rq，用于调度子sched_entity，

它们每个都包含了load.weight，

• cfs_rq的load.weight是enqueue的子sched_entity的load.weight的和，参考account_entity_enqueue/dequeue()
• sched_entity的load.weight按照一定的比例从task_group.shares划分而来，即下面的公式：

 
                      tg->shares * grq->load.weight
   ge->load.weight = -----------------------------
 			              Sum grq->load.weight
 
ge  : task group per-cpu sched_entity
grp : task group per-cpu cfs_rq
具体计算过程与上述公式略有差别，详情参考calc_group_shares()函数及其注释

1.3 virtual runtime

即sched_entity.vruntime，其决定的是该调度实体在红黑树cfs_rq.tasks_timeline中的位置，决定了该调度实体何时可以被调度；其计算方式如下：

static inline u64 calc_delta_fair(u64 delta, struct sched_entity *se)
{
	if (unlikely(se->load.weight != NICE_0_LOAD))
		delta = __calc_delta(delta, NICE_0_LOAD, &se->load);
 
	return delta;
}
计算公式为，vruntime = (delta_exec * NICE_0_LOAD) / se.load.weight

对照sched_prio_to_weight可知，优先级越高，weight越大，则vruntime增长的越慢，在红黑树上的位置向右移动的速度越慢，则可以越多的执行时间。

1.4 physical runtime

即当前正在运行的调度实体已经运行的物理时间，

update_curr()
---
	u64 now = rq_clock_task(rq_of(cfs_rq));
	...
	delta_exec = now - curr->exec_start;
	curr->exec_start = now;
	curr->sum_exec_runtime += delta_exec;
---

该时间本身并无特殊之处，其主要用途包括，

• 保证调度周期每个任务都被调度一次，
•  CFS带宽控制，即cpu.cfs_quota_us

1.5 nr_running

跟cfs有关的nr_running有三个，

• rq.nr_running，rq上所有的运行的任务的数量，包括了所有的调度类，可以参考add_nr_running()的调用；
• cfs_rq.nr_running，该cfs_rq上调度实例的数量，参考account_entity_enqueue();
• cfs_rq.h_nr_running，该cfs_rq下所有的任务的数量，包括所有的子cgroup；具体可以参考函数unthrottle_cfs_rq()，在遇到on_rq的se之后，依然继续向上累加。

综上，rq.nr_running是在rq上所有的running的任务的数量，而rq.cfs.h_nr_running则代表所有的cfs任务的数量，基于此，pick_next_task()通过两者是否相等判断该rq上是否只有cfs任务，

	/*
	 * Optimization: we know that if all tasks are in the fair class we can
	 * call that function directly, but only if the @prev task wasn't of a
	 * higher scheduling class, because otherwise those loose the
	 * opportunity to pull in more work from other CPUs.
	 */
	if (likely((prev->sched_class == &idle_sched_class ||
		    prev->sched_class == &fair_sched_class) &&
		   rq->nr_running == rq->cfs.h_nr_running)) {
 
		p = pick_next_task_fair(rq, prev, rf);

1.6 load三件套

1.6.1 衰减算法

cfs在计算load的时候，引入了一个衰减算法，如下：

 V = Y*P + delta
 
 Y : decay factor, Y^32 = 0.5, Y ~= 0.9785
 P : previous value of V
 
用下面的程序模拟一个Long running task的计算过程，
int main(int argc, const char *argv[]) 
{
	float y, p;
	int i, s, d, m;
 
	y = 0.9785;
	p = d = 1000;
	s = atoi(argv[1]);
	m = atoi(argv[2]);
 
	for (i = 0; i < m; i++) {
		if (i % s)
			p = p * y;
		else
			p = p * y + d;
 
		printf("%.0f\n", p);
	}
 
	return 0;
}

                 ​​​​​

可以看到有两个点：

• 在delta一定的情况下，最终的load值会有一个最大值，在内核代码中，delta的值为1024，load的最大值是47732；
• step越大，则load的最大值越小，这里的step模拟的是程序的wait & work的工作过程；由此可知，对于经常睡眠等待资源的进程来说，其load值不会很大。

如果我们让load一直衰减，也就是delta一直为0时，如下：

#include <stdio.h>
#include <stdlib.h>
 
int main(int argc, const char *argv[]) 
{
	float y, p;
	int i, s, d, m;
 
	y = 0.9785;
	p = d = 1024;
	s = atoi(argv[1]);
	m = atoi(argv[2]);
 
	for (i = 0; i < m; i++) {
		if (i % s)
			p = p * y;
		else
			p = p * y + d;
 
		printf("%.0f\n", p);
	}
 
	while ((int)p) {
		p = p * y;
		printf("%.0f\n", p);
	}
 
	return 0;
}

                                        

可以看到，load从最大值衰减到0会经历一定的时间。

 接下来我们看下cfs如何使用这个算法计算load_avg，参考函数___update_load_sum()

static int ___update_load_sum(u64 now, struct sched_avg *sa,
		  unsigned long load, unsigned long runnable, int running)
 
load, runnable, running 
     : 累加delta时的系数，这三个系数分别用来统计三种类型的load
now  : 来自cfs_rq_clock_pelt()，该函数将该cfs_rq被throttle的时间去掉了，参考
       throttle/unthrottle_cfs_rq()，在被throttle期间，se.on_rq是0，也就是说，
       在load_avg计算中，throttle状态不算离开cpu。
last_update_time:
       该load_avg的上次更新时间，参考函数update_load_avg()的调用点，涵盖了所有的
       sched_entity状态更新函数；now - last_update_time就是delta，1024ns为一个
       衰减周期
 
结果保存在sum中(有load_sum, runnable_sum, util_sum三种)，计算公式可以大致表
 
               Sum = Sum * Decay + delta * Factor
 
 
___update_load_avg()则计算出avg，同样有(load, runnable, util三种)，算法大致如下：
 
               Avg = (Factor * Sum) / divider
 
divider : 近似等于LOAD_AVG_MAX，在解释load算法时，我们说过，delta一定的情况下，
          load计算出的最大值是一定的
 
FIXME: 不太理解这里为什么称为平均值，Max是step = 1，也就是任务一直处于running状态的Sum， 
       Sum/Max的意义更像是评估任务的 - 忙碌程度

在下文中，我们统一称，计算Sum的Factor为Sum_Factor， 计算Avg的Factor为Avg_Factor，Sum/Max称为Busy_Factor。

1.6.2 load

uptime命令中显示的load，统计的是系统中处于running状态和waitio状态的任务的数量；接下来我们看下cfs中的load表征的是什么？

在cfs调度算法中，有两个实例拥有load，即sched_entity和cfs_rq，下面我们分别开下，他们是如何计算的，

更新sched_entity的load_avg，
int __update_load_avg_se(u64 now, struct cfs_rq *cfs_rq, struct sched_entity *se)
{
	if (___update_load_sum(now, cpu, &se->avg, !!se->on_rq, !!se->on_rq,
				cfs_rq->curr == se)) {
 
		___update_load_avg(&se->avg, se_weight(se), se_runnable(se));
}
 
!!se->on_rq   : Sum_Factor，0或者1代表该实例是否被调度
se_weight(se) : Avg_Factor，即该sched_entity的load.weight
 
 
load_avg的意义是 weight * Busy_Factor
如果该任务100% busy，则load_avg = weight，但是如果50% busy，load_avg = weight/2 
(参考load 计算时step = 2的情况，load最终的值大概只有step = 1时候的一半)

sched_entity的load_avg反映了它的load.weight和繁忙程度。

注意，这里的繁忙，并不是只是该任务被cpu运行，还包括处于就绪态，或者从linux内核的角度讲，处于running状态；这是非常合理的，load balance的一个重要的作用就是，避免一个cpu上累积了太多running的进程排队导致调度延迟。

cfs_rq的sched_avg反映的是其下所有的sched_entity的load.weight与繁忙程度；

• 在sched_entity的load avg在enqueue的时候，会被累加到cfs_rq.load_avg，而在dequeue的时候则被减掉；原因在于，load的计算方式，从0涨到最高值是需要一段时间的，如果不做sched_entity load_avg的加减，cfs_rq的load就会缺乏实时性。具体函数可参考，enqueue/dequeue_load_avg()；
• 在没有dequeue/enqueue时，cfs_rq.load_avg也会基于衰减算法更新，如下，

int __update_load_avg_cfs_rq(u64 now, struct cfs_rq *cfs_rq)
{
	if (___update_load_sum(now, &cfs_rq->avg,
				scale_load_down(cfs_rq->load.weight),
				scale_load_down(cfs_rq->runnable_weight),
				cfs_rq->curr != NULL)) {
 
		___update_load_avg(&cfs_rq->avg, 1, 1);
	}
}
 
cfs_rq->load.weight : Sum_Factor是该cfs_rq上所有sched_entity的权重之和
         1          : __update_load_avg()的入参是 1，也就是
                      load_avg = load_sum / LOAD_AVG_MAX
 
那么为什么不让Sum_Factor = 1，而让Avg_Factor = cfs_rq.load.weight ?
 
__update_load_avg()中的计算覆盖过去所有的历史，这对于会频发发生enqueue/dequeue的cfs_rq来说
明显是不合理的；__update_load_sum()中对delta的累加系数则只针对刚刚过去的这段时间，且这段时间
并没有状态变化(每次调度状态的变化都会调用update_load_avg)。

 综上，cfs_rq的sched_avg反映的是位于其上的所有sched_entity的load.weight和繁忙程度。

1.6.3 blocked load

对于因等待资源而block的任务的load，cfs如何处理？load的算法会让load值在之后的时间里相对平滑的衰减；一个sched_entity的load，在对一个任务被blocked之后，load值不会立刻减到0，而是有一个平滑的衰减的过程；也就是说，即使一个任务不处于running状态，其仍然可能拥有一个不为0的load，我们称之为blocked load(FIXME: 个人理解)。

cfs_rq的load也遵从了类似的规则，在任务被从队列dequeue之后，其load_avg并不会立即从队列的load_avg中减掉，而是只将任务的load.weight从cfs_rq的load.weight中减掉；在之后的运行过程中，因为cfs_rq.load.weight减小，cfs_rq的load_avg会发生衰减。

当任务被dequeue/enqueue的时候，
(1) 将sched_entity.load.weight从cfs_rq.load.weight减掉或者加上，具体参考 
    account_enqueue/dequeue_entity()
(2) 对cfs_rq load_avg不会做任何操作；enqueue/dequeue_load_avg()会操作cfs_rq
    load_avg，但是这两个函数是在任务cpu迁移的时候被调用的
 
任务在cpu之间迁移主要有两个场景，
(1) load balance时的cpu迁移，
(2) wakeup的时候选择了另外一个cpu，
相关代码可以参考
set_task_cpu() -> migrate_task_rq_fair()
enqueue_entity() -> update_load_avg()
//The code branch check se.avg.last_update_time and DO_ATTACH flag

1.6.4 runnable load

为什么需要runnable load ？官方解释是，

'runnable load' was originally introduced to take into account the case
where blocked load biases the load balance decision which was selecting
underutilized groups with huge blocked load whereas other groups were
overloaded.

当任务睡眠被dequeue之后，所在的队列的load会逐渐衰减。但是在这个衰减的过程中，blocked load仍然存在；于是可能出现，一个cpu上大多数任务都处于blocked状态，并不需要多少cpu，而另外一个cpu上，多个处于running状态的任务排队；runnable load avg就是为了避免出现这个场景。

下面我们看下，runnable load如何统计，

• 与load不同，在enqueue/dequeue的时候，sched_entity的runnbale load_avg会从cfs_rq中被加上或者减掉，这个是runnable load的关键；参考函数，enqueue/dequeue_runnable_load_avg()；
• 参考函数__update_load_avg_se()与__update_load_avg_cfs_rq()，runnable load_avg的计算方式几乎与load一模一样，唯一的区别是它的Sum_Factor和Avg_Factor都使用了runnable_weight；

runnable weight的计算要分成两种情况，

• 普通任务的调度实体的runnable weight就是load.weight，
• task_group的per-cpu调度实体的runnable weight通过如下公式计算，

 
 			       	                       grq->avg.runnable_load_avg
   ge->runnable_weight = ge->load.weight * -------------------------- 
 						                         grq->avg.load_avg
 
这个计算过程会在以下函数发生，所以，runnabel_weight实时性很强
enqueue_entity() \
dequeue_entity()  > update_cfs_group -> calc_group_runnable()
entity_tick()    /

 1.6.5 util

cfs中有两个利用率，util和util_est，我们先说第一个，它使用了跟load一样的算法，不过Sum_Factor有两个，

• 对于sched_entity为cfs_rq->curr == se，cfs_rq的为!!cfs_rq->curr，这代表着该sched_entity或者cfs_rq对应的sched_entity是否正在被cpu运行(注意，这与load是不同的，load的统计关注的是任务是否处于running状态)；相关函数可参考set/put_next_enity()；
• arch_scale_cpu_capacity()，这是为了同cpu capacity做比较；

Avg_Factor为1，所以util反映的是sched_entity或者cfs_rq所占用的cpu capacity。

跟load类似，sched_entity的util也不会在enqueue/dequeue之后被从cfs_rq的util中加上或者减掉，而只是在attach/detach的时候；函数可以参考，attach/detach_entity_load_avg()。

1.6.6 层级

前几小结提到的有关enqueue/dequeue和attach/detach的load变更，在不存在cgroup的情况下，非常好理解；但是，如果加入了cgroup层级，最底层task_struct.sched_entity的sched_avg的变更，如何传导到最顶层的rq.cfs_rq ？

首先我们看enqueue/dequeue的场景：

以dequeue场景为例，
 
                           rq.cfs_rq
                               |
                          tg  se
                              cfs_rq0
                              / | \
                           se0 se1 se2
                                   ^^^^
                                  dequeue
dequeue_runnable_load_avg()的影响如何能传导到上层？
答案在update_cfs_group()，
 
(1) dequeue虽然将se2.load.weight从cfs_rq0.load.weight中减掉了，但
    cfs_rq0.avg.load_avg和tg.load_avg并不会发生变化，因为dequeue并
    不会操作load，而tg.load_avg需要等待cfs_rq0.avg.load_avg衰减，参
    考函数upate_tg_load_avg()，所以，参考函数calc_group_shares()，
    se.load.weight并不会立刻变化；
 
(2) cfs_rq0.load.weight和avg.runnable_load_avg/sum都已经变小，参考
    函数calc_group_runnable()，se.runnable_weight也会变小，
 
到这里，相关更新传导到了se2所在的cfs_rq0的se；
 
(3) 参考函数reweight_entity()
reweight_entity //函数做了裁剪
---
	if (se->on_rq) {
		dequeue_runnable_load_avg(cfs_rq, se);
	}
 
	se->runnable_weight = runnable;
	update_load_set(&se->load, weight);
 
	do {
		u32 divider = LOAD_AVG_MAX - 1024 + se->avg.period_contrib;
 
		se->avg.load_avg = div_u64(se_weight(se) * se->avg.load_sum, divider);
		se->avg.runnable_load_avg =
			div_u64(se_runnable(se) * se->avg.runnable_load_sum, divider);
	} while (0);
 
	if (se->on_rq) {
		enqueue_runnable_load_avg(cfs_rq, se);
	}
---
 
se的runnable_load_avg在这里根据新的runnable_weight做了新的计算，然后重新累加到
rq.cfs_rq，由此，便传导到了最顶层。

enqueue/dequeue主要发生在任务wait & wakeup的时候，而attach/detach 主要发生在，task在cpu之前迁移的时候，例如：

• load balance时的迁移，可参考attch_tasks/detach_tasks()
• 任务在睡眠之后，重新选择一个新的cpu，也可以认为是发生了cpu的迁移，参考set_task_cpu()->migrate_task_rq_fair()

在attach/detach的时候，load、runnable load和util全都会发生迁移；具体可以参考函数

attch_entity_load_avg()和detach_entity_load_avg()
这两个函数还会通过propagate机制，将相关更新一层一层向上传递。
 
                    cfs_rq
                       |
                   tg  se
                       cfs_rq0
                      / | \
                   se0 se1 se2 [new]
 
(1) 当se2被enqueue到cfs_rq0时，其相关load信息也会被更新到cfs_rq0，参考
    attach_entity_load_avg()，同时调用add_tg_cfs_propagate()将
    se2.avg.load_sum向上传递
(2) update_tg_cfs_runnable()会重新计算se的load信息，并根据se load
    信息的delta，向cfs_rq更新
 
 
如果仔细观察propagate_entity_load_avg()，
---
	cfs_rq = cfs_rq_of(se);
 
	add_tg_cfs_propagate(cfs_rq, gcfs_rq->prop_runnable_sum);
                                 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
	update_tg_cfs_util(cfs_rq, se, gcfs_rq);
	update_tg_cfs_runnable(cfs_rq, se, gcfs_rq);
---
 
此处直接向上跨级propagate，不需要考虑weight吗？
 
参考load和runnable load，se的load sum的Sum_Factor都是!!se->on_rq，
并没有引入weight

1.7 capacity

capacity指的是cpu的能力，参考函数arch_scale_cpu_capacity()，

• 3和4都是SCHED_CAPACITY_SCALE，是个常量，
• 1和2对应的是arm架构大小核，

big.LITTLE – Arm®

Arm big.LITTLE technology is a heterogeneous processing architecture that uses two types of processor. ”LITTLE” processors are designed for maximum power efficiency while ”big” processors are designed to provide maximum compute performance. With two dedicated processors, the big.LITTLE solution is able to adjust to the dynamic usage pattern for smartphones, tablets and other devices. Big.LITTLE adjusts to periods of high-processing intensity, such as those seen in mobile gaming and web browsing, alternate with typically longer periods of low-processing intensity tasks such as texting, e-mail and audio, and quiescent periods during complex apps.

那么是不是非arm架构的cpu，他们的capacity就是一样的呢？

参考函数，scale_rt_capacity()，cpu可以给cfs任务使用的capacity为，
 
max = arch_scale_cpu_capacity(sd, rq)
higher = rq->avg_rt.util_avg + rq->avg_dl.util_avg
irq = cpu_util_irq(rq)
 
free = (max - higher) * (max - irq) / max

在runqueue中，保存了两个capacity，

• capacity，来自scale_rt_capacity()，
• capacity_orig，来自 arch_scale_cpu_capacity

函数check_cpu_capacity()，可用来检查side activity(包括，hardirq, softirq, 
rt任务，dl任务等)是否占用了过多的CPU，判断公式为，
  ((rq->cpu_capacity * sd->imbalance_pct) < (rq->cpu_capacity_orig * 100))

1.8 task_h_load

task_h_load()一个任务的avg_load，我们不能简单的使用task_struct.se.avg.load_avg，而需要考虑层级；

cfs的层级关系如下：
           root_task_group rq
                           cfs_rq
                           |
                      tg0  se0
                           cfs_rq0
                           |
                      tg1  se1
                           cfs_rq1
                           |
                      task se2
                            
h_load = cfs_rq.avg.load_avg;
 
task's h_load = h_load * (se0.load_avg/cfs_rq.load_avg)
                       * (se1.load_avg/cfs_rq0.load_avg)
                       * (se2.load_avg/cfs_rq1.load_avg)

2. 调度

2.1 红黑树

作为内核中最常用的两种数据结构之一(另外一个是list)，红黑树并不是cfs专用的；但是，我们需要明白cfs算法为什么要选用红黑树？

• It is self balancing: no path in the tree will ever be more than twice as long as any other.
• Operations (insertion, search and delete) occur in O(log n) time (where n is the number of nodes in the tree)

因为红黑树算法稳定，增删查的时间复杂度都是O(log n)，这也反映了cfs是一种通用型调度算法。

作为对比，我们可以参考rt调度算法的数据结构，是一个以优先级为索引的链表数组，通过bitmap来标明哪一个优先级有可运行的任务，参考函数pick_next_rt_entity()、__enqueue_rt_entity(), __dequeue_rt_entity，其时间复杂度为O(1)；不过rt调度算法在选取任务的时候，并不考虑任务的运行时间，而只考虑优先级，所以，可以采用这种相对高效的数据结构。

而cfs算法，在选取任务的时候，需要考虑任务已经运行的时间，以保证公平性，所以，在enqueue的时候，需要对元素进行排序，所以具有稳定性能的红黑树就成了cfs的选择。

任务什么时候"上树"？什么时候"下树" ？

参考__enqueue_entity/__dequeue_entity的调用链，我们总结出，cfs调度器的红黑树上保存的是处于"就绪态"的任务；之所以打上引号，是因为linux内核中并没有一个叫做就绪态的任务状态，而只有TASK_RUNNING；但实际上，真正运行态的任务，每个CPU只有一个(即rq.curr)，它并不在cfs调度器的红黑树上，具体可以参考set_next_task()/put_prev_task()函数。

注：红黑树只维护就绪态任务，这符合调度器的设计；同时，我们假设正在运行的任务如果也放到树上的话，因为是以vruntime为索引，那么每次更新vruntime都需要更新该任务在树中的位置，这操作起来比较费CPU吧。

常规的wait/wakeup场景很好理解，参考enqueue/dequeue_entity()。

2.2 Timeline

基于virtual runtime的sched entity的排序是cfs算法的核心；vruntime决定了sched entity在cfs_timeline红黑树中的位置，也就决定了这个任务什么时候被pick调度。那么vruntime都会在什么时间被更新？

首先是正常运行状态增量，如下

最常见的场景，在update_curr()
 
curr->vruntime += calc_delta_fair(delta_exec, curr)
 
根据已经运行的时间和sched_entity的weight计算vruntime的增量

 但是当进程睡眠之后被唤醒，如果直接将任务放到红黑树里，其vruntime的值可能远小于其他任务，而"饿死"其他任务；cfs算法做了如下处理，参考函数place_entity()，

se->vruntime = max_vruntime(se->vruntime, cfs_rq->min_vruntime - thresh)

thresh = sysctl_sched_latency

对于一个睡眠较长时间的任务来说，被唤醒之后，会在下一轮中被首先调度，甚至thresh还可以让它抢占正在运行的任务，不过，GENTLE_FAIR_SLEEPS 可以弱化这个效果，参考它的注释：

Only give sleepers 50% of their service deficit. This allows them to run sooner, but does not allow tons of sleepers to rip the spread apart.

对于迁移进程，由于不同的CPU的min_vruntime有差异，所以为了保证公平性，会对任务做normalize，也就是保证任务在cfs_rq中的相对位置，方式如下：

MIGRATION: dequeue (vruntime -= min_vruntime) enqueue (vruntime += min_vruntime)

WAKEUP (remote): 

migrate_task_rq_fair() (p->state == TASK_WAKING) (vruntime -= min_vruntime)

enqueue (vruntime += min_vruntime)

对于一个新创建的进程，该赋予多少vruntime呢？参考函数task_fair_fork()，基本上，子任务会继承父任务在红黑树中的相对位置，可以参考下面的代码

task_fork_fair()
---
	cfs_rq = task_cfs_rq(current);
	curr = cfs_rq->curr;
	if (curr) {
		update_curr(cfs_rq);
		se->vruntime = curr->vruntime;
	}
	place_entity(cfs_rq, se, 1);
 
	if (sysctl_sched_child_runs_first && curr && entity_before(curr, se)) {
		/*
		 * Upon rescheduling, sched_class::put_prev_task() will place
		 * 'current' within the tree based on its new key value.
		 */
		swap(curr->vruntime, se->vruntime);
		resched_curr(rq);
	}
 
	se->vruntime -= cfs_rq->min_vruntime;
 
---

2.3 Period

cfs调度算法有一个基本保证，即，在一个调度周期内，每个cpu上的所有任务都必须得到一次调度。调度周期的其计算方式为：

static u64 __sched_period(unsigned long nr_running)
{
	if (unlikely(nr_running > sched_nr_latency))
		return nr_running * sysctl_sched_min_granularity;
	else
		return sysctl_sched_latency;
}
 
sched_nr_latency               : 8       by default
sysctl_sched_min_granularity   : 0.75 ms by default
sysctl_sched_latency           : 6 ms    by default

sched_slice()用于计算每个任务在每个调度周期中可以分得的份额，其并非平均分配，而是按照load.weight比例划分，其计算公式是，

slice = slice * se.load.weight / cfs_rq.load.weight

当一个进程超过其sched_slice()时，就会被抢占，然后scheduler会pick下一个进程出来。

check_preempt_tick()
---
    ideal_runtime = sched_slice(cfs_rq, curr);
    delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;
    if (delta_exec > ideal_runtime) {
        resched_curr(rq_of(cfs_rq));
        ...
        return;
    }
----

需要说明的是，决定一个任务所能分得的CPU时间的并不是这个机制，而是vruntime的算法(参考1.3小节)；以上机制确保的是任务的调度延迟，而这，也是公平性的一部分。

2.4 层级

之所以需要层级，是因为调度任务组的引入；任务组即需要以一个整体参与调度，又需要调度组内的任务，所以，每个任务组都包含了每CPU的sched_entity，用来以整体的方式参与调度，同时，每CPU的cfs_rq用来维护组内的任务或者子任务组；这里有两点需要说明：

任务组的每CPU的sched_entity/cfs_rq；每个任务组在每个cpu上都有一个sched_entity/cfs_rq，参与每CPU的runquue的调度；这里的cfs_rq的每CPU是比较好理解的，因为runqueue都是每CPU的，任务调度的核心是分享CPU资源；但是任务组的sched_entity也是每CPU的，而普通任务只需一个sched_entity，原因是？任务组每个CPU上的sched_entity代表的并不是整个任务组，而是，该任务组在该CPU上“分组”，参考下图：

 
task_group A { task_A0, task_A1, task_A2, task_A3 }
 
 
        CPU0                     CPU1
         rq0                      rq1
     cfs_rq0                  cfs_rq1 
      /    \                     |
  se_0      se_A0               se_A1 
task_0  cfs_rq_A0           cfs_rq_A1
          /    \              /    \
     se_A0    se_A1       se_A2   se_A3
   task_A0  task_A1     task_A2 task_A3
 
一个任务组中的任务，是可能分布在多个CPU上的

任务组如何参与调度？

 
task_group A { task_A0, task_A1 }
 
 
        CPU0
         rq0 (curr = task_1)
     cfs_rq0 (curr = se_1)
      /    \
  se_0      SE_A0
task_0  cfs_rq_A0
          /    \
     se_A0    se_A1
   task_A0  task_A1
 
 
task_1.se_1让出CPU，从rq0.cfs_rq0上选择SE_A0，
 
 
        CPU0
         rq0                               SE_A0
     cfs_rq0 (curr = SE_A0)            cfs_rq_A0
      /    \                               /   \
  se_0     se_1                        se_A0   se_A1  
task_0   task_1                      task_A0 task_A1
 
在cfs_rq_A0上选择出se_A1，
 
 
        CPU0
         rq0 (curr = task_A1)              SE_A0
     cfs_rq0 (curr = SE_A0)            cfs_rq_A0 (curr= se_A1)
      /    \                                |  
  se_0     se_1                           se_A0    
task_0   task_1                         task_A0

 在上图中，se_0(代表任务0)和se_A0(代表任务组A)是平级的，它们会首先根据各自的优先级(任务组的优先级就是cpu.shares)瓜分CPU0的时间；然后，se_A0获得的CPU0的时间再被task_A0和task_A1瓜分。参考下面的试验：

a.out is a while(1).
1 a.out is running under root group,
4 a.out are running under a cgroup with shares 1024
 
top:
  PID USER      PR  NI    VIRT    RES    SHR S  %CPU %MEM     TIME+ COMMAND                               
36006 root      20   0    4176    652    576 R  49.8  0.0   7:34.66 a.out                                 
35675 root      20   0    4176    648    576 R  12.6  0.0   1:56.88 a.out                                 
35677 root      20   0    4176    712    636 R  12.6  0.0   1:56.31 a.out                                 
35679 root      20   0    4176    656    584 R  12.6  0.0   1:56.20 a.out                                 
35676 root      20   0    4176    612    540 R  12.3  0.0   1:56.49 a.out 

任务组的sched_entity和cfs_rq在整个runqueue中层级关系如下：

        [sched]     [parent]  [cfs_rq]  
global  rq          NULL                
	    cfs_rq      ^         rq.cfs_rq 
	    |           |            ^      
	    v           |            |      
    tg  se          se        se.cfs_rq 
        cfs_rq      ^         se.my_q   
        |           |            ^      
		v           |            |      
    tg  se          se        se.cfs_rq 
        cfs_rq      ^         se.my_q   
	    |           |            ^      
	    v           |            |      
  task  se          se        se.cfs_rq

 2.5 Quota

CPU Quota用来设置任务组可以用使用的CPU时间上限；其主要有两个参数，cfs_quota_us和cfs_period_us，语义是，该任务组内的任务，在cfs_period_us这段时间内，使用的CPU时间的上限是cfs_quota_us。在cfs代码中，CPU Quota的实现基于cfs bandwidth control机制。

2.5.1 cfs_period_us和cfs_quota_us

cfs_period_us指的这段时间，是系统内所有CPU上并行的时间，比如各个CPU都是从01:30 -> 01:31；cfs_quota_us是所有CPU上的任务组使用的CPU时间总和。

如果这个任务组中有两个任务，cpu利用率都是100%
task_group A (task0, task1)
period = 100   quota = 100
 
CPU0 ----+XX--+XX--+XX--+XX--+XX-->
 
CPU1 ----+XX--+XX--+XX--+XX--+XX-->
 
CPU2 ----+----+----+----+----+---->
 
CPU3 ----+----+----+----+----+---->
 
task_group A (task0, task1)
period = 100   quota = 200
 
CPU0 -----+XXXX+XXXX+XXXX+XXXX+XXXX>
 
CPU1 -----+XXXX+XXXX+XXXX+XXXX+XXXX>
 
CPU2 ----+----+----+----+----+---->
 
CPU3 ----+----+----+----+----+---->
 
 
如果这个任务组中有四个任务，cpu利用率都是100%
task_group A (task0, task1, task2, task3)
period = 100   quota = 100
 
CPU0 ----+X---+X---+X---+X---+X--->
 
CPU1 ----+X---+X---+X---+X---+X--->
 
CPU2 ----+X---+X---+X---+X---+X--->
 
CPU3 ----+X---+X---+X---+X---+X--->
 
task_group A (task0, task1, task2, task3)
period = 100   quota = 200
 
CPU0 ----+XX--+XX--+XX--+XX--+XX-->
 
CPU1 ----+XX--+XX--+XX--+XX--+XX-->
 
CPU2 ----+XX--+XX--+XX--+XX--+XX-->
 
CPU3 ----+XX--+XX--+XX--+XX--+XX-->
 

2.5.2 CPU时间的统计

支持cfs bandwidth control或者quota机制的，有3个和时间有关测变量：

• task_group.cfs_bandwidth.runtime，这是整个任务组在一个period内的CPU时间quota的余量；每个period，会通过一个高精度定时器重新刷新，具体代码可以参考__refill_cfs_bandwidth_runtime()
• cfs_rq.runtime_remaining，每个cfs_rq的CPU时间quota，用于避免在统计时间时访问全局的task_group.cfs_bandwidth.runtime；每次会从全局中申请一个sysctl_sched_cfs_bandwidth_slice的值，默认是5us；参考函数assign_cfs_rq_runtime()。
• 任务的执行时间，参考以下：

• cfs_rq的当前sched_entity的执行时间计算方式：
  update_curr()
  ---
  	u64 now = rq_clock_task(rq_of(cfs_rq));
   
  	delta_exec = now - curr->exec_start;
   
  	curr->exec_start = now;
  ---
  同时，这个delta_exec会被计入当前cfs_rq，并从当前cfs_rq.runtime_remaining减掉，
  参考函数__account_cfs_rq_runtime()。
   
  考虑层级，
          CPU0
           rq0 (curr = task_1)
       cfs_rq0 (curr = se_1)
        /    \
    se_0      SE_A0
  task_0  cfs_rq_A0
            /    \
       se_A0    SE_B0
     task_A0    cfs_rq_B0
                 /    \
             se_B0     se_B1
           task_B0   task_B1
   
  task_B0和task_B1被调度时候，SE_B0一直在cfs_rq_A0上调度，SE_B0的执行时间都会
  计入cfs_rq_A0
  

2.5.2 如何节流

当cfs_rq.runtime_remaining无法从task_group.cfs_bandwidth.runtime获得CPU时间，即quota耗尽，当前cfs_rq就会被节流，上面的sched_entity无法被调度，如何办到？

• quota耗尽之后，当前正在运行的进程会被设置need_resched标记，参考函数__account_cfs_rq_runtime()，
• 当前进程在检测到抢占标记之后，让出CPU，在put_prev_entity()的时候，会调用check_cfs_rq_runtime()，紧接着进入throttle_cfs_rq()，
• throttle_cfs_rq()会将cfs_rq对应的sched_entity，从所在的cfs_rq上dequeue掉

 
        CPU0
         rq0 (curr = task_1)
     cfs_rq0 (curr = se_1)
      /    \
  se_0      SE_A0
task_0  cfs_rq_A0
          /    \
     se_A0    SE_B0
   task_A0    cfs_rq_B0
               /    \
           se_B0     se_B1
         task_B0   task_B1
 
当task_group B的quota用尽之后， SE_B0会被从cfs_rq_A0上dequeue下来，并保存在
task_group.cfs_bandwith.throttled_cfs_rq上，如下：
        CPU0
         rq0 (curr = task_1)   cfs_b_B.throttled_cfs_rq
     cfs_rq0 (curr = se_1)                  |
      /    \                            cfs_rq_B0
  se_0      SE_A0                         /    \
task_0  cfs_rq_A0                     se_B0   se_B1
          /                         task_B0 task_B1
     se_A0
   task_A0

2.5.2 如何恢复

在cfs_rq从task_group.cfs_bandwidth中申请runtime之后，就会启动period定时器；当定时器超时之后，会给当前task_group重新赋予quota，参考函数__refill_cfs_bandwidht_runtime()；然后，调用distribute_cfs_runtime()，将时间分配给被throttle的cfs_rq，并把它对应的sched_entity挂回它的父cfs_rq；这里我们重点关注下，在distribute_cfs_runtime()的时候，该cfs_rq分配多少CPU时间呢？

runtime = -cfs_rq->runtime_remaining + 1;

3 负载均衡

负载均衡的本质是给任务选择一个合适的CPU运行，以最大限度的利用现代CPU的多核并行架构，提高任务的性能和系统的整体吞吐；其主要分为两大部分：

• on-cpu任务的负载均衡，这里就是我们通常所讲的负载均衡；
• off-cpu任务的负载均衡，当任务被唤醒时，我们需要给人物选择一个合适的CPU，这也是负载均衡的一部分；

3.1 调度域

3.2 load imbalance

负载均衡的过程，其实是从别的CPU往本CPU拉任务以达到均衡的过程；对此，我们需要解答两个问题，

• 从哪个CPU拉？
• 拉几个任务？

3.2.1 busiest group

选择busiest group的时候，需要收集各个sched group的统计信息，这个过程是由函数update_sg_lb_stats()完成的，该函数会遍历sched_group.cpumask中的CPU以获得runqueue指针，这些信息包括，

选择最忙的sched_group参考函数update_sd_pick_busiest()，不考虑异构的话，主要依据为：

• group_type，也就是overloaded > imbalanced > other
• 如果group_type相同，则考虑avg_load

3.2.2 imbalance

在选择出busiest sched_group之后，还需要判断是不是存在imbalance，并且计算出imblance的load的值。判断方式参考函数find_busiest_group()，主要分成两种情况，

• 基于local sg的load_avg，比sd的avg_load更高，比busiest sg avg_load更高，或者基于imbalance_pct比busiest更高，则任务balanced
• balance cpu idle时，如果local sg capacity还有余力，而busiest没有，则强制balance；而如果busiest没有overload，且有更多的idle cpu，则认为balance....

在判断确实存在imbalance之后，我们需要计算一个imbalance的load的值，这个值将决定拉几个任务过来，具体计算方法请参考calculate_imbalance，我们这里只看下最简单的情况，

            ^
			|_ busiest sg avg_load \
			|                       > gap0
			|_         sd avg_load /      
			|                      \        
		    |                       > gap1
			|_   local sg avg_load /
 
 
            imbalance = min(gap0, gap1)

3.2.3 busiest rq

参考函数find_busiest_queue()，选取busiest queue时的判断标准是，

     weighted_cpuload      busiest_wl
     ----------------- >  -------------
      cpu_capacity         busiest_cap

选择好之后，将从这个run queue上拉取task，并将拉取的任务的task_h_load()，从imbalance中交掉，直到imbalance小于0为止；对于task_h_load() / 2 > imbalance的任务将被略过，具体参考detach_tasks()。 

3.3 Wakeup

Wakeup的时候，需要选择一个合适的CPU来唤醒任务，需要考虑的因素有：

• 调度延迟，即在runqueue中的排队时间；
• 微架构的Cache资源，包括i/dCache、L2Cache、i/dTLB、STLB等；对于CPU密集型任务，Cache的命中率对性能的影响非常大；

3.3.1 Cache Hot

对于存在热的Cache的CPU有两个选择：

• prev_cpu，即之前运行的CPU，上面可能存在着可用的Data和Instruction的Cache；
• wake_cpu，即对任务执行唤醒操作的CPU，例如典型的生产者/消费者模型，两个任务可能处理的是同一份数据，因此wake_cpu上可能存在着热的Data Cache；

3.3.2 IDLE CPU

核心代码在select_idle_sibling()，参考代码：

select_idle_sibling()
---
	sd = rcu_dereference(per_cpu(sd_llc, target));
	if (!sd)
		return target;
 
	i = select_idle_core(p, sd, target);
	if ((unsigned)i < nr_cpumask_bits)
		return i;
 
	i = select_idle_cpu(p, sd, target);
	if ((unsigned)i < nr_cpumask_bits)
		return i;
 
	i = select_idle_smt(p, sd, target);
	if ((unsigned)i < nr_cpumask_bits)
		return i;
---

其策略如下：

• sd_llc，选择与target在同一个last level cache的llc级调度域；这里决定的是，选择的大范围是与target在同一个numa节点上；
• select_idle_core与select_idle_cpu；idle core和idle cpu的选择策略可以参考下图；优先选择idle core然后idle cpu的基于的逻辑是，超线程技术是一种微架构资源的分时共享技术，两个运行在同一个物理核上的两个逻辑核上的任务，互相之间会对微架构资源，比如cache和一些计算资源，存在一定的争抢，影响彼此的性能； 
• select_idle_smt，既没有idle core，也没有idle cpu，那么smt siblings肯定也不是idle的，所以，4.19 LTS这里的逻辑并不太合理；参考最新的6.0的代码如下：

4 问题讨论

4.1 cfs_quota和cpuset

理论上两种方式都可以实现给cgroup限流的结果，但是哪种方式更好呢？

下面理论上的推算，调度对性能的影响，主要包括两方面：

• 调度延迟，即从任务被唤醒到真正被运行的时间间隔；从这个角度讲，在没有引起cfs throttle的情况下，cfs quota可利用的CPU数量更多，任务运行的并行度也自然更高，所以，调度延迟会更低一些；如果一直被cfs quota限流，因为quota的分配周期period的存在，而cpuse情况下，cfs schedule latency的保证，cpuset的保证会更好些；不过这种类型的任务，也对调度延迟不会太敏感。
• 微架构性能，即CPU的Dcache、Icache、DTLB、ITLB、NUMA等微架构资源的使用，这个主要是跟CPU Placement策略有关，包括wakeup和loadbalance时的cpu选择等；在这方面，cpuset有天然的优势，因为其可以保证任务运行在一个固定的CPU范围内，尤其是吞吐型的任务有利；

这里参考下memcahced和kbuild两个吞吐型的测试，

• memcached测试，曾经向sched社区反映过，cpuset配置没有考虑超线程问题，Memcached with cfs quota 400% performance boost after bind to 4 cpushttps://www.spinics.net/lists/cgroups/msg30253.html
• kbuild测试，kernel build，代码和输出都放到/dev/shm下，并且保证数据和numa的亲和性；

  配置		cfs quota	cpuset
  16线程	cpuset 跨越16个物理核	17m40s	12m5s
  	cpuset 跨越8个物理核	17m40s	17m45s

  从测试结果来看，影响性能的关键似乎是超线程问题。

再看下调度延迟测试：

测试命令为: ./schbench -m 8 -t 4 -r 900 -c 80000 -R 10

 这个测试结果是符合预期的

从有限的两组测试来看，cpuset对比cfs quota似乎没有体现出明显的优势。