Linux 进程调度原理

代码摘自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。
流程图：

[1] [2] [3]

编辑 webmaster