原创 Linux进程调度原理

优先权只是调度算法考虑的一个方面
进程调度依据
调度程序运行时，要在所有可运行状态的进程中选择最值得运行的进程投入运行。选择进程的依据是什么呢？在每个进程的task_struct结构中有以下四项：policy、priority、counter、rt_priority。这四项是选择进程的依据。其中，policy是进程的调度策略，用来区分实时进程和普通进程，实时进程优先于普通进程运行；priority是进程(包括实时和普通)的静态优先级；counter是进程剩余的时间片，它的起始值就是priority的值；由于counter在后面计算一个处于可运行状态的进程值得运行的程度goodness时起重要作用，因此，counter也可以看作是进程的动态优先级。rt_priority是实时进程特有的，用于实时进程间的选择。
Linux用函数goodness()来衡量一个处于可运行状态的进程值得运行的程度。该函数综合了以上提到的四项，还结合了一些其他的因素，给每个处于可运行状态的进程赋予一个权值(weight)，调度程序以这个权值作为选择进程的唯一依据。关于goodness()的情况在后面将会详细分析。
进程调度策略
调度程序运行时,要在所有处于可运行状态的进程之中选择最值得运行的进程投入运行。选择进程的依据是什么呢?在每个进程的task_struct 结构中有这么四项：
policy, priority , counter, rt_priority
这四项就是调度程序选择进程的依据.其中,policy是进程的调度策略,用来区分两种进程-实时和普通；priority是进程(实时和普通)的优先级；counter 是进程剩余的时间片,它的大小完全由priority决定;rt_priority是实时优先级,这是实时进程所特有的，用于实时进程间的选择。
首先，Linux 根据policy从整体上区分实时进程和普通进程，因为实时进程和普通进程度调度是不同的，它们两者之间，实时进程应该先于普通进程而运行，然后，对于同一类型的不同进程，采用不同的标准来选择进程：
对于普通进程，Linux采用动态优先调度，选择进程的依据就是进程counter的大小。进程创建时，优先级priority被赋一个初值，一般为0～70之间的数字，这个数字同时也是计数器counter的初值，就是说进程创建时两者是相等的。字面上看，priority是"优先级"、counter是"计数器"的意思，然而实际上，它们表达的是同一个意思-进程的"时间片"。Priority代表分配给该进程的时间片，counter表示该进程剩余的时间片。在进程运行过程中，counter不断减少，而priority保持不变，以便在counter变为0的时候（该进程用完了所分配的时间片）对counter重新赋值。当一个普通进程的时间片用完以后，并不马上用priority对counter进行赋值，只有所有处于可运行状态的普通进程的时间片(p->counter==0)都用完了以后，才用priority对counter重新赋值，这个普通进程才有了再次被调度的机会。这说明，普通进程运行过程中，counter的减小给了其它进程得以运行的机会，直至counter减为0时才完全放弃对CPU的使用，这就相对于优先级在动态变化，所以称之为动态优先调度。至于时间片这个概念，和其他不同操作系统一样的，Linux的时间单位也是"时钟滴答"，只是不同操作系统对一个时钟滴答的定义不同而已（Linux为10ms）。进程的时间片就是指多少个时钟滴答，比如，若priority为20，则分配给该进程的时间片就为20个时钟滴答，也就是20*10ms=200ms。Linux中某个进程的调度策略(policy)、优先级(priority)等可以作为参数由用户自己决定，具有相当的灵活性。内核创建新进程时分配给进程的时间片缺省为200ms(更准确的，应为210ms)，用户可以通过系统调用改变它。
对于实时进程，Linux采用了两种调度策略，即FIFO(先来先服务调度)和RR（时间片轮转调度）。因为实时进程具有一定程度的紧迫性，所以衡量一个实时进程是否应该运行，Linux采用了一个比较固定的标准。实时进程的counter只是用来表示该进程的剩余时间片，并不作为衡量它是否值得运行的标准。实时进程的counter只是用来表示该进程的剩余时间片，并不作为衡量它是否值得运行的标准，这和普通进程是有区别的。上面已经看到，每个进程有两个优先级，实时优先级就是用来衡量实时进程是否值得运行的。
这一切看来比较麻烦，但实际上Linux中的实现相当简单。Linux用函数goodness()来衡量一个处于可运行状态的进程值得运行的程度。该函数综合了上面提到的各个方面，给每个处于可运行状态的进程赋予一个权值(weight)，调度程序以这个权值作为选择进程的唯一依据。
Linux根据policy的值将进程总体上分为实时进程和普通进程，提供了三种调度算法：一种传统的Unix调度程序和两个由POSIX.1b(原名为POSIX.4)操作系统标准所规定的"实时"调度程序。但这种实时只是软实时，不满足诸如中断等待时间等硬实时要求，只是保证了当实时进程需要时一定只把CPU分配给实时进程。
非实时进程有两种优先级，一种是静态优先级，另一种是动态优先级。实时进程又增加了第三种优先级，实时优先级。优先级是一些简单的整数，为了决定应该允许哪一个进程使用CPU的资源，用优先级代表相对权值-优先级越高，它得到CPU时间的机会也就越大。
? 静态优先级(priority)-不随时间而改变，只能由用户进行修改。它指明了在被迫和其他进程竞争CPU之前，该进程所应该被允许的时间片的最大值（但很可能的，在该时间片耗尽之前，进程就被迫交出了CPU）。
? 动态优先级(counter)-只要进程拥有CPU，它就随着时间不断减小；当它小于0时，标记进程重新调度。它指明了在这个时间片中所剩余的时间量。
? 实时优先级(rt_priority)-指明这个进程自动把CPU交给哪一个其他进程；较高权值的进程总是优先于较低权值的进程。如果一个进程不是实时进程，其优先级就是0，所以实时进程总是优先于非实时进程的（但实际上，实时进程也会主动放弃CPU）。
当policy分别为以下值时：
1) SCHED_OTHER：这是普通的用户进程，进程的缺省类型，采用动态优先调度策略，选择进程的依据主要是根据进程goodness值的大小。这种进程在运行时，可以被高goodness值的进程抢先。
2) SCHED_FIFO：这是一种实时进程，遵守POSIX1.b标准的FIFO(先入先出)调度规则。它会一直运行，直到有一个进程因I/O阻塞，或者主动释放CPU，或者是CPU被另一个具有更高rt_priority的实时进程抢先。在Linux实现中，SCHED_FIFO进程仍然拥有时间片-只有当时间片用完时它们才被迫释放CPU。因此，如同POSIX1.b一样，这样的进程就象没有时间片(不是采用分时)一样运行。Linux中进程仍然保持对其时间片的记录（不修改counter）主要是为了实现的方便，同时避免在调度代码的关键路径上出现条件判断语句 if (!(current->policy&SCHED_FIFO)){...}-要知道，其他大量非FIFO进程都需要记录时间片，这种多余的检测只会浪费CPU资源。（一种优化措施，不该将执行时间占10%的代码的运行时间减少到50%；而是将执行时间占90%的代码的运行时间减少到95%。0.9+0.1*0.5=0.95>0.1+0.9*0.9=0.91）
3) SCHED_RR：这也是一种实时进程，遵守POSIX1.b标准的RR(循环round-robin)调度规则。除了时间片有些不同外，这种策略与SCHED_FIFO类似。当SCHED_RR进程的时间片用完后，就被放到SCHED_FIFO和SCHED_RR队列的末尾。
只要系统中有一个实时进程在运行，则任何SCHED_OTHER进程都不能在任何CPU运行。每个实时进程有一个rt_priority，因此，可以按照rt_priority在所有SCHED_RR进程之间分配CPU。其作用与SCHED_OTHER进程的priority作用一样。只有root用户能够用系统调用sched_setscheduler，来改变当前进程的类型(sys_nice,sys_setpriority)。
此外，内核还定义了SCHED_YIELD，这并不是一种调度策略，而是截取调度策略的一个附加位。如同前面说明的一样，如果有其他进程需要CPU，它就提示调度程序释放CPU。特别要注意的就是这甚至会引起实时进程把CPU释放给非实时进程。
主要的进程调度的函数分析
真正执行调度的函数是schedule(void),它选择一个最合适的进程执行，并且真正进行上下文切换，使得选中的进程得以执行。而reschedule_idle(struct task_struct *p)的作用是为进程选择一个合适的CPU来执行，如果它选中了某个CPU，则将该CPU上当前运行进程的need_resched标志置为1,然后向它发出一个重新调度的处理机间中断，使得选中的CPU能够在中断处理返回时执行schedule函数，真正调度进程p在CPU上执行。在schedule()和reschedule_idle()中调用了goodness()函数。goodness()函数用来衡量一个处于可运行状态的进程值得运行的程度。此外，在schedule()函数中还调用了schedule_tail()函数;在reschedule_idle()函数中还调用了reschedule_idle_slow()。这些函数的实现对理解SMP的调度非常重要，下面一一分析这些函数。先给出每个函数的主要流程图，然后给出源代码，并加注释。
goodness()函数分析
goodness()函数计算一个处于可运行状态的进程值得运行的程度。一个任务的goodness是以下因素的函数：正在运行的任务、想要运行的任务、当前的CPU。goodness返回下面两类值中的一个：1000以下或者1000以上。1000或者1000以上的值只能赋给"实时"进程，从0到999的值只能赋给普通进程。实际上，在单处理器情况下，普通进程的goodness值只使用这个范围底部的一部分，从0到41。在SMP情况下，SMP模式会优先照顾等待同一个处理器的进程。不过，不管是UP还是SMP，实时进程的goodness值的范围是从1001到1099。
goodness()函数其实是不会返回-1000的，也不会返回其他负值。由于idle进程的counter值为负，所以如果使用idle进程作为参数调用goodness，就会返回负值，但这是不会发生的。
goodness()是个简单的函数，但是它是linux调度程序不可缺少的部分。运行队列中的每个进程每次执行schedule时都要调度它，因此它的执行速度必须很快。



//在/kernel/sched.c中
static inline int goodness(struct task_struct * p, int this_cpu, struct mm_struct *this_mm)
{ int weight;

if (p->policy != SCHED_OTHER) {/*如果是实时进程，则*/
weight = 1000 + p->rt_priority;
goto out;
}
/* 将counter的值赋给weight，这就给了进程一个大概的权值，counter中的值表示进程在一个时间片内，剩下要运行的时间.*/
weight = p->counter;
if (!weight) /* weight==0,表示该进程的时间片已经用完，则直接转到标号out*/
goto out;
#ifdef __SMP__

/*在SMP情况下，如果进程将要运行的CPU与进程上次运行的CPU是一样的，则最有利，因此，假如进程上次运行的CPU与当前CPU一致的话，权值加上PROC_CHANGE_PENALTY，这个宏定义为20。*/
if (p->processor == this_cpu)
weight += PROC_CHANGE_PENALTY;
#endif

if (p->mm == this_mm) /*进程p与当前运行进程，是同一个进程的不同线程，或者是共享地址空间的不同进程，优先选择，权值加1*/
weight += 1;
weight += p->priority; /* 权值加上进程的优先级*/
out:
return weight; /* 返回值作为进程调度的唯一依据，谁的权值大，就调度谁运行*/
}
schedule()函数分析
schedule()函数的作用是，选择一个合适的进程在CPU上执行，它仅仅根据'goodness'来工作。对于SMP情况，除了计算每个进程的加权平均运行时间外，其他与SMP相关的部分主要由goodness()函数来体现。
Schedule()函数的主要流程图如下：



流程：
①将prev和next设置为schedule最感兴趣的两个进程：其中一个是在调用schedule时正在运行的进程(prev)，另外一个应该是接着就給予CPU的进程（next）。注意：prev和next可能是相同的-schedule可以重新调度已经获得cpu的进程.
②中断处理程序运行"下半部分".
③内核实时系统部分的实现，循环调度程序（SCHED_RR）通过移动"耗尽的"RR进程-已经用完其时间片的进程-到队列末尾，这样具有相同优先级的其他RR进程就可以获得CPU了。同时，这补充了耗尽进程的时间片。
④由于代码的其他部分已经决定了进程必须被移进或移出TASK_RUNNING状态，所以会经常使用schedule，例如，如果进程正在等待的硬件条件已经发生，所以如果必要，这个switch会改变进程的状态。如果进程已经处于TASK_RUNNING状态，它就无需处理了。如果它是可以中断的（等待信号），并且信号已经到达了进程，就返回TASK_RUNNING状态。在所以其他情况下（例如，进程已经处于TASK_UNINTERRUPTIBLE状态了），应该从运行队列中将进程移走。
⑤将p初始化为运行队列的第一个任务；p会遍历队列中的所有任务。
⑥c记录了运行队列中所有进程最好的"goodness"-具有最好"goodness"的进程是最易获得CPU的进程。goodness的值越高越好。
⑦遍历执行任务链表，跟踪具有最好goodness的进程。
⑧这个循环中只考虑了唯一一个可以调度的进程。在SMP模式下，只有任务不在cpu上运行时，即can_schedule宏返回为真时，才会考虑该任务。在UP情况下，can_schedule宏返回恒为真.
⑨如果循环结束后，得到c的值为0。说明运行队列中的所有进程的goodness值都为0。goodness的值为0,意味着进程已经用完它的时间片，或者它已经明确说明要释放CPU。在这种情况下，schedule要重新计算进程的counter；新counter的值是原来值的一半加上进程的静态优先级（priortiy），除非进程已经释放CPU，否则原来counter的值为0。因此，schedule通常只是把counter初始化为静态优先级。（中断处理程序和由另一个处理器引起的分支在schedule搜寻goodness最大值时都将增加此循环中的计数器，因此由于这个原因计数器可能不会为0。显然，这很罕见。）在counter的值计算完成后，重新开始执行这个循环，找具有最大goodness的任务。
⑩如果schedule已经选择了一个不同于前面正在执行的进程来调度，那么就必须挂起原来的进程并允许新的进程运行。这时调用switch_to来进行切换。

代码摘自linux/kernel/sched.c：
asmlinkage void schedule(void)
{
struct schedule_data * sched_data;
struct task_struct *prev, *next, *p;
int this_cpu, c;

if (tq_scheduler) /*tq_scheduler是一个特殊的队列，只在调度程序运行时得到执行，其目的是为了进行扩充，用来支持系统中多于32个的任务队列*/
goto handle_tq_scheduler;
tq_scheduler_back:

prev = current;
this_cpu = prev->processor;

if (in_interrupt()) /*判断schedule是否在中断处理中执行，如果是在中断中执行，就说明发生了错误，会引发OOPS错误*/
goto scheduling_in_interrupt;

release_kernel_lock(prev, this_cpu); /*释放全局内核锁，并开this_cpu的中断，主要是在进行进程切换前释放内核锁，否则，若不释放，切换后的进程也要获得内核锁，就会发生死锁*/
/*检测是否有中断下半部需要处理*/
if (bh_mask & bh_active)
goto handle_bh;
handle_bh_back:

/*对于aligned_data[this_cpu].schedule_data的读写不需要用锁保护，因为，每个CPU上任意时刻只有一个进程运行*/
sched_data = & aligned_data[this_cpu].schedule_data;/*取得本地cpu上的调度数据*/

spin_lock_irq(&runqueue_lock);/*要开始操作要运行进程队列，不允许打断，故锁住运行队列，并且同时关中断*/

/*将一个时间片用完的SCHED_RR进程放到队列的末尾*/
if (prev->policy == SCHED_RR)
goto move_rr_last;
move_rr_back:

switch (prev->state) {
case TASK_INTERRUPTIBLE: /*此状态表明进程可以被信号中断*/
if (signal_pending(prev)) {/*如果该进程有未处理的信号*/
prev->state = TASK_RUNNING;
break;
}
default:
del_from_runqueue(prev);
case TASK_RUNNING:
}
prev->need_resched = 0;

repeat_schedule: /*真正找合适的进程*/

p = init_task.next_run;
/* Default process to select.. */
next = idle_task(this_cpu); /*缺省选择空闲进程*/
c = -1000;
if (prev->state == TASK_RUNNING)
goto still_running;
still_running_back:

while (p != &init_task) {
if (can_schedule(p)) { /*进程p不占用cpu*/
int weight = goodness(prev, p, this_cpu);
if (weight > c)
c = weight, next = p;
}
p = p->next_run;
}

/*c中存放最大的goodness值*/
if (!c) /*如果goodness（prev,p,this_cpu）函数返回的是0,表示进程p剩余的运行时间为0,则要重新计算*/
goto recalculate;
/*到这一点，已经确定了要调度执行的进程*/
/*记录调度选择的情况*/
sched_data->curr = next;
#ifdef __SMP__
next->has_cpu = 1;
next->processor = this_cpu;
#endif
spin_unlock_irq(&runqueue_lock); /*对运行队列数据结构操作完成，释放运行队列锁，并打开中断*/

if (prev == next) /*如果选中的进程和原来运行的进程是同一个*/
goto same_process;

#ifdef __SMP__
/*计算该进程在其生命周期里占有cpu的平均时间：avg_slice。这是加权平均，进程近期的活动远比很久以前的活动权值大。这个值将在reschedule_idle中用来决定是否将进程调入到另一个CPU中。因此，在UP情况下，它不需要而且也不会被计算。*/
{
cycles_t t, this_slice;

t = get_cycles();
this_slice = t - sched_data->last_schedule;
sched_data->last_schedule = t;

/*计算进程的平均运行时间*/
prev->avg_slice = (this_slice*1 + prev->avg_slice*1)/2;
}
#endif /* __SMP__ */

kstat.context_switch++;
get_mmu_context(next);
switch_to(prev, next, prev); /*切换到选中的进程执行*/
__schedule_tail(prev); /*该函数调用的作用是：考虑将当前被切换下来的进程，放到别的CPU上运行*/

same_process:
reacquire_kernel_lock(current); /*重新获得内核锁*/
return;

recalculate:
{
struct task_struct *p;
spin_unlock_irq(&runqueue_lock);
read_lock(&tasklist_lock); /*tasklist可以允许多个读者读，但当有一个写者时，不运行有其他读者或写者*/
for_each_task(p) /*对于每个重新计算p->counter*/
p->counter = (p->counter >> 1) + p->priority;
read_unlock(&tasklist_lock);
spin_lock_irq(&runqueue_lock);
goto repeat_schedule;
}

still_running:
c = prev_goodness(prev, prev, this_cpu);
next = prev;
goto still_running_back;

handle_bh:/*处理中断下半部*/
do_bottom_half();
goto handle_bh_back;

handle_tq_scheduler:/*处理tq_scheduler中的任务*/
run_task_queue(&tq_scheduler);
goto tq_scheduler_back;

move_rr_last:/*将一个时间片用完的进程放到运行队列的末尾*/
if (!prev->counter) {
prev->counter = prev->priority;
move_last_runqueue(prev);
}
goto move_rr_back;

scheduling_in_interrupt: /*处理在中断中调度的情况，产生一个错误*/
printk("Scheduling in interrupt\n");
*(int *)0 = 0; /*向一个非法地址写,产生错译*/
return;
}
reschedule_idle()函数分析
当已经不在运行队列中的进程被唤醒时，wake_up_process(struct task_struct * p)将调用reschedule_idle，进程是作为p而被传递进reschedule_idle中的。这个函数试图把新近唤醒的进程在一个最合适的CPU上运行。
reschedule_idle()函数主要针对SMP系统，不过，在该函数中调用了reschedule_idle_slow()中，在reschedule_idle_slow()中，存在一些针对UP的代码。
在reschedule_idle()中使用goodness()，目的是用来预测在我们发送到的CPU上运行schedule()的效果。通过预测未来执行schedule()的效果，可以在任务被唤醒时，选择最好的CPU去运行。reschedule_idle()的最后一个目标是：让选中的CPU上调用schedule()，使得被唤醒的任务能在该CPU上重新调度运行。这是如何做的的呢？如果选择到的最好CPU不是当前CPU，就可以通过CPU间消息传递方法（在i386中，是SMP-IPI中断），向该CPU发送一个重新调度的事件。如果就是当前CPU，就可以直接将当前运行进程的need_resched标志置为1，在随后的时钟中断结束时引发调度。
Reschedule_idle的主要流程：



以下代码摘自linux/kernel/sched.c
static void reschedule_idle(struct task_struct * p)
{
/*这个函数代码分两部分。第一部分：快速判断是否需要找一个合适的CPU让进程p运行，如果不需要直接返回；这部分代码，只是在SMP情况下才会执行。第二部分代码调用reschedule_idle_slow(),真正去找一个合适的CPU让进程p执行。*/
#ifdef __SMP__
int cpu = smp_processor_id();

/*检查是否值得找一个合适的CPU让p执行,如果不值得，则直接返回*/
if ((p->processor == cpu) && related(cpu_curr(cpu), p))
return;
#endif /* __SMP__ */

reschedule_idle_slow(p);
}

宏related(p1,p2)的分析：
其中宏related(p1,p2)定义为：
摘自：kernel/sched.c
#define related(p1,p2) (((p1)->lock_depth >= 0) && (p2)->lock_depth >= 0) && (((p2)->policy== SCHED_OTHER) && ((p1)->avg_slice < cacheflush_time))
当以下三种条件同时满足时，该宏返回为真：
①(p1)->lock_depth >= 0) && (p2)->lock_depth >= 0)为真，表明进程p1和p2都在控制着，或想要控制内核锁，说明这两个进程存在相互依赖关系，则不管这两个进程生存于何处，都不可能同时运行；
②进程p1的的平均运行时间小于清空本地高速缓存的时间（cacheflush_time），cacheflush_time在系统启动时被赋值为cpu_hz/1024*cachesize/5000，其中cpu_hz为CPU的时钟频率，cachesize为高速缓存的大小；
③进程p2是一个普通进程；
从总体上来说，宏related(p1,p2)主要检测进程p1和p2是否存在相互依赖关系。如果依赖关系存在，则不管这两个进程生存于何处，都不可能同时运行。宏related(p1,p2)返回真，表明没有必要找另一个合适的CPU让进程p2执行。
reschedule_idle_slow()函数分析
reschedule_idle_slow(struct task_struct * p)的目标是试图找出一个合适的CPU来运行进程p。
流程图：


SMP情况下流程：
①先检查p进程上一次运行的cpu是否空闲，如果空闲，这是最好的cpu，直接返回；
②找一个合适的cpu，查看SMP中的每个CPU上运行的进程，与p进程相比的抢先goodness，把具有最高的抢先goodness值的进程记录在target_task中，该进程运行的cpu为最合适的CPU。但是，如果在检查的过程中，发现某个cpu上运行的进程与进程p是相关的，即related宏返回为真，表明没有必要找一个CPU让进程运行，直接转到标号out_no_target执行；
③如target_task为空，说明没有找到合适的cpu，直接转到标号out_no_target执行。
④如果target_task不为空，则说明找到了合适的cpu，因此将target_task->need_resched置为1,如果运行target_task的cpu不是reschedule_idle_slow运行的cpu，则向运行target_task的cpu发送一个中断，让它重新调度；
⑤out_no_target后的语句，就直接返回；
UP情况下流程：
检查p能否抢先cpu上运行的进程，如果能抢先（即preemtion_goodness(task,p,this_cpu)>0），则将cpu上当前进程的need_resched域置为1，引发调度。
以下代码摘自：linux/kernel/sched.c
static inline void reschedule_idle_slow(struct task_struct * p)
{
#ifdef __SMP__
/*在SMP中，尽力找一个最合适的CPU让进程p执行。这个合适的CPU可能是空闲CPU，但也有可能不是空闲CPU。只要进程p的goodness值比CPU上运行的当前进程的goodness值要高，就可以抢先在该CPU上运行的进程。当然，在选择合适的CPU时，是选择进程p与该CPU上运行进程的goodness的值相差最大的CPU。*/
int this_cpu = smp_processor_id(), target_cpu;
struct task_struct *tsk, *target_tsk;
int cpu, best_cpu, weight, best_weight, i;
unsigned long flags;

best_weight = 0;
/*要读写运行队列，必须先获得运行队列自旋锁，并且确保关中断*/
spin_lock_irqsave(&runqueue_lock, flags);

best_cpu = p->processor;
target_tsk = idle_task(best_cpu); /*idle_task（）得到当该cpu的空闲进程*/
if (cpu_curr(best_cpu) == target_tsk) /*进程上一次运行的cpu是空闲的*/
goto send_now;

target_tsk = NULL;
for (i = 0; i < smp_num_cpus; i++) {
cpu = cpu_logical_map(i);
tsk = cpu_curr(cpu);
if (related(tsk, p)) /*如果tak和p相依赖，则这两个进程几乎不可能同时运行，因此，不需要找在空闲cpu让p执行*/
goto out_no_target;
/*计算p抢先tsk的goodness,preemption_goodness(),实际上是计算两个进程的goodness()的差值*/
weight = preemption_goodness(tsk, p, cpu);
if (weight > best_weight) {
best_weight = weight;
target_tsk = tsk;
}
}

/*以上for循环执行完后，target_task应该是最合适的cpu上运行的进程*/
if (!target_tsk) /*如果没有合适的cpu*/
goto out_no_target;
send_now:
target_cpu = target_tsk->processor;
target_tsk->need_resched = 1;
/*释放运行队列锁，并恢复中断标志，注意：不一定是开中断，恢复执行spin_lock_irqsave前的状态*/
spin_unlock_irqrestore(&runqueue_lock, flags);

if (target_cpu != this_cpu) /*如果不是是当前调度程序运行的cpu，则*/
smp_send_reschedule(target_cpu);/*向选择的CPU发送一个IPI,使得该CPU上能进行调度*/
return;
out_no_target:
/*没有找到合适的CPU，释放运行队列锁，并恢复中断标志*/
spin_unlock_irqrestore(&runqueue_lock, flags);
return;
#else
/*处理单CPU的情况，因为只有一个CPU，因此不需要选择了，只需要看是否值得抢先当前正在运行的进程就可以了。*/
int this_cpu = smp_processor_id();
struct task_struct *tsk;
tsk = current;
if (preemption_goodness(tsk, p, this_cpu) > 0)
tsk->need_resched = 1;
#endif
}
这里涉及处理机间通信/中断，我们将在第三部分详细介绍，这里只讨论与处理机调度有关的部分。Intel多处理规范MP的核心就是高级可编程中断控制器（Advanced Programmable Interrupt Controllers，APIC）的使用。CPU通过彼此发送中断来完成它们之间的通信。通过给中断附加动作，不同的CPU可以在某种程度广彼此进行控制。每个CPU有自己的APIC（成为那个CPU的本地APIC），并且还有一个I／O APIC来处理由I／O设备引起的中断。在普通的多处理器系统中，I／O APIC中断控制器芯片组的作用。
void smp_send_reschedule(int cpu)
{
send_IPI_single(cpu, RESCHEDULE_VECTOR);
}
这个函数只有一行，它仅仅是给其ID以参数形式给出的目标CPU发送一个中断。函数用CPU ID和RESCHEDULE＿VECTOR向量调用send＿IPI＿single函数。RESCHEDULE_VECTOR与其他CPU中断向量是一起在arch/i386/kernel/irq.h中被定义。
#define RESCHEDULE_VECTOR 0x30
#define INVALIDATE_TLB_VECTOR 0x31
#define STOP_CPU_VECTOR 0x40
#define LOCAL_TIMER_VECTOR 0x41
#define CALL_FUNCTION_VECTOR 0x50
static inline void send_IPI_single(int dest, int vector)
send＿IPI＿single函数发送一个IPI--那是Intel对处理器问中断（Interprocessor interruPt）的称呼--给指定的目的CPU。在这一行，内核以相当低级的方式与发送CPU的本地APIC对话。
{
unsigned long cfg;
#if FORCE_APIC_SERIALIZATION
unsigned long flags;

__save_flags(flags);
__cli();
#endif
cfg = __prepare_ICR2(dest);
得到中断命令寄存器（ICR）上半部分的内容--本地APIC就是通过这个寄存器进行编程的--不过它的目的信息段要被设置为dest。尽管．＿prepare＿ICRZ里使用了"2"，CPU实际上只有一个ICR，而不是两个。但是它是一个64位寄存器，内核更愿意把它看作是两个32位寄存器--在内核代码里，"ICR"表示这个寄存器的低端32位，所以"ICR2"就表示高端32位。我们想要设置的目的信息段就在高端32位，即ICR2里。
apic_write(APIC_ICR2, cfg);
把修改过的信息写回ICR。现在ICR知道了目的CPU。
cfg = __prepare_ICR(0, vector);
调用＿prepare＿ICR来设置我们想要发送给目的CPU的中断向量（注意没有什么措施能够保证目的CPU不是当前CPU--ICR完全能够发送一个IPI给它自己的CPU。尽管这样，没有任何理由要这样做）。
apic_write(APIC_ICR, cfg);
通过往ICR里写入新的配置来发送中断。
#if FORCE_APIC_SERIALIZATION
__restore_flags(flags);
#endif
}
schedule_tail()函数分析
顾名思义，该函数的作用是执行schedule()函数的一些扫尾工作。在SMP情况下，如果失去CPU的进程,其状态是TASK_RUNNING,并且不是空闲进程，则调用reschedule_idle()，找一个合适的CPU去运行。并且将失去CPU的进程的has_cpu域置为0。并且为保证处理器一致性，调用wmb()来has_cpu=0这个操作不会被提前执行。
代码摘自：linux/kernel/sched.c：
static inline void __schedule_tail (struct task_struct *prev)
{
#ifdef __SMP__
if ((prev->state == TASK_RUNNING) &&(prev != idle_task(smp_processor_id())))
reschedule_idle(prev);
wmb(); /*根据处理器一致性（PO）,保证读、写操作的顺序*/
prev->has_cpu = 0;
#endif /* __SMP__ */
}

此外，源码是最好的文档，看看kernel/sched.c
#ifndef __alpha__
/*
* This has been replaced by sys_setpriority. Maybe it should be
* moved into the arch dependent tree for those ports that require
* it for backward compatibility?
*/

asmlinkage int sys_nice(int increment)
{
unsigned long newprio;
int increase = 0;

/*
* Setpriority might change our priority at the same moment.
* We don't have to worry. Conceptually one call occurs first
* and we have a single winner.
*/

newprio = increment;
if (increment < 0) {
if (!capable(CAP_SYS_NICE))
return -EPERM;
newprio = -increment;
increase = 1;
}

if (newprio > 40)
newprio = 40;
/*
* do a "normalization" of the priority (traditionally
* Unix nice values are -20 to 20; Linux doesn't really
* use that kind of thing, but uses the length of the
* timeslice instead (default 210 ms). The rounding is
* why we want to avoid negative values.
*/
newprio = (newprio * DEF_PRIORITY + 10) / 20;
increment = newprio;
if (increase)
increment = -increment;
/*
* Current->priority can change between this point
* and the assignment. We are assigning not doing add/subs
* so thats ok. Conceptually a process might just instantaneously
* read the value we stomp over. I don't think that is an issue
* unless posix makes it one. If so we can loop on changes
* to current->priority.
*/
newprio = current->priority - increment;
if ((signed) newprio < 1)
newprio = 1;
if (newprio > DEF_PRIORITY*2)
newprio = DEF_PRIORITY*2;
current->priority = newprio;
return 0;
)

#endif