1. 先来先服务(FCFS)调度算法#

FCFS调度算法是一种最简单的调度算法，既可用于作业调度，也可用于进程调度。

在作业调度中，FCFS算法每次从后备作业队列中选择最早进入该队列的一个或多个作业，将它们调入内存，分配必要的资源，创建相应的进程，并放入就绪队列。

在进程调度中，FCFS算法每次从就绪队列中选择最早进入该队列的进程，将CPU分配给它，使其投入运行，直到该进程运行完成，或因某种原因而进入阻塞态，此时才会交出CPU。

下面用一个实例来说明FCFS算法的性能。假设系统中有4个作业，它们的提交时间分别是8.0、8.4、8.8和9.0，运行时间依次为2、1、0.5和0.2。若系统采用FCFS算法，则这组作业的平均等待时间、平均周转时间和平均带权周转时间如表2.2所示。

FCFS 算法属于非抢占式算法。从表面上看，它对所有作业都是公平的；但若一个长作业先到达系统，则会导致后续的许多短作业长时间等待，因此它不适合作为分时系统和实时系统的主要调度策略。不过，FCFS算法常被结合到其他调度策略中使用。例如，在采用优先级调度的系统中，对于多个具有相同优先级的进程，通常按照FCFS的原则进行调度。

FCFS算法的特点是实现简单，但效率较低。它对长作业较为有利，而对短作业相对不利（与SJF或高响应比优先调度算法相比)。此外，它更有利于CPU繁忙型作业；而对于I/O繁忙型作业，由于其运行过程中会频繁发起I/O请求并进入阻塞状态，本可及时让出CPU以提高系统并发性，但在FCFS调度下，若排在长作业之后，则仍需长时间等待，难以发挥其优势。

表2.2 FCFS调度算法的性能

平均等待时间 $t = (0 + 1.6 + 2.2 + 2.5)/4 = 1.575$；

平均周转时间 $T = (2 + 2.6 + 2.7 + 2.7)/4 = 2.5$；

平均带权周转时间 $W = (1 + 2.6 + 5.4 + 13.5)/4 = 5.625$。

2. 短作业优先(SJF)调度算法#

短作业优先(SJF)调度算法是一种按照作业或进程的预计运行时间进行调度的策略。

在作业调度中，SJF算法从后备作业队列中选择一个或多个估计运行时间最短的作业，将它们调入内存，分配资源并创建进程。

在进程调度中，该策略称为短进程优先(SPF)，即从就绪队列中选择估计运行时间最短的进程，将CPU分配给它，使其立即执行，直至完成，或因某种事件而阻塞时才释放CPU。

例如，考虑与表2.2中示例相同的一组作业，若系统采用SJF调度算法，则这组作业的平均等待时间、平均周转时间和平均带权周转时间如表2.3所示。

表2.3 SJF调度算法的性能

平均等待时间 $t = (0 + 2.3 + 1.4 + 1)/4 = 1.175$；

平均周转时间 $T = (2 + 3.3 + 1.9 + 1.2)/4 = 2.1$；

平均带权周转时间 $W = (1 + 3.3 + 3.8 + 6)/4 = 3.525$。

尽管SJF算法在某些指标上表现优异，但它也存在不容忽视的缺点：

1. 对长作业不利。由表2.2与表2.3可知，在SJF调度下，长作业的周转时间明显增加。更严重的是，若一个长作业进入系统的后备队列，而此后不断有新的短作业到达，调度程序将总是优先调度这些短作业，导致长作业长期得不到服务，从而产生饥饿现象(注意：饥饿是由于调度策略导致的无限期等待，与死锁中的环形等待有本质区别)。
2. 未考虑作业的紧迫程度。该算法仅依据运行时间长短进行调度，完全忽略了作业的截止时间或紧急性，因此无法保证紧迫性作业被及时处理。
3. 作业的“长短”由用户提交的估计值决定，而用户可能有意或无意地低估其作业的实际运行时间，以获取调度优势，从而使算法难以真正实现“短作业优先”的目标。

SPF算法既可以是非抢占式的（默认情况），也可以是抢占式的。在抢占式版本中，当一个新进程到达就绪队列时，若其估计运行时间比当前进程的剩余执行时间更短，则立即暂停当前进程，将CPU分配给新进程。这种抢占式策略也称最短剩余时间优先调度算法。

NOTE

当所有作业同时到达且运行时间已知时，SJF算法的平均等待时间和平均周转时间是最优的。

3. 高响应比优先调度算法#

高响应比优先调度算法主要用于作业调度，是对FCFS算法和SJF算法的一种综合平衡。它在调度决策时同时考虑每个作业的等待时间和估计运行时间。在每次进行作业调度时，系统首先计算后备作业队列中每个作业的响应比，然后选择响应比最高的作业调入内存并执行。

响应比的计算公式为

由该公式可知：

1. 当作业的等待时间相同时，估计运行时间越短，响应比越高，因此有利于短作业，这与SJF 算法的特性相似。
2. 当估计运行时间相同时，响应比由等待时间决定，等待时间越长，响应比越高，这体现了FCFS调度的公平性。
3. 对于长作业，其响应比会随着等待时间的增加而不断提高。当等待时间足够长时，即使估计运行时间较长，其响应比也可能超过其他作业，从而被调度执行。这一机制有效避免了长作业因长期得不到服务而产生的饥饿现象。

4. 优先级调度算法#

优先级调度算法通过为每个作业或进程分配一个优先级，以反映其紧迫程度。

在作业调度中，优先级调度算法每次从后备作业队列中选择优先级最高的一个或多个作业，将它们调入内存，分配资源并创建进程。

在进程调度中，该算法每次从就绪队列中选择优先级最高的进程，将CPU分配给它，使其投入运行。

根据是否允许抢占，优先级调度算法可分为以下两类：

1. 非抢占式优先级调度算法。当一个进程正在CPU上运行时，即使有更高优先级的进程进入就绪队列，系统仍允许当前进程继续执行，直到其因自身原因(如任务完成或等待事件)而让出CPU时，此时将CPU分配给就绪队列中优先级最高的进程。
2. 抢占式优先级调度算法。当一个进程正在CPU上运行时，若有更高优先级的进程进入就绪队列，系统将立即暂停当前进程，将CPU分配给优先级更高的进程。

此外，根据进程创建后其优先级是否可变，优先级又可分为静态与动态两类：

1. 静态优先级。优先级在进程创建时确定，并在其整个运行期间保持不变。确定静态优先级的主要依据包括：进程类型、对资源的需求、用户指定的优先级等。优点是实现简单，系统开销小；缺点是不够灵活，可能出现低优先级进程长期得不到调度的饥饿现象。
2. 动态优先级。进程创建时赋予一个初始优先级，但该优先级会随着进程的推进或等待时间的增加而动态调整，以获得更好的调度效果。例如，规定优先级随等待时间的增加而提高，这样，即使初始优先级较低的进程，在等待足够长时间后也能获得CPU调度。

在实际系统中，进程优先级的设置通常遵循以下原则：

1. 系统进程 $>$ 用户进程。系统进程负责管理核心资源和服务，通常被赋予更高的优先级。
2. 交互型进程 $>$ 非交互型进程（或前台进程 $>$ 后台进程）。交互型进程需要快速响应用户输入，因此应优先调度，以保证良好的用户体验。
3. I/O型进程 $>$ 计算型进程。I/O型进程指频繁进行I/O操作的进程，而计算型进程主要消耗CPU时间，很少使用I/O设备。我们知道，I/O设备（如打印机）的处理速度远低于CPU，因此若将I/O型进程的优先级设置得更高，就能让它尽快获得CPU并启动I/O操作，使I/O设备尽早开始工作，进而提高系统整体吞吐量。

5. 时间片轮转(RR)调度算法#

时间片轮转(RR)调度算法主要适用于分时系统，其最大特点是公平性。系统将所有就绪进程按FCFS的原则组织成一个就绪队列。每隔固定的时间间隔（称为时间片，例如30ms），系统会产生一次时钟中断，激活调度程序，将CPU分配给就绪队列的队首进程，并允许其执行一个时间片。当该进程执行完一个时间片后，即使尚未运行完毕，也必须被剥夺CPU，并重新放入就绪队列的末尾，等待下一次调度；而下一个队首进程则获得CPU的使用权。

RR算法的调度时机：

1. 若当前进程在时间片结束前已运行完成，则调度程序会立即被激活，进行进程切换；
2. 若时间片用尽，则由时钟中断处理程序触发调度程序，完成上下文切换。

在RR算法中，时间片的大小对系统性能有显著影响。时间片过大，大到足以让每个进程在一个时间片内完成运行时，RR算法将退化为FCFS算法，无法满足短作业和交互式用户对快速响应的需求；时间片过小时，虽然部分短作业可能在一个时间片内完成，但会导致系统频繁进行进程调度和上下文切换，大幅增加系统开销，真正用于执行用户程序的CPU时间反而减少。

因此，时间片的长度应合理设置，在响应速度与运行效率之间取得平衡。通常，其取值需综合考虑以下因素：系统的期望响应时间、就绪队列中的进程数量以及系统的处理能力。特别地，在交互式系统中，常以“典型交互”作为参考基准，例如，用户在文本编辑器中输入一个字符，或在终端中按下回车键，这类操作通常只需几十至上百毫秒即可完成。一个较为合理的时间片大小，应略长于一次典型交互所需的时间，这样既能确保大多数交互式进程在单个时间片内完成处理、获得流畅的响应体验，又能有效控制上下文切换频率，避免不必要的系统开销。

6. 多级队列调度算法#

前述的各种调度算法通常只设置一个就绪队列，采用固定且单一的调度策略，难以满足系统中不同类型进程对调度的不同需求。例如，交互型进程要求快速响应，而批处理进程更关注吞吐量和资源利用率。为兼顾这些差异，多级队列调度算法被提出。

该算法将系统中的就绪进程划分为多个独立的就绪队列，每个队列对应一类具有相似特性的进程（如系统进程、交互型进程、批处理进程等）。每个队列可独立采用适合其特性的调度算法：例如，交互型队列常使用RR算法以保证响应性，而批处理队列可采用FCFS算法或SJF算法以提高吞吐量。更重要的是，各队列本身具有不同的优先级。调度时，系统总是优先调度高优先级队列中的进程；只有当所有高优先级队列均为空时，才会调度低优先级队列中的进程。这种机制确保了关键任务（如系统服务或用户交互）能够及时获得CPU资源。

7. 多级反馈队列调度算法（融合了前几种算法的优点）#

多级反馈队列调度算法是时间片轮转调度算法与优先级调度算法的综合与发展。

通过动态调整进程所处的队列（优先级）和对应的时间片大小，该算法能够兼顾系统的多种目标：既有利于短进程，可提高吞吐量并缩短平均周转时间，又有利于I/O型进程以提升设备利用率和响应速度，同时无须事先知道进程的运行时间。

多级反馈队列调度算法的实现机制如下。

1. 设置多个就绪队列。为每个队列赋予不同的优先级，第1级队列优先级最高，第2级次之，其余队列优先级依次降低。该算法为各级队列分配不同的时间片，优先级越高的队列，时间片越小。例如，第 $i+1$ 级队列的时间片长度通常是第 $i$ 级的2倍。
2. 每个队列内部采用时间片轮转(RR)调度。新进程创建后，首先被放入第1级队列的末尾。当轮到该进程执行时：若其在当前时间片内完成，则终止并退出系统；若时间片用完仍未完成，则被移至下一级（优先级更低）队列的末尾，等待后续调度。这一过程持续进行，直至进程在某一级队列中完成。通常，最低优先级队列（如第 $n$ 级）的时间片较长，其行为接近FCFS，但仍采用时间片轮转以保证公平性。
3. 按队列优先级调度。调度程序总是优先调度最高优先级队列中的进程执行。具体而言：仅当第1级队列为空时，才调度第2级队列中的进程；仅当第 $1 \sim i-1$ 级队列均为空时，才会调度第 $i$ 级队列中的进程。此外，由于新进程总是首先进入第1级队列，因此若当前正在执行的是低优先级队列中的进程，而有新进程进入系统，则系统将立即抢占当前进程，将其放回原队列末尾，同时将CPU分配给新的高优先级进程。

多级反馈队列调度算法的优势主要体现在以下场景中：

1. 交互型（终端型）用户：进程通常较短且频繁进行I/O，能在高优先级队列中快速完成。
2. 短批处理作业用户：因优先级高、时间片小，可迅速执行完毕，周转时间较短。
3. 长批处理作业用户：虽最终降至低优先级队列，但已在高优先级队列中获得部分CPU时间，不会因长期得不到调度而产生饥饿现象，最终仍能完成。

8. 基于公平原则的调度算法#

前面介绍的调度算法主要关注响应时间、吞吐量或周转时间等性能指标，但通常未将调度公平性作为主要设计目标。本节介绍两种以公平性为核心目标的调度算法。

1. 亲和性和负载平衡#

SMP的调度面临两个核心矛盾：处理器亲和性和负载平衡。

当一个进程从一个CPU迁移到另一个CPU上时，应将第一个CPU的缓存设置为无效，然后重新填充第二个CPU的缓存。这种操作的代价较高，因此系统应尽量避免将进程从一个CPU移到另一个CPU，而应尽量让一个进程运行在同一个CPU上，这称为处理器亲和性。

对于SMP系统，应尽量保证所有CPU的负载平衡（也称负载均衡），以便充分利用多处理机的优势。否则，一个或多个CPU会空闲，而其他CPU会处于高负载状态，且有一些进程处于等待状态。负载平衡应设法将负载平均分配到SMP系统的所有CPU上。

然而，负载平衡通常会抵消处理器亲和性带来的好处：保持一个进程运行在同一个CPU上的好处是可以利用它在该CPU的缓存，而将进程从一个CPU迁移到另一个CPU会失去这个好处。因此，在某些系统中，只有当不平衡达到一定程度后，才会触发进程迁移。

2. 多处理机调度方案#