操作系统三种处理机调度算法介绍

以下是对先来先服务（FCFS）、短作业优先（SJF）、高响应比优先（HRRN）详细介绍：

先来先服务（FCFS）算法

• 算法原理：按照作业或进程到达系统的先后顺序进行调度，先到达的先被服务，就如同日常生活中排队办事一样，先来的人先得到处理。

• 计算步骤：

1. 记录每个作业（或进程）的到达时间和服务时间（即执行该作业所需的时间）。

2. 依据到达时间对所有作业进行排序，形成一个等待队列，到达时间早的排在前面。

3. 依次计算每个作业的周转时间，周转时间 = 作业完成时间 - 作业到达时间。

4. 最后计算平均周转时间，平均周转时间 = 所有作业周转时间之和÷作业数量。

• 举例：假设有三个作业 J1、J2、J3，它们的到达时间分别为 0、1、2，服务时间分别为 3、2、1。

• 按照 FCFS 算法，J1 先执行，其完成时间就是它的服务时间 3（因为它 0 时刻就到达了），周转时间为 3 - 0 = 3。

• 接着 J2 执行，它的开始时间是 J1 完成的时间 3，完成时间就是 3 + 2 = 5，周转时间为 5 - 1 = 4。

• 最后 J3 执行，开始时间是 5，完成时间是 5 + 1 = 6，周转时间为 6 - 2 = 4。

• 平均周转时间为 (3 + 4 + 4)÷3 = 11÷3。

短作业优先（SJF）算法

• 算法原理：优先选择估计运行时间最短的作业或进程进行调度，旨在使系统整体的平均周转时间尽可能短，让短作业能快速得到处理机资源并完成。

• 计算步骤：

1. 同样先记录每个作业的到达时间和服务时间。

2. 在每次处理机空闲时，从当前的就绪队列中挑选出服务时间最短的作业来执行。

3. 按照和 FCFS 算法相同的方式计算每个作业的周转时间以及平均周转时间，即周转时间 = 完成时间 - 到达时间，平均周转时间 = 所有作业周转时间之和÷作业数量。

• 举例：还是上述的 J1、J2、J3 三个作业。

• 首先比较它们的服务时间，J3 的服务时间最短为 1，所以 J3 先执行，它在到达时间 2 开始执行，完成时间就是 2 + 1 = 3，周转时间为 3 - 2 = 1。

• 接着 J2 执行，开始时间是 3，完成时间为 3 + 2 = 5，周转时间为 5 - 1 = 4。

• 最后 J1 执行，开始时间是 5，完成时间是 5 + 3 = 8，周转时间为 8 - 0 = 8。

• 平均周转时间为 (1 + 4 + 8)÷3 = 13÷3。

高响应比优先（HRRN）算法

• 算法原理：响应比 =（等待时间 + 服务时间）÷服务时间。每次调度时选择响应比最高的作业或进程，综合考虑了作业的等待时间和服务时间，既照顾到了短作业，又不会让长作业长时间等待而得不到执行机会。

• 计算步骤：

1. 记录每个作业的到达时间和服务时间。

2. 计算每个作业的初始响应比，在处理机空闲时，选择响应比最高的作业执行。

3. 当有作业正在执行时，其余作业的等待时间会随着时间推移而增加，所以需要在每次调度决策前重新计算各作业的响应比。

4. 同样按照周转时间的常规计算方式算出每个作业的周转时间以及平均周转时间。

• 举例：假设有三个作业 J1、J2、J3，到达时间分别为 0、1、2，服务时间分别为 3、2、1。

• 初始时，J1 响应比为（0 + 3）÷3 = 1，J2 响应比为（0 + 2）÷2 = 1，J3 响应比为（0 + 1）÷1 = 1，因为 J1 先到达，所以 J1 先执行。

• 当 J1 执行到时间为 1 时，J2 的等待时间变为 1，响应比为（1 + 2）÷2 = 1.5，J3 的等待时间变为 1，响应比为（1 + 1）÷1 = 2，此时 J3 响应比最高，J3 执行。

• J3 完成时间为 2（到达时间 2 开始执行，服务时间 1），周转时间为 2 - 2 = 0。

• 接着 J2 执行，完成时间为 2 + 2 = 4，周转时间为 4 - 1 = 3。

• J1 继续执行完，完成时间为 4 + 3 = 7，周转时间为 7 - 0 = 7。

• 平均周转时间为 (0 + 3 + 7)÷3 = 10÷3。

对比来看：

• FCFS 算法简单直观，容易实现，但对短作业不太友好，长作业先到达时可能导致短作业等待时间过长，平均周转时间可能较长。

• SJF 算法能有效降低平均周转时间，让短作业优先执行，但它需要事先知道作业的服务时间，而且长作业可能长时间得不到执行机会，容易出现“饥饿”现象。

• HRRN 算法在一定程度上兼顾了长作业和短作业，通过动态计算响应比来决定执行顺序，避免了 SJF 中长作业饥饿的问题，不过计算响应比会增加一定的系统开销。