Linux内核组调度的研究与应用

杜慧江，王云光

0 引言

进程调度是操作系统内核的重要组成部分，直接影响着操作系统的效率。常用的调度算法一般基于静态或动态优先级，维护若干个优先级不同的运行队列；有些情况下要采取特殊方法对待，调度过程相对复杂。Linux2.6.23以后内核采用完全公平调度算法CFS[1]，取消了优先级队列，公平对待每一个进程，算法和实现简单清晰，效率也较高。但是在公平对待所有进程的同时，也存在一些不足，例如：假设在系统中有两个任务，任务A拥有一个进程；任务B的进程拥有多个子进程。如果简单地公平对待所有进程，则任务B就会占用大部分CPU时间，在任务级别上违背了公平原则。

1 组调度

针对上述不足，Linux内核在2.6.26之后加入了组调度[1]：将上例任务B的多个子进程分为一组，将任务A单独作为一组，将两个组用CFS算法公平调度，A和B各占有50%的CPU时间。当调度器将CPU时间分配给任务B时，再进一步确定应该分配给B的哪个子进程。这样对于A和B两个任务，是公平的。

分组的方法不只限定为根据每个任务的进程所属关系，也可以根据用户来分：比如教师为一组，学生为另一组；或者系统管理员一组，数据库管理员一组，普通用户一组等。

Linux 2.6.27内核有三种分组调度方式：公平组调度CONFIG_FAIR_GROUP_SCHED、实时组调度CONFIG_RT_GROUP_SCHED和控制组调度CONFIG_CGROUP_SCHED[2]。这几种方式在内核中都有对应的布尔开关参数来控制，并且都以CONFIG_GROUP_SCHED参数为真作为前提条件。

1.1 公平组调度

公平组调度建立在CFS算法的基础上。CFS用基于时间计算键值的红黑树来选取下一个任务，公平组调度对此做了一些改变[4]：

首先，创建了调度实体sched_entity取代单个进程作为调度对象，作为红黑树的叶子结点。sched_entity 是一个结构体，既封装了与需要调度的若干个进程有关的信息，又没有改变CFS调度算法的工作方式；它代表一组指定的进程；每个实体都有自己的一个运行队列，同时也都有一个父亲指针、一个指向需要调度的运行队列的指针。

在内核代码的/include/linux/sched.h中定义了sched_entity：

其次，公平组调度采用了嵌套层次结构。在顶层有一棵红黑树，所有叶子结点都是一个调度实体；这层的调度实体如果不只是一个单独的进程而是包含一组进程，就嵌套一棵子红黑树，每个子进程都处于子红黑树的叶子结点。还可以继续嵌套下去，不过目前的Linux内核还没有实现更多层次的嵌套调度。

当调度器挑选下一个将要运行的任务时，它查找所有顶层的调度实体并且找出最应当占用CPU的那个实体，也就是顶层红黑树最左边的叶子结点；如果那个实体不只是一个进程，而是一个有多个进程的调度实体，那么调度器就查找该实体的运行队列，继续寻找其中应该获得CPU的任务，沿着层次向下直到找到一个实际的进程。当进程开始运行，有关的运行信息被收集起来，沿着层次结构向上传送以便当前进程的CPU占用情况可以被每个层次知晓。

1.2 实时组调度

实时组调度要调度多个包含实时任务的组，就要给每个组分配固定比例的可用CPU时间。如果没有给定占用CPU时间的下限，很明显一个组会被别的组挤占；如果没有给定占用CPU时间的上限，则会挤占不属于自己的CPU时间，因此只能分配某个固定的比例。

CPU时间是根据每个组在一个周期内可以占用的比例来分配的，给每个实时组都分配某个比例，这个比例内的CPU时间别的组不能占用。没有分配给实时组的时间，会被用在普通优先级的任务；分配给实时组的时间如果没有被使用，也会被转给普通优先级的任务。

例如：一个实时渲染任务要求达到每秒25帧，即帧之间的间隔最多为 0.04秒；并且同时还要播放音乐、响应用户输入。渲染任务属于图形组，音乐属于音频组。如果cpu时间的80%分配给图形组，也就是渲染任务的每两帧之间的时间间隔最多0.032秒。于是，图形组会有0.04秒的周期，最多占用其中 0.032秒。如果音频组需要每 0.005秒填充DMA缓冲，但是只需要 3%时间就可以完成，那么音频组会被分配0.005秒的时间，但是只用0.00015秒运行。空余出来的0.00485秒会被用于用户输入和其他任务。

要让某个组加入实时组调度，必须先给这个组分配一定比例的CPU时间，然后实时任务才能运行；否则，哪怕这个组的任务已经有了实时运行的优先级也不行。默认情况下，所有的CPU时间都被分给root组，如果想分CPU时间给别的组，就要减少root组的配额然后把空出的CPU时间分给别的组。

1.3 控制组调度

控制组调度可以让管理员随意对系统中的任务分组，它是基于控制组虚拟文件系统来实现的。控制组在以下方面对内核做了扩展：

1) 组内每个任务有对css_set引用计数的指针；

2) css_set包含一系列对子系统状态的引用计数指针。为了提高性能，没有从任务到某个层次中某个控制组的直接链接，但是可以用这些指针找到控制组。

3) 控制组的文件系统可以被加载或者从用户空间操纵。

4) 可以列出控制组中所有的任务。

5) 启动后系统拥有初始的根控制组和css_set

6) 用建立和解除与css_set的联系来完成fork和exit操作。

在cgroup.h文件中定义了cgroup如下：

控制组调度引入了子系统和层次两个概念，可以把一系列任务、子任务聚合或分割到设定了定制行为的组中。

子系统：一个子系统是一个模块，利用控制组功能提供的分组工具，为控制组内的任务调度资源或者实现针对该分组的某些资源占用限制。为了简单也可以把一个子系统理解为一个组。

层次：指位于树中同一层的多个控制组，每个任务必定属于某个控制组。

每个子系统有系统指定的状态，与层次中的每个控制组联接。每个层次有一个组虚拟文件系统（VFS）的实例和它自己联接。

可以举例来说明子系统和层次之间的关系。服务器上有几种不同的用户：学生、教授和系统任务。那么cpu资源可以如下规划：把cpu资源分为两个层，顶层是top CPU set，第二层有两个cpuset，分别是cpuset1和cpuset2。

图1 子系统和层次关系

系统任务被联系在顶层的 cputset，可能会在任何 cpu时间运行，上限是20%的cpu时间。其他资源的分配如下：

内存：教授50%，学生30%，系统20%

磁盘：教授50%，学生30%，系统20%

网络：WWW浏览20%，NFS网络文件服务60%，其他20%；WWW中教授15%，学生5%

浏览器进程归入WWW的网络组，nfs文件访问进程归入NFS网络组；浏览器会依据打开浏览器的是教授还是学生来分享适当比例的CPU、内存、磁盘和网络资源。

然后可以回头看一下sched.c中task_group的定义，不难理解其中针对每种调度方式的变量设置：

2 应用

在2.6.28内核中，增加了两个互斥的公平组调度实现[2]：基于用户 id对任务组公平调度CONFIG_FAIR_USER_SCHED和基于控制组虚拟文件系统对任务组公平调度CONFIG_FAIR_CGROUP_SCHED。某一时刻只能选择其中一种方式，在运行过程中调度参数可以调整。下面通过举例说明公平用户组调度和公平控制组两种方式的使用方法：

当内核CONFIG_FAIR_USER_SCHED参数打开后，在/sys/kernel/uids目录中会为每一个新用户创建一个子目录,其中有一个“cpu_share”文件。

当内核CONFIG_FAIR_CGROUP_SCHED参数打开后，每个用虚拟文件系统创建的用户组都会有一个属于自己的“cpu.shares”文件。

3 结论

通过公平组调度、实时组调度、控制组调度等几种组调度方式，Linux内核扩展了进程调度的范畴、丰富了调度的手段，能够更出色地适应多种应用需求。

[1] Molnar Ingo. Modular Scheduler Core and Completely Fair Scheduler[EB/OL] .(2007-04-13).http://lkml.org/lkml/2007/4/13/180.

[2] Linux内核文档(2.6.27.1) [CP] . Documentation/scheduler/sched-design-CFS.txt. (2008-10-16).http://www.kernel.org.

[3] Avinesh Kumar.使用完全公平调度程序进行多任务处理[EB/OL] .(2008-02-04).http://www.ibm.com/developerwor ks/cn/linux/l-cfs/index.html.

[4] Linux内核源代码(2.6.27.1) [CP] . (2008-10-16).http://lxr.linux.no/linux/init/Kconfig.