现在的计算机基本都支持多用户登陆。如果一台计算机被两个用户A和B使用。假设用户A运行9个进程，用户B只运行1个进程。按照之前文章对CFS调度器的讲解，我们认为用户A获得90%CPU时间，用户B只获得10%CPU时间。随着用户A不停的增加运行进程，用户B可使用的CPU时间越来越少。这显然是不公平的。因此，我们引入组调度（GROUPSCHEDULING）的概念。我们以用户组作为调度的单位，这样用户A和用户B各获得50%CPU时间。用户A中的每个进程分别获得5.5%（50%/9）CPU时间。而用户B的进程获取50%CPU时间。这也符合我们的预期。本篇文章讲解CFS组调度实现原理。通过之前的文章，我们已经介绍了CFS调度器主要管理的是调度实体。每一个进程通过描述，包含调度实体参与调度。暂且针对这种调度实体，我们称作TASKSE。现在引入组调度的概念，我们使用描述一个组。在这个组中管理组内的所有进程。因为CFS就绪队列管理的单位是调度实体，因此，也脱离不了，所以在结构体也包含调度实体，我们称这种调度实体为GROUPSE。定义在文件。系统中一共运行8个进程。CPU0上运行3个进程，CPU1上运行5个进程。其中包含一个用户组A，用户组A中包含5个进程。CPU0上GROUPSE获得的CPU时间为GROUPSE对应的GROUPCFS_RQ管理的所有进程获得CPU时间之和。系统启动后默认有一个，管理系统中最顶层CFS就绪队列CFS_RQ。在2个CPU的系统上，结构体SE和CFS_RQ成员数组长度是2，每个GROUPSE都对应一个GROUPCFS_RQ。假设系统包含4个CPU，组调度的打开的情况下，各种结构体之间的关系如下图。在每个CPU上都有一个全局的就绪队列，在4个CPU的系统上会有4个全局就绪队列，如图中紫色结构体。系统默认只有一个根叫做ROOT_TASK_GROUP。指向系统根CFS就绪队列。根CFS就绪队列维护一棵红黑树，红黑树上一共10个就绪态调度实体，其中9个是TASKSE，1个GROUPSE（图上蓝色SE）。GROUPSE的成员指向自己的就绪队列。该就绪队列的红黑树上共9个TASKSE。其中成员指向GROUPSE。每个GROUPSE对应一个GROUPCFS_RQ。4个CPU会对应4个GROUPSE和GROUPCFS_RQ，分别存储在结构体SE和CFS_RQ成员。成员记录SE嵌套深度。最顶层CFS就绪队列下的SE的深度为0，GROUPSE往下一层层递增。成员记录CFS就绪队列所有调度实体个数，不包含子就绪队列。成员记录就绪队列层级上所有调度实体的个数，包含GROUPSE对应GROUPCFS_RQ上的调度实体。例如，图中上半部，NR_RUNING和H_NR_RUNNING的值分别等于10和19，多出的9是GROUPCFS_RQ的H_NR_RUNNING。GROUPCFS_RQ由于没有GROUPSE，因此NR_RUNING和H_NR_RUNNING的值都等于9。用户组内的进程该如何调度呢？通过上面的分析，我们可以通过根CFS就绪队列一层层往下便利选择合适进程。例如，先从根就绪队列选择适合运行的GROUPSE，然后找到对应的GROUPCFS_RQ，再从GROUPCFS_RQ上选择TASKSE。在CFS调度类中，选择进程的函数是PICK_NEXT_TASK_FAIR()。FOR_EACH_SCHED_ENTITY()是一个宏定义，顺着SE的PARENT链表往上走。ENTITY_TICK()函数继续调用CHECK_PREEMPT_TICK()函数，这部分在之前的文章已经说过了。CHECK_PREEMPT_TICK()函数会根据满足抢占当前进程的条件下设置TIF_NEED_RESCHED标志位。满足抢占条件也很简单，只要顺着这条链表便利下去，如果有一个SE运行时间超过分配限额时间就需要重新调度。每一个进程都会有一个权重，CFS调度器依据权重的大小分配CPU时间。同样也不例外，前面已经提到使用SHARE成员记录。按照前面的举例，系统有2个CPU，中势必包含两个GROUPSE和与之对应的GROUPCFS_RQ。这2个GROUPSE的权重按照比例分配权重。如下图所示。CPU0上GROUPSE下有2个TASKSE，权重和是3072。CPU1上GROUPSE下有3个TASKSE，权重和是4096。权重是1024。因此，CPU0上GROUPSE权重是439（1024*3072/(3072+4096)）,CPU1上GROUPSE权重是585（1024-439）。当然这里的计算GROUPSE权重的方法是最简单的方式，代码中实际计算公式是考虑每个GROUPCFS_RQ的负载贡献比例，而不是简单的考虑权重比例。分配给每个进程时间计算函数是SCHED_SLICE()，之前的分析都是基于不考虑组调度的情况下。现在考虑组调度的情况下进程应该分配的时间如何调整呢？先举个简单不考虑组调度的例子，在一个单核系统上2个进程，权重都是1024。在不考虑组调度的情况下，调度实体SE分配的时间限额计算公式如下：我们还需要计算SE的权重占整个CFS就绪队列权重的比例乘以调度周期时间即可。2个进程根据之前文章的分析，调度周期是6MS，那么每个进程分配的时间是6MS*1024/(1024+1024)=3MS。现在考虑组调度的情况。系统依然是单核，存在一个，所有的进程权重是1024。权重也是1024（即SHARE值）。如下图所示。依据上面的2个计算公式，我们可以计算上面例子中每个进程分配的时间如下图所示。以上简单介绍了嵌套一层的情况，如果下面继续包含，那么上面的计算公式就要再往上计算一层比例。实现该计算公式的函数是SCHED_SLICE()。上面举例说到GROUPSE的权重计算是根据权重比例计算。但是，实际的代码并不是。当我们DEQUEUETASK、ENQUEUETASK以及TASKTICK的时候会通过UPDATE_CFS_GROUP()函数更新GROUPSE的权重信息。指所有的GROUPCFS_RQ负载贡献和。是指该GROUPCFS_RQ已经向贡献的负载。因为TG是一个全局共享变量，多个CPU可能同时访问，为了避免严重的资源抢占。GROUPCFS_RQ负载贡献更新的值并不会立刻加到上，而是等到负载贡献大于TG_LOAD_AVG_CONTRIB一定差值后，再加到上。例如，2个CPU的系统。CPU0上GROUPCFS_RQ初始值TG_LOAD_AVG_CONTRIB为0，当GROUPCFS_RQ每次定时器更新负载的时候并不会访问TG变量，而是等到GROUPCFS_RQ的负载GRP->AVG.LOAD_AVG大于TG_LOAD_AVG_CONTRIB很多的时候，这个差值达到一个数值（假设是2000），才会更新为2000。然后，TG_LOAD_AVG_CONTRIB的值赋值2000。又经过很多个周期后，GRP->AVG.LOAD_AVG和TG_LOAD_AVG_CONTRIB的差值又等于2000，那么再一次更新的值为4000。这样就避免了频繁访问TG变量。但是上面的计算公式的依据是什么呢？如何得到的？首先我觉得我们能介绍的计算方法是上一节《用户组的权重》说的方法，计算GROUPCFS_RQ的权重占的比例。公式如下。由于计算\SUMGRQ->LOAD.WEIGHT这个总和开销太大（原因可能是CPU数量比较大的系统，访问其他CPUGROUPCFS_RQ造成数据访问竞争激烈）。因此我们使用平均负载来近似处理，平均负载值变化缓慢，因此近似后的值更容易计算且更稳定。近似处理条件如下，将权重和平均负载近似处理。公式(3)问题在于，因为平均负载值变化很慢(它的设计正是如此)，这会导致在边界条件的时候的瞬变。具体而言，当空闲GROUP开始运行一个进程的时候。我们的CPU的GRQ->AVG.LOAD_AVG需要花费时间来慢慢变化，产生不良的延迟。在这种特殊情况下（单核CPU也是这种情况），公式(1)计算如下：我们的目标就是将近似公式(3)在UP情景时修改成公式(4)的情况。在UP系统上，公式(6)和公式(4)相似。在正常情况下，公式(6)和公式(3)相似。说实话，真的是一大堆的公式，而且是各种近似处理和怼参数。一下看到公式的结果总是一头雾水，因为这可能涉及多次不同的优化修改，有些可能是经验总结，有些可能是实际环境测试。当你看不懂公式的时候，不妨会退到这个功能刚刚添加时候的样子，最初的版本总是让人容易接受。然后，顺着每一笔提交记录查看优化代码的原因，一步一个脚印，或许“面向大海春暖花开”。
更多文章
友情链接