进程调度
调度时机
发生调度的必要条件，当进程从用户态因为系统调用，中断进入内核态后，从内核态返回前夕会尝试着调度。 如：
ENTRY(ret_from_intr) GET_CURRENT(%ebx) movl EFLAGS(%esp),%eax # mix EFLAGS and CS movb CS(%esp),%al testl $(VM_MASK | 3),%eax # return to VM86 mode or non-supervisor? jne ret_with_reschedule jmp restore_all ALIGN
1) testl $(VM_MASK | 3),%eax jne ret_with_reschedule 注意eax的内容是中断发生前夕保存在栈上的CS(%esp)，如果低2位是3，正说明中断发生前夕运行在用户态，否则说明中断发生前夕运行在内核态。 只有，中断发生前夕CS低2位是3，才会进行 rt_with_reschedule。 2) 为什么调度发生在返回用户态前夕呢？ 简化内核的设计。如果内核线程代码在执行过程中被中断打断了， 等中断返回后不会还会回到原来的内核线程，不会进入其他的线程，不必担心原来线程的资源被其他内核线程征用。因为内核线程的执行不会发生调度。 但是在SMP环境下，天生面临着多个核征用同一个资源，这种设计优势逐渐丧失了。 3) 缺点？ 如果内核线程很耗时，或者发生多次中断，导致一直执行不到ret_wit_reschedule，导致用户进程得不到相应。
调度策略
整体的思路是，以优先级为基础的调度。内核给每个进程计算一个权值，权值会随着时间而递减。从而下一下调度的时候权值低的有机会被运行。 为了适应不同的场景，内核在此基础上实现了3种策略: SCHED_FIFO, SCHED_RR, SCHED_OTHER。 进程可以通过sched_setscheduler设置自己的调度策略。 SCHED_FIFO和SCHED_RR都是基于优先级的，优先级高的肯定要优于优先级低的得到执行。区别是在相同优先级的调度上的差别。 SCHED_FIFO:如果一个进程通过调度得到执行，其他和他优先级相同的进程不会打断当前进程，知道当前进程自动放弃CPU，或者有更高优先级进程需要调度，才会打断当前进程。 SCHED_RR:对相同优先级进程，每次调度都有一个时间片，时间片用完后就会让给其他相同优先级进程执行。同样的，如果有更高优先级进程需要调度，也会打断当前进程。
schedule()
这个调度函数的整体代码，以前代码阅读的方法是逐行阅读，遇到重要的函数就跟踪进去，这个的整体感被削弱了。 这次换个代码阅读的方法，以第一级上以标号为段落，分段阅读，并整理出每个段落的功能。这样更能理解之所以设计的妙处。
asmlinkage void schedule(void) { struct schedule_data * sched_data; struct task_struct *prev, *next, *p; struct list_head *tmp; int this_cpu, c; if (!current->active_mm) BUG(); need_resched_back: prev = current; this_cpu = prev->processor; if (in_interrupt()) goto scheduling_in_interrupt; release_kernel_lock(prev, this_cpu); if (softirq_active(this_cpu) & softirq_mask(this_cpu)) goto handle_softirq; handle_softirq_back: sched_data = & aligned_data[this_cpu].schedule_data; spin_lock_irq(&runqueue_lock); 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: next = idle_task(this_cpu); c = -1000; if (prev->state == TASK_RUNNING) goto still_running; still_running_back: 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 (!c) goto recalculate; sched_data->curr = next; spin_unlock_irq(&runqueue_lock); if (prev == next) goto same_process; kstat.context_swtch++; prepare_to_switch(); { struct mm_struct *mm = next->mm; struct mm_struct *oldmm = prev->active_mm; if (!mm) { if (next->active_mm) BUG(); next->active_mm = oldmm; atomic_inc(&oldmm->mm_count); enter_lazy_tlb(oldmm, next, this_cpu); } else { if (next->active_mm != mm) BUG(); 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; recalculate: { 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; still_running: c = goodness(prev, this_cpu, prev->active_mm); next = prev; goto still_running_back; handle_softirq: do_softirq(); goto handle_softirq_back; move_rr_last: if (!prev->counter) { prev->counter = NICE_TO_TICKS(prev->nice); move_last_runqueue(prev); } goto move_rr_back; scheduling_in_interrupt: printk("Scheduling in interrupt\n"); BUG(); return; }
schedule第1段: need_resched_back
need_resched_back在每次调度函数schedule被执行的都要进行的例行工作：判断是否在中断中，是否有软中断待处理.
asmlinkage void schedule(void) { struct schedule_data * sched_data; struct task_struct *prev, *next, *p; struct list_head *tmp; int this_cpu, c; if (!current->active_mm) BUG(); need_resched_back: prev = current; this_cpu = prev->processor; if (in_interrupt()) goto scheduling_in_interrupt; release_kernel_lock(prev, this_cpu); if (softirq_active(this_cpu) & softirq_mask(this_cpu)) goto handle_softirq; ... ... ... }
1) if (!current->active_mm) BUG(); 普通进程有active_mm，而内核线程会用上一个运行的进程的active_mm，所以所有的task_struct都会有一个active_mm 2) scheduling_in_interrupt: printk("Scheduling in interrupt\n"); BUG(); return; 如果调度发生在中断中，则出错处理，printk像/var/log/message中打一条log。 看一下 BUG的实现： #define BUG() do { \ printk("kernel BUG at %s:%d!\n", __FILE__, __LINE__); \ __asm__ __volatile__(".byte 0x0f,0x0b"); \ } while (0) 关键的地方是__asm__ __volatile__(".byte 0x0f,0x0b"); 在可执行的二进制文件中顺序写入了两个字节0x0f, 0x0b，做为指令执行。而这两条指令是不存在的。 因而产生一次"invalid_op"异常。 3) if (softirq_active(this_cpu) & softirq_mask(this_cpu)) 查看是否有软中断需要处理。若果有则goto handle_softirq。 handle_softirq: do_softirq(); goto handle_softirq_back; 处理完软中断后回到handle_softirq_back中来。
schedule第2段: handle_softirq_back:
处理完软中断后，根据调度测率作相应的初始化。
asmlinkage void schedule(void) { ... ... ... handle_softirq_back: sched_data = & aligned_data[this_cpu].schedule_data; spin_lock_irq(&runqueue_lock); if (prev->policy == SCHED_RR) goto move_rr_last; ... ... ... }
1) sched_data = & aligned_data[this_cpu].schedule_data; static union { struct schedule_data { struct task_struct * curr; cycles_t last_schedule; } schedule_data; char __pad [SMP_CACHE_BYTES]; } aligned_data [NR_CPUS] __cacheline_aligned = { {{&init_task,0}}}; 记录上一次调度的信息。 2) if (prev->policy == SCHED_RR) goto move_rr_last; 如果当前进程的调度策略是SCHED_RR要进行一些初始化的工作。
schedule第3段: move_rr_last
asmlinkage void schedule(void) { ... ... ... move_rr_last: if (!prev->counter) { prev->counter = NICE_TO_TICKS(prev->nice); move_last_runqueue(prev); } goto move_rr_back; ... ... ... }
1) if (!prev->counter) prev->counter是进程运行的时间配额，在每次时钟中断到来都要递减，在函数update_process_times中进行。 2) prev->counter = NICE_TO_TICKS(prev->nice); move_last_runqueue(prev); 如果当前进程的时间配额用完了，就结合进程的nice值重恢复配额。 并且，把这个进程移动到runqueue尾部。 3) move_last_runqueue(prev); static inline void move_last_runqueue(struct task_struct * p) { list_del(&p->run_list); list_add_tail(&p->run_list, &runqueue_head); }
schedule第4段: move_rr_back:
schedule调度函数操作的runqueue队列，但是，这个队列中的进程状态并不都是TASK_RUNNING。 如，前面的wait4中，父进程会把自己的状态改成 TASK_INTERRUPTIBLE，然后自发的调动scheldule。 表示期望自己的状态是 TASK_INTERRUPTIBLE，schedule帮我处理。
asmlinkage void schedule(void) { ... ... ... 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; ... ... ... }
1) case TASK_INTERRUPTIBLE: 如果进程的状态是TASK_INTERRUPTIBLE并且有待处理的信号，说明这个可被打断的进程已经收到了信号，可以再次运行起来。 2) prev->need_resched = 0; 当前进程已经处于调度中了，要把 need_resched 设置为0。
schedule第5段: repeat_schedule
asmlinkage void schedule(void) { ... ... ... repeat_schedule: next = idle_task(this_cpu); c = -1000; if (prev->state == TASK_RUNNING) goto still_running; still_running: c = goodness(prev, this_cpu, prev->active_mm); next = prev; goto still_running_back; ... ... ... }
1) next = idle_task(this_cpu); repeat_schedule的任务是找到一个权重最大的进程。 从idle_task下一个进程开始，并初始化其权重为最小值-1000. 2) if (prev->state == TASK_RUNNING) 如果当前进程的意图是继续执行则先进入到still_running。 3) still_running 用当前进程的权重最为初始化值，这样，相同权重的进程，当前进程会得到优先执行。
优先权重的计算
static inline int goodness(struct task_struct * p, int this_cpu, struct mm_struct *this_mm) { int weight; weight = -1; if (p->policy & SCHED_YIELD) goto out; if (p->policy == SCHED_OTHER) { weight = p->counter; if (!weight) goto out; if (p->mm == this_mm || !p->mm) weight += 1; weight += 20 - p->nice; goto out; } weight = 1000 + p->rt_priority; out: return weight; }
可以看到, 如果进程设置了SCHED_YIELD(放弃执行的权利), weight为最低值-1; 如果进程的策略是SCHED_OTHER，则weight的值为p->counter + 20 - p->nice; 如果进程的策略是SCHED_RR,SCHED_FIFO，则weight为1000 + p->rt_priority。
schedule第6段: still_running_back
asmlinkage void schedule(void) { ... ... ... still_running_back: 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 (!c) goto recalculate; ... recalculate: { 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; ... ... ... }
1) list_for_each(tmp, &runqueue_head) 遍历runqueue_head中的进程，找到权重最大的进程。 2) if (!c) 最大的权重为0，说明runqueue队列中没有实时进程(SCHED_FIFO和SCHED_RR)，都是SCHED_OTHER进程，而且已经持续了一段时间了(SCHED_OTHER把配额消耗完了，导致weight为0)。 需要重新计算权重。
schedule第7段: 切换
asmlinkage void schedule(void) { ... ... ... prepare_to_switch(); { struct mm_struct *mm = next->mm; struct mm_struct *oldmm = prev->active_mm; if (!mm) { if (next->active_mm) BUG(); next->active_mm = oldmm; atomic_inc(&oldmm->mm_count); enter_lazy_tlb(oldmm, next, this_cpu); } else { if (next->active_mm != mm) BUG(); switch_mm(oldmm, mm, next, this_cpu); } if (!prev->mm) { prev->active_mm = NULL; mmdrop(oldmm); } } switch_to(prev, next, prev); __schedule_tail(prev); ... ... ... }
1) prepare_to_switch(); 在386平台是一条空的语句。 2) if (!mm) 如果当前进程没有自己的mm，就借用前一个进程的mm。 3) switch_mm(oldmm, mm, next, this_cpu); 切换pgd到CR3寄存器。 4) switch_to(prev, next, prev); 真正的切换。值得仔细研究的地方。
switch_to
#define switch_to(prev,next,last) do { \ asm volatile("pushl %%esi\n\t" \ "pushl %%edi\n\t" \ "pushl %%ebp\n\t" \ "movl %%esp,%0\n\t" /* save ESP */ \ "movl %3,%%esp\n\t" /* restore ESP */ \ "movl $1f,%1\n\t" /* save EIP */ \ "pushl %4\n\t" /* restore EIP */ \ "jmp __switch_to\n" \ "1:\t" \ "popl %%ebp\n\t" \ "popl %%edi\n\t" \ "popl %%esi\n\t" \ :"=m" (prev->thread.esp),"=m" (prev->thread.eip), \ "=b" (last) \ :"m" (next->thread.esp),"m" (next->thread.eip), \ "a" (prev), "d" (next), \ "b" (prev)); \ } while (0)
1) "movl %%esp,%0\n\t" 保存当前进程内核栈的栈顶到第0个参数prev->thread.esp中。 2) "movl %3,%%esp\n\t" 把第3个参数(next->thread.esp) 加载到esp寄存器中。 这条语句之后内核栈就切换到了新进程的内核栈空间！！！如果此时get_current得到的就是新的进程。 但是，此时的EIP没改变，继续往下面执行。 1) "movl $1f,%1\n\t" 把标号1处的pop执行的地址保存到第1个参数prev->thread.eip中。 下次当前进程被调度起来的时候就会从1处开始执行，也就是说所有被调度出去的进程都停留在标号1处！！！ 2) "pushl %4\n\t" 保存新进程的next->thread.eip到栈顶，注意，测试新进程的栈顶也就是被调度出去的时候保存的标号1，这个指令地址被保存到了栈顶，做为接下来jmp到__switch_to的返回地址。 3) "jmp __switch_to\n" 更新TSS中的esp0 __switch_to是一个函数，通过return返回到栈顶的指令，也就是新进程的thread->eip，也就是2)中提到的标号1.
