1.写在前面

操作系统的进程调度算法直接关系到用户的使用体验。

• 运行时间快不快
• 任务的截止时间有没有保证
• 优先权高的作业能不能先被执行等等。

如果把用户的体验时间，引入到计算机里面，我们引入以下几个概念。

1.1 周转时间

周转时间，指作业从提交系统开始，直到作业完成为止的时间间隔。包括：

• 作业在外存后备队列中的等待时间
• 作业调入内存后创建的相应进程在就绪队列中的等待时间
• 进程在CPU上执行的时间
• 进程等待某些操作完成后的时间
• 其中2、3、4在一个作业的整个处理过程中可能会发生多次。

1.2 带权周转时间

是指作业周转时间与作业实际运行服务时间的比值。
平均周转时间和平均带权周转时间是衡量批处理系统调度算法的重要准则。

---

2.常见的调度算法

2.1 先来先服务

先来先服务调度算法（First Come First Served, FCFS）是最简单的调度算法，可以用于作业调度和进程调度。
按照作业进入系统后备作业队列的先后次序来挑选作业，加入就绪队列，等待执行。

image

FCFS是非抢占式的，易于实现，效率不高，性能不好.
有利于长作业（CPU繁忙性）而不利于短作业（I/O繁忙性）。

2.1.1关于几个时间概念的解释

服务时间：作业需要运行的时间
完成时间 = 开始时间 + 服务时间
等待时间 = 开始时间 - 提交时间
周转时间 = 完成时间 - 提交时间
带权周转时间 = 周转时间 / 服务时间
响应比 = （等待时间 + 服务时间） / 服务时间 = 等待时间/服务时间 + 1

2.2 短作业优先

该算法每次从后备作业队列中挑选估计服务时间最短的一个或几个作业，
将他们调入内存，分配必要的资源，创建进程并放入就绪队列。
在进程调度中的原理类似。

image

SJF是非抢占式的，优先照顾短作业，具有很好的性能，降低平均等待时间，提高吞吐量。
但是不利于长作业，长作业可能一直处于等待状态，出现饥饿现象；
完全未考虑作业的优先紧迫程度，不能用于实时系统。

2.3 高响应比优先调度算法

高响应比优先调度算法（Highest Reponse Ratio First, HRRF）是非抢占式的，主要用于作业调度。
基本思想：每次进行作业调度时，先计算后备作业队列中每个作业的响应比，挑选最高的作业投入系统运行。
响应比 = （等待时间 + 服务时间） / 服务时间 = 等待时间 / 服务时间 + 1

image

由响应比分析可知，该算法介于FCFS和SJF之间，但是每次需要计算每个作业的响应比，增加系统开销。