分类: LINUX
2009-08-06 23:14:41
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 中实现)。
鉴于以下原因,需要对策略作出一些更改:
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 sched_entity { /* Defined in 2.6.23:/usr/include/linux/sched.h */ |
该调度类类似于一个模块链,协助内核调度程序工作。每个调度程序模块需要实现 struct sched_class
建议的一组函数。
struct sched_class { /* Defined in 2.6.23:/usr/include/linux/sched.h */ |
我们来看一下清单 3 中的函数:
enqueue_task
:当某个任务进入可运行状态时,该函数将得到调用。它将调度实体(进程)放入红黑树中,并对 nr_running
变量加 1。dequeue_task
:当某个任务退出可运行状态时调用该函数,它将从红黑树中去掉对应的调度实体,并从 nr_running
变量中减 1。yield_task
:在 compat_yield sysctl
关闭的情况下,该函数实际上执行先出队后入队;在这种情况下,它将调度实体放在红黑树的最右端。 check_preempt_curr
:该函数将检查当前运行的任务是否被抢占。在实际抢占正在运行的任务之前,CFS 调度程序模块将执行公平性测试。这将驱动唤醒式(wakeup)抢占。 pick_next_task
:该函数选择接下来要运行的最合适的进程。 load_balance
:每个调度程序模块实现两个函数,load_balance_start()
和
load_balance_next()
,使用这两个函数实现一个迭代器,在模块的 load_balance
例程中调用。内核调度程序使用这种方法实现由调度模块管理的进程的负载平衡。 set_curr_task
:当任务修改其调度类或修改其任务组时,将调用这个函数。task_tick
:该函数通常调用自 time
tick 函数;它可能引起进程切换。这将驱动运行时(running)抢占。 task_new
:内核调度程序为调度模块提供了管理新任务启动的机会。CFS 调度模块使用它进行组调度,而用于实时任务的调度模块则不会使用这个函数。 对于每个运行队列,都提供了一种结构来保存相关红黑树的信息。
struct cfs_rq {/* Defined in 2.6.23:kernel/sched.c */ |
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 结尾的名称以纳秒为单位):
sched_latency_ns
:针对 CPU 密集型任务进行目标抢占延迟(Targeted preemption latency)。sched_batch_wakeup_granularity_ns
:针对 SCHED_BATCH
的唤醒(Wake-up)粒度。sched_wakeup_granularity_ns
:针对 SCHED_OTHER
的唤醒粒度。sched_compat_yield
:由于 CFS 进行了改动,严重依赖 sched_yield()
的行为的应用程序可以要求不同的性能,因此推荐启用 sysctls
。 sched_child_runs_first
:child 在 fork
之后进行调度;此为默认设置。如果设置为 0,那么先调度 parent。 sched_min_granularity_ns
:针对 CPU 密集型任务执行最低级别抢占粒度。 sched_features
:包含各种与调试相关的特性的信息。 sched_stat_granularity_ns
:收集调度程序统计信息的粒度。下面是系统中运行时参数的典型值:
[root@dodge ~]# sysctl -A|grep "sched" | grep -v "domain" |
新调度程序附带了一个非常棒的调试接口,还提供了运行时统计信息,分别在 kernel/sched_debug.c 和 kernel/sched_stats.h 中实现。要提供调度程序的运行时信息和调试信息,需要将一些文件添加到 proc pseudo 文件系统:
sched_debug_show()
函数并在 sched_debug.c 中定义。 show_schedstat()
函数将处理 proc 条目中的读操作。 proc_sched_show_task()
函数 Linux 2.6.24 版本中有哪些值得期待的新变化?新版本中不再追赶全局时钟(fair_clock
),任务之间将彼此追赶。将引入每个任务(调度实体)的时钟 vruntime
(wall_time
/task_weight
),并且将使用近似的平均时间初始化新任务的时钟。
其他重要改动将影响关键数据结构。下面展示了 struct sched_entity
中的预期变动:
struct sched_entity { /* Defined in /usr/include/linux/sched.h */ |
以下是 struct cfs_rq
中的变动:
struct cfs_rq { /* Defined in kernel/sched.c */ |
组任务中引入了一个全新结构:
struct task_group { /* Defined in kernel/sched.c */ |
每个任务都跟踪它的运行时,并根据该值对任务进行排队。这意味着运行最少的任务将位于树的最左侧。同样,通过对时间加权划分优先级。每个任务在下面的时间段内力求获得精确调度:
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 赢得了高度的评价。