大家好，我是本期栏目编辑小友，现在为大家讲解Linux 组调度浅析问题。
原文来源：ctthuangchengcgroup和group scheduling。
linux内核实现了控制组功能(cgroup，从linux 2.6.24开始)，可以支持对进程进行分组，然后根据组来划分各种资源。例如，组-1拥有30%的CPU和50%的磁盘IO，组-2拥有10%的CPU和20%的磁盘IO，以此类推。详情请见集团相关文章。
Cgroup支持多种资源的划分，其中CPU资源是一种，这就导致了组调度。
在linux内核中，传统的调度程序是基于进程的。假设用户A和B共用一台机器，主要用来编译程序。我们可能希望A和B能够公平地共享CPU资源，但是如果用户A使用make -j8(8个线程并行make)，用户B直接使用make(假设他们的make程序都使用默认优先级)，那么用户A的make程序产生的进程将是用户B的8倍，从而占用(大致)8倍于用户B的CPU.因为调度器是基于进程的，所以用户拥有的进程越多，被调度的机会就越大，对CPU的竞争力就越强。
如何保证A、B用户公平共享CPU？分组调度可以做到这一点。将属于用户A和B的进程分成组，调度器将首先从这两个组中选择一个组，然后从选择的组中选择一个进程执行。如果两个组被选中的概率相等，那么用户A和B各占CPU的50%左右。
相关数据结构
在linux内核中，task_group结构用于管理按组调度的组。所有已有的task_group形成一个树形结构(对应于cgroup的目录结构)。
一个task_group可以包含任意调度类别的进程(具体来说就是实时进程和普通进程)，因此task_group需要为每个调度策略提供一组调度结构。这里的调度结构集主要包括两部分，调度实体和运行队列(两者都是针对每个CPU的)。调度实体将被添加到运行队列中，对于task_group，其调度实体将被添加到其父task_group的运行队列中。
为什么会有调度实体这种东西？因为有两种调度对象，task_group和task，所以需要一个抽象的结构来表示它们。如果调度实体表示task_group，则它的my_q字段指向与该调度组对应的运行队列。否则，my_q字段为空，调度实体代表任务。在调度实体中，X_rq与my_q相对(具体来说是普通进程的cfs_rq和实时进程的rt_rq)。前者指向组自己的运行队列，它的子节点将放在该队列中。后者指向该组的父节点的运行队列，即该调度实体应该放入的运行队列。
因此，调度实体和运行队列形成了另一种树形结构，其中每个非叶节点对应task_group的树形结构，而叶节点对应特定的任务。就像非TASK_RUNNING状态的进程不会被放入运行队列一样，如果一个组中没有TASK_RUNNING状态的进程，那么这个组(对应的调度实体)也不会被放入它的上层运行队列。需要明确的是，只要创建了调度组，其对应的task_group就一定会存在于task_group组成的树形结构中。运行队列和调度实体组成的树形结构中是否存在对应的调度实体，取决于该组中是否存在TASK_RUNNING进程。
作为根节点，task_group没有调度实体，调度器总是从其运行队列开始选择下一个调度实体(根节点必须是第一个被选中的，没有其他候选，所以根节点不需要调度实体)。根task_group对应的运行队列被包装在rq结构中，该结构不仅包含特定的运行队列，还包含全局统计等一些字段。
当调度发生时，调度器从根task_group的运行队列中选择一个调度实体。如果这个调度实体代表一个task_group，那么调度器需要继续从对应于这个组的运行队列中选择一个调度实体。递归进行，直到选择一个进程。除非根task_group的运行队列为空，否则可以通过递归找到进程。如果task_group对应的运行队列为空，则其对应的调度实体不会添加到其父节点对应的运行队列中。
最后，对于一个task_group，它的调度实体和运行队列都是每个CPU，一个调度实体(对应task_group)只会被添加到对应同一个CPU的运行队列中。对于任务，只有一个调度实体(不按CPU划分)，调度器的负载均衡功能可以将调度实体(对应任务)从不同CPU对应的运行队列中移出。(参见《linux内核SMP负载均衡浅析》)
群体调度策略。
群组调度的主要数据结构已经明确，这里有一个非常重要的问题。我们知道任务有其对应的优先级(静态优先级或动态优先级)，调度器根据优先级选择运行队列中的进程。那么，既然task_group和task一样，被抽象为一个调度实体，接受同样的调度，那么task_group的优先级应该如何定义呢？这个问题需要通过调度类别(不同的调度类别有不同的优先级定义)来解决，具体来说就是rt(实时调度)和cfs(完全公平调度)。
实时进程的分组调度。
实时进程是对CPU有实时要求的进程，其优先级与具体任务相关，完全由用户定义。调度程序总是选择优先级。
最高的实时进程来运行。发展到组调度，组的优先级就被定义为“组内最高优先级的进程所拥有的优先级”。比如组内有三个优先级分别为10、20、30的进程，则组的优先级就是10（数值越小优先级越大）。
组的优先级如此定义，引出了一个有趣的现象。当task入队或者出队时，要把它的所有祖先节点都先出队，然后再重新由底向上依次入队。因为组节点的优先级是依赖于它的子节点的，task的入队和出队将影响它的每一个祖先节点。
于是，当调度程序从根节点的task_group出发选择调度实体时，总是能沿着正确的路径，找到所有TASK_RUNNING状态的实时进程中优先级最高的那一个。这个实现似乎理所当然，但是仔细想想，这样一来，将实时进程分组还有什么意义呢？无论分组与否，调度程序要做的事情都是“在所有TASK_RUNNING状态的实时进程中选择优先级最高的那一个”。这里似乎还缺了些什么……
现在需要先介绍一下linux系统中的两个proc文件：/proc/sys/kernel/sched_rt_period_us和/proc/sys/kernel/sched_rt_runTIme_us。这两个文件规定了，在以sched_rt_period_us为一个周期的时间内，所有实时进程的运行时间之和不超过sched_rt_runTIme_us。这两个文件的默认值是1s和0.95s，表示每秒种为一个周期，在这个周期中，所有实时进程运行的总时间不超过0.95秒，剩下的至少0.05秒会留给普通进程。也就是说，实时进程占有不超过95%的CPU。而在这两个文件出现之前，实时进程的运行时间是没有限制的，如果一直有处于TASK_RUNNING状态的实时进程，则普通进程会一直不能得到运行。相当于sched_rt_runTIme_us等于sched_rt_period_us。
为什么要有sched_rt_runTIme_us和sched_rt_period_us两个变量呢？直接使用一个表示CPU占有百分比的变量不可以么？我想这应该是由于很多实时进程实际上都是周期性地在干某件事情，比如某语音程序每20ms发送一个语音包、某视频程序每40ms刷新一帧、等等。周期是很重要的，仅仅使用一个宏观的CPU占有比无法准确描述实时进程需求。
而实时进程的分组就把sched_rt_runtime_us和sched_rt_period_us的概念扩展了，每个task_group都有自己的sched_rt_runtime_us和sched_rt_period_us，保证自己组内的进程在以sched_rt_period_us为周期的时间内，最多只能运行sched_rt_runtime_us这么多时间。CPU占有比为sched_rt_runtime_us/sched_rt_period_us。
对于根节点的task_group，它的sched_rt_runtime_us和sched_rt_period_us就等于上面两个proc文件中的值。而对于一个task_group节点来说，假设它下面有n个调度子组和m个TASK_RUNNING状态的进程，它的CPU占有比为A、这n个子组的CPU占有比为B，则B必须小于等于A，而A-B剩下的CPU时间将分给那m个TASK_RUNNING状态的进程。（这里讨论的是CPU占有比，因为每个调度组可能有着不同的周期值。）
为了实现sched_rt_runtime_us和sched_rt_period_us的逻辑，内核在更新进程的运行时间的时候（比如由周期性的时钟中断触发的时间更新）会给当前进程的调度实体及其所有祖先节点都增加相应的runtime。如果一个调度实体达到了sched_rt_runtime_us所限定的时间，则将其从对应的运行队列中剔除，并将对应的rt_rq置throttled状态。在这个状态下，这个rt_rq对应的调度实体不会再次进入运行队列。而每个rt_rq都会维护一个周期性的定时器，定时周期为sched_rt_period_us。每次定时器触发，其对应的回调函数就会将rt_rq的runtime减去一个sched_rt_period_us单位的值（但要保持runtime不小于0），然后将rt_rq从throttled状态中恢复回来。
还有一个问题，前面说到，默认情况下，系统中每秒钟内实时进程的运行时间不超过0.95秒。如果实时进程实际对CPU的需求不足0.95秒（大于等于0秒、小于0.95秒），则剩下的时间都会分配给普通进程。而如果实时进程的对CPU的需求大于0.95秒，它也只能够运行0.95秒，剩下的0.05秒会分给其他普通进程。但是，如果这0.05秒内没有任何普通进程需要使用CPU（一直没有TASK_RUNNING状态的普通进程）呢？这种情况下既然普通进程对CPU没有需求，实时进程是否可以运行超过0.95秒呢？不能。在剩下的0.05秒中内核宁可让CPU一直闲着，也不让实时进程使用。可见sched_rt_runtime_us和sched_rt_period_us是很有强制性的。
最后还有多CPU的问题，前面也提到，对于每一个task_group，它的调度实体和运行队列是每CPU维护一份的。而sched_rt_runtime_us和sched_rt_period_us是作用在调度实体上的.所以如果系统中有N个CPU，实时进程实际占有CPU的上限N*sched_rt_runtime_us/sched_rt_period_us。也就是说，尽管默认情况下限制了每秒钟之内，实时进程只能运行0.95秒。但是对于某个实时进程来说，如果CPU有两个核，也还是能满足它100%占有CPU的需求的（比如执行死循环）。然后，按道理说，这个实时进程占有的100%的CPU应该是由两部分组成的（每个CPU占有一部分，但都不超过95%）。但是实际上，为了避免进程在CPU间的迁移导致上下文切换、缓存失效等一系列问题，一个CPU上的调度实体可以向另一个CPU上对应的调度实体借用时间。其结果就是，宏观上既满足了sched_rt_runtime_us的限制，又避免了进程的迁移。
普通进程的组调度
文章一开头提到了希望A、B两个用户在进程数不相同的情况下也能平分CPU的需求，但是上面关于实时进程的组调度策略好像与此不太相干，其实这就是普通进程的组调度所要干的事。
相比实时进程，普通进程的组调度就没有这么多讲究。组被看作是跟进程几乎完全相同的实体，它拥有自己的静态优先级、调度程序也动态地调整它的优先级。对于一个组来说，组内进程的优先级并不影响组的优先级，只有这个组被调度程序选中时，这些进程的优先级才被考虑。
为了设置组的优先级，每个task_group都有一个shares参数（跟前面提到的sched_rt_runtime_us和sched_rt_period_us两个参数并列）。shares并不是优先级，而是调度实体的权重（这是CFS调度器的玩法），这个权重和优先级是有一一对应的关系的。普通进程的优先级也会被转换成其对应调度实体的权重，所以可以说shares就代表了优先级。
shares的默认值跟普通进程默认优先级对应的权重是一样的。所以在默认情况下，组和进程是平分CPU的。
示例
（环境：ubuntu 10.04，kernel 2.6.32，Intel Core2 双核）
挂载一个只划分CPU资源的cgroup，并创建grp_a和grp_b两个子组：
12345678910111213141516171819kouu@kouu-one:~$ sudo mkdir /dev/cgroup/cpu -p kouu@kouu-one:~$ sudo mount -t cgroup cgroup -o cpu /dev/cgroup/cpu kouu@kouu-one:/dev/cgroup/cpu$ cd /dev/cgroup/cpu/ kouu@kouu-one:/dev/cgroup/cpu$ mkdir grp_{a,b} kouu@kouu-one:/dev/cgroup/cpu$ ls * cgroup.procs cpu.rt_period_us cpu.rt_runtime_us cpu.shares notify_on_release release_agent tasks grp_a: cgroup.procs cpu.rt_period_us cpu.rt_runtime_us cpu.shares notify_on_release tasks grp_b: cgroup.procs cpu.rt_period_us cpu.rt_runtime_us cpu.shares notify_on_release tasks分别开三个shell，第一个加入grp_a，后两个加入grp_b：
123kouu@kouu-one:~/test/rtproc$ cat ttt.sh echo $1 > /dev/cgroup/cpu/$2/tasks（为什么要用ttt.sh来写cgroup下的tasks文件呢？因为写这个文件需要root权限，当前shell没有root权限，而sudo只能赋予被它执行的程序的root权限。其实sudo sh，然后再在新开的shell里面执行echo操作也是可以的。）
1234567891011121314151617kouu@kouu-one:~/test1$ echo $$ 6740 kouu@kouu-one:~/test1$ sudo sh ttt.sh $$ grp_a kouu@kouu-one:~/test2$ echo $$ 9410 kouu@kouu-one:~/test2$ sudo sh ttt.sh $$ grp_b kouu@kouu-one:~/test3$ echo $$ 9425 kouu@kouu-one:~/test3$ sudo sh ttt.sh $$ grp_b回到cgroup目录下，确认这几个shell都被加进去了：
123456789kouu@kouu-one:/dev/cgroup/cpu$ cat grp_a/tasks 6740 kouu@kouu-one:/dev/cgroup/cpu$ cat grp_b/tasks 9410 9425现在准备在这三个shell下同时执行一个死循环的程序（a.out），为了避免多CPU带来的影响，将进程绑定到第二个核上：
123456789101112131415161718192021#define _GNU_SOURCE #include int main() { cpu_set_t set; CPU_ZERO(&set); CPU_SET(1, &set); sched_setaffinity(0, sizeof(cpu_set_t), &set); while(1); return 0; }
编译生成a.out，然后在前面的三个shell中分别运行。三个shell分别会fork出一个子进程来执行a.out，这些子进程都会继承其父进程的cgroup分组信息。然后top一下，可以观察到属于grp_a的a.out占了50%的CPU，而属于grp_b的两个a.out各占25%的CPU（加起来也是50%）：
12345678910111213kouu@kouu-one:/dev/cgroup/cpu$ top -c ...... PID USER PR NI VIRT RES SHR S %CPU %MEM TIME+ COMMAND 19854 kouu 20 0 1616 328 272 R 50 0.0 0:11.69 ./a.out 19857 kouu 20 0 1616 332 272 R 25 0.0 0:05.73 ./a.out 19860 kouu 20 0 1616 332 272 R 25 0.0 0:04.68 ./a.out ......
接下来再试试实时进程，把a.out程序改造如下：
1234567891011121314151617#define _GNU_SOURCE #include int main() { int prio = 50; sched_setscheduler(0, SCHED_FIFO, (struct sched_param*)&prio); while(1); return 0; }然后设置grp_a的rt_runtime值：
1234567891011kouu@kouu-one:/dev/cgroup/cpu$ sudo sh # echo 300000 > grp_a/cpu.rt_runtime_us # exit kouu@kouu-one:/dev/cgroup/cpu$ cat grp_a/cpu.rt_* 1000000 300000现在的配置是每秒为一个周期，属于grp_a的实时进程每秒种只能执行300毫秒。运行a.out（设置实时进程需要root权限），然后top看看：
12345678910111213kouu@kouu-one:/dev/cgroup/cpu$ top -c ...... Cpu(s): 31.4%us, 0.7%sy, 0.0%ni, 68.0%id, 0.0%wa, 0.0%hi, 0.0%si, 0.0%st ...... PID USER PR NI VIRT RES SHR S %CPU %MEM TIME+ COMMAND 28324 root -51 0 1620 332 272 R 60 0.0 0:06.49 ./a.out ......
可以看到，CPU虽然闲着，但是却不分给a.out程序使用。由于双核的原因，a.out实际的CPU占用是60%而不是30%。
其他
前段时间，有一篇“200+行Kernel补丁显著改善Linux桌面性能”的新闻比较火。这个内核补丁能让高负载条件下的桌面程序响应延迟得到大幅度降低。其实现原理是，自动创建基于TTY的task_group，所有进程都会被放置在它所关联的TTY组中。通过这样的自动分组，就将桌面程序（Xwindow会占用一个TTY）和其他终端或伪终端（各自占用一个TTY）划分开了。终端上运行的高负载程序（比如make -j64）对桌面程序的影响将大大减少。（根据前面描述的普通进程的组调度的实现可以知道，如果一个任务给系统带来了很高的负载，只会影响到与它同组的进程。这个任务包含一个或是一万个TASK_RUNNING状态的进程，对于其他组的进程来说是没有影响的。）
标签：
版权声明：转载此文是出于传递更多信息之目的。若有来源标注错误或侵犯了您的合法权益，请作者持权属证明与本网联系，我们将及时更正、删除，谢谢您的支持与理解。