进程调度算法2
上一篇进程调度算法1——FCFS、SJF、HRRN介绍了适合早期操作系统（如批处理系统）的三种调度算法：FCFS、SJF、HRRN算法，但是这些这些调度算法的交互性差，不能很好的适合当前的实时操作系统、交互式系统，所以本文介绍几种适合交互式操作系统的调度算法。
1 时间片轮转调度（RR，Round_Robin）
时间片轮转调度：又称RR调度，该调度算法轮流让就绪队列中的进程依次执行一个时间片（每次选择的都是排在就绪队列队头的进程）。
由于进程不能在时间片内运行完，就会被强行剥夺处理机的使用权，因此时间片轮转算法属于抢占式的算法。由时钟装置发出的时钟中断来通知CPU时间片以到。
1.1 先取时间片大小为2的情况
0时刻：0时刻只有P1进程到达就绪队列，让P1上处理机运行一个时间片。
2时刻：进程2进入就绪队列，同时进程1的时间片用完，被剥夺处理机，重新放入就绪队列。线程1和线程2同时在时刻2要进入就绪队列，这里默认新的进程放在对头。
然后选择进程2上处理机运行一个时间片。
4时刻：进程3进入就绪队列。同时进程2的时间片被使用完，被剥夺处理机，重新进入就绪队列。
然后选择再进程1上处理机运行一个时间片。
5时刻：线程4到达插入就绪队列的尾部，但是线程1的时间片没有运行完，因此暂时不会调度，此时的就绪队列为：
6时刻：线程1的时间片使用完，下处理机进入就绪队列，此时就绪队列中的状态为：
进程1进入就绪队列后，进程3上处理机运行
7时刻：进程3运行结束退出，进程2获得时间片上处理机运行，此时就绪队列为：
9时刻：进程2时间片用完，进程2也正好结束退出，进程4获得时间片。
11时刻：进程4时间片用完，进程4重新进入就绪队列，进程1获取时间片上处理机运行，此时就绪队列中就只剩下进程4。
12时刻：进程1进程结束，主动放弃时间片，进程4获取时间片上处理机运行。
14时刻：就绪对列为空，所以让进程4继续运行一个时间片。
16时刻，所有进程运行结束。
1.2 时间片为5的情况
从上可以看出，当时间片过大时，所有的进程在一个时间片内就可以完成，时间片轮转调度算法就退化成了先到先服务调度算法。所以时间片不能太大。
同时，时间片也不能太小，太小会导致进程之间切换频繁，然而进程切换是需要代价的（保存、回复进程的运行状态等），系统会花费大量的时间在进程切换上，实际处理任务的时间很少。会导致系统的效率降低，响应变慢。
2 优先级调度算法
优先级调度算法包括抢占式和非抢占式两种。
2.1非抢占式优先级调度算法
非抢占式优先级调度算法：当前进程主动放弃处理机时发生调度，每次调度时选择当前已到达且优先级最高的进程。
由于是非抢占式，所以只有进程主动放弃处理机才会调度。
0时刻：只有P1到达，P1上处理机运行。
7时刻：P1完成主动放弃处理机，此时P2、P3、P4进程都到达就绪队列，但是P3进程的优先级最高，所以P3上处理机运行。
.....
2.2 抢占式优先级调度算法
0时刻：只有P1到达，P1上处理机运行。
2时刻：P2到达就绪队列，P2优先级比P1高，发生抢占，P1回到就绪队列，P2使用处理机。
4时刻：P3到达，优先级比P2高，发生抢占，P2回到就绪队列，P3抢找处理机执行。
5时刻：P3完成，主动释放处理机，同时P4到达，由于P2比P4先达到，所以选择P2上处理机。
7时刻：P2完成，P4比P1优先级高，所以P4抢占处理机。
11时刻：P4完成，P1上处理机。
16时刻：所有进程均完成。
3 多级反馈队列调度算法
多级反馈队列调度算法：是对其他调度算法的折中。
算法规则：
(1) 设置多级就绪队列，各级队列优先级从高到低，时间片从小到大。
(2) 新进程到达时先进入第1级队列，按FCFS原则排队等待被分配时间片。若时间片用完进程还没未结束，则进程进入下一级队列队尾。如果此时已经是最下级的队列，则重新放回最下级队列队尾。
(3) 只有第k级队列为空时，才会为k+1级队头的进程分配时间片。
(4) 被抢占处理机的进程将重新放回原队列队尾。
下面用一个例子演示多级反馈队列调度算法
假设一共有三级队列，对应时间片分别为1、2和3.
0时刻，P1到达第一级队列，获取时间片后开始执行。
1时刻：P2进程进入第1级队列，同时P1时间片用完，P1进程没有结束，所以P1进入第2级队列的队尾，P2开始上处理机运行。
2时刻：P2的时间片用完，P2也没有结束，所以P2进入第2级队列的队尾。
由于此时第1级队列是空的，所以第2级队列的队头获得时间片开始执行，级P1开始执行。
4时刻：P1的时间片用完，P1未结束，进入下一级队列，同时P2进程获取时间片开始执行。
5时刻：P3进程进入第1级队列，但是此时P2进程的时间片还没有用完。由于第1级队列的优先级高，所以P3会抢占时间片，P2会进入同级队列即第2级队列的队尾等待。P3获取时间片开始执行。
6时刻：P3时间片用完，并且P3也运行结束退出。
此时第1级队列中又没有进程了，所以第2级队列中的队头即P2进程又获得了时间片开始执行。
8时刻：P2进程时间片用完，同时P2进程结束退出。
P2进程退出后，只有P1一个进程在第3级队列中，所以P1进程获取时间片运行，P1用完一个时间片后，此时P1已经在最底层队列，所以它会被重新放到该级队列的队尾。
最后，P1再次获取时间片运行结束退出。
3.1算法思想
对其他调度算法的折中权衡。
3.2算法规则
见前面。
3.3 用于作业/进程调度
多级反馈队列调度算法用于进程调度。
3.4 是否抢占
是抢占式的算法。在k级队列运行过程中，若更上级的队列进入一个新进程，新进程就会抢占处理机，原来的进程就会k级队列的队尾。
3.5优缺点
对各类型进程相对公平（FCFS的优点）；每个新到的进程都可以很快的得到响应（RR调度的优点）；短进程只用较少的时间就可以完成（SJF的优点）。
3.6 是否会导致饥饿
会导致饥饿。如果上面的队列源源不断的由进程进入，会导致下面队列中的进程长时间得不到处理。
4 小结
交互式操作系统（分时操作系统、实时操作系统等）更注重系统的响应时间、公平性、平衡性等指标。而这几种调度算法更好的满足交互式系统的需求，因此这三种算法适合于交互式系统。
