详解操作系统四大常用的作业调度算法（FCFS丨SJF丨HRRN丨RR）

先来先服务调度算法（FCFS）

先来先服务调度算法（First-Come, First-Served, FCFS）是一种基本的进程调度算法，其核心思想是按照作业到达时间的先后顺序进行调度。

FCFS调度算法的工作过程如下：

1. 当一个作业到达时，将其放入就绪队列的末尾。
2. 当前执行的作业执行完毕后，从就绪队列中选择队首的作业进行运行。
3. 重复步骤2，直到所有作业都执行完毕。

FCFS调度算法的优点是实现简单，公平性较好。由于按照作业到达的先后顺序进行调度，所以所有作业都可以得到执行，不存在作业“饥饿”问题。

然而，FCFS调度算法也存在一些缺点。首先，如果有一个长作业在队首，那么后面的作业就必须等待很长时间才能得到执行，导致平均等待时间较长。而且，FCFS调度算法无法适应作业的不同执行时间，执行时间较长的作业会导致整个系统的响应时间变长。

总结来说，FCFS调度算法是一种简单易实现的调度算法，公平性较好。但在实际应用中，需要注意长作业的等待时间较长的问题。

样例1：

有三个作业按下表的时间提交给系统，请按照先来先服务的调度算法计算它们的平均周转时间T和平均带权周转时间W

分析：按照先来先服务的原则，可以计算出各个作业在系统中的开始执行时刻、结束时刻、周转时间。为了一目了然，我们可以在给定表的基础上增加四个新的列：开始执行时刻、结束时刻、周转时间、带权周转时间

周转时间 = 作业结束时刻 - 作业提交时刻
带权周转时间 = 周转时间 / 作业长度

三个作业的平均周转时间T和平均带权周转时间W为：

T =（2.00+2.90+3.00）/ 3 = 2.63（小时）

W =（1+2.9+12）/ 3 = 5.30（小时）

短作业优先调度算法（SJF）

短作业优先调度算法是一种常见的进程调度算法，其核心思想是优先执行执行时间较短的作业。短作业指的是估计执行时间短的作业，也可以理解为剩余执行时间短的作业。

短作业优先调度算法的工作过程如下：

1. 首先，按照作业的执行时间对待执行的作业队列进行排序，即将估计执行时间较短的作业排在前面。
2. 然后，选择执行时间最短的作业来运行，直到该作业执行完毕或者被阻塞。
3. 当作业执行完毕或者被阻塞时，从待执行作业队列中选择下一个执行时间最短的作业来运行。
4. 重复步骤2和步骤3，直到所有作业都执行完毕。

短作业优先调度算法的优点是可以最大程度地减少平均等待时间，使得作业能够快速执行完毕。然而，该算法可能会导致长作业等待时间过长，造成长作业的“饥饿”现象。

总结来说，短作业优先调度算法是一种简单高效的调度算法，适用于执行时间短的作业，并能够减少平均等待时间。但在实际应用中需要注意长作业的“饥饿”问题。

样例2：

还是上面的例子，请按短作业优先算法计算它们的平均周转时间和平均带权周转时间

分析：为了运算方便，在上面作业表的基础上增加五个新的列：调度次序、开始执行时刻、结束时刻、周转时间，以及带权周转时间，从而得到下面的表：

三个作业的平均周转时间T和平均带权周转时间W为：

T =（2.00+3.10+2.00）/ 3 = 2.37（小时）

W =（1+2.9+12）/ 3 = 4.03（小时）

高响应比优先调度算法（HRRN）

高响应比优先调度算法（High Response Ratio Next, HRRN）是一种动态优先级的进程调度算法，其核心思想是根据作业的响应比来确定执行顺序。

HRRN调度算法的工作过程如下：

1. 当一个作业到达时，计算其响应比。响应比定义为作业等待时间加上作业执行时间除以作业执行时间，即 (等待时间 + 作业长度) / 作业长度。
2. 将计算得到的响应比最高的作业放入就绪队列。
3. 当前执行的作业执行完毕后，从就绪队列中选择响应比最高的作业进行运行。
4. 重复步骤2和步骤3，直到所有作业都执行完毕。

HRRN调度算法的优点是能够根据作业的等待时间和执行时间动态调整优先级，使得等待时间较长的作业能够优先得到执行，提高系统的响应速度。

然而，HRRN调度算法也存在一些缺点。首先，计算响应比需要动态获取作业的等待时间和执行时间，增加了系统的开销。此外，如果作业的执行时间很短，那么响应比会很高，导致其他作业长时间等待，可能会出现“长作业优先”问题。

总结来说，HRRN调度算法是一种具有动态优先级的调度算法，能够提高系统的响应速度。但需要注意计算响应比的开销以及长作业优先问题。

样例3：

表中有4个作业提交给系统，按响应比高者优先算法调度，计算它们的平均周转时间和平均带权周转时间

分析：为了计算方便，同样在表中增加五个新列：调度次序、开始执行时刻、结束时刻、周转时间，以及带权周转时间

先画出一个表格，后五列是空的，等待我们填入数据：

作业1做完后，其它三个作业的响应比为：

R2p = 1 + 已等待时间/作业长度 = 1 + 1.5/0.5 = 4

R3p = 1 + 1.0/0.1 = 11

R4p = 1 + 0.5/0.2 = 3.5

故作业3的响应比最大，作业1完成后要运行作业3。

作业3运行结束时，时间为10：06，这时候再看作业2、4的响应比哪个高：

R2p = 1 + 已等待时间/作业长度 =1 + 1.6/0.5 = 4.2

R4p = 1 + 0.6/0.2 = 4

R2p > R4p 所以先调度作业2到内存中，作业2运行完毕，结束时间为：10：36，最后调入作业4到内存。即作业调度的次序为：作业1、作业3、 作业2、 作业4

根据上面的表，可计算出4个作业的平均周转时间T和平均带权周转时间W为：

T =（2+2.1+1.1+1.3）/ 4 = 1.625（小时）

W =（1+4.2+11+6.5）/ 4 = 5.675（小时）

时间片轮转调度算法（RR）

时间片轮转调度算法（Round Robin Scheduling）是一种基于时间片的进程调度算法，旨在公平地分配CPU时间给各个就绪进程。

时间片轮转调度算法的工作过程如下：

1. 将所有就绪进程按照到达时间的顺序放入就绪队列。
2. 设定一个固定的时间片大小，通常为几十毫秒。
3. 从就绪队列中选择一个进程，分配给它一个时间片的CPU时间。
4. 若该进程在时间片结束前完成任务，则该进程被移出就绪队列，否则将其放到队列的末尾等待下一次调度。
5. 重复步骤3和步骤4，直到所有进程执行完毕。

时间片轮转调度算法的优点是能够公平地分配CPU时间给每个就绪进程，避免某个进程独占CPU资源，从而提高系统的可响应性和吞吐量。

然而，时间片轮转调度算法也存在一些缺点。首先，如果时间片太短，频繁进行上下文切换会带来较大的开销。另外，如果某些进程的执行时间较长，会导致其他进程长时间等待，可能会出现“长作业效应”问题。

总结来说，时间片轮转调度算法是一种能够公平分配CPU时间的调度算法，适用于多道程序环境。但需要注意时间片大小的设置以及长作业效应问题。

样例4：

5个进程P1、P2、P3、P4、P5几乎同时到达，预期运行时间分别为10、6、2、4、8个时间单位。请按时间片轮转调度算法计算任务的平均周转时间（假定时间片大小为2个时间单位）。

分析：

按顺序运行5个进程

时间片轮转调度顺序：