本文共 2657 字，大约阅读时间需要 8 分钟。

• 在上一篇博文中，学习了为什么要进行处理机调度，调度的分级，何时和如何调度以及调度的原则等内容。接下来，在本文学习常用的处理机调度算法。

调度算法

• 操作系统中往往存在多种调度算法，有的适用于作业调度，有的适用于进程调度。经典的调度算法有：先来先服务调度算法、短作业优先调度算法、优先级调度算法、高响应比优先调度算法、时间片轮转调度算法和多级反馈队列调度算法。

1、先来先服务

• 先来先服务算法，即 FCFS 算法，可用于作业调度也可用于进程调度。
• 在作业调度中，算法每次从后备作业队列中选择最先进入该队列的一个或几个作业调入内存，并分配必要的资源创建对应的进程放入就绪队列。
• 同理，FCFS 算法用于进程调度时，会选择最先进入就绪队列的进程先占用 CPU 去运行。
• FCFS 调度算法属于非剥夺式调度算法，特点是算法简单、效率低，对长作业有利而对短作业不利，利于 CPU 繁忙型作业而不利于 I/O 繁忙型作业；通常与其他调度策略结合一起使用，例如在优先级优先的调度策略中遇到进程优先级一样的情况下，使用 FCFS 进行最终选择。

2、短作业优先

• 短作业优先调度算法，简称 SJF 算法，是指对短作业或短进程优先调度的算法，具体就是从后备作业队列中选择一个或若干估计运行时间最短的作业，或从就绪队列选择估计运行时最短的进程，去占有处理机运行直到完成或阻塞才释放处理机。
• SJF 算法有如下不可忽视的缺点：

  1）对长作业不利，使长作业的周转时间增长，更严重的是，若有一长作业进入系统的后备队列，由于短作业优先，极可能出现长作业长期不被调度，也就是“饥饿”现象。2）未考虑作业的紧迫程度，因而不能保证紧迫性作业会被及时处理。3）由于作业的长短只是根据用户提供的估计执行时间而定，若用户有意或无意地缩短其作业地估计运行时，则不一定能真正做到短作业优先调度。

• 有着这些缺点的同时，SJF 算法是平均等待时间、平均周转时间最少的。

3、优先级调度

• 又称为优先权调度算法，同样的可用于作业调度和进程调度；优先级是对作业或进程运行的紧迫程度。根据策略，优先级调度算法每次会从后备队列（就绪队列）选择优先级最高的一个或几个作业（进程）最先进入运行；更进一步，进程运行之后，若有新的更高优先级进程就绪了，依据是否要抢占正在执行的进程分为：剥夺式优先级调度算法和非剥夺式优先级调度算法。而根据进程创建后其优先级是否可以更改分为静态优先级调度算法和动态优先级调度算法，前者指优先级在进程创建时确定，而在整个执行过程中优先级不改变；后者指进程在运行过程中根据进程情况动态调整进程的优先级；静态优先级主要依据进程类型、进程对资源的要求和用户要求，动态优先级则是根据进程占有 CPU 时间的长短、就绪进程等待 CPU 的时间的长短。
• 一般进程优先级的设置参考以下原则：

  1）系统进程优先于用户进程2）交互性进程优先于非交互性进程3）I/O型进程优先于计算型进程。

• 所谓 I/O 型进程是指频繁使用 I/O 的进程，将这些进程优先级调高有利于系统的整体效率，因为 I/O 处理速度远比处理机的处理速度慢。

4、高响应比优先调度

• 高响应比优先调度算法主要用于作业调度，是对 FCFS 调度算法和 SJF 调度算法的一种综合平衡，同时考虑了每个作业的等待时间和估计的运行时间。
  进行作业调度时，先计算后备队列中每个作业的响应比，从中选择最高响应比的作业投入运行。
• 响应比的变化规律：
  
• 1）作业等待的时间相同时，要求服务的时间越短，响应比越高，有利于短作业
• 2）要求服务时间相同时，作业的响应比由其等待时间决定，等待时间越长，其响应比越高，因而它实现的是先来先服务。
• 3）对于长作业，作业的响应比随等待时间增加而提高，当等待时间到一定时，响应比便高到可以获得处理机，克服了“饥饿“现象。

4、时间片轮转调度

• 该算法主要适用于分时系统。具体策略就是，系统将所有就绪进程按到达时间先后排列，进程调度程序总是选择就绪队列的第一个进程运行，但是仅能运行一个时间片，时间片用完后即使工作未完成，运行的进程也必须释放处理机给下一个就绪进程，而这个刚退出运行的进程会被安排到就绪队列的末尾重新排队，等待下一次运行。
• 在这种算法中，时间片的大小变得极其关键，时间片太小时将会出现处理机在进程间频繁切换的现象，导致处理机开销增大，而真正用于运行用户进程的时间很少；反之时间片适当，则大部分进程都能在一个时间片内完成运行。
• 时间片通常根据系统响应时间、就绪队列中的进程数目和系统的处理能力进行安排。

5、多级反馈队列调度算法

• 该算法时时间片轮转调度算法和优先级调度算法的综合与发展，通过动态调整进程优先级和时间片大小，多级反馈队列调度算法可以兼顾多方面的系统目标，如，为提高系统吞吐量和缩短平均周转时间而照顾进程，为获得较好的 I/O 设备利用率而缩短响应时间和缩短响应时间而照顾 I/O 型进程，同时，也不必实现估计进程的执行时间。
  
• 多级反馈队列调度算法的实现思想如下：
• 1）设置多个就绪队列，并为各个队列赋予不同的优先级，第 1 级队列的优先级最高，第 2 级队列次之，其余队列的优先级逐次降低。
• 2）赋予各个队列中进程执行时间片的大小各不相同。在优先级越高的队列中，每个进程的运行时间片越小，第二级队列的时间片要比第一级队列的时间片长一倍……第 i+1 级队列的时间片要比第 I 级队列的时间片长 1 倍。
• 3）新进程进入内存后，首先将他放在第一级队列的末尾，按 FCFS 原则排队等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可准备撤离系统；若在一个时间片结束时尚未完成，调度程序便将该进程转入第2级队列的末尾，再按FCFS原则等待调度执行……如此下去，当一个长进程从第一级队列依次降到第 n 级队列后采用时间片轮转的方式运行。
• 4）仅当第一级队列为空时，调度程序才调度第二级队列中的进程运行；仅当第1~（i-1）级队列均为空时，才会调度第 I 级 队列中的进程运行。若处理机正在执行第 I 级队列的某进程，这时又有新进程进入优先级较高的队列，则此时新进程将抢占正在运行进程的处理机，即由调度程序将正在运行的进程放回第 I 级队列末尾，把处理机分配给新到的更高优先级的进程。
• 多级反馈队列的优势如下：

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

转载地址：http://emqgn.baihongyu.com/