在前文中，多进程切换中有一个重要部分还没有提及，就是在触发调度时，如何选择下一个要执行的进程，这个就涉及到cpu的调度策略。

调度需要考虑的问题

计算机上运行的任务是各种各样的，每种类型的任务需求不一样。
前台任务关注响应时间，后台任务关注周转时间。响应时间小 => 切换次数多 => 系统内耗大 => 吞吐量小 => 周转时间变长。
IO约束型任务和CPU约束型任务有各自特点，IO任务一般执行一小段CPU指令就会开始执行IO，而CPU约束型的任务往往会占用大量的cpu时间片，因此IO约束型的任务应该优先级更高

因此cpu调度算法需要折中和综合，并且调度算法本身的overhead也不能很高，否则系统内耗就大

常见的调度思路

FCFS：First Come， First Served
SJF: 短作业优先 周转时间最短，响应时间无法保障
Round Robin: 轮转调度 保障响应时间
优先级调度：前台任务进行轮转调度，后台任务执行短作业优先，但是绝对的优先级可能会导致后台任务饥饿，因此任务优先级要能够动态升高

Linux 0.11 schedule

  1. void Schedule(void) //在kernel/sched.c中 { 
  2.     while(1) { 
  3.         c=-1; next=0; i=NR_TASKS;
  4.         p=&task[NR_TASKS];
  5.         while(--i) { 
  6.             if((*p->state == TASK_RUNNING&&(*p)->counter>c) // 找到就绪态中最大的counter
  7.             c=(*p)->counter, next=i; 
  8.         }
  9.     if(c) break; //找到了最大的counter 
  10.     for(p=&LAST_TASK;p>&FIRST_TASK;--p) {
  11.         (*p)->counter=((*p)->counter>>1) + (*p)->priority); 
  12.     }
  13.   switch_to(next);
  14. }
  1. //在kernel/sched.c中
  2. void do_timer(...) { 
  3.     if((--current->counter>0) return;
  4.     current->counter=0; schedule(); 
  5. }
  7. _timer_interrupt: //在kernel/system_call.s中 ...
  8. call _do_timer
  10. void sched_init(void) { set_intr_gate(0x20, &timer_interrupt);
  1. 从就绪态的进程中找出最大的counter，counter是时间片
  2. 如果存在最大的counter，就直接switch_to
  3. 如果就绪态进程的conuter都等于0，对于所有进程执行 counter = 1/2 counter + p.priority
    1. 就绪态当前是0，所以就变成了优先级作为counter初值
    2. 阻塞进程当前非0，所以counter = 1/2 counter + p.priority，增大io类进程的优先级
  4. 时间片在每次时钟中断时会将当前current运行的时钟中断-1

在这个算法中，counter既用作优先级（最大的counter优先调度）counter也是时间片 所以是优先级调度和轮转调度的综合，并且实现对了IO类型的进程动态调整增加。在IO类型，每次调度时增加1/2 counter，值这个值是收敛的，收敛于2counter，保障了IO进程的时间片增加，但是最大也不会超过2倍。非常精妙

以上的调度算法是O(n)的实现，在新的Linux内核中已经不是这种算法了，新的调度算法可以学习下面的一些文章。

Linux的公平调度（CFS）原理 - kummer话你知
Linux调度算法