使用完全公平调度程序（CFS）进行多任务处理

2536阅读　0评论2009-08-06　chinahhucai
分类：LINUX

Linux® 2.6.23 内核附带了一个模块化调度程序内核和一个被实现为调度模块的完全公平调度程序（Completely Fair Scheduler，CFS）。本文将介绍 CFS 的主要特性和工作原理，并提前预览 2.6.24 版本中的预期变动。®

Linux 2.6.23 内核的调度程序为其他调度模块并行处理内核打好了基础（这里所说的 “模块化” 并不意味着将调度程序分解为若干可加载的模块，而是指代码本身模块化）。有关调度程序工作原理的更多细节，请参考 developerWorks 文章 “Inside the Linux scheduler”（参见本文末尾 参考资料 小节中的链接）。

最新版调度程序引入的主要特性包括：

调度类的引入显著增强了内核调度程序的可扩展性。这些类（调度程序模块）封装了调度策略。这个调度程序将调度策略模块化，但是与 Pluggable CPU 调度程序框架不同的是，并没有把调度程序本身模块化（后者在内核编译时选择默认调度程序，而通过在启动时向内核传递参数来使用其他 CPU 调度程序）。

完 全公平调度程序（CFS）试图按照对 CPU 时间的 “最大需求（gravest need）” 运行任务；这有助于确保每个进程可以获得对 CPU 的公平共享。如果某个任务休眠时间 “非常短”，那么 CFS 不会将该任务视为休眠任务 — 短暂休眠的进程可能会获得一些额外时间，但是决不会超过它的未休眠时间。

考 虑一个两用户示例，用户 A 和用户 B 在一台机器上运行作业。用户 A 只有两个作业正在运行，而用户 B 正在运行 48 个作业。组调度使 CFS 能够对用户 A 和用户 B 进行公平调度，而不是对系统中运行的 50 个作业进行公平调度。每个用户各拥有 50% 的 CPU 使用。用户 B 使用自己 50% 的 CPU 分配运行他的 48 个作业，而不会占用属于用户 A 的另外 50% 的 CPU 分配。

CFS 调度模块（在 kernel/sched_fair.c 中实现）用于以下调度策略：SCHED_NORMAL、SCHED_BATCH 和 SCHED_IDLE。对于 SCHED_RR 和 SCHED_FIFO 策略，将使用实时调度模块（该模块在 kernel/sched_rt.c 中实现）。

鉴于以下原因，需要对策略作出一些更改：

Con Kolivas 证明了实现 “公平调度” 不会与交互性的延迟目标相冲
突。他已经使用 RSDL/SD 调度程序证明，公平性可以很轻易地实现，不需要使用复杂的启发式处理来判断进程的交互性。

CFS 没有使用优先级数组，它去掉了 vanilla 调度程序的数组切换工件。RSDL 和 CFS 之间的重要区别包括以下几点：

CFS 不会跟踪休眠时间，也不会使用启发式处理识别交互式任务 — 它仅仅确保在既定时间内，对于一定数量的可运行进程，每个进程获得公平的 CPU 占用。

对于每个 CPU，CFS 使用按时间排序的红黑（red-black）树。

该树方法能够良好运行的原因在于：

让我们了解一下实现这种新调度程序的一些关键数据结构。

CFS 去掉了 struct prio_array，并引入调度实体（scheduling entity）和调度类 （scheduling classes），分别由 struct sched_entity 和 struct sched_class 定义。因此，task_struct 包含关于 sched_entity 和 sched_class 这两种结构的信息：



 
struct task_struct { /* Defined in 2.6.23:/usr/include/linux/sched.h */
....
-   struct prio_array *array;
+  struct sched_entity se;
+  struct sched_class *sched_class;
   ....
   ....
};

该结构包含了完整的信息，用于实现对单个任务或任务组的调度。它可用于实现组调度。调度实体可能与进程没有关联。 



struct sched_entity { /* Defined in 2.6.23:/usr/include/linux/sched.h */
 long wait_runtime;   /* Amount of time the entity must run to become completely */
                      /* fair and balanced.*/
 s64 fair_key;
 struct load_weight   load;         /* for load-balancing */
 struct rb_node run_node;            /* To be part of Red-black tree data structure */
 unsigned int on_rq; 
 ....
};

该调度类类似于一个模块链，协助内核调度程序工作。每个调度程序模块需要实现 struct sched_class 建议的一组函数。



 
struct sched_class { /* Defined in 2.6.23:/usr/include/linux/sched.h */
      struct sched_class *next;
      void (*enqueue_task) (struct rq *rq, struct task_struct *p, int wakeup);
      void (*dequeue_task) (struct rq *rq, struct task_struct *p, int sleep);
      void (*yield_task) (struct rq *rq, struct task_struct *p);

      void (*check_preempt_curr) (struct rq *rq, struct task_struct *p);

      struct task_struct * (*pick_next_task) (struct rq *rq);
      void (*put_prev_task) (struct rq *rq, struct task_struct *p);

      unsigned long (*load_balance) (struct rq *this_rq, int this_cpu,
                 struct rq *busiest,
                 unsigned long max_nr_move, unsigned long max_load_move,
                 struct sched_domain *sd, enum cpu_idle_type idle,
                 int *all_pinned, int *this_best_prio);

      void (*set_curr_task) (struct rq *rq);
      void (*task_tick) (struct rq *rq, struct task_struct *p);
      void (*task_new) (struct rq *rq, struct task_struct *p);
};

我们来看一下清单 3 中的函数：

对于每个运行队列，都提供了一种结构来保存相关红黑树的信息。 



struct cfs_rq {/* Defined in 2.6.23:kernel/sched.c */
      struct load_weight load;
      unsigned long nr_running;

      s64 fair_clock; /* runqueue wide global clock */
      u64 exec_clock;
      s64 wait_runtime;
      u64 sleeper_bonus;
      unsigned long wait_runtime_overruns, wait_runtime_underruns;

      struct rb_root tasks_timeline; /* Points to the root of the rb-tree*/
      struct rb_node *rb_leftmost; /* Points to most eligible task to give the CPU */
      struct rb_node *rb_load_balance_curr;
#ifdef CONFIG_FAIR_GROUP_SCHED
      struct sched_entity *curr; /* Currently running entity */
      struct rq *rq;      /* cpu runqueue to which this cfs_rq is attached */
      ...
      ...
#endif
};

CFS 调度程序使用安抚（appeasement）策略确保公平性。当某个任务进入运行队列后，将记录当前时间，当某个进程等待 CPU 时，将对这个进程的 wait_runtime 值加一个数，这个数取决于运行队列当前的进程数。当执行这些计算时，也将考虑不同任务的优先级值。 将这个任务调度到 CPU 后，它的 wait_runtime 值开始递减，当这个值递减到其他任务成为红黑树的最左侧任务时，当前任务将被抢占。通过这种方式，CFS 努力实现一种理想 状态，即 wait_runtime 值为 0！

CFS 维护任务运行时（相对于运行队列级时钟，称为 fair_clock(cfs_rq->fair_clock)），它在某个实际时间的片段内运行，因此，对于单个任务可以按照理想的速度运行。


例如，如果具有 4 个可运行的任务，那么 fair_clock 将按照实际

时间速度的四分之一增加。每个任务将设法跟上这个速度。这是由分时多任务处理的量子化特性决定的。也就是说，在任何一个时间段内只有一个任务可以运行；因此， 其他进程在时间上的拖欠将增大（wait_runtime）。因此，一旦某个任务进入调度，它将努力赶上它所欠下的时间（并且要比所欠时间多一点，因为在追赶时间期间，fair_clock 不会停止计时）。

加权任务引入了优先级。假设我们有两个任务：其中一个任务占用 CPU 的时间量是另一个任务的两倍，比例为 2:1。执行数学转换后，对于权重为 0.5 的任务，时间流逝的速度是以前的两倍。

我们根据 fair_clock 对树进行排队。

请注意，CFS 没有使用时间片（time slices），至少，没有优先使用。CFS 中的时间片具有可变的长度并且动态确定。

对于负载平衡程序，调度模块实现了迭代器，使用它遍历由调度模块管理的所有任务，从而进行负载平衡。

引入了重要的 sysctls 来在运行时对调度程序进行调优（以 ns 结尾的名称以纳秒为单位）：

下面是系统中运行时参数的典型值： 



[root@dodge ~]# sysctl -A|grep "sched" | grep -v "domain"
kernel.sched_min_granularity_ns = 4000000
kernel.sched_latency_ns = 40000000
kernel.sched_wakeup_granularity_ns = 2000000
kernel.sched_batch_wakeup_granularity_ns = 25000000
kernel.sched_stat_granularity_ns = 0
kernel.sched_runtime_limit_ns = 40000000
kernel.sched_child_runs_first = 1
kernel.sched_features = 29
kernel.sched_compat_yield = 0
[root@dodge ~]#

新调度程序附带了一个非常棒的调试接口，还提供了运行时统计信息，分别在 kernel/sched_debug.c 和 kernel/sched_stats.h 中实现。要提供调度程序的运行时信息和调试信息，需要将一些文件添加到 proc pseudo 文件系统：


Linux 2.6.24 版本中有哪些值得期待的新变化？新版本中不再追赶全局时钟（fair_clock），任务之间将彼此追赶。将引入每个任务（调度实体）的时钟 vruntime（wall_time/task_weight），并且将使用近似的平均时间初始化新任务的时钟。

其他重要改动将影响关键数据结构。下面展示了 struct sched_entity 中的预期变动： 



struct sched_entity { /* Defined in /usr/include/linux/sched.h */
- long    wait_runtime;
- s64     fair_key;
+ u64     vruntime;
- u64     wait_start_fair;
- u64     sleep_start_fair;
      ...
      ...
}

以下是 struct cfs_rq 中的变动：



 
 struct cfs_rq { /* Defined in kernel/sched.c */
-         s64 fair_clock;
-         s64 wait_runtime;
-         u64 sleeper_bonus;
-         unsigned long wait_runtime_overruns, wait_runtime_underruns;
+        u64 min_vruntime;
 
+        struct sched_entity *curr;
 
+#ifdef CONFIG_FAIR_GROUP_SCHED
       ...
+        struct task_group *tg;    /* group that "owns" this runqueue */
       ...
#endif
 };

组任务中引入了一个全新结构： 



struct task_group { /* Defined in kernel/sched.c */
    #ifdef CONFIG_FAIR_CGROUP_SCHED
        struct cgroup_subsys_state css;
   #endif
        /* schedulable entities of this group on each cpu */
        struct sched_entity **se;
        /* runqueue "owned" by this group on each cpu */
        struct cfs_rq **cfs_rq;
        unsigned long shares;
        /* spinlock to serialize modification to shares */
        spinlock_t lock;
        struct rcu_head rcu;
};

每个任务都跟踪它的运行时，并根据该值对任务进行排队。这意味着运行最少的任务将位于树的最左侧。同样，通过对时间加权划分优先级。每个任务在下面的时间段内力求获得精确调度：

sched_period = (nr_running > sched_nr_latency) ? sysctl_sched_latency : ((nr_running * sysctl_sched_latency) / sched_nr_latency)

其中 sched_nr_latency = (sysctl_sched_latency / sysctl_sched_min_granularity)。这表示，当可运行任务数大于 latency_nr 时，将线性延长调度周期。sched_fair.c 中定义的 sched_slice() 是进行这些计算的位置。

因此，如果每个可运行任务运行与 sched_slice() 等价的时间，那么将花费的时间为 sched_period，每个任务将运行与其权重成比例的时间量。此外，在任何时刻，CFS 都承诺超前运行 sched_period，因为最后执行调度的任务将在这个时限内再次运行。

因此，当一个新任务变为可运行状态时，对其位置有严格的要求。在所有其他任务运行之前，此任务不能运行；否则，将破坏对这些任务作出的承诺。然而，由于该任务确实进行了排队，对运行队列的额外权重将缩短其他所有任务的时间片，在 sched_priod 的末尾释放一点位置，刚好满足新任务的需求。这个新的任务就被放在这个位置。

在 2.6.24 中，您将能够对调度程序进行调优，从而实现对用户或组的公平性，而不是任务公平性。可以将任务进行分组，形成多个实体，调度程序将平等对待这些实体，继而公平对待实体中的任务。要启用这个特性，在编译内核时需要选择 CONFIG_FAIR_GROUP_SCHED。目前，只有 SCHED_NORMAL 和 SCHED_BATCH 任务可以进行分组。

可以使用两个独立的方法对任务进行分组，它们分别基于：

内核配置参数 CONFIG_FAIR_USER_SCHED 和 CONFIG_FAIR_CGROUP_SCHED 可帮助您进行选择。




通过引入调度类并通过增强调度统计信息来简化调试，这个新的调度程序进一步扩展了调度功能。当针对线程密集型应用程序（包括 3D 游戏）进行测试时，CFS 赢得了高度的评价。

上一篇：kmem_cache_init初始化文字解析
下一篇：运行队列函数入队操作分析enqueue_task_fair