操作系统常用调度算法 你知道几个？(2)

时间片轮转调度算法主要适用于分时系统。在这种算法中，系统将所有就绪进程按到达时间的先后次序排成一个队列，进程调度程序总是选择就绪队列中第一个进程执行，即先来先服务的原则，但仅能运行一个时间片，如100ms。在使用完一个时间片后，即使进程并未完成其运行，它也必须释放出(被剥夺)处理机给下一个就绪的进程，而被剥夺的进程返回到就绪队列的末尾重新排队，等候再次运行。

在时间片轮转调度算法中，时间片的大小对系统性能的影响很大。如果时间片足够大，以至于所有进程都能在一个时间片内执行完毕，则时间片轮转调度算法就退化为先来先服务调度算法。如果时间片很小，那么处理机将在进程间过于频繁切换，使处理机的开销增大，而真正用于运行用户进程的时间将减少。因此时间片的大小应选择适当。

时间片的长短通常由以下因素确定：系统的响应时间、就绪队列中的进程数目和系统的处理能力。

多级反馈队列调度算法(集合了前几种算法的优点)

多级反馈队列调度算法是时间片轮转调度算法和优先级调度算法的综合和发展，如图2-5 所示。通过动态调整进程优先级和时间片大小，多级反馈队列调度算法可以兼顾多方面的系统目标。例如，为提高系统吞吐量和缩短平均周转时间而照顾短进程;为获得较好的I/O设备利用率和缩短响应时间而照顾I/O型进程;同时，也不必事先估计进程的执行时间。

图2-5 多级反馈队列调度算法

多级反馈队列调度算法的实现思想如下：

1.应设置多个就绪队列，并为各个队列赋予不同的优先级，第1级队列的优先级最高，，第2级队列次之，其余队列的优先级逐次降低。

2.赋予各个队列中进程执行时间片的大小也各不相同，在优先级越高的队列中，每个进程的运行时间片就越小。例如，第2级队列的时间片要比第1级队列的时间片长一倍， ……第i+1级队列的时间片要比第i级队列的时间片长一倍。

3.当一个新进程进入内存后，首先将它放入第1级队列的末尾，按FCFS原则排队等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可准备撤离系统;如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第2级队列的末尾，再同样地按FCFS 原则等待调度执行;如果它在第2级队列中运行一个时间片后仍未完成，再以同样的方法放入第3级队列……如此下去，当一个长进程从第1级队列依次降到第 n 级队列后，在第 n 级队列中便釆用时间片轮转的方式运行。

4.仅当第1级队列为空时，调度程序才调度第2级队列中的进程运行;仅当第1 ~ (i-1)级队列均为空时，才会调度第i级队列中的进程运行。如果处理机正在执行第i级队列中的某进程时，又有新进程进入优先级较高的队列(第 1 ~ (i-1)中的任何一个队列)，则此时新进程将抢占正在运行进程的处理机，即由调度程序把正在运行的进程放回到第i级队列的末尾，把处理机分配给新到的更高优先级的进程。

多级反馈队列的优势有：

• 终端型作业用户：短作业优先。
• 短批处理作业用户：周转时间较短。
• 长批处理作业用户：经过前面几个队列得到部分执行，不会长期得不到处理。

【编辑推荐】

1. 对不起 Linux，Kubernetes现在是更重要的操作系统！
2. Linux操作系统有什么吸引力，在程序员中这么受欢迎！
3. 成为“黑客”前，必须学习的“操作系统架构体系”
4. 为什么中国至今没有像样的国产操作系统？
5. 必须装！Windows 7下月发布SHA-2加密算法补丁

（编辑：ASP站长网）