郑州市园林局领导班子:FreeBSD ULE调度器浅析

FreeBSD ULE调度器浅析


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一份FreeB
SD-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_cpu

struct kg_sched {
  int skg_slptime;
};
#define kg_slptime kg_sched->skg_slptime

struct 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 0x0001
struct 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_SCA
LE-按比例计算的时间片长度， SCHED_PRI_TOSLICE-根据优先级计算的时间片长度，SCHE
D_SLP_TOSLICE-根据休眠时间计算时间片长度(反比)； SCHED_SLP_COMP和SCHED_PRI_COM
P宏决定时间片长度中，休眠加权和优先级加权分别所占的份额。

宏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 void
kseq_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 void
kseq_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 SMP
static __inline void
kseq_sleep(struct kseq *kseq,

struct kse *ke)
{
  kseq->ksq_bload++;
}

static __inline void
kseq_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);
}
#endif

struct 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 void
kseq_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 void
sched_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的一对执行队列，它被sc
hed_setup调用，后者用于系统初启时对系统的所有CPU的执行队列进行初始化。kseq_cho
ose将被后面的函数调用，在此暂不介绍。

在ULE调度器中，kseq_开头的函数是ULE调度器特有的，它们被相关的BSD实现调用。前面
sched_setup函数严格地说应该算BSD Unix实现接口的一部分。以下介绍其余部分：
static int
sched_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: %d\tpri: %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对调度实体的执行时间进行重新计算。

请适当地参考前面所描述的数据结构。
void
sched_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之间还可以“窃取”调度实体。关于这些机制将在后面
介绍。
void
sched_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);
  }
}

void
sched_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);
}

void
sched_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
}

void
sched_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_swit
chout分别用于将进程切入和切出执行队列。

有一个能够影响调度器行为的符：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;

这段代码处理当前执行队列中拥有更高优先级的调度实体。这种情况会在其他处理器唤醒
这一处理器执行队列中进程的前提下发生。
int
sched_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根据用户优先级对调度实体的优先级进行调整。
void
sched_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 Implem
entation of the 4.4BSD Operating System》一书中第3，4，6，14章的有关内容。书中
没有对调度器的实现细节作详细论述，但其中介绍的调度器设计思想等对于理解调度器的
实现是非常有帮助的。