福建小伙子打拾荒老人:schedule()函数（重点）

好了，前面的准备工作都做完了，我们就进入进程调度的主体程序——schedule()函数。
函数schedule()实现调度程序。它的任务是从运行队列的链表rq中找到一个进程，并随后将CPU分配给这个进程。schedule()可以由几个内核控制路径调用，可以采取直接调用或延迟调用（可延迟的）的方式。下面，我们就来详细介绍。
1 直接调用
如果current进程因不能获得必须的资源而要立刻被阻塞，就直接调用调度程序。在这种情况下，如何阻塞进程该进程的内核路径呢？按下述步骤执行：
1．把current进程current插入适当的等待队列，参见《非运行状态进程的组织 》博文。
2．把current进程的状态改为TASK_INTERRUPTIBLE或TASK_UNINTERRUPTIBLE。
3．调用schedule()。
4．检查资源是否可用，如果不可用就转到第2步。
5．一但资源可用就从等待队列中删除当前进程current。
内核路径反复检查进程需要的资源是否可用，如果不可用，就调用schedule( )把CPU分配给其它进程。稍后，当调度程序再次允许把CPU分配给这个进程时，要重新检查资源的可用性。这些步骤与wait_event( )所执行的步骤很相似，也与《非运行状态进程的组织》博文的函数很相似。
许多反复执行长任务的设备驱动程序也直接调用调度程序。每次反复循环时，驱动程序都检查TIF_NEED_RESCHED标志，如果需要就调用schedule()自动放弃CPU。
2 延迟调用
延迟调用的方法是，把TIF_NEED_RESCHED标志设置为1（thread_info），在以后的某个时段调用调度程序schedule()。由于总是在恢复用户态进程的执行之前检查这个标志的值，所以schedule()将在不久之后的某个时间被明确地调用。
延迟调用调度程序的典型例子，也是最重要的三个进程调度实务：
- 当 current 进程用完了它的CPU 时间片时，由scheduler_tick( )函数做延迟调用，前面的博文已经讲得很清楚了。
- 当一个被唤醒进程的优先权比当前进程的优先权高时，由try_to_wake_up( )函数做延迟调用，前面的博文也已经讲得很清楚了。
- 当发出系统调用sched_setscheduler( )时，有兴趣的同志可以玩玩这个系统调用对应的函数库。
下面，我们就来分析schedule函数到底做了些什么工作。咱先把代码摆出来，来自Linux-2.6.18/kernel/Sched.c：
asmlinkage void __sched schedule(void)
{
struct task_struct *prev, *next;
struct prio_array *array;
struct list_head *queue;
unsigned long long now;
unsigned long run_time;
int cpu, idx, new_prio;
long *switch_count;
struct rq *rq;
if (unlikely(in_atomic() && !current->exit_state)) {
printk(KERN_ERR "BUG: scheduling while atomic: "
"%s/0x%08x/%d/n",
current->comm, preempt_count(), current->pid);
dump_stack();
}
profile_hit(SCHED_PROFILING, __builtin_return_address(0));
need_resched:
preempt_disable();
prev = current;
release_kernel_lock(prev);
need_resched_nonpreemptible:
rq = this_rq();
if (unlikely(prev == rq->idle) && prev->state != TASK_RUNNING) {
printk(KERN_ERR "bad: scheduling from the idle thread!/n");
dump_stack();
}
schedstat_inc(rq, sched_cnt);
spin_lock_irq(&rq->lock);
now = sched_clock();
if (likely((long long)(now - prev->timestamp) < NS_MAX_SLEEP_AVG)) {
run_time = now - prev->timestamp;
if (unlikely((long long)(now - prev->timestamp) < 0))
run_time = 0;
} else
run_time = NS_MAX_SLEEP_AVG;
run_time /= (CURRENT_BONUS(prev) ? : 1);
if (unlikely(prev->flags & PF_DEAD))
prev->state = EXIT_DEAD;
switch_count = &prev->nivcsw;
if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) {
switch_count = &prev->nvcsw;
if (unlikely((prev->state & TASK_INTERRUPTIBLE) &&
unlikely(signal_pending(prev))))
prev->state = TASK_RUNNING;
else {
if (prev->state == TASK_UNINTERRUPTIBLE)
rq->nr_uninterruptible++;
deactivate_task(prev, rq);
}
}
update_cpu_clock(prev, rq, now);
cpu = smp_processor_id();
if (unlikely(!rq->nr_running)) {
idle_balance(cpu, rq);
if (!rq->nr_running) {
next = rq->idle;
rq->expired_timestamp = 0;
wake_sleeping_dependent(cpu);
goto switch_tasks;
}
}
array = rq->active;
if (unlikely(!array->nr_active)) {
/*
* Switch the active and expired arrays.
*/
schedstat_inc(rq, sched_switch);
rq->active = rq->expired;
rq->expired = array;
array = rq->active;
rq->expired_timestamp = 0;
rq->best_expired_prio = MAX_PRIO;
}
idx = sched_find_first_bit(array->bitmap);
queue = array->queue + idx;
next = list_entry(queue->next, struct task_struct, run_list);
if (!rt_task(next) && interactive_sleep(next->sleep_type)) {
unsigned long long delta = now - next->timestamp;
if (unlikely((long long)(now - next->timestamp) < 0))
delta = 0;
if (next->sleep_type == SLEEP_INTERACTIVE)
delta = delta * (ON_RUNQUEUE_WEIGHT * 128 / 100) / 128;
array = next->array;
new_prio = recalc_task_prio(next, next->timestamp + delta);
if (unlikely(next->prio != new_prio)) {
dequeue_task(next, array);
next->prio = new_prio;
enqueue_task(next, array);
}
}
next->sleep_type = SLEEP_NORMAL;
if (dependent_sleeper(cpu, rq, next))
next = rq->idle;
switch_tasks:
if (next == rq->idle)
schedstat_inc(rq, sched_goidle);
prefetch(next);
prefetch_stack(next);
clear_tsk_need_resched(prev);
rcu_qsctr_inc(task_cpu(prev));
prev->sleep_avg -= run_time;
if ((long)prev->sleep_avg <= 0)
prev->sleep_avg = 0;
prev->timestamp = prev->last_ran = now;
sched_info_switch(prev, next);
if (likely(prev != next)) {
next->timestamp = now;
rq->nr_switches++;
rq->curr = next;
++*switch_count;
prepare_task_switch(rq, prev, next);
prev = context_switch(rq, prev, next);
barrier();
finish_task_switch(this_rq(), prev);
} else
spin_unlock_irq(&rq->lock);
prev = current;
if (unlikely(reacquire_kernel_lock(prev) < 0))
goto need_resched_nonpreemptible;
preempt_enable_no_resched();
if (unlikely(test_thread_flag(TIF_NEED_RESCHED)))
goto need_resched;
}
3 进程切换之前schedule()所做的工作
schedule()函数的任务之一是用另外一个进程来替换当前正在执行的进程。因此，该函数的关键结果是设置一个叫做next的变量，使它指向被选中的进程，该进程将取代当前进程。如果系统中没有优先权高于当前进程的可运行进程，最终next与current相等，不发生任何进程切换。
schedule( )函数在一开始，先禁用内核抢占并初始化一些局部变量：
need_resched:
preempt_disable();
prev = current;
release_kernel_lock(prev);
need_resched_nonpreemptible:
rq = this_rq();
正如你所见，把current返回的指针赋给prev，并把与本地CPU相对应的运行队列数据结构的地址赋给rq。
下一步，schedule( )要保证prev不占用大内核锁（我们会在同步和互斥专题中详细讲解）：
if (prev->lock_depth >= 0)
up(&kernel_sem);
注意，schedule( )不改变lock_depth 字段的值，当prev恢复执行的时候，如果该字段的值不等于负数，prev重新获得kernel_flag 自旋锁。因此，通过进程切换，会自动释放和重新获取大内核锁。
继续走，调用sched_clock( )函数以读取TSC，并将它的值转换成纳秒，所获得的时间戳存放在局部变量now中。然后，schedule( )计算prev所用的时间片长度：
now = sched_clock( );
run_time = now - prev->timestamp;
if (run_time > 1000000000)
run_time = 1000000000;
通常使用限制在1秒（要转换成纳秒）的时间。run_time的值用来限制进程对CPU的使用。不过，鼓励进程有较长的平均睡眠时间：run_time /= (CURRENT_BONUS(prev) ? : 1);记住，CURRENT_BONUS返回0到10之间的值，它与进程的平均睡眠时间是成比例的。
在开始寻找可运行进程之前，schedule( )必须关掉本地中断，并获得所要保护的运行队列的自旋锁：
spin_lock_irq(&rq->lock);
prev可能是一个正在被终止的进程。为了确认这个事实，schedule( )检查PF_DEAD标志：
if (prev->flags & PF_DEAD)
prev->state = EXIT_DEAD;
接下来，schedule()检查prev的状态，如果不是可运行状态，而且它没有在内核态被抢占，就应该从运行队列删除prev进程。不过，如果它是非阻塞挂起信号，而且状态为TASK_INTERRUPTIBLE，函数就把该进程的状态设置为TASK_RUNNING，并将它插入运行队列。这个操作与把处理器分配给prev是不同的，它只是给prev一次被选中执行的机会。
if (prev->state != TASK_RUNNING && !(preempt_count() & PREEMPT_ACTIVE)) {
if (prev->state == TASK_INTERRUPTIBLE && signal_pending(prev))
prev->state = TASK_RUNNING;
else {
if (prev->state == TASK_UNINTERRUPTIBLE)
rq->nr_uninterruptible++;
deactivate_task(prev, rq);
}
}
函数deactivate_task( )从运行队列中删除该进程：
rq->nr_running--;
dequeue_task(p, p->array);
p->array = NULL;
现在，schedule( )检查运行队列中剩余的可运行进程数。如果有可运行的进程，schedule()就调用dependent_sleeper( )函数，在绝大多数情况下，该函数立即返回0。但是，如果内核支持超线程技术（见本后面“多处理器系统中运行队列的平衡”博文），函数检查要被选中执行的进程，其优先权是否比已经在相同物理CPU的某个逻辑CPU上运行的兄弟进程的优先权低，在这种特殊的情况下，schedule()拒绝选择低优先权的进程，而去执行swapper进程。
if (rq->nr_running) {
if (dependent_sleeper(smp_processor_id( ), rq)) {
next = rq->idle;
goto switch_tasks;
}
}
如果运行队列中没有可运行的进程存在，函数就调用idle_balance( )，从另外一个运行队列迁移一些可运行进程到本地运行队列中，idle_balance( )与load_balance( )类似，在“多处理器系统中运行队列的平衡”博文中将对它进行说明。
if (!rq->nr_running) {
idle_balance(smp_processor_id( ), rq);
if (!rq->nr_running) {
next = rq->idle;
rq->expired_timestamp = 0;
wake_sleeping_dependent(smp_processor_id( ), rq);
if (!rq->nr_running)
goto switch_tasks;
}
}
如果idle_balance( ) 没有成功地把进程迁移到本地运行队列中，schedule( )就调用wake_sleeping_dependent( )重新调度空闲CPU（即每个运行swapper进程的CPU）中的可运行进程。就象前面讨论dependent_sleeper( )函数时所说明的，通常在内核支持超线程技术的时候可能会出现这种情况。然而，在单处理机系统中，或者当把进程迁移到本地运行队列的种种努力都失败的情况下，函数就选择swapper进程作为next进程并继续进行下一步骤。
我们假设schedule( )函数已经肯定运行队列中有一些可运行的进程，现在它必须检查这些可运行进程中是否至少有一个进程是活动的，如果没有，函数就交换运行队列数据结构的active和expired字段的内容，因此，所有的过期进程变为活动进程，而空集合准备接纳将要过期的进程。
array = rq->active;
if (!array->nr_active) {
rq->active = rq->expired;
rq->expired = array;
array = rq->active;
rq->expired_timestamp = 0;
rq->best_expired_prio = 140;
}
现在可以在活动的prio_array_t数据结构中搜索一个可运行进程了。首先，schedule()搜索活动进程集合位掩码的第一个非0位。回忆一下，当对应的优先权链表不为空时，就把位掩码的相应位置1。因此，第一个非0位的下标对应包含最佳运行进程的链表，随后，返回该链表的第一个进程描述符：
idx = sched_find_first_bit(array->bitmap);
next = list_entry(array->queue[idx].next, task_t, run_list);
函数sched_find_first_bit( )是基于bsfl 汇编语言指令的，它返回32位字中被设置为1的最低位的位下标。局部变量next现在存放将取代prev的进程描述符。schedule( )函数检查next->activated字段，该字段的编码值表示进程在被唤醒时的状态，如表所示：
值
说明
0
进程处于TASK_RUNNING 状态。
1
进程处于TASK_INTERRUPTIBLE 或TASK_STOPPED 状态，而且正在被系统调用服务例程或内核线程唤醒。
2
进程处于TASK_INTERRUPTIBLE 或TASK_STOPPED 状态，而且正在被中断处理程序或可延迟函数唤醒。
-1
进程处于TASK_UNINTERRUPTIBLE 状态而且正在被唤醒。
如果next是一个普通进程而且它正在从TASK_INTERRUPTIBLE 或 TASK_STOPPED状态被唤醒，调度程序就把自从进程插入运行队列开始所经过的纳秒数加到进程的平均睡眠时间中。换而言之，进程的睡眠时间被增加了，以包含进程在运行队列中等待CPU所消耗的时间。
if (next->prio >= 100 && next->activated > 0) {
unsigned long long delta = now - next->timestamp;
if (next->activated == 1)
delta = (delta * 38) / 128;
array = next->array;
dequeue_task(next, array);
recalc_task_prio(next, next->timestamp + delta);
enqueue_task(next, array);
}
next->activated=0;
要说明的是，调度程序把被中断处理程序和可延迟函数所唤醒的进程与被系统调用服务例程和内核线程所唤醒的进程区分开来，在前一种情况下，调度程序增加全部运行队列等待时间。而在后一种情况下，它只增加等待时间的一部分。这是因为交互式进程更可能被异步事件（考虑用户在键盘上的按键操作）而不是同步事件唤醒。
4 schedule( )完成进程切换时所执行的操作
现在schedule( )函数已经要让next 进程投入运行。内核将立刻访问next 进程的thread_info数据结构，它的地址存放在next进程描述符的接近顶部的位置。
switch_tasks:
prefetch(next);
prefetch 宏提示CPU控制单元把next进程描述符的第一部分字段的内容装入硬件高速缓存，正是这一点改善了schedule()的性能，因为对于后续指令的执行（不影响next），数据是并行移动的。
在替代prev之前，调度程序应该完成一些管理的工作：
clear_tsk_need_resched(prev);
rcu_qsctr_inc(prev->thread_info->cpu);
以防（万一）以延迟方式调用schedule( )， clear_tsk_need_resched( )函数清除prev的TIF_NEED_RESCHED标志。然后，函数记录CPU正在经历静止状态。
schedule( )函数还必须减少prev的平均睡眠时间，并把它补充给进程所使用的CPU时间片：
prev->sleep_avg -= run_time;
if ((long)prev->sleep_avg <= 0)
prev->sleep_avg = 0;
prev->timestamp = prev->last_ran = now;
随后更新进程的时间戳。
prev 和next很可能是同一个进程：在当前运行队列中没有优先权较高或相等的其他活动进程时，会发生这种情况。在这种情况下，函数不做进程切换：
if (prev == next) {
spin_unlock_irq(&rq->lock);
goto finish_schedule;
}
之后，prev和next肯定是不同的进程了，那么进程切换确实地发生了：
next->timestamp = now;
rq->nr_switches++;
rq->curr = next;
prev = context_switch(rq, prev, next);
context_switch( )函数建立next的地址空间：
static inline struct task_struct *context_switch(struct rq *rq, struct task_struct *prev, struct task_struct *next)
{
struct mm_struct *mm = next->mm;
struct mm_struct *oldmm = prev->active_mm;
trace_sched_switch(rq, prev, next);
if (unlikely(!mm)) {
next->active_mm = oldmm;
atomic_inc(&oldmm->mm_count);
enter_lazy_tlb(oldmm, next);
} else
switch_mm(oldmm, mm, next);
if (unlikely(!prev->mm)) {
prev->active_mm = NULL;
WARN_ON(rq->prev_mm);
rq->prev_mm = oldmm;
}
#ifndef __ARCH_WANT_UNLOCKED_CTXSW
spin_release(&rq->lock.dep_map, 1, _THIS_IP_);
#endif
/* Here we just switch the register state and the stack. */
switch_to(prev, next, prev);
return prev;
}
进程描述符的active_mm字段指向进程所使用的内存描述符，而mm字段指向进程所拥有的内存描述符。对于一般的进程，这两个字段有相同的地址，但是，内核线程没有它自己的地址空间，因而它的mm字段总是被设置为NULL。context_switch( )函数保证：如果next是一个内核线程，它使用prev所使用的地址空间：
if (!next->mm) {
next->active_mm = prev->active_mm;
atomic_inc(&prev->active_mm->mm_count);
enter_lazy_tlb(prev->active_mm, next);
}
一直到Linux 2.2 版，内核线程都有自己的地址空间。那种设计选择不是最理想的，因为不管什么时候当调度程序选择一个新进程（即使是一个内核线程）运行时，都必须改变页表；因为内核线程都运行在内核态，它仅使用线性地址空间的第4个GB，其映射对系统的所有进程都是相同的。甚至最坏情况下，写cr3寄存器会使所有的TLB表项无效，这将导致极大的性能损失。现在的Linux具有更高的效率，因为如果next是内核线程，就根本不触及页表。作为进一步的优化，如果next是内核线程， schedule( )函数把进程设置为懒惰TLB模式。
相反，如果next是一个普通进程，schedule( )函数用next的地址空间替换prev的地址空间：
if (next->mm)
switch_mm(prev->active_mm, next->mm, next);
如果prev是内核线程或正在退出的进程，context_switch( )函数就把指向prev内存描述符的指针保存到运行队列的prev_mm 字段中，然后重新设置prev->active_mm：
if (!prev->mm) {
rq->prev_mm = prev->active_mm;
prev->active_mm = NULL;
}
现在，context_switch( )终于可以调用switch_to( )执行prev 和next之间的进程切换了（参见前面博文“执行进程间切换 ”）：
switch_to(prev, next, prev);
return prev;
5 进程切换后schedule( )所执行的操作
schedule( )函数中在switch_to宏之后紧接着的指令并不由next进程立即执行，而是稍后当调度程序选择prev又执行时由prev执行。然而，在那个时刻，prev局部变量并不指向我们开始描述schedule( )时所替换出去的原来那个进程，而是指向prev被调度时由prev替换出的原来那个进程。（如果你被搞糊涂，请回到“执行进程间切换 ”博文）。
进程切换后的第一部分指令是：
barrier( );
finish_task_switch(prev);
在schedule( )中，紧接着context_switch( )函数调用之后，宏barrier( )产生一个代码优化屏障（以后博文会讨论，这里略过）。然后，执行finish_task_switch( )函数：
mm = this_rq( )->prev_mm;
this_rq( )->prev_mm = NULL;
prev_task_flags = prev->flags;
spin_unlock_irq(&this_rq( )->lock);
if (mm)
mmdrop(mm);
if (prev_task_flags & PF_DEAD)
put_task_struct(prev);
如果prev是一个内核线程，运行队列的prev_mm 字段存放借给prev的内存描述符的地址。mmdrop( )减少内存描述符的使用计数器，如果该计数器等于0了，函数还要释放与页表相关的所有描述符和虚拟存储区。
finish_task_switch( )函数还要释放运行队列的自旋锁并打开本地中断。然后，检查prev 是否是一个正在从系统中被删除的僵死任务， 如果是，就调用put_task_struct( )以释放进程描述符引用计数器，并撤消所有其余对该进程的引用。
schedule( )函数的最后一部分指令是：
//finish_schedule:
prev = current;
if (prev->lock_depth >= 0)
__reacquire_kernel_lock( );
preempt_enable_no_resched();
if (test_bit(TIF_NEED_RESCHED, ¤t_thread_info( )->flags)
goto need_resched;
return;
如你所见，schedule( )在需要的时候重新获得大内核锁、重新启用内核抢占、并检查是否一些其他的进程已经设置了当前进程的TIF_NEED_RESCHED标志，如果是，整个schedule( )函数重新开始执行，否则，函数结束。
最核心的schedule( )胜利结束！感谢党，感谢人民！