本文引证图片均来自 李治军: 操作系统32讲
其实只需给定起始履行地址CPU就能主动的不断往下取指履行，但正如 操作系统(3) 多进程图画 所介绍过的那样，CPU以这种方法作业效率是很低的，所以咱们要人为的介入CPU的作业，也就是调度CPU
调度要素
如下图，当正在履行的进程由于读写磁盘堵塞住了，关于CPU来说在磁盘拜访完毕前它都是无法作业的由于可能进程后面的代码就需求使用从磁盘读取的数据。假如此刻不对CPU进行调度，那么CPU在这段时刻的等候就会造成资源浪费
此刻可以让CPU先履行另一个使命，等IO完毕后再回来履行当时使命，这样就避免了等候提高了CPU使用率
调度中如何决议接下来履行哪一个使命呢？咱们先看看不同的使命关心什么样的目标
- 关于后台使命，比方GCC编译器，希望在准备安排妥当到终究被调用履行完成的时刻短一些
- 关于前台使命，比方Word，希望呼应用户操作的时刻短一些
- 关于操作系统，希望时刻能够尽量用来履行使命而不是花在诸如切换使命等操作上
这些目标之间相互影响
要想呼应时刻小就要在不同使命间频繁切换，切换多了系统花在切换上的时刻就多，那么用来履行使命的时刻也就相应的变少
不同的使命有不同的特点，比方GCC编译器需求进行大量运算是CPU束缚型，Word经常要保存文件拜访磁盘是IO束缚型等等
根据以上咱们可以知道调度要考虑的要素很多，偏重这方面就会忽略另一方面，所以在决议下一个履行进程的时候各个要素要综合，折中，因而人们发明了各种各样的调度算法
其实调度算法没有最好的，只有最适合的，比方说个人用操作系统和工业用操作系统要考虑的调度要素就不相同，针对不同使用场景”最好”的调度算法也必定不同
简略调度算法
本节简略介绍几个根本的调度算法
FCFS
FCFS（First Come First Served）先来先服务，非抢占式（当时使命开释CPU其他使命才能取得CPU），行列中的使命谁先来谁先履行
FCFS很简略很容易完成，但缺点也很明显。如上图，仅仅将P2和P3的顺序调换就将平均周转时刻从40.2降到35，但就连这点变化FCFS都做不到
SJF
SJF（Shortest Job First）短作业优先，非抢占式，行列中的使命履行时刻短的优先，寻求最短平均周转时刻
最优性的证明感兴趣可自行查找相关材料，本文不做介绍
RR
RR（Round Robin）时刻片轮转，抢占式（时刻片完毕CPU会被强制开释），每个使命轮番履行，时刻完毕就到下一个使命
如上图时刻片为10ms，P1履行10ms后轮到P2，P2履行10ms后尽管还未履行完但CPU仍然要转移去履行P3，以此类推
RR算法照顾了每一个使命，避免了使命长时刻等候确保了呼应时刻
以上都是根本的调度算法，只考虑了呼应时刻或周转时刻，实际上咱们还要考虑使命是不是等候了很久没履行？是不是紧急使命无论时刻长短都优先履行？等等。调度算法还有最高优先级优先、高呼应比优先和多级反应行列等，本文不做一一介绍
Linux中的调度函数
Linux 0.11中的schedule函数代码少却又综合了优先级，时刻片和等候时刻等要素
schedule (void) {
int i, next, c;
struct task_struct **p;
// 省掉信号相关的十来行代码
while (1) {
c = -1;
next = 0;
i = NR_TASKS;
p = &task[NR_TASKS];
while (--i) {
if (!*--p)
continue;
if ((*p)->state == TASK_RUNNING && (*p)->counter > c)
c = (*p)->counter, next = i;
}
if (c)
break;
for (p = &LAST_TASK; p > &FIRST_TASK; --p)
if (*p)
(*p)->counter = ((*p)->counter >> 1) + (*p)->priority;
}
switch_to (next);
}
1. 首先从安排妥当行列末尾往前遍历，找到counter最大（此处表明优先级）的安排妥当使命，假如能找到则直接跳出循环履行使命
2. 假如所有安排妥当使命时刻片耗尽（此处counter表明时刻片），那么更新行列中所有使命的时刻片
2.1. 关于安排妥当使命，当时时刻片为0，右移一位（除以2）后仍为0，重置时刻片为初始值（priority）
2.2. 关于堵塞使命，当时时刻片不为0，右移一位后加上初值，counter增大
关于堵塞使命来说，从头安排妥当之后会比时刻片耗尽后重置counter的使命优先级更高，且堵塞越久优先级越高（上限为2倍初始值)
关于安排妥当使命来说，当时调度被选择履行后时刻片减小，下次调度大概率会选择另一个使命，相当于轮转调度
