调度性能的衡量

面向用户

周转时间短

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

  1. 作业在外存后备队列中的等待时间
  2. 作业调入内存后创建的相应进程在就绪队列中的等待时间
  3. 进程在CPU上执行的时间
  4. 进程等待某些操作完成后的时间

其中2、3、4在一个作业的整个处理过程中可能会发生多次。

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

响应时间快

响应时间，从用户提交请求开始，直达系统首次产生响应为止的时间间隔。是衡量分时系统调度算法的重要准则。

截止时间的保证

开始截止时间，指某任务必须开始执行的最迟时间。完成截止时间，指某任务必须完成的最迟时间。对于比较严格的实时系统，调度算法必须做到这一点，否则后果严重。

优先权

批处理系统、分时系统、实时系统都可以优先执行优先级别更高的作业。

面向系统

系统吞吐量高

系统吞吐量，系统在单位时间内所能完成的总的工作量，它与批处理系统中的作业长短有关。短作业执行时间短，吞吐量高，长作业相反。

CPU利用率

资源的平衡利用

调度的相关时间

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

调度算法

先来先服务

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

算例：假设系统中有4个作业，到达时间分别为8、8.5、9、9.5，服务时间分别为2、0.5、0.1、0.2，FCFS的调度为：

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

短作业优先

短作业优先调度算法（Short Job First）用于进程调度时又被称为短进程优先调度算法（Short Process First），该算法既可以用于作业调度，又可以用于进程调度。

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

算例：假设系统中有4个作业，到达时间分别为8、8.5、9、9.5，服务时间分别为2、0.5、0.1、0.2，SJF的调度为：

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

最短剩余时间优先

SJF本身是非抢占式的，用于抢占式调度系统时，对应的算法陈伟最短剩余时间优先调度算法。

该算法首先按照作业的服务时间挑选最短的作业运行，在该作业运行期间，一旦有新作业到达系统，并且该新作业的服务时间比当前运行作业的剩余服务时间短，则发生抢占；否则，当前作业继续运行。该算法确保一旦新的短作业或短进程进入系统，能够很快得到处理。

算例：假设系统中有4个作业，到达时间分别为8、8.5、9、9.5，服务时间分别为2、0.5、0.1、0.2，SJF的调度为：

由于频繁的抢占和进程切换，系统开销大，该算法实现代价高，一般用于实时系统。

高响应比优先

高响应比优先调度算法（Highest Reponse Ratio First, HRRF）是非抢占式的，主要用于作业调度。

基本思想：每次进行作业调度时，先计算后备作业队列中每个作业的响应比，挑选最高的作业投入系统运行。

响应比 = （等待时间 + 服务时间） / 服务时间 = 等待时间 / 服务时间 + 1

算例：假设系统中有4个作业，到达时间分别为8、8.5、9、9.5，服务时间分别为2、0.5、0.1、0.2，SJF的调度为：

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

优先级

每次挑选优先级最高的一个或几个调入，可以用于作业调度和进程调度。分为非抢占式和抢占式。

时间片轮转

用于分时系统的进程调度。

基本思想：系统将CPU处理时间划分为若干个时间片（q），进程按照到达先后顺序排列。每次调度选择队首的进程，执行完1个时间片q后，计时器发出时钟中断请求，该进程移至队尾。以后每次调度都是如此。该算法能在给定的时间内响应所有用户的而请求，达到分时系统的目的。

其性能主要取决于时间片q的大小，q太大，则所有的进程在1个时间片完成，退外围FCFS；太小则进程频繁切换，系统开销大。

该算法简单有效，常用于分时系统，但不利于I/O频繁的而紧凑，由于这种进程用不完一个时间片，就因为等待I/O操作而被阻塞，当I/O操作结束后，只能插入到就绪队列的末尾，等待下一轮调度。