Linux内核组调度研究与应用.pdfVIP

Microcomputer Applications Vol. 26, No.2, 2010 学习园地 微型电脑应用 2010 年第 26 卷第 2 期 文章编号：1007-757X(2010)2-0062-03 Linux 内核组调度的研究与应用 杜慧江，王云光 摘 要：进程调度是操作系统内核的重要功能。组调度是当前操作系统内核调度算法的发展方向之一，在 linux 必威体育精装版内核中， 在完全公平调度算法 CFS 的基础之上，实现了基于分组的进程调度。该文以 Kernel2.6.27 源代码为参考，从数据结构和程序 实现等方面对组调度算法做了分析，并举例说明了组调度应用的方法。 关键词：Linux; 内核; 组调度 中图分类号：TP316 文献标志码：A 0 引言 每个实体都有自己的一个运行队列，同时也都有一个父亲指 针、一个指向需要调度的运行队列的指针。 进程调度是操作系统内核的重要组成部分，直接影响着 在 内 核 代 码 的 /include/linux/sched.h 中 定 义 了 操作系统的效率。常用的调度算法一般基于静态或动态优先 sched_entity： 级，维护若干个优先级不同的运行队列；有些情况下要采取 struct sched_entity { 特殊方法对待，调度过程相对复杂。Linux2.6.23 以后内核 struct load_weight load; 采用完全公平调度算法 CFS[1] ，取消了优先级队列，公平对 struct rb_node run_node; /*实体在红黑树对应结点*/ 待每一个进程，算法和实现简单清晰，效率也较高。但是在 struct list_head group_node; 公平对待所有进程的同时，也存在一些不足，例如：假设在 … … 系统中有两个任务，任务 A 拥有一个进程；任务 B 的进程 #ifdef CONFIG_FAIR_GROUP_SCHED 拥有多个子进程。如果简单地公平对待所有进程，则任务 B struct sched_entity *parent; 就会占用大部分 CPU 时间，在任务级别上违背了公平原则。 struct cfs_rq *cfs_rq; /*实体所处红黑树运行队列*/ struct cfs_rq *my_q; /*实体的红黑树运行队列*/ 1 组调度 #endif }; 针对上述不足，Linux 内核在2.6.26 之后加入了组调度 其次，公平组调度采用了嵌套层次结构。在顶层有一棵 [1] ：将上例任务 B 的多个子进程分为一组，将任务 A 单独 红黑树，所有叶子结点都是一个调度实体；这层的调度实体 作为一组，将两个组用 CFS 算法公平调度，A 和 B 各占有 如果不只是一个单独的进程而是包含一组进程，就嵌套一棵 50%的CPU 时间。当调度器将 CPU 时间分配给任务B 时， 子红黑树，每个子进程都处于子红黑树的叶子结点。还可以 再进一步确定应该分配给 B 的哪个子进程。这样对于 A 和 继续嵌套下去，不过目前的 Linux 内核还没有实现更多层次 B 两个任务，是公平的。 的嵌套调度。 分组的方法不只限定为根据每个任务的进程所属关系， 当调度器挑选下一个将要运行的任务时，它查找所有顶 也可以根据用户来分：比如教师为一组，学生为另一组；或 层的调度实体并且找出最应当占用