操作系统——15.FCFS、SJF、HRRN调度算法

这节我们来看一下进程调度的FCFS、SJF、HRRN调度算法

目录

1.概述 

2.先来先服务算法（FCFS，First Come First Serve）

3.短作业优先算法（SJF，Shortest Job First）

4.高响应比优先算法（HRRN，Highest Response Ratio Next）

5.对比分析

---

1.概述 

首先，我们来看一下本篇的大体框架：

学习算法的大体思路如下：

1. 算法思想
2. 算法规则
3. 这种调度算法是用于作业调度还是进程调度?
4. 抢占式？非抢占式？
5. 优点和缺点
6. 是否会导致饥饿（饥饿：某进程/作业长期得不到服务）

2.先来先服务算法（FCFS，First Come First Serve）

算法总结：

 

下面来看一下例题：

3.短作业优先算法（SJF，Shortest Job First）

算法总结：

下面看一下例题：

 

注意几个小细节：

1. 如果题目中未特别说明，所提到的“短作业/进程优先算法”默认是非抢占式的
2. 很多书上都会说“SJF调度算法的平均等待时间、平均周转时间最少”。严格来说，这个表述是错误的，不严谨的。之前的例子表明，最短剩余时间优先算法得到的平均等待时间、平均周转时间还要更少。应该加上一个条件“在所有进程同时可运行时，采用SJF调度算法的平均等待时间、平均周转时间最少”；或者说“在所有进程都几乎同时到达时，采用SJF调度算法的平均等待时间、平均周转时间最少”；如果不加上述前提条件，则应该说“抢占式的短作业/进程优先调度算法（最短剩余时间优先, SRNT算法）的平均等待时间、平均周转时间最少”
3. 虽然严格来说，SJIF的平均等待时间、平均周转时间并不一定最少，但相比于其他算法〈如FCFS)，SJF依然可以获得较少的平均等待时间、平均周转时间
4. 如果选择题中遇到“SJF算法的平均等待时间、平均周转时间最少”的选项，那最好判断其他选项是不是有很明显的错误，如果没有更合适的选项，那也应该选择该选项

4.高响应比优先算法（HRRN，Highest Response Ratio Next）

算法思想的提出：

• FCFS 算法是在每次调度的时候选择一个等待时间最长的作业（进程）为其服务。但是没有考虑到作业的运行时间，因此导致了对短作业不友好的问题
• SJF算法是选择一个执行时间最短的作业为其服务。但是又完全不考虑各个作业的等待时间，因此导致了对长作业不友好的问题，甚至还会造成饥饿问题
• 能不能设计一个算法，即考虑到各个作业的等待时间，也能兼顾运行时间呢?

能，高响应比优先算法！

算法思想总结：

 

看一下例题

5.对比分析