深入Linux内核架构——进程管理和调度（下）

五、调度器的实现

调度器的任务是在程序之间共享cpu时间，创造并行执行的错觉。该任务可分为调度策略和上下文切换两个不同部分。

1、概观

暂时不考虑实时进程，只考虑cfs调度器。经典的调度器对系统中的进程分别计算时间片，使进程运行直至时间片用尽，所有进程的所有时间片用完时，需要重新计算。相比之下，cfs只考虑进程等待时间，即进程在就绪队列（run_queue）中已等待的时间，对cpu时间需求最严格的进程被调度执行。每次调度器会挑选具有最高等待时间的进程提供cpu，如此进程的不公平等待不会被积累，而会均匀分布到系统所有进程。

图1是cfs调度器的工作原理，所有可运行进程都按等待时间在一个红黑树中排序，等待cpu时间最长的进程是最左侧的项，调度器下一次会考虑该进程。等待时间稍短的进程在该树上从左至右排序。（调度器时间复杂度为o(logn)）

 

图1 cfs调度器工作原理示意图

除了红黑树外，就绪队列还装备了虚拟时钟。该时钟的时间流逝速度慢于实际的时钟，精确的速度依赖于当前等待调度器挑选的进程数目（如4个进程，那么虚拟时钟将以实际时钟的四分之一的速度运行，如果以完全公平的方式分享计算能力，那么该时钟是判断等待进程将获得多少cpu时间的基准）。

就绪队列的虚拟时间由fair_clock给出，进程的等待时间保存在wait_runtime中，为排序红黑树上的进程，内核使用差值fair_clock - wait_runtime的绝对值。fair_clock是完全公平调度的情况下进程将会得到的cpu时间的度量，而wait_runtime直接度量了实际系统的不足造成的不公平。

在进程允许运行时，将从wait_runtime减去它已经运行的时间。这样，在按时间排序的树中它会向右移动到某一点，另一个进程将成为最左边，下一次会被调度器选择。

当前该调度策略还受到的影响因素：

• 进程的不同优先级（即，nice值）必须考虑，更重要的进程必须比次要进程更多的cpu时间份额。
• 进程不能切换得太频繁，因为上下文切换，即从一个进程改变到另一个，是有一定开销的。另一方面，两次相邻的任务切换之间，时间也不能太长，否则会累积比较大的不公平值。

2、数据结构

 调度器使用一系列数据结构排序和管理系统中的进程，调度器的工作方式与这些结构的设计密切相关。几个组件在许多方面彼此交互，如图2所示。

 

图2 调度子系统各组件概观

激活调度器方法：

• 直接的，进程打算睡眠或其他因素放弃cpu。（通用调度器，generic scheduler，本质上是分配器）
• 周期性的，以固定频率运行，不时检查是否有必要进行进程切换。（核心调度器，core scheduler）

调度类：用于判断接下来运行哪个进程。内核支持不同的调度策略（完全公平调度、实时调度、在无事可做时调度空闲进程），调度类使得能够以模块化方法实现这些策略，即一个类的代码不需要与其他类的代码交互。

进程切换：在选中将执行的程序之后，要执行底层的任务切换。（需要与cpu紧密交互）

注：每个进程都刚好属于某一调度类，各个调度类负责管理所属的进程。通用调度器自身完全不涉及进程管理，其工作都委托给调度器类。

（1）task_struct成员

各进程的task_struct有几个成员与调度相关：

 1 struct task_struct {
 2 ...
 3     int prio, static_prio, normal_prio; // prio和normal_prio表示动态优先级，static_prio表示进程的静态优先级。静态优先级是进程启动时分配的优先级。它可以用nice和sched_setscheduler系统调用修改，否则在进程运行期间会一直保持恒定。normal_priority表示基于进程的静态优先级和调度策略计算出的优先级。调度器考虑的优先级则保存在prio。由于在某些情况下内核需要暂时提高进程的优先级，因此需要第3个成员来表示。
 4     unsigned int rt_priority; //表示实时进程的优先级。该值不会代替先前讨论的那些值。最低的实时优先级为0，最高的是99。值越大，优先级越高。这里使用的惯例不同于nice值。
 5     struct list_head run_list; //是循环实时调度器所需要的，但不用于完全公平调度器，run_list是一个表头，用于维护包含各进程的一个运行表
 6     const struct sched_class *sched_class; //表示该进程所属的调度器类
 7     struct sched_entity se; //由于调度器设计为处理可调度的实体，在调度器看来各个进程必须也像是这样的实体。因此se在task_struct中内嵌了一个sched_entity实例，调度器可据此操作各个task struct。
 8     unsigned int policy; //保存了对该进程应用的调度策略。（sched_normal用于普通进程，sched_batch用于非交互、cpu使用密集的批处理进程，sched_idle是空闲进程，sched_rr和sched_fifo用于实现软实时进程，）
 9     cpumask_t cpus_allowed; //是一个位域，在多处理器系统上用来限制进程可以在哪些cpu上运行
10     unsigned int time_slice; // 是循环实时调度器所需要的，但不用于完全公平调度器，time_slice则指定进程可使用cpu的剩余时间段
11 ...
12 }

（2）调度器类

调度器类由特定数据结构中汇集的几个函数指针表示。全局调度器请求的各个操作都可以由一个指针表示。这使得无需了解不同调度器类的内部工作原理，即可创建通用调度器。

对各个调度类，都必须提供struct sched_class的一个实例。调度类之间的层次结构是平坦的：实时进程最重要，在完全公平进程之前处理；而完全公平进程则优先于空闲进程；空闲进程只有cpu无事可做时才处于活动状态。next成员将不同调度类的sched_class实例，按上述顺序连接起来，要注意这个层次结构在编译时已经建立。

用户层应用程序无法直接与调度类交互。它们只知道上文定义的常量sched_...。在这些常量和可用的调度类之间提供适当的映射，这是内核的工作。sched_normal、sched_batch和sched_idle映射到fair_sched_class，而sched_rr和sched_fifo与rt_sched_class关联。fair_sched_class和rt_sched_class都是struct sched_class的实例，分别表示完全公平调度器和实时调度器。

（3）就绪队列

就绪队列：核心调度器用于管理活动进程的主要数据结构。各个cpu都有自身的就绪队列，各个活动进程只出现在一个就绪队列中。进程不是由就绪队列的成员直接管理的，而是有调度类管理，就绪队列中嵌入了特定于调度器类的子就绪队列。

就绪队列核心成员及解释：

 1 struct rq {
 2     unsigned long nr_running; //指定了队列上可运行进程的数目，不考虑其优先级或调度类
 3 #define cpu_load_idx_max 5 
 4     unsigned long cpu_load[cpu_load_idx_max]; //用于跟踪此前的负荷状态
 5 ...
 6     struct load_weight load; //提供了就绪队列当前负荷的度量
 7     struct cfs_rq cfs;  //嵌入的子就绪队列，用于完全公平调度器
 8     struct rt_rq rt;  //嵌入的子就绪队列，用于和实时调度器
 9     struct task_struct *curr, *idle; //指向idle进程的task_struct实例，该进程亦称为idle线程
10     u64 clock; //用于实现就绪队列自身的时钟。每次调用周期性调度器时，都会更新clock的值。
11 ...
12 };

系统的所有就绪队列都在runqueues数组中，该数组的每个元素分别对应于系统中的一个cpu。在单处理器系统中，由于只需要一个就绪队列，数组只有一个元素。

（4）调度实体

由于调度器可以操作比进程更一般的实体，因此需要一个适当的数据结构来描述此类实体。其定义为：

 1 struct sched_entity {
 2     struct load_weight load;  //指定了权重，用于负载均衡
 3     struct rb_node run_node; //是标准的树结点，使得实体可以在红黑树上排序
 4     unsigned int on_rq; //表示该实体当前是否在就绪队列上接受调度
 5     u64 exec_start; //新进程加入就绪队列时，或者周期性调度器中。每次调用时，会计算当前时间和exec_start之间的差值，exec_start则更新到当前时间。差值则被加到sum_exec_runtime。
 6     u64 sum_exec_runtime; //用于记录消耗的cpu时间
 7     u64 vruntime; //统计进程执行期间虚拟时钟上流逝的时间数量
 8     u64 prev_sum_exec_runtime; //进程被撤销cpu时，保存当前sum_exec_runtime
 9 ...
10 }

3、处理优先级

 （1）优先级的内核表示

在用户空间可以通过nice命令设置进程的静态优先级，这在内部会调用nice系统调用。进程的nice值在-20和+19之间（包含）。值越低，表明优先级越高。

内核使用一个简单些的数值范围，从0到139（包含），用来表示内部优先级。同样是值越低，优先级越高。从0到99的范围专供实时进程使用，nice值[-20, +19]映射到范围100到139。

（2）计算优先级

进程的优先级计算需要考虑动态优先级(prio)，普通优先级(normal_prio)和静态优先级(static_prio)，调用相关函数计算结果。（完成设置到优先级内核表示的转换）

图3综述了针对不同类型进程的计算结果。

 图3 对各种类型进程计算优先级

在进程分支出子进程时，子进程的静态优先级继承自父进程。子进程的动态优先级，即task_struct->prio，则设置为父进程的普通优先级。这确保了实时互斥量引起的优先级提高不会传递到子进程。

（3）计算负荷权重

进程的重要性由优先级和保存在task_struct->se.load的负荷权重同时决定。进程每降低一个nice值，则多获得10%的cpu时间，每升高一个nice值，则放弃10%的cpu时间。

4、核心调度器

 调度器的实现基于两个函数：周期性调度器函数和主调度器函数。

（1）周期性调度器

• 在scheduler_tick中实现，如果系统正在活动中，内核会按照频率hz自动调用该函数。
• 没进程等待时，供电不足情况下，可以关闭周期性调度器以减少电能消耗。
• 主要任务是管理内核中与系统和每个进程的调度相关的统计量和激活负责当前进程的调度类的周期性调度方法。

 1 void scheduler_tick(void)
 2 {
 3     int cpu = smp_processor_id();
 4     struct rq *rq = cpu_rq(cpu);
 5     struct task_struct *curr = rq->curr;
 6 ...
 7     __update_rq_clock(rq);  //更新struct rq当前实例的时钟时间戳
 8     update_cpu_load(rq);   //更新rq->cup_load[]数组
 9     if (curr != rq->idle)
10     curr->sched_class->task_tick(rq, curr);
11 }

如果当前进程应该被重新调度，那么调度器类方法会在task_struct中设置tif_need_resched标志，以表示该请求，而内核会在接下来的适当时机完成该请求。

（2）主调度器

将当前cpu分配给另一个进程需要调用主调度器函数(schedule)，从该系统调用返回后也要检查当前进程是否设置了重调度标志tif_need_reschedule，如果有，内核会调用schedule。

 __sched前缀的用处：有该前缀的函数，都是可能调用schedule的函数，包括schedule自身。该前缀目的在于将相关代码的函数编译后，放到目标文件的特定段中，.sched.text中。该信息使内核在现实栈转储或类似信息时，忽略所有与调度有关的调用。由于调度器函数调用不是普通代码流程的部分，因此这种情况下是无意义的。

asmlinkage void __sched schedule( void );该函数的过程：

1. 首先确定当前就绪队列，并在prev中保存一个指向（当前）活动进程的task_struct的指针。
2. 更新就绪队列的时钟，清除当前进程task_struct的重调度标志tif_need_resched。
3. 判断当前进程是否在可中断睡眠状态，而且现在接收到信号，那么它将再次提升为可运行。否则，用deactivate_task讲进程停止。
4. 用put_prev_task通知调度类，当前进程要被另一进程代替。pick_next_task，选择下一个要执行的进程。
5. 只有1个进程，是不要切换的，还让它留在cpu。如果已经选择了一个新进程，就用context_switch进行上下文切换。
6. 当前进程，被重新调度回来时，检测是否要重新调度，如果要，就又重复前面(1)至(5)的步骤了。

（3）与fork的交互

用fork或其变体新建进程时，调度器有机会用sched_fork函数挂钩到该进程。

单处理器中，sched_fork执行如下:

• 初始化新进程与调度相关的字段。
• 建立数据结构（相当简单直接）。
• 确定进程的动态优先级。

通过使用父进程的普通优先级作为子进程的动态优先级，内核确保父进程优先级的临时提高不会被子进程继承。在用wake_up_new_task唤醒进程时，内核调用调度类的task_new将新进程加入相应类的就绪队列中。

（4）上下文切换

内核选择新进程之后，必须处理与多任务相关的技术细节。这些细节总称为上下文切换（context switching）。

• context_switch是个分配器，它会调用所需的特定于体系结构的方法，主要进行如下操作：
• prepare_task_switch，执行特定于体系结构的代码，为切换做准备。
• switch_mm更换task_struct->mm描述的内存管理上下文。
• switch_to切换处理器寄存器和内核栈（虚拟地址空间的用户部分在第一步已经变更，其中也包括了用户状态下的栈，因此用户栈就不需要显式变更了）。
• 切换前，用户空间进程的寄存器进入和心态时保存在内核栈上，在上下文切换时，内核栈的值自动回复寄存器数据，再返回用户空间。

内核线程没有自身的用户空间内存上下文，可能在某个随机进程地址空间的上部执行。其task_struct->mm为null。从当前进程“借来”的地址空间记录在active_mm中。

此外，由于上下文切换的速度对系统性能的影响举足轻重，所以内核使用了一种技巧来减少所需的cpu时间。浮点寄存器（及其他内核未使用的扩充寄存器，例如ia-32平台上的sse2寄存器）除非有应用程序实际使用，否则不会保存。此外，除非有应用程序需要，否则这些寄存器也不会恢复。这称之为惰性fpu技术。由于使用了汇编语言代码，因此其实现依平台而有所不同，但基本原理总是同样的。

六、完全公平调度类

1、数据结构

 cfs的就绪队列cfs_rq:

1 struct cfs_rq {
2     struct load_weight load;        //维护了所有这些进程的累积负荷值
3     unsigned long nr_running;    //计算了队列上可运行进程的数目
4     u64 min_vruntime;        //跟踪记录队列上所有进程的最小虚拟运行时间
5     struct rb_root tasks_timeline;        //用于在按时间排序的红黑树中管理所有进程
6     struct rb_node *rb_leftmost;        //总是设置为指向树最左边的结点，即最需要被调度的进程
7     struct sched_entity *curr;    //指向当前执行进程的可调度实体
8 }

2、cfs操作

（1）虚拟时钟

完全公平调度算法依赖于虚拟时钟，用以度量等待进程在完全公平系统中所能得到的cpu时间。数据结构中，可以根据现存的实际时钟与每个进程相关的负荷权重推算出来。所有与虚拟时钟有关的计算都在update_curr中执行，该函数在系统中各个不同地方调用，包括周期性调度器之内。

图4 update_curr代码流程图

首先，该函数确定就绪队列的当前执行进程，并获取主调度器就绪队列的实际时钟值（每个调度周期都会更新），如果就绪队列上当前没有进程正在执行，则无事可做。否则，内核会计算当前和上一次更新负荷统计量时两次的时间差，并将其余的工作委托给__update_curr。

然后，__update_curr需要更新当前进程在cpu上执行花费的物理时间和虚拟时间。物理时间的更新只要将时间差加到先前统计的时间即可；对于虚拟时间，对于运行在nice级别0的进程来说，定义虚拟时间和物理时间是相等的，nice值不为0时，必须根据进程的负荷权重重新衡定时间。

最后，内核需要设置min_vruntime（min_vruntime是单调递增的）。

cfs调度器真正关键点：红黑树根据键值进行排序（se->vruntime -cfs_rq->min_vruntime），键值较小的结点，排序位置就更靠左（被更快调度）。由此，内核实现了以下两种对立机制：

• 在进程运行时，其vruntime稳定地增加，它在红黑树中总是向右移动的。
• 如果进程进入睡眠，则其vruntime保持不变（进程再被唤醒后，在红黑树的位置会更靠左）。

（2）延迟跟踪

良好的调度延迟是 保证每个可运行的进程都应该至少运行一次的某个时间间隔（它在sysctl_sched_latency给出）。一个延迟周期中处理的最大活动数目为sched_nr_latency，超出该上限，则延迟周期也成比例线性扩展。

通过考虑各个进程的相对权重，将一个延迟周期的时间在活动进程之间进行分配。

3、队列操作

 enqueue_task_fair和dequeue_task_fair分别用来增删就绪队列的成员。图5为enqueue_task_fair代码流程图。

图5 enqueue_task_fair代码流程图

如果通过struct sched_entity的on_rq成员判断进程已经在就绪队列上，则无事可做。否则，具体的工作委托给enqueue_entity。

进入enqueue_entity后，首先用updater_curr更新统计量，然后若进程此前在睡眠，那么在place_entity中首先会调整进程的虚拟运行时间；如果进程最近在运行，其虚拟运行时间仍然有效，那么（除非它当前在执行中）它可以直接用__enqueue_entity加入红黑树中。

4、选择下一个进程

选择下一个将要运行的进程由pick_next_task_fair执行。pick_next_task_fair的代码流程图如图6所示。

图6 pick_next_task_fair的代码流程图

如果nr_running计数器为0，即当前队列上没有可运行进程，则无事可做，函数可以立即返回。否则将具体工作委托给pick_next_entity。

如果树中最左边的进程可用，可以使用辅助函数first_fair立即确定，然后用__pick_next_entity从红黑树中提取出sched_entity实例。

完成了选择工作之后，通过set_next_entity函数将该进程标记为运行进程。当前执行进程不保存在就绪队列上，因此使用__dequeue_entity将其从树中移除。如果当前进程是最左边的结点，则将leftmost指针设置到下一个最左边的进程。

5、处理周期性调度器

在处理周期调度时，差值sum_exec_runtime - prev_sum_exec_runtime（表示进程在cpu上执行所花时间）很重要。这个差值形式上由函数task_tick_fair负责，但实际工作由entity_tick完成。

 图7 entity_tick代码流程图

首先，使用update_curr更新统计量。

然后判断nr_running计数器表明队列上可运行的进程数，如果少于两个，则无事可做；否则由由check_preempt_tick作出决策（确保没有哪个进程能够比延迟周期中确定的份额运行得更长），如果进程运行时间比期望的时间间隔长，那么通过resched_task发出重调度请求。这会在task_struct中设置tif_need_resched标志，核心调度器会在下一个适当时机发起重调度。

6、唤醒抢占

当在try_to_wake_up和wake_up_new_task中唤醒进程时，内核使用check_preempt_curr看看是否新进程可以抢占当前运行的进程（该过程不涉及核心调度器）。

新唤醒的进程不必一定由完全公平调度器处理。如果新进程是一个实时进程，则会立即请求重调度，因为实时进程总是会抢占cfs进程。

当运行进程被新进程抢占时，内核确保被抢占者至少已经运行了某一最小时间限额（sysctl_sched_wakeup_granularity）。如果新进程的虚拟运行时间，加上最小时间限额，仍然小于当前执行进程的虚拟运行时间（由其调度实体se表示），则请求重调度。

7、处理新进程

cfs在创建新进程时调用的挂钩函数：task_new_fair。该函数的行为可用sysctl_sched_child_runs_first控制，用于判断新建子进程是否需要在父进程之前运行。如果父进程的虚拟运行时间（由curr表示）小于子进程的虚拟运行时间，则意味着父进程将在子进程之前调度运行，如果子进程应该在父进程之前运行，则二者的虚拟运算时间需要换过来。然后子进程按常规加入就绪队列，并请求重调度。

七、实时调度类

1、性质

按照posix标准的要求，除了“普通”进程之外，linux还支持两种实时调度类。调度器结构使得实时进程可以平滑地集成到内核中，而无需修改核心调度器。

实时进程与普通进程有一个根本的不同之处：如果系统中有一个实时进程且可运行，那么调度器总是会选中它运行，除非有另一个优先级更高的实时进程。

现有的两种实时类：

• 循环进程（sched_rr）有时间片，其值在进程运行时会减少，就像是普通进程。在所有的时间段都到期后，则该值重置为初始值，而进程则置于队列的末尾。
• 先进先出进程（sched_fifo）没有时间片，在被调度器选择执行后，可以运行任意长时间。

2、数据结构

实时进程的调度类定义：

 1 const struct sched_class rt_sched_class = {
 2     .next = &fair_sched_class,
 3     .enqueue_task = enqueue_task_rt,
 4     .dequeue_task = dequeue_task_rt,
 5     .yield_task = yield_task_rt,
 6     .check_preempt_curr = check_preempt_curr_rt,
 7     .pick_next_task = pick_next_task_rt,
 8     .put_prev_task = put_prev_task_rt,
 9     .set_curr_task = set_curr_task_rt,
10     .task_tick = task_tick_rt,
11 };

实时调度器类的实现比完全公平调度器简单（核心调度器的就绪队列也包含了用于实时进程的子就绪队列，是一个嵌入的struct rt_rq实例）

图8是时调度类就绪队列示意图，一个链表中，表头为active.queue[prio]，而active.bitmap位图中的每个比特位对应于一个链表，凡包含了进程的链表，对应的比特位则置位。如果链表中没有进程，则对应的比特位不置位。

图8 实时调度器就绪队列

实时调度器类中对应于update_cur的是update_curr_rt，该函数将当前进程在cpu上执行花费的时间记录在sum_exec_runtime中（所有计算的单位都是实际时间，不需要虚拟时间）。

3、调度器操作

进程的入队和离队以p->prio为索引访问queue数组queue[p->prio]，访问链表，将进程加入链表或从链表删除（程总是排列在每个链表的末尾）。

对于选择下一个要执行的进程，通过函数pick_next_task_rt，该函数书意图如图9所示。

图9 ick_next_task_rt的代码流程图

sched_find_first_bit是一个标准函数，可以找到active.bitmap中第一个置位的比特位（高优先级）。取出所选链表的第一个进程，并将se.exec_start设置为就绪队列的当前实际时钟值。

对于周期调度：sched_fifo进程可以运行任意长的时间，而且必须使用yield系统调用将控制权显式传递给另一个进程。对循环进程（sched_rr），则减少其时间片。在尚未超出时间段时，进程可以继续执行。计数器归0后，其值重置为def_timeslice，即100 * hz / 1000（ 100毫秒）。如果该进程不是链表中唯一的进程，则重新排队到末尾。通过用set_tsk_need_resched设置tif_need_resched标志，照常请求重调度。

为将进程转换为实时进程，必须使用sched_setscheduler系统调用，该系统调用完成了以下几个任务：

• 使用deactivate_task将进程从当前队列移除。
• 在task_struct中设置实时优先级和调度类。
• 重新激活进程。

只有具有root权限（或等价于cap_sys_nice）的进程执行了sched_setscheduler系统调用，才能修改调度器类或优先级。否则，调度类只能从sched_normal改为sched_batch。只有目标进程的uid或euid与调用者进程的euid相同时，才能修改目标进程的优先级。此外，优先级只能降低，不能提升。

八、调度器增强

1、smp调度

对于多处理器系统，cpu负荷必须尽可能公平地在所有的处理器上共享；进程与系统中某些处理器的亲合性（affinity）必须是可设置的；内核必须能够将进程从一个cpu迁移到另一个。

进程对特定cpu 的亲合性， 定义在task_struct 的cpus_allowed成员中，可以通过sched_setaffinity系统调用修改进程与cpu的现有分配关系。

（1）数据结构的扩展

每当内核认为有必要重新均衡时，核心调度器就会调用load_balance和move_one_task函数。特定于调度器类的函数建立一个迭代器，使核心调度器能遍历所有可能迁移到另一个队列的备选进程。load_balance函数指针采用了一般性的函数load_balance，允许从最忙的就绪队列分配多个进程到当前cpu，但移动的负荷不能比max_load_move更多；move_one_task使用了iter_move_one_task，从最忙碌的就绪队列移出一个进程，迁移到当前cpu的就绪队列。

负载均衡发起过程：在smp系统上，周期性调度器函数scheduler_tick按上文所述完成所有系统都需要的任务之后，会调用trigger_load_balance函数。这会引发schedule_softirq软中断softirq（确保会在适当的时机执行run_rebalance_domains）。该函数最终对当前cpu调用rebalance_domains，实现负载均衡。

就绪队列是特定于cpu的，内核为每个就绪队列提供了一个迁移线程，可以接收迁移请求，这些请求保存在链表migration_queue中，这样的请求通常发源于调度器自身，但如果进程被限制在某一特定的cpu集合上，而不能在当前执行的cpu上继续运行时，也可能出现这样的请求。内核试图周期性地均衡就绪队列，但如果对某个就绪队列效果不佳，则必须使用主动均衡（active balancing）。

所有的就绪队列组织为调度域（scheduling domain）。这可以将物理上邻近或共享高速缓存的cpu群集起来，应优先选择在这些cpu之间迁移进程。

 对于load_balance函数，它会检测在上一次重新均衡操作之后是否已经过去了足够多的时间，在必要的情况下，它会发起一轮新的均衡操作。首先该函数通过find_busiest_queue标识出哪个队列工作量最大，如果至少有一个进程在该队列上执行，则使用move_tasks将该队列中适当数目的进程迁移到当前队列。move_tasks函数接下来会调用特定于调度器类的load_balance方法。如果均衡操作失败，那么将唤醒负责最忙的就绪队列的迁移线程。

（2）迁移线程

迁移线程是一个执行migration_thread的内核线程（如图10所示），用于两个目的：

• 完成发自调度器的迁移请求；
• 实现主动均衡。

图10 migration_thread代码流程图

migration_thread内部是一个无限循环，在无事可做时进入睡眠状态。

首先，该函数检测是否需要主动均衡。如果需要，则调用active_load_balance满足该请求。该函数试图从当前就绪队列移出一个进程，且移至发起主动均衡请求cpu的就绪队列。它使用move_one_task完成该工作，后者又对所有的调度器类，分别调用特定于调度器类的move_one_task函数，直至其中一个成功。

完成主动负载均衡之后，迁移线程会检测migrate_req链表中是否有来自调度器的待决迁移请求。如果没有，则线程发出重调度请求。否则，用__migrate_task完成相关请求，该函数会直接移出所要求的进程，而不再与调度器类进一步交互。

（3）核心调度器的改变

smp系统与单处理器系统相比的主要差别：

• 在用exec系统调用启动一个新进程时，由于进程尚未执行，这时是调度器跨越cpu移动该进程的一个良好的时机。
• 完全公平调度器的调度粒度与cpu的数目是成比例的。系统中处理器越多，可以采用的调度粒度就越大。

2、调度域和控制组

对于组调度，进程置于不同的组中，调度器首先在这些组之间保证公平，然后在组中的所有进程之间保证公平（比如系统可以向每个用户授予相同的cpu时间份额）。

把进程按用户分组不是唯一可能的做法。内核还提供了控制组（control group），该特性使得通过特殊文件系统cgroups可以创建任意的进程集合，甚至可以分为多个层次。

3、内核抢占和低延迟相关工作

（1）内核抢占

在系统调用时返回用户状态之前，或者是内核中某些指定的点上，都会调用调度器，这确保除了一些明确指定的情况之外，内核是无法中断的，这不同于用户进程，如果内核处于相对耗时较长的操作中，这种行为可能会带来问题。启用了抢占特性的内核能够比普通内核更快速地用紧急进程替代当前进程。

在编译内核时启用对内核抢占的支持。如果高优先级进程有事情需要完成，那么在启用内核抢占（与用户空间程序被其他进程抢占不同）的情况下，不仅用户空间应用程序可以被中断，内核也可以被中断。

为了避免竞态条件使系统不一致，内核不能在任意点上被中断，大多数不能中断的点已被smp实现标识，并且实现内核抢占时可以重用这些信息。内核的某些易于出现问题（临界区）的部分每次只能由一个处理器访问，这些部分使用自旋锁保护。每次内核进入临界区时，我们必须停用内核抢占。

系统中的每个进程都有一个特定于体系结构的struct thread_info实例，该结构包含了一个抢占计数器。

1 struct thread_info {
2 ...
3     int preempt_count; /* 0 => 可抢占， <0 => bug */
4 ...
5 }

preempt_count的值（该值通过辅助函数dec_preempt_count和inc_preempt_count分别进行减1和加1操作）确定了内核当前是否处于一个可被中断的位置，在内核再次启用抢占之前，必须确认已经离开所有的临界区。

抢占机制中主要的函数是preempt_schedule。设置了tif_need_resched标志，它不能保证一定可以抢占内核（内核有可能正处于临界区中），可以通过preempt_reschedule检查是否可抢占。

激活抢占的两种方法（本质区别在于，preempt_schedule_irq调用时停用了中断，防止中断造成递归调用）：

• 使用preempt_schedule，如果调度是由抢占机制发起的（查看抢占计数器中是否设置了preempt_active），无需停止当前进程的活动（跳过使用deactivate_task停止不处于可运行状态进程的活动），尽可能快速选择下一个进程。
• 是通过preempt_schedule_irq，处理中断请求后返回和心态，会检查抢占技术企的值和是否设置了重调度标志，若都满足，则调用调度器。

（2）低延迟

内核中耗时长的操作（比如繁重的io操作）不应该完全占据整个系统。相反，它们应该不时地检测是否有另一个进程变为可运行，并在必要的情况下调用调度器选择相应的进程运行。该机制不依赖于内核抢占，即使内核联编时未指定支持抢占，也能够降低延迟。发起有条件重调度的函数是cond_resched，内核代码中，长时间运行的函数都在适当之处插入了对cond_resched的调用，保证较高的相应速度。