FreeBSDULE调度器浅析
FreeBSD 5-CURRENT刚刚引入了一个名为ULE调度器的内核调度单元调度器。这个调度器在SMP系统中的效率要远好于FreeBSD以前版本的调度器(目前，那个调度器被称为4BSD调度器)。
新的ULE调度器的设计更像Solaris和Linux等操作系统的调度器。Solaris的SMP性能非常好这一点是它的卖点之一，其调度器采用的优秀算法就是一个很重要的原因。BSD派生系统，尽管由于系统整体设计的合理，以及操作系统其他部分的卓越性能弥补了它在SMP调度器上的不足，甚至尽管FreeBSD在绝大多数情况下的性能都超过
其他系统，但它使用的4BSD调度器的SMP性能不高仍然为人诟病。
令人高兴的是，全新设计的ULE调度器引入了Solaris、Linux等系统在SMP调度方面的先进算法，并且，它在单处理器系统中的性能也相当不错，与4BSD调度器的性能相当。
为什么新的ULE调度器能够获得更高的性能呢？最主要的原因在于，新的ULE调度器为每一个CPU单独维护运行队列，并且，CPU之间能够相互“窃取”对方就绪队列中的任务，从而达到更好的平衡。基本上，ULE调度器的设计符合下面的原则：尽可能利用更多的执行资源，尽可能使用局部锁，尽可能避免使用浪费执行资源的自旋锁，尽可能采用高效的调度算法(目前ULE调度器采用的算法的复杂度是O(1))。
在笔者撰写这篇文章的时候，ULE调度器仍然处于进一步完善的过程中。一方面，它已经能够提供比4BSD调度器更好的调度性能——内核态调度开销减少大约25%，而用户态的计算也有一定程度的缩减。
本文所说的ULE调度器(src/sys/kern/sched_ule.c)的cvs tag是$FreeBSD: src/sys/kern/sched_ule.c,v 1.8 2003/02/03 05:30:07 jeff Exp $
未来版本的ULE调度器可能会和这个版本有一些出入，但不会太大。
如果需要，您可以在这里下载所需的源代码[当然，我个人建议您还是checkout一份FreeBSD-CURRENT的源代码]。由于引用
了调度器中的代码，根据源代码的授权许可协议，以下首先重述它的版权声明。这份代码使用的是典型的BSD风格授权。为了不至造成阅读困难，这断代马没有作语法点亮。/*-* Copyright (c) 2003, Jeffrey Roberson* All rights reserved.** Redistribution and use in source and binary forms, with or without* modification, are permitted provided that the following conditions* are met:* 1. Redistributions of source code must retain the above copyright* notice unmodified, this list of conditions, and the following* disclaimer.* 2. Redistributions in binary form must reproduce the above copyright* notice, this list of conditions and the following disclaimer in the* documentation and/or other materials provided with the distribution.** THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.*/中文大意如下，供参考；与英文不一致的地方以英文版本为准。版权所有©2003 Jeffrey Roberson ，保留所有权力。在满足下列条件的前提下，允许重新分发修改过或未经修改的，以源代码或已编译形式存在的本软件：1. 以源代码形式的发布必须保留未经修改的上述版权声明、本许可条件，以及其后的不承诺条款。2. 以已编译形式的发布必须在发布版本的文档和/或其他资料上重述上述版权声明、本许可条件，以及其后的不承诺条款。此软件由其作者以“即此”方式提供。无论明示的或暗示的，包括但不必限于间接的关于基于某种目的的适销性、实用性，在此皆明示不予保证。在任何情况下，作者皆不对由于使用此软件造成的，直接、间接、连带、特别、惩戒或因此而来造成的损害(包括，但不必限于获得替代品及服务，无法使用，丢失数据，损失盈利或业务中断)，无论此类损害是如何造成的，基于何种责任推断，是否属于合同范畴，严格赔偿责任或民事侵权行为(包括疏忽和其他原因)承担任何责任，即使预先被告知此类损害可能发生。
在这个调度器中，仍然有许多部分标注了“XXX”，这些部分目前还没有经过充分的优化，或者需要在未来进行较大规模的修改；此外，其中的注释有一些和源代码不一致的地方，这些部分我会尽量进行最低限度(即，不影响代码原意)的修正或避开。此外，部分调度器的细节我也不打算进行详细的描述——这可能包括一些与调度器本身关系不密切的宏定义，等等。如果您对调度器的这些部分感兴趣，请自行察看代码。
一般性数据结构
这些数据结构贯穿ULE调度器的几乎所有代码。进程调度的时间单位是tick，它是hz的倒数。struct ke_sched {
int ske_slice;
struct runq *ske_runq;
/* 以下变量仅用于计算进程所用CPU时间 */
int ske_ltick;/* 执行体的最后一个tick */
int ske_ftick;/* 执行体的第一个tick */
int ske_ticks;/* tick总数 */
u_char ske_cpu;};#define ke_slice ke_sched->ske_slice#define ke_runq ke_sched->ske_runq#define ke_ltick ke_sched->ske_ltick#define ke_ftick ke_sched->ske_ftick#define ke_ticks ke_sched->ske_ticks#define ke_cpu ke_sched->ske_cpustruct kg_sched {
int skg_slptime;};#define kg_slptime kg_sched->skg_slptimestruct td_sched {
int std_slptime;
int std_schedflag;};#define td_slptime td_sched->std_slptime#define td_schedflag td_sched->std_schedflag/** 线程将作为一种短期的休眠处理*/#define TD_SCHED_BLOAD 0x0001struct td_sched td_sched;struct ke_sched ke_sched;struct kg_sched kg_sched;struct ke_sched *kse0_sched = &ke_sched;struct kg_sched *ksegrp0_sched = &kg_sched;struct p_sched *proc0_sched = NULL;struct td_sched *thread0_sched = &td_sched;
关于内核调度实体时间片的一些宏定义#define SCHED_SLICE_MIN (hz / 100)#define SCHED_SLICE_MAX (hz / 4)#define SCHED_SLICE_RANGE (SCHED_SLICE_MAX - SCHED_SLICE_MIN + 1)#define SCHED_SLICE_SCALE(val, max) (((val) * SCHED_SLICE_RANGE) / (max))#define SCHED_PRI_TOSLICE(pri)
(SCHED_SLICE_MAX - SCHED_SLICE_SCALE((pri), SCHED_PRI_RANGE))#define SCHED_SLP_TOSLICE(slp)
(SCHED_SLICE_MAX - SCHED_SLICE_SCALE((slp), SCHED_SLP_MAX))#define SCHED_SLP_COMP(slice) (((slice) / 5) * 3) /* 60% */#define SCHED_PRI_COMP(slice) (((slice) / 5) * 2) /* 40% */
这些宏定义的名称非常容易理解：SCHED_SLICE_MIN-线程时间片最小长度，SCHED_SLICE_MAX-线程时间片最大长度，SCHED_SLICE_RANGE-时间片长度可选范围，SCHED_SLICE_SCALE-按比例计算的时间片长度，SCHED_PRI_TOSLICE-根据优先级计算的时间片长度，SCHED_SLP_TOSLICE-根据休眠时间计算时间片长度(反比)；SCHED_SLP_COMP和SCHED_PRI_COMP宏决定时间片长度中，休眠加权和优先级加权分别所占的份额。
宏SCHED_CURR确定进程调度实体属于当前运行队列(运行态)，还是下一运行队列(就绪态)：#define SCHED_CURR(kg) ((kg)->kg_slptime > (hz / 4) ||
(kg)->kg_pri_class != PRI_TIMESHARE)
kseq结构，它包括一队执行队列，每一个处理器都有一个：struct kseq {
struct runq ksq_runqs[2];
struct runq *ksq_curr;
struct runq *ksq_next;
int ksq_load; /* 运行队列长度 */#ifdef SMP
unsigned int ksq_rslices; /* 运行队列时间片数 */
unsigned int ksq_bload; /* 等待I/O的线程数 */#endif};
下面是一部分关于kse(进程调度实体)的操作，它们与处理器相关，换言之，这些操作都是针对特定处理器的执行队列进行的：static __inline voidkseq_add(struct kseq *kseq,struct kse *ke){
runq_add(ke->ke_runq, ke);
kseq->ksq_load++;#ifdef SMP
kseq->ksq_rslices += ke->ke_slice;#endif}static __inline voidkseq_rem(struct kseq *kseq,struct kse *ke){
kseq->ksq_load--;
runq_remove(ke->ke_runq, ke);#ifdef SMP
kseq->ksq_rslices -= ke->ke_slice;#endif}#ifdef SMPstatic __inline voidkseq_sleep(struct kseq *kseq,struct kse *ke){
kseq->ksq_bload++;}static __inline voidkseq_wakeup(struct kseq *kseq,struct kse *ke){
kseq->ksq_bload--;}struct kseq *kseq_load_highest(void){
struct kseq *kseq;
int load;
int cpu;
int i;cpu = 0;
load = 0;for (i = 0; i < mp_maxid; i++) {
if (CPU_ABSENT(i))
continue;
kseq = KSEQ_CPU(i);
if (kseq->ksq_load > load) {
load = kseq->ksq_load;
cpu = i;
}
}
if (load)
return (KSEQ_CPU(cpu));
return (NULL);}#endifstruct kse *kseq_choose(struct kseq *kseq){
struct kse *ke;
struct runq *swap;
if ((ke = runq_choose(kseq->ksq_curr)) == NULL) {
swap = kseq->ksq_curr;
kseq->ksq_curr = kseq->ksq_next;
kseq->ksq_next = swap;
ke = runq_choose(kseq->ksq_curr);
}return (ke);}static voidkseq_setup(struct kseq *kseq){
kseq->ksq_curr = &kseq->ksq_runqs[0];
kseq->ksq_next = &kseq->ksq_runqs[1];
runq_init(kseq->ksq_curr);
runq_init(kseq->ksq_next);
kseq->ksq_load = 0;#ifdef SMP
kseq->ksq_rslices = 0;
kseq->ksq_bload = 0;#endif}static voidsched_setup(void *dummy){
int i;mtx_lock_spin(&sched_lock);
/* 初始化执行队列 */
for (i = 0; i < MAXCPU; i++)
kseq_setup(KSEQ_CPU(i));
mtx_unlock_spin(&sched_lock);}
这些函数比较容易解释。kseq_add、kseq_rem分别是在执行队列中添加和删除项目；kseq_sleep、kseq_wakeup分别让内核调度实体进入休眠和脱离休眠，并修正相关数值。kseq_load_highest返回执行队列最长的那个CPU的kseq指针(函数最终返回NULL，但这种情况在操作系统正常运行的前提下是不可能的)；kseq_setup初始化CPU的一对执行队列，它被sched_setup调用，后者用于系统初启时对系统的所有CPU的执行队列进行初始化。kseq_choose将被后面的函数调用，在此暂不介绍。
在ULE调度器中，kseq_开头的函数是ULE调度器特有的，它们被相关的BSD实现调用。前面sched_setup函数严格地说应该算BSD Unix实现接口的一部分。以下介绍其余部分：static intsched_priority(struct ksegrp *kg){
int pri;if (kg->kg_pri_class != PRI_TIMESHARE)
return (kg->kg_user_pri);pri = SCHED_SLP_TOPRI(kg->kg_slptime);
CTR2(KTR_RUNQ, "sched_priority: slptime: %dpri: %d",kg->kg_slptime, pri);pri += PRI_MIN_TIMESHARE;
pri += kg->kg_nice;if (pri > PRI_MAX_TIMESHARE)
pri = PRI_MAX_TIMESHARE;
else if (pri < PRI_MIN_TIMESHARE)
pri = PRI_MIN_TIMESHARE;kg->kg_user_pri = pri;return (kg->kg_user_pri);}
这个函数的作用是根据进程的“交互性”对进程的调度优先级进行调整，其返回值是新的调度优先级。
sched_slice主要是一些纯计算逻辑，它将根据内核调度实体的优先级、休眠时间计算最终该调度实体能够获得的时间片长度，这主要依靠了前面定义的那些宏。
sched_pctcpu_update对调度实体的执行时间进行重新计算。
请适当地参考前面所描述的数据结构。voidsched_pctcpu_update(struct kse *ke){
/*
* 调整pctcpu的计数器等信息
*/
ke->ke_ticks = (ke->ke_ticks / (ke->ke_ltick - ke->ke_ftick))
* SCHED_CPU_TICKS;
ke->ke_ltick = ticks;
ke->ke_ftick = ke->ke_ltick - SCHED_CPU_TICKS;}
sched_pickcpu是一段正在改进的调度代码。它将选出符合最轻(执行队列最短)的CPU。由于每次在增加新的调度实体时都会调用它，因此最终的结果是多个CPU得到的调度实体数基本平衡。当然，在执行过程中，CPU之间还可以“窃取”调度实体。关于这些机制将在后面介绍。voidsched_prio(struct thread *td, u_char prio){
struct kse *ke;
struct runq *rq;mtx_assert(&sched_lock, MA_OWNED);
ke = td->td_kse;
td->td_priority = prio;if (TD_ON_RUNQ(td)) {
rq = ke->ke_runq;runq_remove(rq, ke);
runq_add(rq, ke);
}}voidsched_switchout(struct thread *td){
struct kse *ke;mtx_assert(&sched_lock, MA_OWNED);ke = td->td_kse;td->td_last_kse = ke;
td->td_lastcpu = ke->ke_oncpu;
ke->ke_oncpu = NOCPU;
ke->ke_flags &= ~KEF_NEEDRESCHED;if (TD_IS_RUNNING(td)) {
setrunqueue(td);
return;
} else
td->td_kse->ke_runq = NULL;/*
* 由于切出运行队列，因此进程应该处于休眠或某种
* 类似的状态
*/
if (td->td_proc->p_flag & P_KSES)
kse_reassign(ke);}voidsched_switchin(struct thread *td){
mtx_assert(&sched_lock, MA_OWNED);td->td_kse->ke_oncpu = PCPU_GET(cpuid);#if SCHED_STRICT_RESCHED
if (td->td_ksegrp->kg_pri_class == PRI_TIMESHARE &&
td->td_priority != td->td_ksegrp->kg_user_pri)
curthread->td_kse->ke_flags |= KEF_NEEDRESCHED;#endif}voidsched_nice(struct ksegrp *kg, int nice){
struct thread *td;kg->kg_nice = nice;
sched_priority(kg);
FOREACH_THREAD_IN_GROUP(kg, td) {
td->td_kse->ke_flags |= KEF_NEEDRESCHED;
}}
sched_prio和sched_nice用于修改进程的优先级和nice值；sched_switchin和sched_switchout分别用于将进程切入和切出执行队列。
有一个能够影响调度器行为的符：SCHED_STRICT_RESCHED；定义时，调度器将置新切入的调度实体“待重调度(KEF_NEEDRESCHED)”位。这样做的负面影响是，它可能影响系统对输入输出的响应行为，然而，它却能大幅度地提高系统的计算性能。
sched_fork, sched_sleep, sched_wakeup, sched_exit分别进行我们所熟知的操作：进程fork、休眠和唤醒，以及结束。sched_clock对调度实体执行计时操作，并且，当时间片用完时，它还将调整优先级并重排队列。
值得一提的是其中的一段与SCHED_STRICT_RESCHED有关的代码：
kseq = KSEQ_SELF();
nke = runq_choose(kseq->ksq_curr);if (nke && nke->ke_thread &&
nke->ke_thread->td_priority < td->td_priority)
ke->ke_flags |= KEF_NEEDRESCHED;
这段代码处理当前执行队列中拥有更高优先级的调度实体。这种情况会在其他处理器唤醒这一处理器执行队列中进程的前提下发生。intsched_runnable(void){
struct kseq *kseq;kseq = KSEQ_SELF();if (kseq->ksq_load)
return (1);#ifdef SMP
/*
* 在SMP环境中，我们可能需要“窃取”其它处理器
* 的调度实体，查询其他CPU上的就绪队列
*/
if (smp_started) {
int i;for (i = 0; i < mp_maxid; i++) {
if (CPU_ABSENT(i))
continue;
kseq = KSEQ_CPU(i);
if (kseq->ksq_load)
return (1);
}
}#endif
return (0);}
sched_runnable并不作实际的调度工作，它只是提供这样的信息：是否有调度实体在就绪状态。这种状态应该说是“全局”的，在SMP环境下，任何CPU的就绪队列只要有就绪实体，这个函数就会返回1，这样，其他CPU就有机会拿到并执行这个调度实体。
sched_userret根据用户优先级对调度实体的优先级进行调整。voidsched_userret(struct thread *td){
struct ksegrp *kg;kg = td->td_ksegrp;if (td->td_priority != kg->kg_user_pri) {
mtx_lock_spin(&sched_lock);
td->td_priority = kg->kg_user_pri;
mtx_unlock_spin(&sched_lock);
}}
下面是sched_choose，它选择一个CPU执行队列，以备添加新的调度实体
。注意：这段代码只处理将要执行(处于就绪状态)运行队列，而不是正在执行的运行队列。struct kse *sched_choose(void){
struct kseq *kseq;
struct kse *ke;kseq = KSEQ_SELF();
ke = kseq_choose(kseq);if (ke) {
ke->ke_state = KES_THREAD;
kseq_rem(kseq, ke);
}#ifdef SMP
if (ke == NULL && smp_started) {
/*
* 查找负荷最重的CPU，并窃取其上的调度实体
*/
kseq = kseq_load_highest();
if (kseq == NULL)
return (NULL);
ke = kseq_choose(kseq);
kseq_rem(kseq, ke);ke->ke_state = KES_THREAD;
ke->ke_runq = NULL;
ke->ke_cpu = PCPU_GET(cpuid);
}#endif
return (ke);}
其后的sched_add和sched_rem是两段非常简单的代码——将调度实体放入执行队列，和删除调度实体。sched_pctcpu用于对调度实体的时间片进行计算。
sched_ult.c的结尾是一组返回相关结构大小的函数，由于逻辑非常简单，在此不作介绍。
从sched_ule.c的代码我们可以很清楚地看到，它非常小心地避免了对锁机制，特别是自旋锁的使用。对于追求性能的操作系统内核代码来说，采用设计逻辑来避免锁(在这里，一个CPU对应两个调度实体队列)，并把大锁分解为小锁，很显然是一个非常明智的设计决策，它能够让内核代码尽可能快地执行，并且，显然地减少了由于设计失误造成死锁的可能性。此外，ULE调度器采用的算法很少使用循环，甚至，多数常用的操作采用的都是O(1)级的算法，与4BSD调度器相比，它无疑拥有明显的优势。目前进行的试验已经证明，ULE调度器的性能要远好于4BSD调度器。
感谢
在此，我要特别感谢Jeffrey Roberson、Robert Watson、Matthew Dillon、Steve Kargl等FreeBSD开发者在ULE调度器的实现工作中所作的努力，以及在笔者撰写本文时提供的资料、注释等必要的信息。
参考文献
本文的撰写过程中，笔者参考了Kirk McKusick博士等人撰写的《The Design and Implementation of the 4.4BSD Operating System》一书中第3，4，6，14章的有关内容。书中没有对调度器的实现细节作详细论述，但其中介绍的调度器设计思想等对于理解调度器的实现是非常有帮助的。
