操作系统之CPU调度算法——FCFS、SJF和SRTF

目录

前言 

FCFS先来先服务调度算法

定义与步骤 

举例

SJF短作业优先调度算法

定义与步骤

举例

SRTF最短剩余时间优先调度算法

定义与步骤

举例

结束语

​​​​​​​

前言 

今天是坚持写博客的第12天，为不断坚持的自己和大家点赞。

最近经历了一场时长半小时的答辩，还是需要多参与答辩，这样才能在更大的场面稳住心态，调整出最好的一面。

今天我们来讲讲CPU调度算法中三个比较简单的算法：FCFS先来先服务算法、SJF短作业优先调度算法和SRTF最短剩余时间优先调度算法。

FCFS先来先服务调度算法

定义与步骤 

FCFS，first come first serve，先来先服务调度算法，即谁先来谁先进行，按照到达顺序依次服务调度，主要可以分为如下两步：

1.  一个作业到达时先进入就绪队列的末尾。
2. 在当前任务完成后，继续执行处在就绪队列第一位的作业。
3. 重复以上步骤，直到所有任务都完成。

FCFS不会出现“饥饿”问题，实现和理解简单，但是由于是因为先来先服务的方式，因此如果先进入的作业服务时间长就容易造成系统响应时间长的问题。

举例

下面我们看一道例题来解释一下先来先服务调度算法

寄术博主的奇妙画图小课堂开课啦

如果有如下几个作业，需要我们使用FCFS调度算法，求解它的周转时间：

此时我们可以看到作业1的提交时间为5，作业2的提交时间为3，作业3的提交时间为7，因此我们按照提交时间进行排序：2-1-3。因为作业2的服务时间为80，且我们要使用的是FCFS，因此无论服务时长多少都必须完成，即使在作业2的服务时长内作业1已经到了，甚至作业3都到了，我们也必须先执行作业2。

注意，周转时间等于结束时间-提交时间，平均周转时间就是它们的平均值。

此时我们也可以得出下图，在实际做题中，画出下面这样的表格更容易帮助大家得出正确答案：

因此我们也可以根据这张图得出它的平均周转时间为94.667。

SJF短作业优先调度算法

定义与步骤

SJF，shortest job first，短作业优先调度算法，即先看哪个算法先来，再看谁的服务时间短，服务时间短的那个先服务。主要可以分为以下三步：

1. 先对提交时间进行排序，并将服务时间短的作业排在前面。
2. 完成当前提交时间最早且服务时间最短的作业。
3. 重复上述步骤，直到所有作业完成

SJF调度算法可以极大程度上减少平均等待时间、平均周转时间等，且是一种非抢占式算法。

举例

它的求解方法与FCFS类似，不过是加入了一个条件：如果提交时间一致，需要先进行服务时间更短的那一个作业。

例如我们在FCFS的例题的基础上增加作业4，它的提交时间为5，服务时间为20，此时作业4的提交时间和作业1一样，但是因为作业1的服务时间更短，因此我们先服务作业1，后服务作业4。

此时可能会有小伙伴问，博主啊，作业4和作业3的服务时间一样长，怎么办？因为此时作业4的提交时间快于作业3，因此我们先进行作业4，后执行作业3。

此时的执行顺序为：2-1-4-3。最终我们得到的答案如下：

SRTF最短剩余时间优先调度算法

定义与步骤

SRTF，shortest remaining time first，最短剩余时间优先调度算法，如果新到达的作业剩余时间比当前运行的作业剩余时间更短，则先处理新到达的作业，当前运行进程重新回到就绪队列，准备后续的服务。主要可以分为以下几步：

1. 作业进入就绪队列，比较服务时间长短，服务时间短的先服务，长的回到就绪队列的末尾等待服务。
2. 若没有新的作业进入就绪队列，则按照当前就绪队列的顺序服务，直到所有作业最后都完成服务。

SRTF是一种抢占式算法，可以减少平均等待时间和平均周转时间等。

举例

我们以这题为例进行解释。

具体步骤如下：

1. 第0时刻作业1到达，作业1先服务。
2. 第1时刻作业2到达，此时作业1的服务时长剩余7，作业2的服务时长剩余4，先服务作业2.
3. 第2时刻作业3到达，此时作业1的服务时长剩余7，作业2的服务时长剩余3，作业3的服务时长剩余9，先服务作业2.
4. 第3时刻作业4到达，此时作业1的服务时长剩余7，作业2的服务时长剩余2，作业3的服务时长剩余9，作业4的服务时长剩余5，先服务作业2.
5. 此时没有新的作业进入进程，我们逐步比较。
6. 时刻5时作业2完成，此时所有作业都在就绪队列，经过对服务时长比较，我们发现作业4的服务时长最短，因此先服务作业4.
7. 时刻10时作业4完成，经过服务时长比较，我们发现作业1的服务时长最短，因此先服务作业1.
8. 时刻17时作业1完成，经过服务时长比较，此时作业3的服务时长最短，因此服务作业3.
9. 时刻26时所有作业完成，服务结束。

经过SRTF，我们可以得出下图作为我们SRTF的流程参考，开始时间、结束时间等与上面的FCFS和SJF求解方法一致，这里不再赘述。

流程图如下： 

结束语

以上就是对三种CPU调度算法的解释，之后博主也会尝试更新更多有关操作系统的相关知识，如果我的解释对您有帮助，希望您可以为我留下点赞和关注，这对我的鼓励与意义重大，真的很重要，谢谢！