到目前为止,我们只考虑了实时系统上的调度。事实上, Linux可以做得更好些。除了支持多个CPU之外,内核也提供其他几种与调度相关的增强功能,在以后几节里会论述。但请注意,这些增强功能大大增加了调度器的复杂性,因此我主要考虑简化的情形,目的在于说明实质性的原理,而不考虑所有的边界情形和调度中出现的奇异情况。
多处理器系统上,内核必须考虑几个额外的问题,以确保良好的调度。
进程对特定CPU的亲合性 ,定义在task_struct的 cpus_allowed 成 员 中 。 Linux 提供了sched_setaffinity系统调用,可修改进程与CPU的现有分配关系。
在SMP系统上,每个调度器类的调度方法必须增加两个额外的函数:
<sched.h>
struct sched_class {
...
#ifdef CONFIG_SMP
unsigned long (*load_balance) (struct rq *this_rq, int this_cpu,
struct rq *busiest, unsigned long max_load_move,
struct sched_domain *sd, enum cpu_idle_type idle,
int *all_pinned, int *this_best_prio);
int (*move_one_task) (struct rq *this_rq, int this_cpu,
struct rq *busiest, struct sched_domain *sd,
enum cpu_idle_type idle);
#endif
...
}
虽然其名字称之为load_balance,但这些函数并不直接负责处理负载均衡。每当内核认为有必要重新均衡时,核心调度器代码都会调用这些函数。特定于调度器类的函数接下来建立一个迭代器,使得核心调度器能够遍历所有可能迁移到另一个队列的备选进程,但各个调度器类的内部结构不能因为迭代器而暴露给核心调度器。 load_balance函数指针采用了一般性的函数load_balance,而move_one_task则使用了iter_move_one_task。这些函数用于不同的目的。
负载均衡处理过程是如何发起的?在SMP系统上,周期性调度器函数scheduler_tick
按上文所述完成所有系统都需要的任务之后,会调用trigger_load_balance
函数。这会引发SCHEDULE_SOFTIRQ
软中断softIRQ(硬件中断的软件模拟,更多细节请参见第14章),该中断确保会在适当的时机执行run_rebalance_domains
。该函数最终对当前CPU调用rebalance_domains,实现负载均衡。
时序如图2-25所示。
为执行重新均衡的操作,内核需要更多信息。因此在SMP系统上,就绪队列增加了额外的字段:
kernel/sched.c
struct rq {
...
#ifdef CONFIG_SMP
struct sched_domain *sd;
/* 用于主动均衡 */
int active_balance;
int push_cpu;
/*该就绪队列的CPU: */
int cpu;
struct task_struct *migration_thread;
struct list_head migration_queue;
#endif
...
}
就绪队列是特定于CPU的,因此cpu表示了该就绪队列所属的处理器。内核为每个就绪队列提供了一个迁移线程,可以接收迁移请求,这些请求保存在链表migration_queue
中。这样的请求通常发源于调度器自身,但如果进程被限制在某一特定的CPU集合上,而不能在当前执行的CPU上继续运行时,也可能出现这样的请求。内核试图周期性地均衡就绪队列,但如果对某个就绪队列效果不佳,则队必须使用主动均衡(active balancing)。如果需要主动均衡,则将active_balance设置为非零值,而cpu则记录了从哪个处理器发起的主动均衡请求。
此外,所有的就绪队列组织为调度域(scheduling domain)。这可以将物理上邻近或共享高速缓存的CPU群集起来,应优先选择在这些CPU之间迁移进程。但在“普通”的SMP系统上,所有的处理器都包含在一个调度域中。因此我不会详细讨论该结构,要提的一点是该结构包含了大量参数,可以通过/proc/sys/kernel/cpuX/domainY
设置。其中包括了在多长时间之后发起负载均衡(包括最大/最小时间间隔),导致队列需要重新均衡的最小不平衡值,等等。此外该结构还管理一些字段,可以在运行时设置,使得内核能够跟踪记录上一次均衡操作在何时执行,下一次将在何时执行。
那么load_balance做什么呢?该函数会检测在上一次重新均衡操作之后是否已经过去了足够的时间,在必要的情况下通过调用load_balance发起一轮新的重新均衡操作。该函数的代码流程图如图2-26所示。请注意,我在该图中描述的是一个简化的版本,因为SMP调度器必须处理大量边边角角的情况。如果都画出来,相关的细节会扰乱图中真正的实质性操作。
首先该函数必须标识出哪个队列工作量最大。该任务委托给find_busiest_queue,后者对一个特定的就绪队列调用。函数迭代所有处理器的队列(或确切地说,当前调度组中的所有处理器),比较其负荷权重。最忙的队列就是最后找到的负荷值最大的队列。
在find_busiest_queue标识出一个非常繁忙的队列之后,如果至少有一个进程在该队列上执行(否则负载均衡就没多大意义),则使用move_tasks将该队列中适当数目的进程迁移到当前队列。move_tasks函数接下来会调用特定于调度器类的load_balance方法。
在选择被迁移的进程时,内核必须确保所述的进程:
如果均衡操作失败(例如,远程队列上所有进程都有较高的内核内部优先级值,即较低的nice值),那么将唤醒负责最忙的就绪队列的迁移线程。为确保主动负载均衡执行得比上述方法更积极一点, load_balance会设置最忙的就绪队列的active_balance标志,并将发起请求的CPU记录到rq->cpu。
迁移线程用于两个目的。一个是用于完成发自调度器的迁移请求,另外一个是用于实现主动均衡。迁移线程是一个执行migration_thread的内核线程。该函数的代码流程图如图2-27所示。
migration_thread
内部是一个无限循环,在无事可做时进入睡眠状态。首先,该函数检测是否需要主动均衡。如果需要,则调用active_load_balance满足该请求。该函数试图从当前就绪队列移出一个进程,且移至发起主动均衡请求CPU的就绪队列。它使用move_one_task
完成该工作,后者又对所有的调度器类,分别调用特定于调度器类的move_one_task函数,直至其中一个成功。注意,这些函数移动进程时会尝试比load_balance更激烈的方法。例如,它们不进行此前提到的优先级比较,因此它们更有可能成功。
完成主动负载均衡之后,迁移线程会检测migrate_req链表中是否有来自调度器的待决迁移请求。如果没有,则线程发出重调度请求。否则,用__migrate_task完成相关请求,该函数会直接移出所要求的进程,而不再与调度器类进一步交互。
除了上述增加的特性之外,在SMP系统上还需要对核心调度器的现存方法作一些修改。虽然到处都是一些小的细节变化,与单处理器系统相比最重要的差别如下所示。
在此前对调度器代码的讨论中,调度器并不直接与进程交互,而是处理可调度实体。这使得可以实现组调度:进程置于不同的组中,调度器首先在这些组之间保证公平,然后在组中的所有进程之间保证公平。举例来说,这使得可以向每个用户授予相同的CPU时间份额。在调度器确定每个用户获得多长时间之后,确定的时间间隔以公平的方式分配到该用户的进程。事实上,这意味着一个用户运行的进程越多,那么每个进程获得的CPU份额就越少。但用户获得的总时间不受进程数目的影响。
把进程按用户分组不是唯一可能的做法。内核还提供了控制组(control group),该特性使得通过特殊文件系统cgroups可以创建任意的进程集合,甚至可以分为多个层次。该情形如图2-29所示。
为反映内核中的此种层次化情形, struct sched_entity增加了一个成员,用以表示这种层次结构:
<sched.h>
struct sched_entity {
...
#ifdef CONFIG_FAIR_GROUP_SCHED
struct sched_entity *parent;
...
#endif
...
}
所有调度类相关的操作,都必须考虑到调度实体的这种子结构。举例来说,考虑一下在完全公平调度器将进程加入就绪队列的实际代码:
kernel/sched_fair.c
static void enqueue_task_fair(struct rq *rq, struct task_struct *p, int wakeup)
{
struct cfs_rq *cfs_rq;
struct sched_entity *se = &p->se;
for_each_sched_entity(se) {
if (se->on_rq)
break;
cfs_rq = cfs_rq_of(se);
enqueue_entity(cfs_rq, se, wakeup);
wakeup = 1;
}
}
for_each_sched_entity会遍历由sched_entity的parent成员定义的调度层次结构,每个实体都加入到就绪队列。
请注意, for_each_sched_entity实际上是一个平凡的循环。如果未选择支持组调度,则会退化为只执行一次循环体中的代码,因此又恢复了先前的讨论所描述的行为特性。
我们现在把注意力转向内核抢占,该特性用来为系统提供更平滑的体验,特别是在多媒体环境下。与此密切相关的是内核进行的低延迟方面的工作,我会稍后讨论。
如上所述,在系统调用后返回用户状态之前,或者是内核中某些指定的点上,都会调用调度器。这确保除了一些明确指定的情况之外,内核是无法中断的,这不同于用户进程。 如果内核处于相对耗时较长的操作中,比如文件系统或内存管理相关的任务,这种行为可能会带来问题。内核代表特定的进程执行相当长的时间,而其他进程则无法运行。这可能导致系统延迟增加,用户体验到“缓慢的”响应。如果多媒体应用长时间无法得到CPU,则可能发生视频和音频漏失现象。
在编译内核时启用对内核抢占的支持,则可以解决这些问题。如果高优先级进程有事情需要完成,那么在启用内核抢占的情况下,不仅用户空间应用程序可以被中断,内核也可以被中断。切记,内核抢占和用户层进程被其他进程抢占是两个不同的概念!
内核抢占是在内核版本2.5开发期间增加的。尽管使内核可抢占所需的改动非常少,但该机制不像抢占用户空间进程那样容易实现。如果内核无法一次性完成某些操作(例如,对数据结构的操作),那么可能出现竞态条件而使得系统不一致。在多处理器系统上出现的同样的问题会在第5章论述。
因此内核不能在任意点上被中断。幸运的是,大多数不能中断的点已经被SMP实现标识出来了,并且在实现内核抢占时可以重用这些信息。内核的某些易于出现问题的部分每次只能由一个处理器访问,这些部分使用所谓的自旋锁保护:到达危险区域(亦称之为临界区)的第一个处理器会获得锁,在离开该区域时释放该锁。另一个想要访问该区域的处理器在此期间必须等待,直到第一个处理器释放锁为止。只有此时它才能获得锁并进入临界区。
如果内核可以被抢占,即使单处理器系统也会像是SMP系统。考虑正在临界区内部工作的内核被抢占的情形。下一个进程也在核心态操作,凑巧也想要访问同一个临界区。这实际上等价于两个处理器在临界区中工作,我们必须防止这种情形。每次内核进入临界区时,我们必须停用内核抢占。
内核如何跟踪它是否能够被抢占?回想一下,可知系统中的每个进程都有一个特定于体系结构的struct thread_info实例。该结构也包含了一个抢占计数器(preemption counter):
<asm-arch/thread_info.h>
struct thread_info {
...
int preempt_count; /* 0 => 可抢占, <0 => BUG */
...
}
在调用调度器之前,抢占计数器的值设置为PREEMPT_ACTIVE。这设置了抢占计数器中的一个标志位,使之有一个很大的值,这样就不受普通的抢占计数器加1操作的影响了,如图2-30所示。它向schedule函数表明,调度不是以普通方式引发的,而是由于内核抢占。在内核重调度之后,代码流程回到当前进程。此时标志位已经再次移除,这可能是在一段时间之后,此间的这段时间供抢先的进程执行。
此前我忽略了该标志与schedule的关系,因此必须在这里讨论。我们知道,如果进程目前不处于可运行状态,则调度器会用deactivate_task停止其活动。实际上,如果调度是由抢占机制发起的(查看抢占计数器中是否设置了PREEMPT_ACTIVE),则会跳过该操作:
kernel/sched.c
asmlinkage void __sched schedule(void) {
...
if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) {
if (unlikely((prev->state & TASK_INTERRUPTIBLE) &&unlikely(signal_pending(prev)))) {
prev->state = TASK_RUNNING;
} else {
deactivate_task(rq, prev, 1);
}
}
...
}
这确保了尽可能快速地选择下一个进程,而无需停止当前进程的活动。如果一个高优先级进程在等待调度,则调度器类将会选择该进程,使其运行。
该方法只是触发内核抢占的一种方法。另一种激活抢占的可能方法是在处理了一个硬件中断请求之后。如果处理器在处理中断请求后返回核心态(返回用户状态则没有影响),特定于体系结构的汇编例程会检查抢占计数器值是否为0,即是否允许抢占,以及是否设置了重调度标志,类似于preempt_schedule
的处理。如果两个条件都满足,则调用调度器,这一次是通过preempt_schedule_irq
,表明抢占请求发自中断上下文。该函数和preempt_schedule
之间的本质区别是, preempt_schedule_irq
调用时停用了中断,防止中断造成递归调用。
根据本节讲述的方法可知,启用了抢占特性的内核能够比普通内核更快速地用紧急进程替代当前进程。
当然,即使没有启用内核抢占,内核也很关注提供良好的延迟时间。例如,这对于网络服务器是很重要的。尽管此类环境不需要内核抢占引入的开销,但内核仍然应该以合理的速度响应重要的事件。例如,如果一网络请求到达,需要守护进程处理,那么该请求不应该被执行繁重IO操作的数据库过度延迟。我已经讨论了内核提供的一些用于缓解该问题的措施: CFS和内核抢占中的调度延迟。第5章中将讨论的实时互斥量也有助于解决该问题,但还有一个与调度有关的操作能够对此有所帮助。
基本上,内核中耗时长的操作不应该完全占据整个系统。相反,它们应该不时地检测是否有另一个进程变为可运行,并在必要的情况下调用调度器选择相应的进程运行。该机制不依赖于内核抢占,即使内核连编时未指定支持抢占,也能够降低延迟。
发起有条件重调度的函数是cond_resched。其实现如下:
kernel/sched.c
int __sched cond_resched(void)
{
if (need_resched() && !(preempt_count() & PREEMPT_ACTIVE))
__cond_resched();
return 1;
}
return 0;
}
need_resched检查是否设置了TIF_NEED_RESCHED标志,代码另外还保证内核当前没有被抢占①,因此允许重调度。只要两个条件满足,那么__cond_resched会处理必要的细节并调用调度器。
如何使用cond_resched?举例来说,考虑内核读取与给定内存映射关联的内存页的情况。这可以通过无限循环完成,直至所有需要的数据读取完毕:
for (;;)
/* 读入数据 */
if (exit_condition)
continue;
如果需要大量的读取操作,可能耗时会很长。由于进程运行在内核空间中,调度器无法象在用户空间那样撤销其CPU,假定也没有启用内核抢占。通过在每个循环迭代中调用cond_resched,即可改进此种情况
for (;;)
cond_resched();
/* 读入数据 */
if (exit_condition)
continue;
内核代码已经仔细核查过,以找出长时间运行的函数,并在适当之处插入对cond_resched的调用。即使没有显式内核抢占,这也能够保证较高的响应速度。
遵循长期以来的UNIX内核传统, Linux的进程状态也支持可中断的和不可中断的睡眠。但在2.6.25的开发周期中,又添加了另一个状态: TASK_KILLABLE。 ①处于此状态进程正在睡眠,不响应非致命信号,但可以被致命信号杀死,这刚好与TASK_UNINTERRUPTIBLE相反。在撰写本书时,内核中适用于TASK_KILLABLE睡眠之处,都还没有修改。
在内核2.6.25和2.6.26开发期间,调度器的清理相对而言是比较多的。 在这期间增加的一个新特性是实时组调度。这意味着,通过本章介绍的组调度框架,现在也可以处理实时进程了。
另外,调度器相关的文档移到了一个专用目录Documentation/scheduler/下,旧的O(1)调度器的相关文档都已经过时,因而删除了。有关实时组调度的文档可以参考Documentation/scheduler/sched-rt-group.txt
。