2015年（100）
分类： LINUX
2015-05-29 20:07:06
具体来说，scheduler_tick()做了以下工作：
1）更新就绪队列的实际时钟时间，不是虚拟时钟时间。
2）更新就绪队列权重数组cpu_load中的权重值
3）调用当前CPU上正在执行的进程所属调度类的task_tick接口，更新调度类相关的统计信息，并检查是否需要重新调度
4）如果是多处理器系统，检查当前CPU是否处于IDLE状态，并调用trigger_load_balance()来检查是否需要对CPU之间的负载进行均衡，如果需要，则触发SCHEDULE_SOFTIRQ软中断来迁移进程。
下面来看一看内核中是如何来完成这些操作的。
1.就绪队列时钟的更新
就绪队列的时钟由update_rq_clock()函数来更新，如果在编译内核的时候启用了CONFIG_HAVE_UNSTABLE_SCHED_CLOCK选项（CentOS的内核是默认开启的），sched_clock_stable变量的值为1，这种情况下会调用sched_clock()函数来获取当前的CPU时间。sched_clock()函数中会调用rdstc指令来读取CPU的周期数，然后调用__cycles_2_ns()将周期数转换为纳秒。rdstc指令在多处理器下会有问题，关于这个问题的描述和解决办法，参见 《多核时代不宜再用 x86 的 RDTSC 指令测试指令周期和时间》 ，较新的内核中已使用同步算法来fix这个问题。
2.权重数组的更新
就绪队列中的cpu_load数组用来跟踪此前的CPU负荷状态，在sched_init()中初始化为0，在CPU间迁移进程时会用到这个数组中记录的权重。cpu_load数组由update_cpu_load()函数更新，在每个tick周期里都会调用该函数，代码如下所示：
static void update_cpu_load( struct rq * this_rq)
{
unsigned long this_load = this_rq - > load.weight;
int i, scale;
this_rq - > nr_load_updates ++ ;
/* Update our load: */
for (i = 0 , scale = 1 ; i < CPU_LOAD_IDX_MAX; i ++ , scale += scale) {
unsigned long old_load, new_load;
/* scale is effectively 1 << i now, and >> i divides by scale */
old_load = this_rq - > cpu_load[i];
new_load = this_load;
/*
* Round up the averaging division if load is increasing. This
* prevents us from getting stuck on 9 if the load is 10, for
* example.
*/
if (new_load > old_load)
new_load += scale - 1 ;
this_rq - > cpu_load[i] = (old_load * (scale - 1 ) + new_load) >> i;
}
if (time_after_eq(jiffies, this_rq - > calc_load_update)) {
this_rq - > calc_load_update += LOAD_FREQ;
calc_load_account_active(this_rq);
}
}
在向就绪队列添加调度实体时，都会将调度实体的权重值添加到就绪队列的当前负荷的统计成员load中。在这里，this_load保存了当前就绪队列中的权重负荷。在更新cpu_load数组前要累加nr_load_updates成员，该成员记录了更新cpu_load数组的次数，只在输出/proc/sched_debug文件时使用，用于调试调度系统。
在for循环中，根据老的权重值和当前的权重值来进行更新。为了便于理解，我们可以进行下面的转换：
this_rq - > cpu_load[i] = (old_load * (scale - 1 ) + new_load) >> i
= (old_load * ( 2 ^ i - 1 ) + new_load) / ( 2 ^ i)
= old_load * ( 1 - 1 / ( 2 ^ i)) + new_load / ( 2 ^ i)
= old_load + (new_load - old_load) / ( 2 ^ i)
通过转换，我们可以清晰地看到cpu_load数组中的元素是如何更新的。如果i等于0，则2^i的值为1，所以this_rq->cpu_load[0]保存的就是更新时当前就绪队列的权重值。如果当前队列的权重值是增加的，会将new_load(保存的就是当前的权重值)加上(scale-1)，向上取整。
update_cpu_load()中除了更新cpu_load数组的内容后，还会检查是否要更新系统平均负载的统计信息，这些信息每隔5秒钟才更新一次，主要是统计在系统中处于active状态的进程的个数，包括进程状态是TASK_RUNNING和TASK_UNINTERRUPTIBLE的进程。系统的平均负载可以通过top或w命令查看。
3.CFS的周期性处理
CFS调度系统的调度类实例由全局变量fair_sched_class表示，设置的周期性处理接口是task_tick_fair()。在2.6.24中引入了组调度的概念，所以在task_tick_fair()中通过for_each_sched_entity宏来遍历处理当前进程所在的调度层级。这里为了简化，我们假设当前进程的parent为NULL，即当前进程处在就绪队列中的红黑树中。对当前进程的周期性处理主要由entity_tick()函数来完成，主要代码流程如下所示：
static void
entity_tick( struct cfs_rq * cfs_rq, struct sched_entity * curr, int queued)
{
/*
* Update run-time statistics of the 'current'.
*/
update_curr(cfs_rq);
......
if (cfs_rq - > nr_running > 1 || ! sched_feat(WAKEUP_PREEMPT))
check_preempt_tick(cfs_rq, curr);
}
update_curr()根据现在的实际时钟时间和进程的权重计算本次运行的虚拟时钟时间，并更新进程和CFS就绪队列相关的统计信息。update_curr()使用CPU就绪队列的实际时钟时间减去当前进程的开始运行时间(由sched_entity结构的exec_start成员描述），得到当前进程实际的运行时间，然后调用__update_curr()来将实际的运行时间转换为虚拟时钟时间，并且加到当前进程总的运行的虚拟时钟时间(由sched_entity的sum_exec_runtime成员描述)。实际时钟时间和虚拟时钟时间的转换公式为：
在update_curr()中更新当前进程的虚拟运行时间后，需要重新计算CFS就绪队列中最小的虚拟运行时间。假设cfs_rq(结构类型为cfs_rq)为当前CPU就绪队列中的CFS就绪队列，最小的虚拟运行时间在CFS就绪队列当前的最小运行时间(即cfs_rq->min_vruntime)、正在执行的进程的虚拟运行时间(即cfs_rq->curr->vruntime,更新后的值)和CFS就绪队列中最左边节点(管理调度实体的红黑树中最左边的节点)的虚拟运行时间(cfs_rq->leftmost->vruntime)这三个值之间选择一个最小值。如果选出来的值大于当前CFS就绪队列的最小虚拟运行时间，则使用选出来的值来作为新的最小虚拟运行时间，并设置到cfs_rq-> min_vruntime上，否则维持原来的值不变。通过这样的策略，可以保证CFS就绪队列中的最小虚拟运行时间总是单调递增的，防止时钟倒流。由于最小虚拟运行时间总是单调递增的，所以就绪队列中最左边节点的运行时间有可能小于cfs_rq->min_vruntime。
完成更新操作后，检查CFS就绪队列中可运行进程的数目是否大于1，如果大于1，则调用check_preempt_tick()检查是否要重新调度正在执行的进程，检查主要分以下几个步骤：
1）调用sched_slice()计算当前进程在调度延迟内期望的运行时间。如果系统中可运行进程的数量小于sched_nr_latency（其值为 sysctl_sched_latency/ sysctl_sched_min_granularity ），调度延迟由系统参数sysctl_sched_latency的值确定；如果可运行进程的数量大于sched_nr_latency，调度延迟的值为（ sysctl_sched_latency * (nr_running / sched_nr_latency)），其中nr_running为CFS就绪队列中可运行进程的数量。而当前进程在调度延迟中分得的时间（实际时钟时间）根据下面的公式来计算(period为调度延迟，weight为当前进程的权重，cfs_rq->load.weight为CFS就绪队列的权重)：
2）如果当前进程本次已经执行的时间（实际时钟时间）超过期望的运行时间，说明当前进程运行的时间已经足够了，这种情况下要重新调度当前进程，并调用clear_buddies()确保当前进程不在CFS就绪队列中的next或last中，避免当前进程在下次选择执行进程时又被优先调度到。
3）如果当前进程本次已经执行的时间小于进程的最小运行时间（保存在sysctl_sched_min_granularity中），也不能重新调度，避免进程切换的太过频繁。
4）如果就绪队列中可运行进程的数量超过1，比较当前进程和就绪队列中最左边进程的运行时间来确定是否要重新调度。如果当前进程的虚拟运行时间减去就绪队列中最左边进程的虚拟运行时间的差值大于当前进程的期望运行时间，则重新调度当前进程。
多处理器系统中，内核必须要保证不同CPU间的负载要均衡，避免某些CPU的负载已经很高了，而某些CPU却很空闲，充分利用CPU资源。但是，迁移进程会导致CPU高速缓存失效，严重影响性能，所以在创建进程时，内核已经开始在CPU间负载均衡。
在SMP系统上，周期性调度器函数scheduler_tick()完成前面的任务后，会调用 trigger_load_balance()来检查是否要发起CPU间的负载均衡。这里我们不考虑启用动态时钟（即设置了CONFIG_NO_HZ选项）下的处理。如果当前的时间已经超过就绪队列中保存的下次均衡的时间，并且当前CPU在某个调度域内，则触发SCHED_SOFTIRQ软中断，适当的时候内核会调用run_rebalance_domains()函数在CPU间进行负载均衡。
调度域是一个CPU的集合，是负载均衡的单位，进程的迁移是在调度域内各CPU间进行，所以只有在当前CPU属于某个调度域的时候才发起进程迁移。通过调度域可以将邻近或共享高速缓存的CPU群集起来，优先选择在这些CPU之间迁移进程，这样可以降低迁移进程导致的性能损失。在普通的SMP系统上，所有的处理器都包含在一个调度域中。
