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 *k