Linux内核进程调度机制详解

Linux的进程管理由进程控制块、进程调度、中断处理、任务队列、定时器、bottom half队列、系统调用、进程通信等等部分组成。

进程调用分为实时进程调度和非实时进程调度两种。前者调度时，可以采用基于动态优先级的轮转法（RR），也可以采用先进现出算法（FIFO）。后者调度时，一律采用基于动态优先级的轮转法。某个进程采用何种调度算法由改进程的进程控制块中的某些属性决定，没有专门的系统用来处理关于进程调度的相关事宜。 Linux的进程调度由schedule（）函数负责，任何进程，当它从系统调用返回时，都会转入schedule（），而中断处理函数完成它们的响应任务以后，也会进入schedule（）。

1.         进程控制块数据结构
Linux系统的进程控制块用数据结构task_struct表示，这个数据结构占用1680个字节，具体的内容不在这里介绍，详细内容见《Linux内核2.4版源代码分析大全》第二页。
进程的状态主要包括如下几个：
TASK_RUNNING   正在运行或在就绪队列run-queue中准备运行的进程，实际参与进程调度。
TASK_INTERRUPTIBLE       处于等待队列中的进程，待资源有效时唤醒，也可由其它进程通过信号或定时中断唤醒后进入就绪队列run-queue。
TASK_UNINTERRUPTIBLE         处于等待队列的进程，待资源有效时唤醒，不也可由其它进程通过信号或者定时中断唤醒。
TASK_ZOMBIE      表示进程结束但尚未消亡的一种状态（僵死），此时，进程已经结束运行并且已经释放了大部分资源，但是尚未释放进程控制块。
TASK_STOPPED    进程暂停，通过其它进程的信号才能唤醒。

所有进程（以PCB形式）组成一个双向列表。next_task和prev_task就是链表的前后向指针。链表的头尾都是init_task（init进程）。不过进程还要根据其进程ID号插入到一个hash表当中，目的是加快进程搜索速度。

2.         进程调度
Linux进程调度由schedule（）执行，其任务是在run-queue队列中选出一个就绪进程。
每个进程都有一个调度策略，在它的task_struct中规定（policy属性），或为SCHED_RR,SCHED_FIFO，或为SCHED_OTHER。前两种为实时进程调度策略，后一种为普通进程调度策略。
用户进程由do_fork（）函数创建，它也是fork系统调用的执行者。do_fork（）创建一个新的进程，继承父进程的现有资源，初始化进程时钟、信号、时间等数据。完成子进程的初始化后，父进程将它挂到就绪队列，返回子进程的pid。
进程创建时的状态为TASK_UNINTERRUPTIBLE，在do_fork（）结束前被父进程唤醒后，变为TASK_RUNNING。处于TASK_RUNNING状态的进程被移到就绪队列中，当适当的时候由schedule（）按CPU调度算法选中，获得CPU。
如果进程采用轮转法，当时间片到时（10ms的整数倍），由时钟中断触发timer_interrupt（）函数引起新一轮的调度，把当前进程挂到就绪队列的尾部。获得CPU而正在运行的进程若申请不到某个资源，则调用sleep_on（）或interruptible_sleep_on（）睡眠，并进入就绪队列尾。状态尾TASK_INTERRUPTIBLE的睡眠进程当它申请的资源有效时被唤醒，也可以由信号或者定时中断唤醒，唤醒以后进程状态变为 TASK_RUNNING，并进入就绪队列。
首先介绍一下2.6版以前的的调度算法的主要思想，下面的schedule（）函数是内核2.4.23中摘录的：
asmlinkage void schedule(void)
{
struct schedule_data * sched_data;
struct task_struct *prev, *next, *p;
struct list_head *tmp;
int this_cpu, c;

spin_lock_prefetch(&runqueue_lock);

BUG_ON(!current->active_mm);
need_resched_back:
       /*记录当前进程和处理此进程的CPU号*/
prev = current;
this_cpu = prev->processor;
/*判断是否处在中断当中，这里不允许在中断处理当中调用sechedule（）*/
if (unlikely(in_interrupt())) {
        printk("Scheduling in interrupt\n");
        BUG();
}

release_kernel_lock(prev, this_cpu);

/*'sched_data' 是收到保护的，每个CPU只能运行一个进程。*/
sched_data = & aligned_data[this_cpu].schedule_data;

spin_lock_irq(&runqueue_lock);

/*如果当前进程的调度策略是轮转RR，那么需要判断当前进程的时间片是否已经用完，如果已经用完，则重新计算时间片值，然后将该进程挂接到就绪队列run-queue的最后*/
if (unlikely(prev->policy == SCHED_RR))
        if (!prev->counter) {
               prev->counter = NICE_TO_TICKS(prev->nice);
               move_last_runqueue(prev);
        }
/*假如前进程为TASK_INTERRUPTTIBLE状态，则将其状态置为TASK_RUNNING。如是其它状态，则将该进程转为睡眠状态，从运行队列中删除。（已不具备运行的条件） */
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:
next = idle_task(this_cpu);
c = -1000;
/*遍历进程就绪队列，如果该进程能够进行调度（对于SMP来说就是判断当前CPU未被占用能够执行这个进程，对于非SMP系统则为1），则计算该进程的优先级，如果优先级大于当前进程，则next指针指向新的进程，循环直到找到优先级最大的那个进程*/
list_for_each(tmp, &runqueue_head) {
        p = list_entry(tmp, struct task_struct, run_list);
        if (can_schedule(p, this_cpu)) {
               int weight = goodness(p, this_cpu, prev->active_mm);
               if (weight > c)
                      c = weight, next = p;
        }
}

/* 判断是否需要重新计算每个进程的时间片，判断的依据是所有正准备进行调度的进程时间片耗尽，这时，就需要对就绪队列中的每一个进程都重新计算时间片，然后返回前面的调度过程，重新在就绪队列当中查找优先级最高的进程执行调度。 */
if (unlikely(!c)) {
        struct task_struct *p;

        spin_unlock_irq(&runqueue_lock);
        read_lock(&tasklist_lock);
        for_each_task(p)
               p->counter = (p->counter >> 1) + NICE_TO_TICKS(p->nice);
        read_unlock(&tasklist_lock);
        spin_lock_irq(&runqueue_lock);
        goto repeat_schedule;
}

/*CPU私有调度数据中记录当前进程的指针，并且将当前进程与CPU绑定，如果待调度进程与前面一个进程属于同一个进程，则不需要调度，直接返回。*/
sched_data->curr = next;
task_set_cpu(next, this_cpu);
spin_unlock_irq(&runqueue_lock);

if (unlikely(prev == next)) {
        /* We won't go through the normal tail, so do this by hand */
        prev->policy &= ~SCHED_YIELD;
        goto same_process;
}
/*全局统计进程上下文切换次数*/
kstat.context_swtch++;
/*如果后进程的mm为0 （未分配页），则检查是否被在被激活的页里（active_mm）,否则换页。令后进程记录前进程激活页的信息，将前进程的active_mm中的 mm_count值加一。将cpu_tlbstate[cpu].state改为 TLBSTATE_LAZY(采用lazy模式) 如果后进程的mm不为0（已分配页），但尚未激活，换页。切换mm（switch_mm）。 如果前进程的mm 为0（已失效） ，将其激活记录置空，将mm结构引用数减一,删除该页。 */
prepare_to_switch();
{
        struct mm_struct *mm = next->mm;
        struct mm_struct *oldmm = prev->active_mm;
        if (!mm) {
               BUG_ON(next->active_mm);
               next->active_mm = oldmm;
               atomic_inc(&oldmm->mm_count);
               enter_lazy_tlb(oldmm, next, this_cpu);
        } else {
               BUG_ON(next->active_mm != mm);
               switch_mm(oldmm, mm, next, this_cpu);
        }

        if (!prev->mm) {
               prev->active_mm = NULL;
               mmdrop(oldmm);
        }
}

/*切换到后进程，调度过程结束*/
switch_to(prev, next, prev);
__schedule_tail(prev);

same_process:
reacquire_kernel_lock(current);
if (current->need_resched)
        goto need_resched_back;
return;
}