CFS调度器(3)-组调度
作者:smcdef 发布于:2018-11-10 20:43 分类:进程管理
CFS调度器(3)-组调度
前言
现在的计算机基本都支持多用户登陆。如果一台计算机被两个用户A和B使用。假设用户A运行9个进程,用户B只运行1个进程。按照之前文章对CFS调度器的讲解,我们认为用户A获得90% CPU时间,用户B只获得10% CPU时间。随着用户A不停的增加运行进程,用户B可使用的CPU时间越来越少。这显然是不公平的。因此,我们引入组调度(Group Scheduling )的概念。我们以用户组作为调度的单位,这样用户A和用户B各获得50% CPU时间。用户A中的每个进程分别获得5.5%(50%/9)CPU时间。而用户B的进程获取50% CPU时间。这也符合我们的预期。本篇文章讲解CFS组调度实现原理。
注:代码分析基于Linux 4.18.0。使能组调度需要配置CONFIG_CGROUPS和CONFIG_FAIR_GROUP_SCHED。图片变形了该怎么办?浏览器单独打开吧!我也没办法
![]()
再谈调度实体
通过之前的文章,我们已经介绍了CFS调度器主要管理的是调度实体。每一个进程通过task_struct
描述,task_struct
包含调度实体sched_entity
参与调度。暂且针对这种调度实体,我们称作task se。现在引入组调度的概念,我们使用task_group
描述一个组。在这个组中管理组内的所有进程。因为CFS就绪队列管理的单位是调度实体,因此,task_group
也脱离不了sched_entity
,所以在task_group
结构体也包含调度实体sched_entity
,我们称这种调度实体为group se。task_group
定义在kernel/sched/sched.h
文件。
struct task_group { struct cgroup_subsys_state css; #ifdef CONFIG_FAIR_GROUP_SCHED /* schedulable entities of this group on each CPU */ struct sched_entity **se; /* 1 */ /* runqueue "owned" by this group on each CPU */ struct cfs_rq **cfs_rq; /* 2 */ unsigned long shares; /* 3 */ #ifdef CONFIG_SMP atomic_long_t load_avg ____cacheline_aligned; /* 4 */ #endif #endif struct cfs_bandwidth cfs_bandwidth; /* ... */ };
- 指针数组,数组大小等于CPU数量。现在假设只有一个CPU的系统。我们将一个用户组也用一个调度实体代替,插入对应的红黑树。例如,上面用户组A和用户组B就是两个调度实体se,挂在顶层的就绪队列cfs_rq中。用户组A管理9个可运行的进程,这9个调度实体se作为用户组A调度实体的child。通过se->parent成员建立关系。用户组A也维护一个就绪队列cfs_rq,暂且称之为group cfs_rq,管理的9个进程的调度实体挂在group cfs_rq上。当我们选择进程运行的时候,首先从根就绪队列cfs_rq上选择用户组A,再从用户组A的group cfs_rq上选择其中一个进程运行。现在考虑多核CPU的情况,用户组中的进程可以在多个CPU上运行。因此,我们需要CPU个数的调度实体se,分别挂在每个CPU的根cfs_rq上。
- 上面提到的group cfs_rq,同样是指针数组,大小是CPU的数量。因为每一个CPU上都可以运行进程,因此需要维护CPU个数的group cfs_rq。
- 调度实体有权重的概念,以权重的比例分配CPU时间。用户组同样有权重的概念,share就是
task_group
的权重。- 整个用户组的负载贡献总和。
如果我们CPU数量等于2,并且只有一个用户组,那么系统中组调度示意图如下。

系统中一共运行8个进程。CPU0上运行3个进程,CPU1上运行5个进程。其中包含一个用户组A,用户组A中包含5个进程。CPU0上group se获得的CPU时间为group se对应的group cfs_rq管理的所有进程获得CPU时间之和。系统启动后默认有一个root_task_group
,管理系统中最顶层CFS就绪队列cfs_rq。在2个CPU的系统上,task_group
结构体se和cfs_rq成员数组长度是2,每个group se都对应一个group cfs_rq。
数据结构之间的关系
假设系统包含4个CPU,组调度的打开的情况下,各种结构体之间的关系如下图。
在每个CPU上都有一个全局的就绪队列struct rq
,在4个CPU的系统上会有4个全局就绪队列,如图中紫色结构体。系统默认只有一个根task_group
叫做root_task_group。rq->cfs_rq
指向系统根CFS就绪队列。根CFS就绪队列维护一棵红黑树,红黑树上一共10个就绪态调度实体,其中9个是task se,1个group se(图上蓝色se)。group se的my_q
成员指向自己的就绪队列。该就绪队列的红黑树上共9个task se。其中parent
成员指向group se。每个group se对应一个group cfs_rq。4个CPU会对应4个group se和group cfs_rq,分别存储在task_group
结构体se和cfs_rq成员。se->depth
成员记录se嵌套深度。最顶层CFS就绪队列下的se的深度为0,group se往下一层层递增。cfs_rq->nr_runing
成员记录CFS就绪队列所有调度实体个数,不包含子就绪队列。cfs_rq->h_nr_running
成员记录就绪队列层级上所有调度实体的个数,包含group se对应group cfs_rq上的调度实体。例如,图中上半部,nr_runing和h_nr_running的值分别等于10和19,多出的9是group cfs_rq的h_nr_running。group cfs_rq由于没有group se,因此nr_runing和h_nr_running的值都等于9。
组进程调度
用户组内的进程该如何调度呢?通过上面的分析,我们可以通过根CFS就绪队列一层层往下便利选择合适进程。例如,先从根就绪队列选择适合运行的group se,然后找到对应的group cfs_rq,再从group cfs_rq上选择task se。在CFS调度类中,选择进程的函数是pick_next_task_fair()。
static struct task_struct *
pick_next_task_fair(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
{
struct cfs_rq *cfs_rq = &rq->cfs; /* 1 */
struct sched_entity *se;
struct task_struct *p;
put_prev_task(rq, prev);
do {
se = pick_next_entity(cfs_rq, NULL); /* 2 */
set_next_entity(cfs_rq, se);
cfs_rq = group_cfs_rq(se); /* 3 */
} while (cfs_rq); /* 4 */
p = task_of(se);
return p;
}
- 从根CFS就绪队列开始便利。
- 从就绪队列cfs_rq的红黑树中选择虚拟时间最小的se。
- group_cfs_rq()返回
se->my_q
成员。如果是task se,那么group_cfs_rq()返回NULL。如果是group se,那么group_cfs_rq()返回group se对应的group cfs_rq。- 如果是group se,我们需要从group cfs_rq上的红黑树选择下一个虚拟时间最小的se,以此循环直到最底层的task se。
组进程抢占
周期性调度会调用task_tick_fair()函数。
static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued)
{
struct cfs_rq *cfs_rq;
struct sched_entity *se = &curr->se;
for_each_sched_entity(se) {
cfs_rq = cfs_rq_of(se);
entity_tick(cfs_rq, se, queued);
}
}
for_each_sched_entity()是一个宏定义for (; se; se = se->parent)
,顺着se的parent链表往上走。entity_tick()函数继续调用check_preempt_tick()函数,这部分在之前的文章已经说过了。check_preempt_tick()函数会根据满足抢占当前进程的条件下设置TIF_NEED_RESCHED标志位。满足抢占条件也很简单,只要顺着se->parent
这条链表便利下去,如果有一个se运行时间超过分配限额时间就需要重新调度。
用户组的权重
每一个进程都会有一个权重,CFS调度器依据权重的大小分配CPU时间。同样task_group
也不例外,前面已经提到使用share成员记录。按照前面的举例,系统有2个CPU,task_group
中势必包含两个group se和与之对应的group cfs_rq。这2个group se的权重按照比例分配task_group
权重。如下图所示。
CPU0上group se下有2个task se,权重和是3072。CPU1上group se下有3个task se,权重和是4096。task_group
权重是1024。因此,CPU0上group se权重是439(1024*3072/(3072+4096)),CPU1上group se权重是585(1024-439)。当然这里的计算group se权重的方法是最简单的方式,代码中实际计算公式是考虑每个group cfs_rq的负载贡献比例,而不是简单的考虑权重比例。
用户组时间限额分配
分配给每个进程时间计算函数是sched_slice(),之前的分析都是基于不考虑组调度的情况下。现在考虑组调度的情况下进程应该分配的时间如何调整呢?先举个简单不考虑组调度的例子,在一个单核系统上2个进程,权重都是1024。在不考虑组调度的情况下,调度实体se分配的时间限额计算公式如下:
se->load.weight time = sched_period * ------------------------- cfs_rq->load.weight
我们还需要计算se的权重占整个CFS就绪队列权重的比例乘以调度周期时间即可。2个进程根据之前文章的分析,调度周期是6ms,那么每个进程分配的时间是6ms*1024/(1024+1024)=3ms。
现在考虑组调度的情况。系统依然是单核,存在一个task_group
,所有的进程权重是1024。task_group
权重也是1024(即share值)。如下图所示。
group cfs_rq下的进程分配时间计算公式如下(gse := group se; gcfs_rq := group cfs_rq):
se->load.weight gse->load.weight time = sched_period * ------------------------- * ------------------------ gcfs_rq->load.weight cfs_rq->load.weight
根据公式,计算group cfs_rq下进程的配时间如下:
1024 1024
time = 6ms * --------------- * ---------------- = 1.5ms
1024 + 1024 1024 + 1024
依据上面的2个计算公式,我们可以计算上面例子中每个进程分配的时间如下图所示。
以上简单介绍了task_group
嵌套一层的情况,如果task_group
下面继续包含task_group
,那么上面的计算公式就要再往上计算一层比例。实现该计算公式的函数是sched_slice()。
static u64 sched_slice(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
u64 slice = __sched_period(cfs_rq->nr_running + !se->on_rq); /* 1 */
for_each_sched_entity(se) { /* 2 */
struct load_weight *load;
struct load_weight lw;
cfs_rq = cfs_rq_of(se);
load = &cfs_rq->load; /* 3 */
if (unlikely(!se->on_rq)) {
lw = cfs_rq->load;
update_load_add(&lw, se->load.weight);
load = &lw;
}
slice = __calc_delta(slice, se->load.weight, load); /* 4 */
}
return slice;
}
- 根据当前就绪进程个数计算调度周期,默认情况下,进程不超过8个情况下,调度周期默认6ms。
- for循环根据se->parent链表往上计算比例。
- 获得se依附的cfs_rq的负载信息。
- 计算slice = slice * se->load.weight / cfs_rq->load.weight的值。
Group Se权重计算
上面举例说到group se的权重计算是根据权重比例计算。但是,实际的代码并不是。当我们dequeue task、enqueue task以及task tick的时候会通过update_cfs_group()函数更新group se的权重信息。
static void update_cfs_group(struct sched_entity *se)
{
struct cfs_rq *gcfs_rq = group_cfs_rq(se); /* 1 */
long shares, runnable;
if (!gcfs_rq)
return;
shares = calc_group_shares(gcfs_rq); /* 2 */
runnable = calc_group_runnable(gcfs_rq, shares);
reweight_entity(cfs_rq_of(se), se, shares, runnable); /* 3 */
}
- 获得group se对应的group cfs_rq。
- 计算新的权重值。
- 更新group se的权重值为shares。
calc_group_shares()根据当前group cfs_rq负载情况计算新的权重。
static long calc_group_shares(struct cfs_rq *cfs_rq)
{
long tg_weight, tg_shares, load, shares;
struct task_group *tg = cfs_rq->tg;
tg_shares = READ_ONCE(tg->shares);
load = max(scale_load_down(cfs_rq->load.weight), cfs_rq->avg.load_avg);
tg_weight = atomic_long_read(&tg->load_avg);
/* Ensure tg_weight >= load */
tg_weight -= cfs_rq->tg_load_avg_contrib;
tg_weight += load;
shares = (tg_shares * load);
if (tg_weight)
shares /= tg_weight;
return clamp_t(long, shares, MIN_SHARES, tg_shares);
}
根据calc_group_shares()函数,我们可以得到权重计算公式如下(grq := group cfs_rq):
tg->shares * load
ge->load.weight = -------------------------------------------------
tg->load_avg - grq->tg_load_avg_contrib + load
load = max(grq->load.weight, grq->avg.load_avg)
tg->load_avg
指所有的group cfs_rq负载贡献和。grq->tg_load_avg_contrib
是指该group cfs_rq已经向tg->load_avg
贡献的负载。因为tg是一个全局共享变量,多个CPU可能同时访问,为了避免严重的资源抢占。group cfs_rq负载贡献更新的值并不会立刻加到tg->load_avg
上,而是等到负载贡献大于tg_load_avg_contrib一定差值后,再加到tg->load_avg
上。例如,2个CPU的系统。CPU0上group cfs_rq初始值tg_load_avg_contrib为0,当group cfs_rq每次定时器更新负载的时候并不会访问tg变量,而是等到group cfs_rq的负载grp->avg.load_avg大于tg_load_avg_contrib很多的时候,这个差值达到一个数值(假设是2000),才会更新tg->load_avg
为2000。然后,tg_load_avg_contrib的值赋值2000。又经过很多个周期后,grp->avg.load_avg和tg_load_avg_contrib的差值又等于2000,那么再一次更新tg->load_avg
的值为4000。这样就避免了频繁访问tg变量。
但是上面的计算公式的依据是什么呢?如何得到的?首先我觉得我们能介绍的计算方法是上一节《用户组的权重》说的方法,计算group cfs_rq的权重占的比例。公式如下。
tg->shares * grq->load.weight
ge->load.weight = ------------------------------- (1)
\Sum grq->load.weight
由于计算\Sum grq->load.weight这个总和开销太大(原因可能是CPU数量比较大的系统,访问其他CPU group cfs_rq造成数据访问竞争激烈)。因此我们使用平均负载来近似处理,平均负载值变化缓慢,因此近似后的值更容易计算且更稳定。近似处理条件如下,将权重和平均负载近似处理。
grq->load.weight -> grq->avg.load_avg (2)
经过近似处理后的公式(1)变换如下:
tg->shares * grq->avg.load_avg
ge->load.weight = ------------------------------ (3)
tg->load_avg
Where: tg->load_avg ~= \Sum grq->avg.load_avg
公式(3)问题在于,因为平均负载值变化很慢 (它的设计正是如此) ,这会导致在边界条件的时候的瞬变。 具体而言,当空闲group开始运行一个进程的时候。 我们的CPU的grq->avg.load_avg需要花费时间来慢慢变化,产生不良的延迟。在这种特殊情况下(单核CPU也是这种情况),公式(1)计算如下:
tg->shares * grq->load.weight
ge->load.weight = ------------------------------- = tg->shares (4)
grq->load.weight
我们的目标就是将近似公式(3)在UP情景时修改成公式(4)的情况。
ge->load.weight =
tg->shares * grq->load.weight
--------------------------------------------------- (5)
tg->load_avg - grq->avg.load_avg + grq->load.weight
但是因为grq->load.weight可以降到0,导致除数是0。因此我们需要使用grq->avg.load_avg作为其下限,然后给出:
tg->shares * grq->load.weight
ge->load.weight = ----------------------------- (6)
tg_load_avg'
Where: tg_load_avg' = tg->load_avg - grq->avg.load_avg +
max(grq->load.weight, grq->avg.load_avg)
在UP系统上,公式(6)和公式(4)相似。在正常情况下,公式(6)和公式(3)相似。
说实话,真的是一大堆的公式,而且是各种近似处理和怼参数。一下看到公式的结果总是一头雾水,因为这可能涉及多次不同的优化修改,有些可能是经验总结,有些可能是实际环境测试。当你看不懂公式的时候,不妨会退到这个功能刚刚添加时候的样子,最初的版本总是让人容易接受。然后,顺着每一笔提交记录查看优化代码的原因,一步一个脚印,或许“面向大海春暖花开”。

评论:
2024-01-11 15:47
**se的长度只取决于当前task_group有多少个任务实体,每一个cfs_rq队列都同时可以接受多个任务实体se,但是一个cfs_rq队列只能对应于一个CPU上的rq
2023-02-24 20:05
这个是因为:
grq->avg.load_avg =
(cfs_rq->load.weight * delta_time) / LOAD_AVG_MAX
当这个CPU一直运行,idle时间很少的时间,可以近似认为delta_time = LOAD_AVG_MAX,也就是可以用load_avg来模拟load.weight
2020-07-27 19:00
新创建的sched_entity group(tg->se[cpu] = se)是如何被插入其隶属于的rbtree的?
2020-06-28 11:18
这里应该是被除数为0哈,虽然除数也为0,但引起问题的显然是被除数为0,源码的注释里也是“a divide by zero”。因为UP scenario,tg->load_**g = grq->**g.load_**g,所以grq->load.weight如果也为0,被除数就为0了,所以grq->load.weight改为 max(...),从这里改的是分母而不是分子也可以判断,引起问题的是被除数为0
2020-06-15 19:44
task_group中的struct sched_entity **se,在每个cpu上面的se list是一定不同的吗?
还是可能不同,有没有什么标准,就是不考虑cpu affine的前提下,task group中的某个se在某个cpu上调度是随机的吗
2020-04-15 18:07
如果有两个位于同一层的cfs_rq A和B, A下辖10个se,B只有一个se,那么A __sched_period的时间就比B多,不太公平
是不是应该用顶层的h_nr_running?
2021-10-18 10:49
$ grep termi /proc/sched_debug
Sgnome-terminal- 3207 475.470142 17885 120 0.000000 5103.923704 0.000000 0 0 /autogroup-168
$ grep -m1 chrome /proc/sched_debug
S chrome 24624 60331.977128 805 120 0.000000 380.673857 0.000000 0 0 /autogroup-129蓝
这样配置,能降低在终端编译内核时,对浏览器影响.
功能
最新评论
文章分类
随机文章
文章存档
- 2024年2月(1)
- 2023年5月(1)
- 2022年10月(1)
- 2022年8月(1)
- 2022年6月(1)
- 2022年5月(1)
- 2022年4月(2)
- 2022年2月(2)
- 2021年12月(1)
- 2021年11月(5)
- 2021年7月(1)
- 2021年6月(1)
- 2021年5月(3)
- 2020年3月(3)
- 2020年2月(2)
- 2020年1月(3)
- 2019年12月(3)
- 2019年5月(4)
- 2019年3月(1)
- 2019年1月(3)
- 2018年12月(2)
- 2018年11月(1)
- 2018年10月(2)
- 2018年8月(1)
- 2018年6月(1)
- 2018年5月(1)
- 2018年4月(7)
- 2018年2月(4)
- 2018年1月(5)
- 2017年12月(2)
- 2017年11月(2)
- 2017年10月(1)
- 2017年9月(5)
- 2017年8月(4)
- 2017年7月(4)
- 2017年6月(3)
- 2017年5月(3)
- 2017年4月(1)
- 2017年3月(8)
- 2017年2月(6)
- 2017年1月(5)
- 2016年12月(6)
- 2016年11月(11)
- 2016年10月(9)
- 2016年9月(6)
- 2016年8月(9)
- 2016年7月(5)
- 2016年6月(8)
- 2016年5月(8)
- 2016年4月(7)
- 2016年3月(5)
- 2016年2月(5)
- 2016年1月(6)
- 2015年12月(6)
- 2015年11月(9)
- 2015年10月(9)
- 2015年9月(4)
- 2015年8月(3)
- 2015年7月(7)
- 2015年6月(3)
- 2015年5月(6)
- 2015年4月(9)
- 2015年3月(9)
- 2015年2月(6)
- 2015年1月(6)
- 2014年12月(17)
- 2014年11月(8)
- 2014年10月(9)
- 2014年9月(7)
- 2014年8月(12)
- 2014年7月(6)
- 2014年6月(6)
- 2014年5月(9)
- 2014年4月(9)
- 2014年3月(7)
- 2014年2月(3)
- 2014年1月(4)
2024-05-03 03:24
==========================================
“nr_runing和h_nr_running的值分别等于10和19”错了,应该是“分别等于10和18”。一个关键的问题是h_nr_running只包含task se(不包含group se),因此,h_nr_running应该是18(而不是文中的19)。
可以通过以下方式来证明:
1. 通过代码证明,http://elixir.bootlin.com/linux/v5.19.17/source/kernel/sched/fair.c#L5659:
代码每次加入的se 必定是task se(不会无缘无故的只加入group se的),group se是在for_each中“被动”加入的相应的cfs_rq的,即:将task se加入之后,for_each一路向上,在这个过程中,如果task se的某个祖先group se尚未加入相应的cfs_rq,则会在for_each中会将其加入相应的cfs_rq。for_each为每一个层级的cfs_rq->h_nr_running都加了1。所以,cfs_rq->h_nr_running永远只包含task se的数量。
2. 通过下面代码做实验,可以证明:
a. cfs_rq->h_nr_running永远只包含task se的数量;cfs_rq->nr_running
b. group se也会被放入 cfs_rq,且,cfs_rq->nr_running 是包含 group se的数量的
sudo cgcreate -g cpu:/tg1/tg2/tg3/tg4
sudo cgexec -g cpu:/tg1/tg2 taskset 2 nice -n 0 /home/marvin/yourvm/capture/h2 2 1000
sudo cgexec -g cpu:/tg1/tg2/tg3 taskset 2 nice -n 0 /home/marvin/yourvm/capture/h3 3 1000
(其中,h2, h3 是 cpu-bound的代码,比如计算sha或无限for循环等)
cat /sys/kernel/debug/sched/debug > /home/marvin/sched_debug.txt
查看sched_debug.txt中的 cfs_rq[1]:/tg1...... 可以看到 其中的 nr_running和h_nr_running满足猜想。